[关闭]
@dantangfan 2015-01-21T17:11:43.000000Z 字数 29249 阅读 2156

简单算法篇

  1. 查找链表的倒数第K个元素。
    直接先遍历一次，发现链表长度，再两个指针先后相距K步遍历
  1. Node *find(Node *n,int k){
  2.     if(n==NULL) return NULL
  3.     Node *head = n;
  4.     int len=0;
  5.     while(head!=NULL){
  6.         len += 1;
  7.         head = head->next;
  8.     }
  9.     if(k>=len) return NULL;
  10.     head = n;
  11.     Node *temp = n;
  12.     for(int i=0;i<k;i++){
  13.         head = head->next;
  14.     }
  15.     while(head!=NULL){
  16.         head = head->next;
  17.         temp = temp->next;
  18.     }
  19.     return temp;
  20. }

检测链表是否出现环路
使用两个指针，一个一次跳一步，一个一次跳两步，总会相遇

  1. bool loop(Node *n){
  2.     Node temp1 = n;
  3.     Node temp2 = n;
  4.     if(n==NULL) return false;
  5.     while(temp->next!=NULL){
  6.         temp1 = temp1->next->next;
  7.         temp2 = temp2->next;
  8.         if(temp1==temp2) return true;
  9.     }
  10.     rerurn false;
  11. }

环路的开头节点
两个节点slow和fast，每当slow走k个节点fast就走2k个节点。假设slow从开始到环的初始节点走了k步，这个时候fast就走了2k步，其中有k步在环内（有可能k比loopsize大得多，不过无所谓，mod(k,loopsize)效果也一样）。如果说我们认为这个时候fast在slow后面，那么他们相距loopsize-k个节点，那么需要t=loopsize-k那么长的时间在还有k步到达环开始的地方相遇。于是，我们可以确定，slow再次从strat出发，fast从相遇节点出发，一定能在环开始的地方相遇。

  1. LinkedListNode FindBeginning(LinkedListNode head){
  2.     LinkedListNode slow = head, fast = head;
  3.     while(fast!=NULL && fast.nest!=NULL){
  4.         slow = slow.next;
  5.         fast = fast.next.next;
  6.         if(slow==fast) break;
  7.     }
  8.     if(fast==NULL||fast.next==NULL) return NULL;
  9.     slow = head;
  10.     while(slow!=fast){
  11.         slow = slow.next;
  12.         fast = fast.next;
  13.     }
  14.     return fast;
  15. }

