1. 有一个整数数组，请求出两两之差绝对值最小的值, 记住，只要得出最小值即可，不需要求出是哪两个数。
思路：若有a[n]个数 构造b[n] 其中 b[i] = a[i] - a[i -1] 这样a[n]中任意两个数之差 就可以用 b[i] +...+b[j] = (a[i]-a[i-1])+(a[i+1]-a[i])..+(a[j]-a[j-1]) = a[j]-a[i-1]
因此 再利用最大连续子序列和的类似方法O(n) 即可求出 （还是有问题 当数组为 {1,20,200,16,1}这种情况时 ）
int GetMinAbsoluteSubsequence(int B[],int begin,int nLen) { int nGlobal=INT_MAX; int nSuffix=0; for(int i=begin; i<nLen; i++) { nSuffix+=B[i]; if(abs(nSuffix)<abs(nGlobal)) { nGlobal=nSuffix; } if(i+1<nLen) { if(nSuffix*B[i+1]>0) //何时清零 ？ nSuffix=0; } } return abs(nGlobal); }
2. 写一个函数，检查字符是否是整数，如果是，返回其整数值。（或者：怎样只用4行代码编写出一个从字符串到长整形的函数？）
思路：按位递归处理 每次处理最后一位 直到结束 ~~ 注意考虑第一个字符为负数的情况
int str2int(char* pstr,int len) { if (len > 1) { return pstr[0] == '-'?str2int(pstr,len - 1)*10 - (pstr[len - 1] - '0'):str2int(pstr,len - 1)*10 + (pstr[len - 1] - '0'); } else return pstr[0] == '-'?0:pstr[0] - '0'; }
3、给出一个函数来输出一个字符串的所有排列。
思路： DFS 排列
//num[] 为可用的字符 ch[i]用来标记是否已经放入num[i] void dfs(char ar[],int len,bool ch[],char num[],int dp) { if (dp == len) { for (int i = 0 ; i< len;++i) { cout<<ar[i]; } cout<<endl; return; } for (int i = 0;i < len;++i) { if (!ch[i]) //如果num[i]还没放入 { ch[i] = true; ar[dp] = num[i]; dfs(ar,len,ch,num,dp + 1); ch[i] = false; } } }
4、请编写实现malloc()内存分配函数功能一样的代码。
给出一个函数来复制两个字符串A和B。字符串A的后几个字节和字符串B的前几个字节重叠。
5、怎样编写一个程序，把一个有序整数数组放到二叉树中？
6、怎样从顶部开始逐层打印二叉树结点数据？请编程。
思路：二叉树的层次遍历 利用队列 记录层次
void print_tree(NODE* T) { if (T == NULL) { cout<<"Empty Tree!"<<endl; return; } int cenci = 1; queue<NODE*>stn; queue<int>cst; stn.push(T); cst.push(cenci); NODE* temp = NULL; while (!stn.empty()) { temp = stn.front(); stn.pop(); if (cst.front() == cenci) { cout<<temp->val<<' '; } else { cenci = cst.front(); cout<<endl<<temp->val<<' '; } cst.pop(); if (temp->lchild) { stn.push(temp->lchild); cst.push(cenci + 1); } if (temp->rchild) { stn.push(temp->rchild); cst.push(cenci + 1); } } }
7、怎样把一个链表掉个顺序（也就是反序，注意链表的边界条件并考虑空链表）？
Nod* rev(Nod* head) //head 当前 { Nod* pre =NULL; //pre 前续 Nod* nex = NULL; //nex 后续 while (head) { nex = head->next; head->next = pre; pre = head; head = nex; } return pre; }
8、请编写能直接实现int atoi(const char * pstr)函数功能的代码。
int atoi_m(const char* p,int len) { if (len == 0) { return 0; } if (len > 1) { return p[0]=='-'?atoi_m(p,len - 1)*10 - p[len - 1]+'0':atoi_m(p,len - 1)*10 + p[len - 1] - '0'; } else return p[0] == '-'?0:p[0] - '0'; }
9、编程实现两个正整数的除法
编程实现两个正整数的除法，当然不能用除法操作符。
// return x/y.
int div(const int x, const int y)
int divv(const int x,const int y) { int x_temp = x; int anw = 0; int multi; while (x_temp >= y) { multi = 1; while (y*multi <= (x_temp>>1)) //y*m <= x/2 m翻倍 { multi = multi<<1; } anw += multi; x_temp -= y*multi; //减去已有的 } return anw; }
10、在排序数组中，找出给定数字的出现次数 比如 [1, 2, 2, 2, 3] 中2的出现次数是3次
思路：二分查找 找到后左右遍历 这样复杂度为O(n + s) ； 如果需要多次查找 还是建立hash比较好
网上有思路说 用二分查找起始点和终点的位置 再相减即可
View Code
int b_search(int ar[],int first,int last,int val) //二分查找 找不到返回-1 { if (first < last) { int mid = (first + last)/2; if (ar[mid] == val) { return mid; } else if (ar[mid] < val) { return b_search(ar,mid + 1,last,val); } else return b_search(ar,first,mid - 1,val); } else if (first == last) { return ar[last] == val?last:-1; } return -1; } int getTim(int ar[],int n,int k) //计算k出现的次数 { int temp = b_search(ar,0,n-1,k); if (temp == -1) { return 0; } else { int num = 1; int pos = temp + 1; while (pos < n&&ar[pos++] == k) //向后找 { ++num; } pos = temp - 1; while (pos >= 0&&ar[pos--] == k) //向前找 { ++num; } return num; } }
int* pos1 = lower_bound(ar,ar + n,k); int* pos2 = upper_bound(ar,ar + n,k); cout<<pos2 - pos1<<endl;
11、平面上N个点，每两个点都确定一条直线，求出斜率最大的那条直线所通过的两个点（斜率不存在的情况不考虑）。时间效率越高越好。
3个点A,B,C,把它们的按x坐标排序。假设排序后的顺序是ABC，那么有两种情况：
1.ABC共线，则k(AB)=k(BC)=k(AC)2.ABC不共线，则ABC将形成一个三角形，那么k(AC)<max(k(AB), k(BC))
1.把N个点按x坐标排序。2.遍历，求相邻的两个点的斜率，找最大值。
请设计一个算法，当你从该数列中随意选取5个数值，判断这5个数值是否连续相邻。
注意：
- 5个数值允许是乱序的。比如： 8 7 5 0 6
- 0可以通配任意数值。比如：8 7 5 0 6 中的0可以通配成9或者4
- 0可以多次出现。
- 复杂度如果是O(n2)则不得分。
思路： 排序 如 8 7 5 0 6 排序后: 0 5 6 7 8 ; 得到0的个数 N0，非0的个数为 N1 ，非0个序列首尾 5 和 8，非0序列的长度 LEN = arr[4] - ar[非0第一个] + 1
若LEN - N1<= N0 则可以，否则 不能组成序列 O(NlogN) + O(N)
sort(arr,arr + n); //首先排序 int pos = 0; //pos 为0的个数 int num = arr[pos]; while (!num) //num为第一个非0值 { ++pos; num = arr[pos]; } if (arr[4] - num + 1 - 5 + pos<= pos) //非0值序列长度-已有元素 <= 0的元素 { cout<<"CAN"<<endl; } else cout<<"No"<<endl;
13、设计一个算法，找出二叉树上任意两个结点的最近共同父结点。复杂度如果是O(n2)则不得分。
思路：网上标准答案是LCA的算法 http://kmplayer.iteye.com/blog/604518
不过感觉对本人来说理解有点困难，如果真遇到面试这种题，O(n)的方法也不是没有，那就是找到两个结点的祖先序列VecA VecB, 其中，长的序列的多出的部分可以抛弃，因为
一定不是公共的部分，(举例，VecA > VecB , 则 VecA的前几个元素都可以删除)，然后查找VecA和VecB的第一个相同元素就是最近公共祖先.
bool dfs(NODE* head,int val,vector<NODE*> &vp)//找val节点的祖先序列 { if (head == NULL) { return false; } if (head->val == val) { vp.push_back(head); return true; } if (dfs(head->lchild,val,vp)) { vp.push_back(head); return true; } else if (dfs(head->rchild,val,vp)) { vp.push_back(head); return true; } else return false; } // 1 2 4 -1 -1 5 -1 -1 3 6 7 -1 9 -1 -1 8 -1 -1 -1 int main() { NODE* head = creat_tree(); // cenci(head); // preDis(head); int a = 9, b = 8; vector<NODE*>vp; dfs(head,a,vp); vector<NODE*>vp2; dfs(head,b,vp2); int len = abs(int(vp.size() - vp2.size())); if (vp.size() > vp2.size()) { while (len--) { vp.erase(vp.begin()); } } else { while (len--) { vp2.erase(vp2.begin()); } } int pos = 0; while (vp[pos] != vp2[pos]) { ++pos; } cout<<vp[pos]->val<<endl;
14、一棵排序二叉树，令 f=(最大值+最小值)/2， 设计一个算法，找出距离f值最近、大于f值的结点。复杂度如果是O(n2)则不得分。
思路： 优化GP： 中序遍历，找到第一个大于f的节点即是 （因为一定存在比f大的数）
bool have = false; //是否找到大于f的数 int f = 4; //f void midDis(NODE* head) //中序遍历 { if (have||head == NULL) { return; } midDis(head->lchild); if (head->val > f) { cout<<head->val<<endl; have = true; return; } midDis(head->rchild); }
15、一个整数数列，元素取值可能是1~N（N是一个较大的正整数）中的任意一个数，相同数值不会重复出现。设计一个算法，找出数列中符合条件的数对的个数，满足数对中两数的和等于N+1。 复杂度最好是O(n)，如果是O(n2)则不得分。
思路： 位图排序？然后扫描 时间复杂度是O(n) 但是需要O(n)的空间
bool arr[n + 1]; //位图 memset(arr,0,sizeof(arr)); for (int i = 0;i < m;++i) //位图排序 { arr[ar[i]] = true; } int i = 1, j = n; //起点和终点(最小值 最大值) int ff = 1 + n; while (i < j) //O(n)遍历求和 { if (i + j < ff) ++i; else if (i + j > ff) --j; else { if (arr[i]&&arr[j]) { cout<<i<<"+"<<j<<"="<<ff<<endl; } ++i; --j; } }