1. 快排的两种写法
以前一直用第一种方式进行快排的，笔试中出现了第二种头尾指针的快排。
第一种：
template<class T,class TCOMP> void quicksort(T a[],int start,int end,TCOMP cmpf=NULL){ int i; if(start>=end) return; int middle = start; T temp = a[start]; bool flag; for(i=start+1;i<end;i++) { if(cmpf==NULL) flag = a[i]<temp; else flag = cmpf(a[i],temp); if(flag) swap(a[++middle],a[i]); } swap(a[middle],a[start]); quicksort(a,start,middle,cmpf); quicksort(a,middle+1,end,cmpf);}
第二种：
void quicksort2side(int* first,int*last){ if(first>=last) return; int *left = first; int *right = last; int temp = *first; while(left<right) { while(*right>temp&&right>left) { right--; } *left = *right; while(*left<=temp&&left<right) { left++; } *right = *left; } *left = temp; quicksort2side(first,left-1); quicksort2side(right+1,last);}
2. 结构体内存对齐问题
这个是非常常见的，笔试面试都很容易被问到，这里总结一下。
typedef struct A{ char a; char a1[102];}A; //103字节，最后结构体整体按sizeof（char）对齐typedef struct C{ char a; short b; //起始地址要2的倍数 char c; char d;}C;//6字节，最后按short对齐typedef struct B{ char a; double i; //起始地址8倍数 short b;}B; //24字节
另外，还有pack和align修饰符的规定。
#pragma pack规定的对齐长度，实际使用的规则是：
结构，联合，或者类的数据成员，第一个放在偏移为0的地方，以后每个数据成员的对齐，按照#pragma pack指定的数值和这个数据成员自身长度中，比较小的那个进行。
当数据定义中出现__declspec( align() )时，指定类型的对齐长度还要用自身长度和这里指定的数值比较，然后取其中较大的。最终类/结构的对齐长度也需要和这个数值比较，然后取其中较大的。
可以这样理解， __declspec( align() ) 和 #pragma pack是一对兄弟，前者规定了对齐的最小值，后者规定了对齐的最大值，两者同时出现时，前者拥有更高的优先级。
3.在循环有序数组中查找某个元素
这个题目比较有意思，在普通有序数组查找直接折半即可，但是循环有序数组还得考虑一下很多问题。因为并不知道循环的起始位置。如下：
123456
234561
456123
//在循环有序数组中查找某个元素，复杂度O(logN)
int find_in_cycle_array(int a[],int n,int elem){ int start =0; int end = n-1; while(start<=end) { int middle = (start+end)/2; if(a[middle]==elem) return middle; if(a[end]>a[start]) { if(a[middle]>elem) end=middle-1; else start = middle+1; } else { if(a[middle]>=a[start]) { if(a[middle]>elem&&a[start]<=elem) end = middle-1; else start = middle+1; } else { if(a[middle]<elem&&a[end]>=elem) start = middle+1; else end = middle-1; } } } return -1;}
4.获取字符串最长数字串
这个是baidu的一道笔试题，虽然简单，但是要当场写对还是要仔细点。
int getlongestdigital(const char* inputstr,char* outputstr){ int start,length,longeststart,longest,offset; start = length = longest = longeststart = offset = 0; while(*inputstr!='\0') { if(*inputstr>='0'&&*inputstr<='9') { if(length==0) start = offset; length++; } else { if(length>longest) { longest = length; longeststart = start; } length =0; } offset++; inputstr++; } if(length>longest) { longest = length; longeststart = start; } inputstr -= offset; for(int i=0;i<longest;i++) { outputstr[i] = inputstr[i+longeststart]; } outputstr[longest] = '\0'; return longest;}
5.完全二叉树的节点添加
这个也是常出现的题目，完全二叉树是笔试面试经常碰到的，最好要熟悉的它的各种操作。
typedef struct TreeNode{ int data; struct TreeNode* left; struct TreeNode* right;}TreeNode;void insertnode(TreeNode* root,TreeNode* newnode){ queue<TreeNode*> nonvisit; nonvisit.push(root); while(!nonvisit.empty()) { TreeNode* pvisit = nonvisit.front(); nonvisit.pop(); if(pvisit->left==NULL) { pvisit->left = newnode; return; } nonvisit.push(pvisit->left); if(pvisit->right == NULL) { pvisit->right = newnode; return; } nonvisit.push(pvisit->right); }}
6.链表反序
链表是又一个重点，熟悉一下它的各种操作吧
void ReverseList(LinkNode **root){ LinkNode *temp1 = (*root)->next; if(temp1==NULL) return; LinkNode *temp2; (*root)->next = NULL; temp2 = temp1->next; temp1->next = *root; *root = temp1; while(temp2!=NULL) { temp1 = temp2; temp2 = temp1->next; temp1->next = *root; *root = temp1; }}
7.
找出最大的一些数，前nums个最大的。
这个题出现的次数还是挺多的，不过大部分都是讲讲思路。基本用快排的思想就行了.
void find_n_most(int* pa,int start,int end,int nums)
{
if(start>=end-1)
return;
int i=start;
for(int j=start+1;j<end;j++)
{
if(pa[j]>pa[start])
swap(pa[j],pa[++i]);
}
swap(pa[start],pa[i]);
if(i==nums-1||i==nums)
return;
if(i>nums)
find_n_most(pa,start,i,nums);
else
find_n_most(pa,i+1,end,nums);
}
上述算法过后，前面nums个数就是所要求的了，注意这个只要求找到前nums个最大的，并不要求排序。
再来一个：
求循环小数的循环体，给两个整数a，b，求a/b的循环小数的循环体字符串，如果不是循环小数则输出空串。
思路：
string get_circle_digits(unsigned int k,unsigned int j)
2
3 {
4
5 if(k%j==0)
6
7 return "";
8
9 int quotient;
10
11 string quotient_result="";
12
13 vector<int> remainders;
14
15 int remainder = k%j;
16
17 remainders.push_back(remainder);
18
19 while(true)
20
21 {
22
23 quotient = remainder*10/j;
24
25 remainder = remainder*10%j;
26
27 if(remainder==0)
28
29 return "";
30
31 quotient_result.append(1,quotient+'0');
32
33 if(find(remainders.begin(),remainders.end(),remainder)!=remainders.end())
34
35 {
36
37 return quotient_result.substr(find(remainders.begin(),remainders.end(),remainder)-remainders.begin());
38
39 }
40
41 remainders.push_back(remainder);
42
43 }
44
45 }