思考题：
检测两个无环链表是否相交
先遍历第一个链表，再把第二个表头链接到第一个表尾，标记该位置，然后第二个表从头开始遍历，如果出现环则相交；分别遍历两个链表，最后一个元素相同。
相交链表的第一个节点
分别遍历两个表，记录长度，然后先后相距k遍历，第一个相同的就是。
检测两个有环链表是否相交
先找出一个链表的环内的一个节点，在看这个节点是否在另一个链表内。
检测两个有环链表的相交节点
先检测出一个链表环的起始并记录长度，再看另一个链表到环起点的长度，最后转换成无环相交情况。

  1. 找到一棵树中两个节点的最低公共父节点
    如果是二叉查找树(left 如果是普通树，但是是双向指针。那么就直接转化成了链表求公共父节点
    如果没有任何特点，用两个链表来保存从根到其中每个所需节点的路径（递归回溯的方法），然后转换
    成两个链表求公共节点。
    还可以直接递归回溯的方法利用全局变量left+right如果=2就返回当前节点。
  1. Bool LEFT = false;
  2. bool RIGHT = false;
  3. Node *target = NULL;
  4. void findCommonRoot(Node *root,int a, int b, Node *target){
  5.     if(root==NULL) return;
  6.     if(root.value==a) LEFT = true;
  7.     if(root.value==b) RIGHT = true;
  8.     findCommonRoot(root.left,a,b,target);
  9.     findCommonRoot(root.right,a,b,target);
  10.     if(LEFT&&RIGHT){
  11.         LEFT = false;
  12.         RIGHT = false;
  13.         target = root;
  14.     }
  15. }

其实就是找一个节点，他的子节点包含了两个要找的节点

  1. Node *pRes = NULL;
  2. int find(Node *root, Node *a, Node *b,){
  3.     if(NULL!=pRes) return 0;
  4.     int sum = 0;
  5.     if(NULL==root)return 0;
  6.     if(root==a) sum+= 1;
  7.     if(root==b) sum+=1;
  8.     sum += find(root->left,a,b);
  9.     sum += find(root->right,a,b);
  10.     if(sum==2&&NULL=pRes){
  11.         pRes = root;
  12.         return 0;   
  13.     }
  14.     return sum;
  15. }

还可以遍历两次树，分别找到两个节点的路径，然后转换成链表求节点问题。

  1. 判断一棵树是否是二叉查找树
    给定一个数组是树的前序遍历，那第一个元素是root，可以将后面元素分为左右子树，并判断是否左子树都小于root，又子树都大于root，然后递归。
  1. Bool heapler(int *arr, int start, int end){
  2.     if(end-start<=1) return true;
  3.     int temp = arr[start];
  4.     for(int i=0;i<end;i++){
  5.         if(arr[i]>arr[start])
  6.             break;
  7.     }
  8.     return helper(arr,start+1,i)&&helper(arr,i,end);
  9. }
  10. Bool binary(int *arr, int len){
  11.     if(n==NULL) return true;
  12.     return helper(arr,0,len);
  13. }
  1. 判断一个树是不是另一个树的子树
    如果两个树都简单，直接对两个树进行前序遍历，如果T2是T1遍历的子序列就成功（字符不重复的 情况），如果字符有重复，还必须标志出每个非叶子节点的NULL指针。
    方法二：搜索较大的那个树T1，如果遇到节点与T2根节点一样，则调用treeMatch方法判断。
  1. Bool containsTree(TreeNode t1,TreeNode T2){
  2.     if(t2==NULL) return true;
  3.     return subTree(t1,t2);
  4. }
  5. bool subTree(TreeNode r1,TreeNode r2){
  6.     if(r1==NULL) return false;
  7.     if(r1.data==r2.data)
  8.         if(matchTree(r1,r2))
  9.             return true;
  10.     return (subTree(r1.left),r2)||subTree(r1.right,r2);
  11. }
  12. bool matchTree(TreeNode r1,TreeNode r2){
  13.     if(r2==NULL&&r1==NULL) return true;
  14.     if(r1==NULL||r2==NULL) return false;
  15.     if(r1.data!=r2.data) return false;
  16.     return matchTree(r1.left,r2.left)&&matchTree(r2.right,r2.right);
  17. }
  1. 打印出二叉树和为定值的路径(递归+回溯)
  1. void findSum(TreeNode node, int sum, int[] path, int level){
  2.     if(node == NULL) return;
  3.     path[level] = node.data;
  4.     int t = 0;
  5.     for(int i=level;i>=0;i--){
  6.         t += path[i];
  7.         if(t==sum)
  8.             print(path,i,level);
  9.     }
  10.     findSum(node.left,sum,path,level+1);
  11.     findSum(node.right,sum,path,level+1);
  12.     path[level] = NULL
  13. }
  1. 十进制数里有多少个二进制1.
  1. Int count = 0;
  2. while(n){
  3.     n = n&(n-1);
  4.     count++;
  5. }
  1. 丑数，只能被2.3.5整除的数。
  1. int Ugly(int length){
  2.     int *ugly = (int *)malloc(sizeof(int)*length);
  3.     ugly[0]=1;
  4.     int index = 1;
  5.     int p2=0,p3=0,p5=0;
  6.     while(index<length){
  7.         ugly[index] = min(ugly[p2]*2,ugly[p3]*3,ugly[p5]*5);
  8.         while(ugly[p2]*2<ugly[index]) p2++;
  9.         while(ugly[p3]*3<ugly[index])p3++;
  10.         while(ugly[p5]*5<ugly[index])p5++;
  11.     }
  12.     return ugly[index-1];
  13. }

  1. 走楼梯问题，多用循环，少用递归，Fab数列

  2. 打印一个集合所有的子集。
    a.如果是空集，就只有一个子集{}
    b.如果有一个元素a，就有{},{a1}
    c.如果有两个元素a，就有{},{a1},{a2},{a1,a2};
    可以看出，如果有n个元素，子集f(n) = f(n-1)+f(n-1)·an;一共有2^n个子集。
    代码可以用递归，也可以用循环

  1. vector<string> ans;
  2. ans.push_back(“”);
  3. string str;
  4. for(int i=0;i<str.length();i++){
  5.     int size = ans.size();
  6.     for(int j=0;j<size;j++){
  7.         ans.push_back(ans[size]+str[i]);
  8.     }
  9. }
  10. return ans;

打印全排列（递归+回溯）

  1. void print(string str, int length, int index){
  2.     if(length==index) cout<<str<<”\t”;
  3.     else for(int i=index;i<length;i++){
  4.         swap(str[index],str[i]);
  5.         print(str,length,index+1);
  6.         swap(str[index],str[i]);
  7.     }
  8. }//没有重复字符串
  9. 如果有重复字符串就要判断不能把相同的字符交换。如下操作
  10. bool IsSwap(string str, int begin, int target){
  11.     for(;begin<target;begin++)
  12.         if(str[begin]==str[target])
  13.             return false;
  14.     return true;
  15. }
  16. void print(string str, int length, int index){
  17.     if(length==index) cout<<str<<endl;
  18.     else for(int i=index;i<length;i++)
  19.         if(IsSwap(string,index,i)){
  20.             swap(str[index],str[i])
  21.             …
  22.             …
  23.         }
  24. }

下一个字典序
a 从右边开始找出第一个比最后一个数字小的数字i
b 从i的右边找出最小的数字j
c 交换i，j
d把j右边的数字反转

  1. 打印n对括号的全部有效组合
    我们可以通过递归+回溯
    a左括号有剩余，加入左括号
    b当字符串有效，加入右括号
    c如果右括号多余左括号，返回
  1. void findParems(int left, int right, int n, vector<char> v){
  2.     if(left>n||left<right) return;
  3.     if(left==n&&right==n){
  4.         for(int i=0;i<v.size();i++)
  5.             cout<<v[i];
  6.         cout<<endl;
  7.     }
  8.     else{
  9.         if(left<n){
  10.             v.push_back('(');
  11.             findParems(left+1,right,n,v);
  12.             v.pop_back();
  13.         }
  14.         if(left>right){
  15.             v.push_back(')');
  16.             findParems(left,right+1,n,v);
  17.             v.pop_back();
  18.         }
  19.     }
  20. }

  1. 如何从40亿个正整数中找出一个不在这个文件中的数字
    a.使用1G内存，也就是1*1000*1000*1000*8=80亿个比特位。那么可以使用bitset来记录扫描 一遍把存在的整数置1,然后不存在的位0
    b.如果只用10M内存，也就是10*1000*1000*8=800万个位，把40亿分开成800分每份500万个数字，我们每次判断0-500万-100万-1500万的数字，分800次检测完

  2. 给定100亿个网址，找出重复网址。如果长度平均100字符，每个字符占1字节，就有1T
    a.储存在磁盘。第一次扫描将地址类表拆分到100个文件中，每个1G，命名为.txt。其中
    n=hast(url)%100。第二次扫描的时候就可以直接将这些单个文件载入内存，创建散列表，找出重复

  3. 给定两个排序好的数组AB，A的末端有足够的空间存放B，请合并两个数组。
    如果从前面开始比较，那么每次插入都可能移动很多数据。所以我们要从两个数组的最后开始比较，然后插入到A数组的末端

  1. int* join(int a[],int lena, int size, int b[], int lenb){
  2.     if(size-lena<lenb) return false;
  3.     int I=lena-1,j=lenb-1,index=size-1;
  4.     while(i>=0&&j>=0){
  5.         if(a[lena]>b[lenb]){
  6.             a[index] = a[i];
  7.             i--;
  8.         }
  9.         else{
  10.             a[index] = b[j];
  11.             j--;
  12.         }
  13.         index--;
  14.     }
  15.     if(i>=0)
  16.         while(i>=0)
  17.             a[index--] = a[i--];
  18.     if(j>=0)
  19.         while(j>=0)
  20.             a[index--] = b[j--];
  21.     return a+index+1;
  22. }
  1. 给定一个n个元素的数组，它是已经排序好（从小到大）的数组经过多次旋转而成，请查找数组中的某个元素。
    不管多少次旋转，都是有一个分界点，一半升序一半降序。比如987612345,我们可以比较当前mid与low和high 的大小，如果mid 
  1. Int find(int arr[], int len, int n){
  2.     int low=0,high=len-1,mid;
  3.     while(low<=high){
  4.         mid = low +(high-low)/2;
  5.         if(arr[mid]==n) return mid;
  6.         if(arr[mid]>=arr[high]){//左边有序
  7.             if(n>arr[mid]&&n<=arr[]) high = mid-1;
  8.             else low = mid+1;
  9.         }
  10.         else{
  11.             if(n>arr[low]&&n<=arr[high]) low = mid+1;
  12.             else high = mid-1;
  13.         }
  14.     }
  15.     return -1;
  16. }

  1. 有个20G的大文件，每行一个字符串，请排序。
    把文件分成x份，每份20*1000/x，能放入内存，然后对每份单独排序。最后逐一将这些文件整合在一起。

  2. 给定一个矩阵，每行列都按照升序排列，请查找某个数。
    从右上角开始，大于向下，小于向左。

  1. Bool find(int arr[][],int len,int high, int target){
  2.     int i=len-1;
  3.     int j=0;
  4.     while(i>=0&&j<high){
  5.         if(arr[j][i]==target) return true;
  6.         if(arr[j][i]>target) I--;
  7.         else j++;
  8.     }
  9.     return false;
  10. }
  1. 交换两个数字，不用临时变量
  1. 法一：
  2. a = a-b;
  3. b = a+b;
  4. a = b-a;
  5. 法二：
  6. a = a^b;
  7. b = a^b;
  8. a = a^b;
  1. n的阶乘有多少个尾随0
    如果直接阶乘再除以10，很快就会越界。我们观察出现10的时候出现0,从而出现2*5对的时候出现0,而2的倍数比5多很多，所以，出现5的倍数的时候必然出现0。有个陷阱就是15=3*5是一个5的倍数，25=5*5是两个5的倍数。于是有了下面代码
  1. int contZero(int num){
  2.     int count = 0;
  3.     if(num<0) return -1;
  4.     for(i = 5; num/i>0;i *= 5)
  5.         count+=num/i;
  6.     return count;
  7. }

N!二进制中第一个1出现的最低位置
如3!=6=1010;最低位在第二位上。一个二进制数字除以二就相当于如果最后一位是0就直接右移一位，如果是1就不能除。所以，这个问题就相当于说N!能够右移次数，也就是质因子2的个数。

  1. int lowestOne(int n){
  2.     int ret = 0;
  3.     for(i=2;n/i>0;i *=2)
  4.         ret += n/i;
  5.     return ret;
  6. }
  1. 找出数组中连续最大和
  1. int maxSum(int a[],int n){
  2.     int max = a[0];
  3.     int sum = 0;
  4.     for(int i=0;i<n;i++){
  5.         if(sum>0) sum+= a[i];
  6.         else sum = a[i];
  7.         if(sum>max) max=sum;
  8.     }
  9.     return max;
  10. }

求连续的最大积
当已经知道了前k个数字的最大，最小值，那么第k+1个数字的最大值只能是max*a[k],min*a[k],a[k]中的最大者。```c
double func(doubel *a,int n){
double *maxA = new double[n];
double *minA = new double[n];
maxA[0] = minA[0] = a[0];
double value = a[0];
for(int i=1;i maxA[i] = max(max(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);
minA[i] = min(min(a[i],maxA[i-1]*a[i]),minA[i-1]*a[i]);
value = max(value,maxA[i]);
}
reutrn value;
}

  1. 20. 寻找数组中出现次数超过一半的元素
  2. 可以用quick select找到中间个元素因为出现次数超过了一半，那么我们每次遇到两个不同的数字就丢掉，最后剩下的肯定只有它
  3. ```c
  4. int find(int array[], int length){
  5.     int temp;
  6.     int times=0,i;
  7.     for(i=0;i<length;i++){
  8.         if(times==0){
  9.             temp = array[i];
  10.             times += 1;
  11.         }
  12.         else{
  13.             if(temp==array[i])
  14.                 times+=1;
  15.             else
  16.                 times-=1;
  17.         }
  18.     }
  19.     return temp;
  20. }
  23. <div class="md-section-divider"></div>

查找两个出现次数超过三分之一的数字。解题方法是一样的，可以用维护times[2]的方法搞定。推广到出现超过n/(m+1)次的数字，可以用俄罗斯方块的形式，维护一个map

  1. int *find(int array[], int len, int m){
  2.     map<int, int> m;
  3.     for(int i=0;i<len;i++){
  4.         if(m.size()<len){
  5.             if(m.find(array[i]))
  6.                 m[array[i]] += 1;
  7.             else
  8.                 m[array[i]]  = 1;
  9.         }
  10.         else{
  11.             for(map<int,int>::iterator it=p.begin();it!=p.end();){
  12.                 it->second -= 1;
  13.                 if(it->second==0){
  14.                     p.erase(it++);
  15.                     continue;
  16.                 }
  17.                 it++;
  18.             }
  19.         }
  20.     }
  21. }
  24. <div class="md-section-divider"></div>
  1. 查找最大的k个数
    当数据不大的时候可以使用quick select找到k位置，那么前面的都是合理的。
    当数据很大（比如说一亿个）就需要建立k个元素的最小堆，然后在继续单个扫描
  1. void buildHeap(int arr[], int len, int index){
  2.     if(index>=len) return;
  3.     int I = index;
  4.     int c = i*2+1;
  5.     while(c<len){
  6.         if(c+1<len && arr[c]>arr[c+1]) c++;
  7.         if(arr[i]<arr[c]) break;
  8.         else{
  9.             swap(arr[i],arr[c]);
  10.             I = c;
  11.             c = 2*i+1;
  12.         }
  13.     }
  14. }
  17. <div class="md-section-divider"></div>

然后每次进入一个数字就与堆顶比较、重新建堆。

  1. 最大公约数问题
    辗转相除
  1. int gcd(int x,int y)//suppose x>y
  2. {
  3.     while(x%y){
  4.         int temp = x%y;
  5.         x = y;
  6.         y = temp;
  7.     }
  8.     return y;
  9. }
  12. <div class="md-section-divider"></div>

同理，辗转相减

  1. int gcd(int x,int y){
  2.     while(y){
  3.         int temp = x-y;
  4.         x = y;
  5.         y = temp;
  6.     }
  7. }
  10. <div class="md-section-divider"></div>
  1. 数组中和为定值的两个数字
    最笨就是sum-a[i]然后从数组中找另一个，复杂度O(n^2)
    稍微好就是先排序，后二分，复杂度O(NlogN+NlogN)
    情况允许时，用hash表存数组需要O(N)时间存，然后直接找另一个数是否在表中。空间O(N)
    最好的办法排序，双向查找O(NlogN+N)
  1. for(int i=0, j=n-1;i<j;){
  2.     if(a[i]+a[j]<sum) i++;
  3.     else(a[i]+a[j]>sum)j--;
  4.     else printf(“%d %d\n”,a[i],a[j]);
  5. }
  8. <div class="md-section-divider"></div>

1-n中随机选择和为m的几个数字
简单的办法是使用递归，回溯

  1. void print(vector<int>v){
  2.     int s = v.size();
  3.     for(int i=0;i<s;i++)
  4.         cout<<v[i]<<”\t”;
  5.     cout<<endl;
  6. }
  7. void helper(int I, int n, int m, int sum, vector<int> v){
  8.     if(sum>m) return;
  9.     if(i>n) return;
  10.     if(sum==m){
  11.         print(v);
  12.         return;
  13.     }
  14.     for(;i<n;i++){
  15.         v.push_back(i);
  16.         helper(i+1,n,m,sum+i,v);
  17.         v.pop_back(i);
  18.     }
  19. }
  20. void find(int n, int m, vetor<int> v){
  21.     if(n>m) n = m;
  22.     int sum = 0;
  23.     int i=1;
  24.     helper(i,n,m,sum,v);
  25. }
  28. <div class="md-section-divider"></div>

24.数组的最长递增序列
如1,-1,2,-2,3,-3,4，-4的最长递增序列就是1,2，3,4
那可以动态规划来解决。
Int findMax(int array[], int length){
int *len = new int[length];
for(int i=0;i len[i] = 1;
for(int j=0;j if(array[i]>array[j] && len[j]+1>len[i])
len[i] = len[j]+1;
}
}
return max(len);
}

  1. 数组的循环移位。
    常规算法中，我们每次移动一个数字，一共需要K*N次操作。
    我们观察数组abcd1234-->1234abcd我们可以分为另外几个步骤
    把abcd旋转-->dcba,把1234旋转4321。此时数组是dcba4321.
    最后把数组旋转，成了1234abcd。只有2*N次操作。
  1. Void reverse(int array[],int low,int high){
  2.     for(;low<high;low++,high--)
  3.         swap(array[low],array[high]);
  4. }
  5. void shift(int array[], int n, int k){
  6.     k = k%n;
  7.     reverse(array,0,n-k-1);
  8.     reverse(array,n-k,n-1);
  9.     reverse(array,0,n-1);
  10. }
  13. <div class="md-section-divider"></div>

  1. 数组分割
    把数组分割成两部分，使得凉拌和尽可能接近。也就是一半的和接近整体和的一半。
    除了暴力我不会

  2. 字符串移位包含问题。
    Str1 = “AABCD” str2=”CDAA”，问str2是否属于str1移位之后的字符串。
    常规解法，每次移动一位，然后通过strstr(str1,str2)来比较如果返回0,则存在
    空间换时间：我们观察str1如果循环移位str1.length()次之后又回到的原来样子，那我们其实可以直接保留原来移位的字符，移位length()次后开始重复。事实上，就是从AABCDAABCD中查找CDAA。

  1. Bool find(string str1,string str2){
  2.     int len1 = str1.length();
  3.     int len2 = str2.length();
  4.     if(len2>len1) return 0;
  5.     string str = str1+str1;
  6.     int len=str.length();
  7.     int I,j;
  8.     for(i=0;i<len;i++){
  9.         for(j=0;j<len2;len++){
  10.             if(str[i+j]!=str2[j])
  11.                 break;
  12.         if(j==len2) return true;
  13.         }
  14.     } 
  15.     return false;
  16. }
  19. <div class="md-section-divider"></div>
  1. 字符串编辑距离计算。
    就是一个字符串通过增删改成为另一个字符串。我们可以用二维数组加动态规划解决。
    Edit(1,1) = min(edit(0,1)+1,edit(1,0)+1,edit(0,0)+f(1,1))其中如果abc[1]==bcd[1],f(1,1)=0,反之为1
    这是一个算法，每个位置都是当前两个字符串的编辑距离，最后我们需要的就是右下角。
  1. Int func(string a,int I,string b,int j){
  2.     if(a[i-1]==b[j-1]) return 0;
  3.     return 1;
  4. }
  5. Int minEdit(string a, string b){
  6.     int lena=a.length(),lenb=b.length();
  7.     if(lena==0) return lenb;
  8.     if(lenb==0) return lena;
  9.     int **dest = new (int *)[lena+1];
  10.     int I,j;
  11.     for(i=0;i<lena;i++)
  12.         dest[i] = new int[lenb+1];
  13.     for(i = 0;i<lena+1;i++) dest[i][0] = i;
  14.     for(j=0;j<lenb+1;j++) dest[0][j] = j; 
  15.     for(i=1;i<lena+1;i++){
  16.         for(j=1;j<lenb+1;j++){
  17.             dest[i][j] = min( min(dest[i-1][j]+1,dest[i][j-1]+1),dest[i-1][j-1]+func(a,i,b,j));
  18.         }
  19.     }
  20.     return dest[lena][lenb];
  21. }
  24. <div class="md-section-divider"></div>

  1. 从无头链表中删除节点。
    把下一个节点值复制给当前节点，删除下一节点（不是尾节点才能这样做）。

  2. 八种常见排序算法
    快速排序：时间复杂度O(nlogn)—O(n*n)，空间复杂度O(logn)，不稳定

  1. void quickSort(int arr[], int low, int high){
  2.     if(low>=high) return;
  3.     int mid = (low+high)/2;
  4.     int i=j=low;
  5.     int povit = arr[low];
  6.     while(j<high){
  7.         if(arr[j]<povit){
  8.             i++;
  9.             int temp = arr[j];
  10.             arr[j] = arr[i];
  11.             arr[i] = temp;
  12.             j++;
  13.         }
  14.         else
  15.             j++;
  16.     }
  17.     int temp = arr[i];
  18.     arr[i] = arr[low];
  19.     arr[low] = temp;
  20.     quickSort(arr,low,i);
  21.     quickSort(arr,i+1,j);
  22. }
  25. <div class="md-section-divider"></div>

插入排序：从0到n逐个排序插入，时间复杂O(n)—O(n*n),空间O(1),稳定

  1. for(int i=0;i<len;i++)
  2.     for(int j=0;j<i;j++){
  3.         if(arr[i]>arr[j]){
  4.             shiftRight(i,j);
  5.         }
  6.     }
  9. <div class="md-section-divider"></div>

希尔排序：分多路的插入排序，时间O(n)—O(n^3/2)—O(n(logn)^2),不稳定

  1. void shellSort(int *data,size_t size){
  2.     for(int gap=size/2;gap>0;gap /= 2)
  3.         for(int i=gap;i<size;i++){
  4.             int k=data[i];
  5.             int j=0;
  6.             for(j=i-gap;j>=0&&data[j>k; j-=gap]){ data[j+gap]=data[j]; data[j]=k;}
  7.         }
  8. }
  11. <div class="md-section-divider"></div>

选择排序：不稳定

  1. for(i=0;i<len;i++)
  2. {
  3.     for(j=i;j<len;j++){
  4.         chose max;
  5.     }
  6.     swap(i,max);    
  7. }
  10. <div class="md-section-divider"></div>

归并排序：O(nlogn)—O(nlogn),O(n)，稳定，常用于已排序的数组或者链表的合并

  1. void mergeSort(int a[], int first, int last, int temp[]){
  2.     if(first<last){
  3.         int mid=(first+last)/2;
  4.         mergeSort(a,first,mid,temp);//归并左边
  5.         mergeSort(a,mid+1,last,temp);//归并右边
  6.         mergearray(a,first,mid,last,temp);//合并
  7.     }
  8. }
  11. <div class="md-section-divider"></div>

堆排序：O(nlogn)—O(nlogn),O(1)，不稳定
主要步骤：建立堆结构，删除根节点。

  1. //建堆
  2. void shift(int d[], int ind, int len){
  3.     int i  = ind;
  4.     int c = 2*i+1;
  5.     while(c<len){
  6.         if( (c+1<len) && d[c]<d[c+1] ) c++;
  7.         if(d[i]>d[c]) break;
  8.         else {
  9.             swap(d[i],d[c]); i=c; c=2*i+1; 
  10.         }
  11.     }
  12. }
  13. void heap_sort(int d[], int n){
  14.     for(int i=n/2;i>=0;i++)
  15.         shift(d,i,n);
  16.     for(int j=0;j<n;j++){
  17.         swap(d[0],d[n-j-1]);
  18.     }
  19. }
  22. <div class="md-section-divider"></div>

计数排序：统计数字出现的次数，比如对年龄排序。适用于小规模整数排序。O(n+k),O(n)稳定

  1. KMP算法
    重要的是利用动态规划求解next数组
  1. void FindNext(char str[], int next[]){
  2.     next[0] = -1;
  3.     int j=-1;
  4.     int i=0;
  5.     int len = strlen(str);
  6.     while(i<len-1){
  7.         if(j==-1||str[i]==str[j])
  8.             str[++i] = ++j;
  9.         else
  10.             j = next[j];
  11.     }
  12. }
  13. main(){
  14.     char p[]=”aaabababcdsre”;
  15.     char str[]=”ababc”;
  16.     int next[5];
  17.     FindNext(str,next);
  18.     int I=j=0;
  19.     int lenp=strlen(p),lens=strlen(str);
  20.     while(i<p){
  21.         while(i<lenp&&j<lens&&p[i++]==str[j++]);
  22.         if(j==lens){
  23.             cout<<i-j<<endl;
  24.             break;
  25.         }
  26.         I -= next[j];
  27.         j = next[j];
  28.     }
  29.     return 0;
  30. }
  33. <div class="md-section-divider"></div>
  1. 一致性hash(google之)
  2. 数组中只出现一次的一个数字,其他数字都出现两次（统一的都可以用n大小空间的计数排序记录）
    直接取异或，最后的结果就是。
    出现一次的两个数字，先异或，然后找到一个为1的位，将数组分解成那位为1和0的两个部分。
  1. Void find(int *arr, int len, int *result){
  2.     int I,all=0,flag=1;
  3.     for(i=0;i<len,i++)
  4.         all ^= arr[i];
  5.     while(!(all&flag))
  6.         flag<<=1;
  7.     result[1] = result[0] = 0;
  8.     for(i=0;i<len;i++){
  9.         if(flag&arr[i])
  10.             result[0] ^= arr[i];
  11.         else
  12.             result[1] ^= arr[i];
  13.     }
  14. }
  17. <div class="md-section-divider"></div>

其他数字都出现三次，找出一个只出现一次的
可以想到，不能用异或了。但是明显有所有出现三次的在每个二进制位上的1的个数肯定能被 三整除。推广说，其他出现n次，那么二进制上每位1的个数都可以被n整除

  1. int FindNumber(int a[], int len){
  2.     int bit[32];
  3.     int I,j;
  4.     memset(bit,0,32*sizeof(int));
  5.     for(i=0;i<n;i++)
  6.         for(j=0;j<32;j++)
  7.             bits[j] += (a[i]>>j)&1;
  8.     int result = 0;
  9.     for(j=0;j<32;j++)
  10.         if(bits[j]%3!=0)
  11.             result += (1<<j);
  12. }
  15. <div class="md-section-divider"></div>
  1. 计算x的n次方
    传统方法直接激计算，但是我们可以通过二分法更好的计算
  1. int power(int x, int n){
  2.     if(n==0) return 1;
  3.     if(n==1) return x;
  4.     if(n%2)
  5.         return power(x, n/2)*power(x,n/2)*x;
  6.     return power(x,n/2)*power(x,n/2);
  7. }
  8. int power(int x,int n){
  9.     if(n==0) return 1;
  10.     if(n==1) return x;
  11.     int result = 1;
  12.     while(n!=0){
  13.         if((n&1)!=0) result *= x;
  14.         x *= x;
  15.         n >> 1;
  16.     }
  17.     return result;
  18. }
  21. <div class="md-section-divider"></div>

  1. 约瑟夫环
    N个人，从第一人开始数，每次数到m的那个就推出，然后继续从下一个从一开始数
    常规解法：直接建立一个环形链表，然后操作
    有数学方法，没想到，懒得看

  2. 一个int数组，里面数据无任何限制，要求求出所有这样的数a[i]，其左边的数都小于等于它，右边的数都大于等于它。能否只用一个额外数组和少量其它空间实现。
    基:我们可以用两个数组max[i]记录位置i左边的最大值，min[i]记录i右边的最小值，由于题目只要一个额外数组，其实左边的最大数组是可以一边遍历一般判断的（如果从右到做也可以不需要min数组）

  1. void find(int arr[], int len, vector<int> &v){
  2.     int *max = new int[len];
  3.     int max[0] = arr[0];
  4.     for(int i=1;i<len;i++){
  5.         if(arr[i]>=max[i-1]);
  6.         max[i] = arr[i];
  7.     }
  8.     int min = arr[len-1];
  9.     for(int j=len-1;j>=0;j--){
  10.         if(arr[j]<min) min = arr[j];
  11.         if(arr[i]>=max[i]&&arr[i]<=min)
  12.             v.push_back(i);
  13.     }
  14. }
  17. <div class="md-section-divider"></div>

  1. 求N长度整数数组中N-1个数字的乘积的最大值
    法一：直接求出N-1个积，查询最大值
    法二：利用N个数字的正负分布情况。扫描一遍，统计数组中出现的整数个数p，负数个数n，零个数z，绝对值最小的正复数a，b
    如果z>=2,结果0,
    如果z=1，当n是奇数结果为0,n是偶数结果是除0以外的乘积
    如果z=0，当n是奇数，就是除开b以外的积，n是偶数就是除开a以外的积

  2. 链表的排序
    快排：改变节点中的值不改变指向/改变指向不改变值
    使用改变指针的时候，每次分割的时候另外开两个指针left和right，最后再将两个指针合并起来。
    我们可以将链表的第一个节点使用空节点，然后每次递归传入的都是pre,left,right三个节点。
    归并：也是递归形式的
    插入排序：

  3. LCS

  1. stra, strb, ans[][]
  2. ans[i][0]=0;ans[0][j]=0;
  3. for(i:0->lena)
  4.     for(j:0->lenb)
  5.         if(stra[i]==strb[j]) ans[i][j] = ans[i-1][j-1]+1;
  6.         else ans[i][j]=max(ans[i-1][j],ans[i][j-1]);
  9. <div class="md-section-divider"></div>

  1. 最大子矩阵和
    从1-n列，n*n个长矩阵，把长矩阵的没一列当成一个数组，求数组连续最大和

  2. 把n个骰子扔地上，所有向上的一面的和是s，输入n，输出所有s出现的概率
    问题其实就是求解每个s出现的次数从[n,6n]
    思路一：利用递归回溯原理，每次扔一个骰子，扔到n次的时候记录当前和进map中
    思路二：动态规划，找到最优子结构，本题的结构是F(k,n)表示k个骰子和为n的次数，有如下关系
    F(k,n)=F(k-1,n-1)+F(k-1,n-2)...+F(k-1,n-6),当k=1时，F(1,1->6)=1

  3. 第一个只出现一次的字符
    扫描一遍，记录每个字符出现的次数，第二遍扫描的时候如果字符对应的是1就返回

  4. 输入n打印出从0到位数为n的最大的数字。
    实际上就是n个数位上从0-9的排列。递归打印

  5. 打印排列和组合，有/没有重复元素

  1. //无重复的排列
  2. void print(string s, int len, int index){
  3.     if(index>len) return;
  4.     if(index==len){
  5.         cout<<s<<endl;
  6.         return;
  7.     }
  8.     for(int i=index;i<len;i++){
  9.         swap(s[i],s[index]);
  10.         print(s,len,index+1);
  11.         swap(s[i],s[index]);
  12.     }
  13. }
  16. <div class="md-section-divider"></div>

  1. 数字的整数次方。
    判断次方是不是0,1；
    当次方是奇数的时候a^n = a^((n-1)/2)*a((n-1)/2)*a
    当次方是偶数的时候a^n = a^(n/2)*a(n/2)

  2. 二叉树生成双向链表

  3. 数字在排序数组中出现的次数
    首先二分查找，然后从节点开始两边遍历

  4. 求二叉树的深度

  1. int deep(Node *node){
  2.     if(node==NULL) return 0;
  3.     int left = deep(node->left);
  4.     int right = deep(node->right);
  5.     return (left>right)? (left+1):(right+1);
  6. }
  9. <div class="md-section-divider"></div>

求二叉树是不是AVL

  1. bool balance(Node *node){
  2.     if(node==NULL) return true;
  3.     int left = deep(node->left);
  4.     int right = deep(node->right);
  5.     int diff = (left>right)? (left-right):(right-left);
  6.     if(diff>1) return false;
  7.     return balance(node->left)&&(node->right);
  8. }//重复计算，效率底下
  11. <div class="md-section-divider"></div>

如果我们后续遍历，那么一遍遍历就可以得到结结果

  1. bool balance(Node *node, int &deep){
  2.     if(node==NULL){
  3.         deep = 0;
  4.         return true;
  5.     }
  6.     int left,right;
  7.     if(balance(node->left,left)&&balance(node->right,right)){
  8.         int diff = (left>right)? (left-right):(right-left);
  9.         if(diff<=1){
  10.             deep = 1+ (left>right? Left:right);
  11.             return true;
  12.         }
  13.     }
  14.     return false;
  15. }
  18. <div class="md-section-divider"></div>

  1. 不用乘除，for，while，if，switch，求1-n的和
    正常情况下可以用循环或者递归来实现。但是这里都不行。
    构造函数求解：用两个静态变量，n和sum每次构造一个实例new boj[n]就n++，sum += n;

  2. 给一个二叉树，每个节点都是正或负整数，如何找到一个子树，它所有节点的和最大？
    后续序遍历，每个节点保存当前值和当前最大值．到顶部的时候就是最大值

  1. int find(Node *node){
  2.     if(node==NULL) return -1;
  3.     return helper(node);
  4. }
  5. int helper(Node *node){
  6.     int left=0,right=0;
  7.     if(node->left!=NULL)
  8.         left = helper(node->left);
  9.     if(node->right!=NULL)
  10.         right = helper(node->right);
  11.     if(node->value<0)
  12.         node->value = max(node->value,left,right);
  13.     int temp = left;
  14.     if(left<right)temp = rigtht;
  15.     if(temp>0)
  16.         node->value+=temp;
  17.     return node->value;
  18. }
  21. <div class="md-section-divider"></div>
  1. 翻译数字串，类似于电话号码翻译：给一个数字串，比如12259，映射到字母数组，比如，1 -> a， 2-> b，... ， 12 -> l ，... 26-> z。那么，12259 -> lyi 或 abbei 或 lbei 或 abyi。输入一个数字串，判断是否能转换成字符串，如果能，则打印所以有可能的转换成的字符串。
    递归遍历，每次加入一个和两个字符递归下去
  1. DICT = { str(i+1):chr((ord('a')+ i)) for i in range(26) }
  2. MAX_SIZE = max(len(k) for k in DICT.keys())
  3. def parse(dt,cache,string):
  4.     if string == "":
  5.         return [""]
  6.     if string in cache:
  7.         return cache[string]
  8.     ret = []
  9.     for i in range(MAX_SIZE):
  10.         if len(string) > i and string[0:i+1] in dt:
  11.             ret += [ dt[string[0:i+1]] + j for j in parse(dt,cache,string[i+1:]) ]
  12.         else:
  13.             break
  14.     cache[string] = ret
  15.     return ret
  18. <div class="md-section-divider"></div>
  1. void print(vector<char> v){
  2.     int i;
  3.     for(i=0;i<v.size();i++)
  4.         cout<<v[i];//>>>>
  5.     cout<<endl;
  6. }
  7. void helper(char *str, int start, vector<char> v){
  8.     int len = strlen(str);
  9.     if(start == len){
  10.         print(v);
  11.     }
  12.     if(start<len&&str[start]-'0'>0&&str[start]-'0'<=9){
  13.         v.push_back(str[start]-'0'+'a');
  14.         helper(str,start+1,v);
  15.         v.pop_back();
  16.         if(start+1<len&&str[start+1]-'0'>0&&str[start+1]-'0'<=9){
  17.             int temp = str[start]-'0';
  18.             temp = temp*10+str[start+1]-'0';
  19.             if(0<temp&&26>temp){
  20.             v.push_back('a'+temp);
  21.             helper(str,start+2,v);
  22.             v.pop_back();
  23.             }
  24.         }
  25.     }
  26. }
  27. void find(char *str){
  28.     vector<char> v;
  29.     helper(str,0,v);
  30. }
  31. int main(int argc, const char *argv[])
  32. {
  33.     char arr[] = "13264811591";
  34.     find(arr);
  35.     return 0;
  36. }
  1. 给一串整数 0，1，2，...，N，其中一个整数缺失。也就是说，如果是排序好放到大小为N的数组中，其实最大的整数应该是N+1。你的任务和算法是找出其中缺失的整数。如果是排序好的，怎么做？如果是无序的，又该如何做？时间复杂度各是什么？你能想到的最优算法是什么？
    有序：二分
    无序：Ｎ比较小的时候直接加起来看少了哪个．Ｎ比较大的话一次遍历，把每个数字放到他应该有的下标，最后数字Ｎ的下标就是缺失的数字
  1. void find(int arr[], int len){
  2.     int I=0;
  3.     int count=0;
  4.     int temp;
  5.     while(count<len){
  6.         count++;
  7.         if(arr[i]==i||arr[i]==len)
  8.             i++;
  9.         else{
  10.             temp = arr[i];
  11.             arr[i] = arr[temp];
  12.             arr[temp] = temp;
  13.         }
  14.     }
  15.     i=0;
  16.     while(i<len)
  17.         if(arr[i++]==len){
  18.             cout<<i-1<<endl;
  19.             break;
  20.         }
  21. }
  1. 一个大小为n的数组，里面的数都属于范围[0, n-1]，有不确定的重复元素，找到至少一个重复元素，要求O(1)空间和O(n)时间．
    可以同上面一题，先把每个数字移动到自己的下标位置，然后对这个数字置-1,再次遇到-1的时候，就是重复数
    如果可以改变数组，那么我们可以访问一个数字ｉ，然后ｉ=a[i]并把a[i]置-1，然后一直这样访问下去，遇到一个值为-1的数字就是重复了
  1. int find(int arr[], int len){
  2.     int count=0;
  3.     int index=0;
  4.     int temp;
  5.     while(count++<len){
  6.         if(arr[index]==-1)
  7.             return index;
  8.         else{
  9.             temp = arr[index];
  10.             arr[index]=arr[temp];
  11.             arr[temp]=-1;
  12.         }
  13.     }
  14.     return -1;
  15. }
  1. 写一个函数，求两个整数之和，要求在函数体内不得使用＋、－、×、÷
    利用计算机加法器原理
  1. int add(int a, int b){
  2.     if(b==0) return a; 
  3.     int sum = a^b; 
  4.     int carry =(a&b)<<1; 
  5.     return add(sum,carry);
  6. }
  1. 给一个无序的正整数数组，找出所有三个元素的组合使它们作为三条边能形成一个三角形。比如，输入为{4, 6, 3, 7}, 可能组合为 {3, 4, 6}，{4, 6, 7}和{3, 6, 7}。
  1. void swap(int &a, int &b)
  2. {
  3.     int temp = a;
  4.     a = b;
  5.     b = temp;
  6. }
  7. bool helper(int a, int b, int c)
  8. {
  9.     if( (a+b)>c && (b-a)<c )
  10.         return true;
  11.     return false;
  12. }
  13. void Judeg(vector<int> vv)
  14. {
  15.     vector<int> v(vv);
  16.     if(v[0]>v[1])
  17.         swap(v[0],v[1]);
  18.     if(v[1]>v[2])
  19.         swap(v[1],v[2]);
  20.     if(helper(v[0],v[1],v[2]))
  21.         if(helper(v[1],v[2],v[0]))
  22.             if(v[0],v[2],v[1])
  23.             {
  24.                 for(int i=0;i<3;i++)
  25.                     cout<< v[i] <<"\t";
  26.                 cout<<endl;
  27.             }
  28. }
  29. void FindTrangLe(int array[], int index, int len, vector<int> v)
  30. {
  31.     if( v.size()==3 )
  32.     {
  33.         Judeg(v);
  34.         return;
  35.     }
  36.     if(index>=len)
  37.         return;
  38.     for(int i=index;i<len;i++)
  39.     {
  40.         v.push_back(array[i]);
  41.         FindTrangLe(array,i+1,len,v);
  42.         v.pop_back();
  43.     }
  44. }
  1. 给出n，答应出合法的n对括号。
    比如输入2,输出()(),(())
  1. void print(vector<char> v){
  2.     int j;
  3.     for(j=0;j<v.size();j++)
  4.         cout<<v[j];
  5.     cout<<endl;
  6. }
  7. void helper(int left, int right, int n, vector<char> v){
  8.     if(left==right&&left==n)
  9.         print(v);
  10.     if(left>n) return;
  11.     v.push_back('(');
  12.     helper(left+1,right,n,v);
  13.     v.pop_back();
  14.     if(left>right){
  15.         v.push_back(')');
  16.         helper(left,right+1,n,v);
  17.         v.pop_back();
  18.     }
  19. }
  20. void find(int n){
  21.     int left=0;
  22.     int right=0;
  23.     vecotr<char> v;
  24.     helper(left, right, n, v);
  25. }

给出n对括号，判断合法性（经典做法用栈，也可以用一个计数器遇到左+1右-1）

  1. bool judeg(char *str){ 
  2.     int count=0; 
  3.     int len=strlen(str); 
  4.     for(int j=0;j<len;j++){ 
  5.         if(count<0) break; 
  6.         if(str[j]!='('&&str[j]!=')') return false; 
  7.         if(str[j]=='(') count++; 
  8.         else if(str[j]==')') count--; 
  9.     } 
  10.     if(count!=0) 
  11.         return false; 
  12.     return true; 
  13. }
  1. 求字符串中的最长回文串
  1. int find(char *str){
  2.     int len = strlen(str);
  3.     int i;
  4.     int left,right;
  5.     if(len==1) return 1;
  6.     int max = 1;
  7.     for(i=1;i<len-1;i++){
  8.         left=i-1;
  9.         right=i+1;
  10.         if(str[left]==str[right]){
  11.             while(left>=0&&right<len&&str[left--]==str[right++]){
  12.                 if(max<right-left-1)
  13.                     max = right-left-1;
  14.             }
  15.         }
  16.         if(str[i]==str[right]){
  17.             right++;
  18.             while(left>=0&&right<len&&str[left--]==str[right++]){
  19.                 if(max<right-left-1)
  20.                     max = right-left-1;
  21.             }
  22.         }
  23.     }
  24.     return max;
  25. }

  1. 一个小猴子边上有100 根香蕉，它要走过50 米才能到家，每次它最多搬50 根香蕉，每走1 米就要吃掉一根，请问它最多能把多少根香蕉搬到家里。
    设折返一次，折返点距离出发点x，在出发点带50个，到达折返点放下50－2x个，返回出发点带上剩下的50个，再次到达扳返点时有(50－2x)+(50－x)=100－3x，剩下50-x米，到家时还剩(100-3x)-(50-x)=50-2x，显然x越小，结果越大，但是需要满足100-3x<=50，因此结果为50/3=16。

  2. 大数加减乘除

  3. 两个软硬程度一样但未知的鸡蛋，它们有可能都在一楼就摔碎，也可能从一百层楼摔下来没事。有座100层的建筑，要你用这两个鸡蛋通过最少的次数确定哪一层是鸡蛋可以安全落下的最高位置。可以摔碎两个鸡蛋
    基于动态规划的方法
    前面提到，若要采用动态规划的方法，最重要的是要找到子问题。做如下的分析，假设f{n}表示从第n层楼扔下鸡蛋，没有摔碎的最少尝试次数。第一个鸡蛋，可能的落下位置(1,n),第一个鸡蛋从第i层扔下，有两个情况：
    碎了，第二个鸡蛋，需要从第一层开始试验，有i-1次机会
    没碎，两个鸡蛋，还有n-i层。这个就是子问题了f{n-i} 所以，当第一个鸡蛋，由第i个位置落下的时候，要尝试的次数为1 + max(i - 1, f{n - i})，那么对于每一个i，尝试次数最少的，就是f{n}的值。状态转移方程如下： f{n} = min(1 + max(i - 1, f{n - 1}) ) 其中: i的范围为(1, n), f{1} = 1 完毕。
    推广
    动态规划的方法，可以推广为n层楼，m个鸡蛋。如下分析： 假设f{n,m}表示n层楼、m个鸡蛋时找到最高楼层的最少尝试次数。当第一个鸡蛋从第i层扔下，如果碎了，还剩m-1个鸡蛋，为确定下面楼层中的安全楼层，还需要f{i-1,m-1}次，找到子问题；不碎的话，上面还有n-i层，还需要f[n-i,m]次，又一个子问题。 状态转移方程如下： f{n, m} = min(1 + max(f{n - 1, m - 1}, f{n - i, m}) ) 其中： i为(1, n), f{i, 1} = 1
    基于数学方程的方法
    假设最少尝试次数为x，那么，第一个鸡蛋必须要从第x层扔下，因为：如果碎了，前面还有x - 1层楼可以尝试，如果没碎，后面还有x-1次机会。如果没碎，第一个鸡蛋，第二次就可以从x +（x - 1）层进行尝试，为什么是加上x - 1，因为，当此时，第一个鸡蛋碎了，第二个鸡蛋还有可以从x+1 到 x + (x - 1) - 1层进行尝试，有x - 2次。如果还没碎，那第一个鸡蛋，第三次从 x + (x - 1) + (x - 2)层尝试。碎或者没碎，都有x - 3次尝试机会，依次类推。那么，x次的最少尝试，可以确定的最高的楼层是多少呢？ x + (x - 1) + (x - 2) + … + 1 = x(x+1) / 2 那反过来问，当最高楼层是100层，最少需要多少次呢？x(x+1)/2 >= 100, 得到x>=14，最少要尝试14次。

  4. 排序只有1，2，3三个元素的数组，不能统计1，2，3的个数。
    方法一：假设，我们有三个指针：p1、p2、p3.p1从左侧开始，指向第一个非1的数字；p3从右侧开始，指向第一个非3的数字。p2从p1开始遍历，如果是2，p2继续遍历，直到p2遇到1或者3。
    方法二：先替换成质数1=2,2=3,3=5.然后把他们相乘，比如211332=322553,乘积是900，然后除以2,3,5；能整除多少次就有多少个235。

  5. 给定一个数组，里面只包含0.1两个数字，请找到一个最长的子序列，使得其中的0,1个数是相同的。
    比如：010101->答案就是本身，1101000->答案是110100
    利用动态规划思想，可以把0换成-1,那么题目就转化成求和为0的子序列了。
    如果子序列是从数组头开始，那么直接记录就可以得到结果；
    如果不是从数组头开始，比如对1101100来说
    那么DP[0]=DP[2]=DP[6]，所以，最大长度就是6-0=6。
    为了求解，我们可以使用一个map来保存k=和，value=位置vector，然后求解最大差值

  1. void find(int arr[], int len){
  2.     map<int,vector<int> > ans;
  3.     int j=0;
  4.     int sum=0;
  5.     for(;j<len;j++){
  6.         if(arr[j]==0){
  7.             sum+=-1;
  8.             ans[sum].pusb_back(j);
  9.         }
  10.         else{
  11.             sum += 1;
  12.             ans[sum].push_back(j);
  13.         }
  14.     }
  15.     int begin=0,end=0;
  16.     int step=0;
  17.     for(map<int,vector<int> >::iterator it=ans.begin();it!=ans.end();it++){
  18.         if((it->second)[(it->second).size()-1]-(it->second)[0]>step){
  19.             step = (it->second)[(it->second).size()-1]-(it->second)[0];
  20.             begin = (it->second)[0];
  21.             end = (it->second)[(it->second).size()-1];
  22.         }
  23.     }
  24.     cout<<begin<<endl<<end<<endl<<step<<endl;
  25.     //值得注意的是，begin是开始的前一个，end是结束的那个
  26. }
  1. 给定一个只包含整数的数组，给出一个方法来求解数组拼接起来的最大值。
    例如：[4,94,9,14,1]最大值是9944141
    法一：我们可以先直接排序，然后9，94…，然后对每个位排序，比如，9和94,就是99和94的比较，4和45就是44和45的比较，每次比较一个段的一位。
    法二：其实我们需要比较的是994和949哪个更大，所以我们直接比较ab和ba的大小就可以了，其他部分和快速排序一样
  1. //我们需要注意，快排的时候，当a>=b的时候i向前，j不移动。
  2. //验证的时候用一个数字、数字结尾、等边界条件
  3. int compare(int a,int b){
  4.     int b1 = b;
  5.     int a1 = a;
  6.     while( (b1=b1/10)>0) a1 *= 10;
  7.     a1 = a1*10+b;
  8.     int b2 = b;
  9.     int a2 = a;
  10.     while((a2=a2/10)>0) b2 *= 10;
  11.     b2 = b2*10+a;
  12.     cout<<a1<<"\t"<<b2<<endl;//>>>>>>
  13.     if(a1>=b2) return 1;
  14.     return 0;
  15. }
  16. void swap(int &a, int &b){
  17.     int temp = a;
  18.     a = b;
  19.     b = temp;
  20. }
  21. void sort(int arr[], int begin, int end){
  22.     if(begin>end) return;
  23.     cout<<begin<<"\t"<<end<<"\t"<<arr[0]<<endl;//>>>>>>>>
  24.     int j=begin,i=begin;
  25.     while(i<=end){
  26.         if(compare(arr[begin],arr[i])){
  27.         //if(arr[i]<=arr[begin]){
  28.             i++;
  29.         }
  30.         else{
  31.             j++;
  32.             swap(arr[j],arr[i]);
  33.             i++;
  34.         }
  35.     }
  36.         swap(arr[begin],arr[j]);
  37.     sort(arr,begin,j-1);
  38.     sort(arr,j+1,end);
  39. }

  1. 一批日志中，在线性时间内找到查询次数多余n/3的查询。
    通用的办法是hashmap，排序，快速选择
    我们做过多余一半的查询——每次删除两个不一样的，剩下的就是结果。
    这个办法可以推广到一般情况，比如查询次数超过n/m，每次删除m个不同的查询。实现办法可以参考俄罗斯方块的实现。我们申请m大小的map，开始遍历日志，如果
    a.遇到一个不在map中的查询，则插入map，设置为1（相当于落下一个新方块）
    b.遇到一个map中的查询，则加1
    c.当map大小为m时候，所有值都减一，然后去掉值为0的部分
    直到遍历完成，对map中剩下的每个查询进行检测（因为不一定每个都是结果）。map 的查询时间是logM，可以当成常数

  2. 给定一个数组，我们可以找到两个不相交的、并且是连续的子数组A和B，A中的数字和为sum(A), B中的元素和为sum(B)。找到这样的A和B，满足sum(A) - sum(B)的绝对值是最大的。 例如：[2, -1 -2, 1, -4, 2, 8]划分为A=[-1, -2, 1, -4], B=[2, 8]， 最大的值为16
    我们前面做过从数组中找到最大的字数组，那么这个问题我们可以这样来做：首先确定一个位置i，使得[0—i],[1+1,n]两个数组的字数组的最大值与最小值的差的绝对值最大，问题就解决了。
    总结整个方法的流程如下：
    1.从左向右遍历数组，计算max_left和min_left数组，O(n)时间复杂度
    2.从右向左遍历数组，计算max_right和min_right数组，O(n)时间复杂度
    3.然后对于每一个i，i从1开始到n-1,计算max_left[i - 1] - min_right[i], max_right[i] - min_left[i - 1]。选取绝对值最大的。

  3. 52张牌，四张A，随机打乱后问，从左到右1张一张翻直到出现第一张A，请问平均要翻几张牌？
    摸到第一张A之前的都是其他的牌，那么，之前会有多少种可能呢？ 之前可能会有0张，1张。。。。48张。考虑4张A在牌中的位置，他们把其他牌分成了5份（四个点把直线分成五段）。每一份的个数从0-48不等，完全随机的情况下，每份的平均长度为48/5=9.6，摸完这9.6张后，接下来的就是第一张A，故平均需要摸9.6+1=10.6张，即11张

  4. n根长度不一的棍子，判断是否有三根棍子可以构成三角形，并且找到周长最长的三角形。
    方法，直接对棍子排序，然后从大到校开始查找连续的三个数是否能组成三角形（最长棍子的长度 < 另外两根棍子的长度和），第一个成功的就是最佳答案

  5. 从1到n，n个数字，每个数字只出现一次。现在，随机拿走一个数字，请给出方法，找到这个数字。如果随机拿走两个数字呢？如果随机拿走k个数字呢？
    如果是一个数字，那么就直接把1-n加起来减去当前数字
    如果是两个数字把1-n加起来减去当前数字，这是等式1；把平方加起来相减是等式2；解方程组
    如果是k个数字，那么就是k阶方程组

  6. 有这样一个数组A，大小为n，相邻元素差的绝对值都是1.如： A={4,5,6,5,6,7,8,9,10,9}。 现在，给定A和目标整数t，请找到t在A中的位置。除了依次遍历，还有更好的方法么？
    比如说t=8
    那么第一次k=4,8-4=4,于是第二次跳到[4]=6,8-6=2,跳到[4+2]=8，成功

  7. 求解最长会文串
    法一：常规解法，两层循环得到一个字串，第三层判断是否是回文
    法二：从1——n-2，分别作为回文的中心，分两次判断回文长度为奇数和偶数的情况

  1. char *palSubstr(char *str){
  2.     int len = strlen(str);
  3.     int  i,left,right;
  4.     int low=0,high=0;
  5.     int maxLen = 0;
  6.     for(i=1;i<len-1;i++){
  7.         left = I-1;
  8.         right = i+1;
  9.         while(left>=0&&right<len&&str[left--]==str[right++]);
  10.         if(right-left-1>maxLen){
  11.             low = left+1;
  12.             high = right -1;
  13.             maxLen = right-left-1;
  14.         }
  15.         left = I;
  16.         rith = I+1;
  17.         while(left>=0&&right<len&&str[left--]==str[right++]);
  18.         if(right-left-1>maxLen){
  19.             low = left+1;
  20.             high = right -1;
  21.             maxLen = right-left-1;
  22.         }
  23.     }
  24.     return str[low to high];
  25. }
  26. ```c
  27. 23. 删除字符串中的“b”和“ac”，需要满足如下的条件:只能遍历一次，不能使用额外空间，而且aaccac删除完了就是ac
  28. 基本思路：abacbcdc
  29. 找到第一个b，把前面的a直接覆盖b，从a开始，遇到ac，把a向前移动到c，从a开始遇到b…然后以此类推。
  30. 方法二：用状态鸡
  31. 有两种状态one, two。two表示前面一个字符是a，其他情况用one表示
  32. 如果我们的当前状态是one，则拷贝；如果当前状态满足如下情况，则不拷贝
  33. 1）当前是b，因为要删除b
  34. 2）当前是a，我们要考虑下一个状态
  35. 3）当前是two，如果当前不是c则先拷贝前面一个a，如果当前不是b、a则拷贝字符
  38. <div class="md-section-divider"></div>
  40. ```c
  41. void stringFilter(char *str){
  42.     int state = one;
  43.     for(int i=0;str[i]!='\0';i++){
  44.         if(state==one&&str[i]!='a'&&str[i]!='b')
  45.             str[j++] = str[i];
  46.         if(state==two&&str[i]!='c'){
  47.             str[j++]  = 'a';
  48.             if(str[i]!='a'&&str[i]!='b')
  49.                 str[j++] = str[i];
  50.         }
  51.     }
  52.     if(state==two)
  53.         str[j++] = 'a';
  54.     return;
  55. }
  1. 从一个长字符串中查找包含给定字符集合的最短子串。例如，长串为“aaaaaaaaaacbebbbbbdddddddcccccc”，字符集为{abcd}，那么最短子串是“acbebbbbbd”。
    首先扫描一遍把所有的字符集装进map中，然后第二次扫描的时候两个指针start和end，先end跑，跑到出现所有字符停下，然后begin跑，跑到直到不满足条件；接着又end跑，如此反复也
  1. int find(char *arr[]){
  2.     map<char,int> ans;
  3.     int j;
  4.     int minlen = len;
  5.     int nowlen;
  6.     len = strlen(arr);
  7.     for(j=0;j<len;j++){
  8.         ans[arr[j]]=0;
  9.     }
  10.     int begin = 0, end = 0;
  11.     while(begin<end&&end<len){
  12.         if(!judeg(ans)){
  13.             ans[arr[end]++;
  14.             end++;
  15.         }
  16.         else{
  17.             nowlen = end-begin;
  18.             if(nowlen<minlen)
  19.                 minlen = nowlen;
  20.             ans[arr[begin]]--;
  21.             begin++;
  22.         }
  23.     }
  24.     return minlen;
  25. }

  1. 给定两个字符串A和B，判断A中是否包含由B中字符重新排列成的新字符串。例如：A=abcdef, B=ba，结果应该返回true。因为ba的排列ab，是A的子串。
    首先把B排序得到D，然后对A有m-n+1个长度为n的子串，对每个长度为n 的字串单独排序比较，就可以得到结果

  2. 给定k个数组，每个数组有k个整数。每个数组中选取一个整数，一共k个整数，取其和，一共可以得到k^k个和。给出方法，求得这k^k个和中，最小的k个。
    使用分置的思想，首先求出两个数组的前k大和， 在和滴三个数组求，以此类推
    但是要求出两个数组的和的前K大也不简单。
    比如说a[k]b[k]
    方法一：排序求前面k个，复杂度k*k+k*klog(k*k)
    方法二：开辟一个新的数组index[k],初始化为0,用来记录每个ai加上bj的bj的下标，每次扫描一遍选出最小的和并且把index[i]++，if(indexi[i]>=k) index[i]=-1;如此直到有k个和或者index数组全都是-1.这样每次都要计算k个和，复杂度是k*k
    方法三：？

  3. 给定两个数组X和Y，元素都是正数。请找出满足如下条件的数对的数目：x^y>y^x,x来自X，y来自Y
    分析：对两边取对数，ylogx>xlogy,再同时除以xy.(logx)/x>(logy)/y，就有了单调性

  4. 给定字符串，以及一个字典，判断字符串是否能够拆分为字段中的单词。例如，字段为{hello，world}，字符串为hellohelloworld，则可以拆分为hello,hello,world，都是字典中的单词。
    最简单办法就是直接递归查找

  1. bool find(string str){
  2.     int size = str.size();
  3.     if (size==0) return true;
  4.     for(int I =1;i<=size;i++){
  5.         if(dictionary.contains( str.substr(0,i)) && find(str.substr(i,size-i)))
  6.             return true;
  7.     }
  8.     return false;
  9. }

但是这样做空间时间太大，有很多需要重复计算的地方，于是就有了动态规划。动态规划是解决递归重复计算的好办法

  1. bool find(string str){
  2.     int size = str.length();
  3.     if(size==0) return ture;
  4.     bool wb[size+1];
  5.     meset(wb,0,sizeof(wb));
  6.     for(int i=1;i<=size;i++){
  7.         if(wb[i]==false && dictionary.contains( str.substr(0,i)))
  8.             wb[i] = true;
  9.         if(wb[i]==true){
  10.             if(i==size) return true;
  11.             for(int j=i+1;j<=size;j++){
  12.                 if(wb[j]==false && dictionary.contains(str.substr(i,j-i))) 
  13.                     wb[j] = true;
  14.                 if(j==size&&wb[j]==true)
  15.                     return true;
  16.             }
  17.         }
  18.     }
  19.     return true;
  20. }
  1. 26 个小写字母组成的字符串str，在str 中查找最长不含相同字符的连续子串,如：abcacfrar，为acfr
    最直接的办法就是遍历每个子串，复杂度N^2
    上面方法有很多的重复计算，比如abca中早就知道了bca是不重复的，于是我们想个办法来记录这些情况。
  1. String longestSubstr(string str){
  2.     int start = 0;
  3.     int end = str.length();
  4.     int pos[] = new int[26];
  5.     int I ;
  6.     fot(i=0;i<26;i++)
  7.         pos[i] = -1;
  8.     int maxLen = -1;
  9.     for(i=0;i<str.length;i++){
  10.         if(pos[str.charAt(i)-'a']<0)
  11.             pos[str.charAt(i)-'a'] = I;
  12.         else{
  13.             int length = I-pos[str.charAt(i)-'a'];
  14.             if(length>maxLen){
  15.                 start = pos[str.charAt(i)-'a'];
  16.                 end = I;
  17.                 maxLen = length;
  18.             }
  19.             pos[str.charAt(i)-'a'] = I;
  20.         }
  21.     }
  22.     return str.substr[start,end];
  23. }
  1. 对于一个n位正整数a,去掉其中任意k(k<=n)个数字后，剩下的数字按原次序排列可以组成一个新的正整数。设计一个删除算法，使得剩下的数字组成的正整数最小。例如，a=13243221，k=5，输出：121
    遇到这个题目，我们可以首先把问题简单化，考虑k=1的情况，在上面的例子中，直观上应该删去3，得到1243221，继续考虑k=1的情况，应该继续删去4，得到123221。我们之前删去的3和4共同具有的特点：都是第一个递减序列的首个数字。再考虑如果数字串中没有递减序列，如a=123，k=1的情况，应该删掉最后一个字符3，得到最小正整数12。因此，这个题目我们只需要不断的删除首个递减序列的首个数字，如果没有递减序列则删去最后一个字符。
  1. String deleteNum(string input, int k){
  2.     int k_orig = k;
  3.     int len = input.size();
  4.     while(k){
  5.         int i=0;
  6.         for(;i<len-1;i++)
  7.             if(input[i]>input[i+1])
  8.                 break;
  9.         for(;i<len-1;i++)
  10.             input[i] = input[i+1];
  11.         k--;
  12.         len--;
  13.     }
  14.     return input.substr(0,input.size()-k_orig);
  15. }
  1. n的字典序全排列
    设p是1～n的一个全排列p=p1p2p……pn
    1）从排列的右端开始，找出第一个比右端数字小的数字的位置j，j=max{i|pi 2)在pj的右边的数字中， 找出所有比pj大的数字中最小的数字pk，k=max{i|pi>pj}
    3）对换pj，pk
    4）将pj+1,pj+2……pk……pn反转得到新的排列p`=p1p2……pjpn……pk……pj+1
    这就是p的下一个全排列
  1. void FindNext(char *str){
  2.     int len=strlen(str),i;
  3.     char temp = str[len-1];
  4.     for(i=len-1;i>=0;i++)
  5.         if(str[i]<str[len-1]){
  6.             swap(str[i],str[len-1]);
  7.             break;
  8.         }
  9.     if(i<0)return;
  10.     for(int j=len-1,i=i+1;i<j;i++,j--)
  11.         swap(str[i],str[j]);
  12. }
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注