必威体育Betway必威体育官网
当前位置:首页 > IT技术

刷题-程序员面试宝典

时间:2019-07-27 20:40:00来源:IT技术作者:seo实验室小编阅读:73次「手机版」
 

程序员面试宝典

最近快面临找工作了,开始每天的刷题之旅

知识点1:关于与或非赋值操作

int x=2,y,z
x*=(y=z=5);//x=2*5=10
x=(y&z);//x=5 y的二进制是101 z的二进制是101
x=(y&&z);//x=1;两个&&表示布尔
同理可知(y|z)与(y||z)的区别

知识点2:统计1的个数

//这个函数返回的时候,形参X转化成二进制后包含1的个数
int func(int x)
{
    int countx = 0;
    while(x)
    {
        countx++;
        x = x&(x-1);
    }
    return countx;
} 
int main()
{
std::cout<<func(9999)<<std::endl;
}

知识点3:for循环

int a,x;
//版本1
for (a=0,x=0;a<=1&&!x++;a++)
{
a++;
}
//程序在运行时的步骤
1、初始化定义a=0,x=0(确定判断的终止条件:a>1或者x=1)
2、进行for循环的前两个语句,此时a=0,x=1
3、进行循环体中此时a=1,x=1
4、进行for循环的第三个语句,此时a=2
5、进入for循环第2个语句,判断终止条件,由于a>1,判断终止,不进入!x++语句,因此
最终输出结果a=2,x=1
在for循环中,如为1则,进入循环判断。不为1则跳出循环判断

知识点4:判断一个数是否是2的n次方

int func(int x)
{
    if( (x&(x-1)) == 0 )//利用X&(X-1)来判断
        return 1;
    else
        return 0;
}

知识点5:一半一半

int f(int x, int y)
{
    return (x&y)+((x^y)>>1)
}
//其中(x&y)+((x^y)>>1)  相当于(x+y)/2

知识点6:时间复杂度空间复杂度

时间复杂度是-》大概程序需要执行的次数(而非执行时间)

空间复杂度是-》大概程序所占用的最大内存

地址是:内存单元的编号  指针就是地址,地址就是指针

指针变量,是存放内存单元地址的变量。

结构体和类的区别,结构体没有方法

struct Student
{
    int sid;
    char name[200];
    int age;
}
 
int main()
{
    struct Student st={1000,"zhangsan",20};
    st.sid=6;
    struct Student *pst;
//   也可以考虑整体的的赋值 psd=&st;
    pst->sid=99;
}

如果我的返回数据是一个数组的话,那么我定义的数据类型应该是一个指针类型。

知识点7  返回一个在0-50之间的随机数

#include <iOStream>
#include <ctime>
#include <cassert>
using namespace std;
namespace SortTestHelper
{
	//由于我需要返回的是一个数组
  int * generateRandomArray(int n,int rangeL,int rangeR){
	  assert(rangeL<=rangeR);//做一个判定
       int *arr=new int[n];
	   srand(time(NULL));//随机种子的测试
	  for(int i=0;i<n;i++)
	  {
	  	arr[i]=rand()%(rangeR-rangeL+1)+rangeL;
	  }
	   return arr; 
  }
}

int main()
{
	//产生0—50之间的,10个随机的数字
	int *arr=SortTestHelper::generateRandomArray(10,0,50);
	for (int i=0;i<10;i++)
	{
		cout<<arr[i]<<endl;
	}	
    delete[] arr;	
   return 0;
}

知识点8:选择排序

选择排序就是对数组中所有的元素,首先找到最小的元素,然后把它放在第一个位置,然后再找这个数组中剩下元素中最小的元素,把他放在第二个位置上面,依次类推。

//版本1	
void selectSort(int arr[],int n)
	{
		//对数组进行遍历
	 for(int i=0;i<n;i++)
	 {
		 int Minindex=i;
		 for(int j=i+1;j<n;j++)//这里写成int j=i只不过多给比较了而一次
		 {
		    if(arr[j]<arr[minIndex])
				minIndex=j;
		 }
	     //经过第一轮互换之后,已经把元素大的全都换到后面去了
		 swap(arr[i],arr[minIndex]);
	 }
	}
//版本2 使用模板
template<typename T>
	void selectSort(T arr[],int n)
	{
		//对数组进行遍历
	 for(int i=0;i<n;i++)
	 {
		 int minIndex=i;
		 for(int j=i+1;j<n&&arr[j]<arr[minIndex];j++)//这里写成int j=i只不过多给比较了而一次
          {
                minIndex=j;
           }
	     //经过第一轮互换之后,已经把元素大的全都换到后面去了
		 swap(arr[i],arr[minIndex]);
	 }
	
	}
int main()
{
	//产生0—50之间的,10个随机的数字
	//int *arr=SortTestHelper::generateRandomArray(10,0,50);
	//接下来要选择排序算法
	int arr[10]={3,2,1,40,53,11,7,18,19,130};
	 selectSort(arr,10);
	for (int i=0;i<10;i++)
	{
		cout<<arr[i]<<endl;
	}		
   return 0;
}

知识点9 测算函数的复杂度

#include <iostream>
#include <ctime>
#include <cassert>
#include <algorithm>
template<typename T>
	void selectSort(T arr[],int n)
	{
		//对数组进行遍历
	 for(int i=0;i<n;i++)
	 {
		 int minIndex=i;
		 for(int j=i+1;j<n;j++)//这里写成int j=i只不过多给比较了而一次
		 {
		    if(arr[j]<arr[minIndex])
				minIndex=j;
		 }
	     //经过第一轮互换之后,已经把元素大的全都换到后面去了
		 swap(arr[i],arr[minIndex]);
	 }
	
	}
//第二个参数是函数指针
template<typename T>//必须写两个template<typename T>,每个模板对应一个
void testSort(string sortName,void(*sort)(T[] ,int),T arr[],int n)
{
    clock_t startTime=clock();
	sort(arr,n);
	clock_t endTime=clock();
	cout<<sortName<<":"<<double(endTime-startTime)/CLOCKS_PER_SEC<<"s"<<endl;
	return ;
}
int main()
{
	//产生0—50之间的,10个随机的数字
	//int *arr=SortTestHelper::generateRandomArray(10,0,50);
	//接下来要今天排序算法
	int arr[10]={3,2,1,40,53,11,7,18,19,130};
	 //selectSort(arr,10);
	testSort("Selection Sort",selectSort,arr,10);
	for (int i=0;i<10;i++)
	{
		cout<<arr[i]<<endl;
	}		
   return 0;
}

知识点10:插入排序

对前面的元素进行排查,然后比较该元素和该元素的前一个元素

template<typename T>
void insertSort(T arr[],int n)
{
	for(int i=0;i<n;i++)//这里的目的是为了遍历
	{
	   for (int j=i;j>0;j--)//对i前面的元素进行排查
	   {
	     if(arr[j]<=arr[j-1])
		 {
			 swap(arr[j],arr[j-1]);	
		 }
         else
           break;
	   }
	}
    return ;
}

在这里由于使用到了swap函数,使得算法的效率不高,因此不适用这个函数

template<typename T>
void insertSort(T arr[],int n)
{
	for(int i=0;i<n;i++)//这里的目的是为了遍历
	{
      T e=arr[i];
      int j;
	   for (j=i;j>0;j--)//对i前面的元素进行排查
	   {
	     if(arr[j-1]>e)
		 {
			arr[j]=arr[j-1]
		 }
         else
           break;
	   }
      arr[j]=e;
	}
    return ;
}

知识点11 拷贝一个数组

int* 的东西就是这个数组头指针

int * CopyArry(int a[],int n)
{
int arr =new int[n];
copy(a,a+n,arr);//第一个参数是头指针,第二个是尾指针,最后一个目标的头指针
return arr;
}

知识点12 冒泡排序的

知识点13 希尔排序

知识点14 归并排序

知识点15 快速排序

相关阅读

程序员如何减掉小肚腩

工作半年了,自己一直提醒自己锻炼,跑步没坚持下来,只有引体向上每天都做。本以为这样就能达到自己想要的结果,保持现状,不胖不瘦,可是今

健康很重要 程序员应该坚持正确的坐姿工作

对大多数程序员而言,弯腰驼背一连几小时趴在办公桌上对着电脑霹雳巴拉敲着键盘,很有可能是一种常态,日复一日,年复一年。我之所以知道

面试简历名称怎么写

目前,校园招聘如火如荼,有的用人单位早在10月份就开始到高校举行专场宣讲会,各高校也纷纷举办双选大会,毕业生一场接一场地参加招聘会

面试者讲述Groupon在中国的疯狂招募 与腾讯建合资公司

1月17日凌晨消息,一个应聘Groupon中国团队职位的面试者披露了Groupon进入中国的最近进展:Groupon将和腾讯建立合资公司,他同时披露了

一道产品面试题:小明要喝果汁,妈妈没空,怎么解决?

偶然看到的一道产品经理面试问答:小明要喝果汁,妈妈没空,怎么解决?看到这个题目时,就引起了我无限的遐想和好奇心(内心os:这是一道相当有

分享到:

栏目导航

推荐阅读

热门阅读