递归、常见
-
求斐波那契数列的第n项。 第一种，用递归。因为存在重复计算，效率很低。 第二种，非递归，考虑从小往大来算。
one=0 two=1 N=0 for(i=2;i<n;i++){ N=one+two two=N one=two } -
快排。 第一种，双指针法。
#include <stdio.h> void qsort(int *ary, int min, int max) { int p1 = min; int p2 = max; int key=(min+max)>>1; while(p1<p2) { while(ary[p2]>ary[key]) { p2--; } while(ary[p1]<ary[key]) { p1++; } if(p1<=p2) { int tmp=ary[p1]; ary[p1]=ary[p2]; ary[p2]=tmp; p1++; p2--; } } if(min<p2) qsort(ary, min, p2); if(p1<max) qsort(ary, p1, max); } int main() { int a[] = {4,6,1,6,9,3,2}; qsort(a, 0, 6); for(int i=0;i<=6;i++) printf("%d ",a[i]); return 0; } -
二分法查找 递归实现
int binserch(int *a, int s, int min, int max) { if (a == NULL) return -1; int mid=(min+max)>>1; if (a[mid] == s) return mid; if (a[mid] > s) { return binserch(a, s, min, mid-1); } else { return binserch(a, s, mid+1, max); } }非递归实现
int binserch(int *a, int s, int len) { if (a == NULL) return -1; int mid=(len-1)>>1; while(mid>0||mid<len-1) {//这儿的条件也可以是设另两个变量low high表示范围 if (a[mid] == s) return mid; if (a[mid] > s) { mid = (mid-1)>>1; } else { mid = (mid+len)>>1; } } }
数组、字符串、位运算
-
在一个二维数组中，每一行都按照从左到右从上到下递增排序。请完成一个函数，输入一个整数，判断数组中是否存在该整数。 从右上角开始查找，小于右上角的删除该列，大于右上角的删除该行。
-
请实现一个函数，把字符串中每个空格都替换成%20. 需要先增加空间，然后从尾部开始移动。两个指针，一个指向原文尾，一个指向最末尾。
-
旋转数组的最小数字，比如{3,4,5,1,2}就是{1,2,3,4,5}的一个旋转，求其最小值为1. 分析得知，其也是一定程序的有序，若把其分成两块，指针p1始终指向前面的块，p2始终指向后面的块。 首先p1 p2位于首尾位置，先算index/2的位置的值，如果其大于第一个值，则属于前面的块，把p1指过来，如果其小于第一个值，则属于后面的块，把p2指过来。 依次直到两个指针位置相差为1，p2的值就是最小的。
-
实现一个函数，输入一个整数，输出该数二进制表示中1的个数。 *位运算中中，左移右边补零，右移左边如果是0补零，是1补1（0为无符号数值，1为有符号） *如果一个整数与1做与运算结果为1，则该整数最右一位为1，否则为0. 常规思路用该数与1与运算，如果是有符号数，会导致左边一直补1，造成死循环。 所以改成该数不变，把1依次左移，再与该数与运算，再统计。
-
输入数组n，依次打印出n位最大的十进制数。如输入3，打印出1~999. 这个考虑大数问题，所以不能先算出10^3再遍历。 换个思路，这其实是一个三位数的全排列，只不过前面的0不打印出来。 *c语言中，数字n+‘0’的意思，‘0’代表ascii中的48，‘1’为49，所以1+‘0’的意思是把1变成'1’。同理n-‘0’是把’n’变成n。 第一步：第一位可能出现的可能性，后面的为另一块。 第二部：后面这一块的第一位出现的可能性，后面的为另一块。
-
char num = new char[n+1] num[n+1]='\0' func(num, n, 0) func(num, n, begin) { if(begin == n) { print num return } for(i=begin;i<n;i++) { for(k=0;k<10;k++) { num[begin]=k+'0' func(num, n, begin+1) } } } -
调整数组顺序使得奇数位于偶数前面。 有点类似快排里的双指针交换，两个指针依次靠近，前面的碰到偶数就停下等着后面的碰到奇数，然后交换。
-
顺时针打印矩阵。
-
字符串的所有排列。输入abc，得到其所有排列。 这儿有一个递归思路，分两步。 第一步，可能出现在第一个位置的所有的可能，即第一个值和后面的值依次替换。 第二步，后面的值再分成第一个位置后后面的部分，第一个位置依次和后面的值替换。
//考虑到递归，那么传入的除了该str，应该还有该次递归的时候指针在第几个字符串的位置。 permut(str, begin) { if(begin == len(str)) { print str } for(i=begin;i<len(str);i++) { //交换第begin个和第i个字符串 tmp=str[begin] str[begin]=str[i] str[i]=tmp //也除开第一个，对后面的继续递归 permut(str, begin+1) //要复原到最开始的字符串，以便下次只交换一个字符 tmp=str[begin] str[begin]=str[i] str[i]=tmp } } -
数组中出现次数超过一半的数字。 如果排序的话，超过一半一定在中位数。 或者换个思路，遍历的时候保存当前的数和出现的次数，如果下一个还是这个数则+1，否则-1.遍历后最后留下的便是。
-
查找最小的k个数。 思路1，弄一个k大小的堆，先填满k个数，然后遍历如果发现比堆最大的值小，则替换。这种方法为O(nlogk)，但是这种方法支持大数。 思路2，想象下快排的思路，找到第k个数字，比它小的在左边，比他大的在右边，这样遍历一次就够了。
-
从1到n整数中1出现的次数。
-
把数组排列成最小的数。
-
判断丑数。丑数指只包含因子2、3、5的数，求从小到大第1500个丑数。
-
在字符串中找出第一次只出现一次的字符。 使用hashtable。
-
数组中的逆序对。数组中的两个数字，如果前面一个大于后面的，则组成一个逆序对。求所有的逆序对。 利用归并的思想，先给数组无限拆分成大小为1的子数组。 两两比较，找出所有逆序对，归并，排序（避免重复计算） 对长度为2的子数组再次两两比较，首先指针都位于末端，如果第一个大于第二个指针的值，构成逆序对，而且第一个和第二组里所有的值都构成逆序对，第一个指针左移。 如果不大于，第二个指针左移，再次比较。 上面每次比较完都要把比对完的数字放入新的辅助数组里，并保持有序。
-
数字在排序数组中出现的次数。 思路是首先得找到这个数字，用二分法速度快。 找到后却不知道这是第几个，可能前面后面都有。 所以思路要分成两块，第一块，找到第一个出现的位置。第二块找到最后一个出现的位置。 对于第一种情况，用二分查找改造一下，当找到为k时，判断其前一个如果不是k，则满足条件返回，否则把end改成k-1，再重新二分。 第二种情况类似处理。
-
数组中只出现一次的数字。
-
查找有序数组中和为s的两个数字。 两个指针，依次相向。
-
翻转句子，单词不变。 翻转两次，摇手法。
栈和队列
-
用两个栈实现队列。实现appendTail和deleteHead方法。
插入方法：始终插入到栈1. 删除方法：如果栈2有值则弹出，直到为空后，把栈1都出栈并写到栈2，并弹出队列头。
-
用两个队列实现一个栈。 维持一个队列为空。
插入方法：如果两个队列都是空，随便插入到一个队列中。否则插入到有值的队列中。 删除方法：把有值的队列挨个都删掉，但是前n-1个进入另一个队列，这时该队列相当于弹出栈顶了。
-
实现一个得到栈的最小值的函数。 使用辅助栈，push的时候，同时push到辅助栈，如果该值大于辅助栈栈顶的值，则再次push栈顶的值一次，如果该值小于辅助栈栈顶的值，则push该值进入辅助栈。 pop的时候，同时也把辅助栈pop了。 min直接取辅助栈栈顶即可。
-
栈的压入弹出序列。？
-
约瑟夫问题。
链表
-
输入一个链表表头，从尾到头打印每个节点的值。 使用栈。
-
在O(1)时间删除链表节点。给定一个表头节点head，给定一个节点指针 按照链表，只能从表头依次遍历到该节点再删除。 但是我们知道该节点就知道其下一个节点，所以可以先把下一个节点的值复制到该节点，再把其next指针指向下一个节点的next的地址。
-
输入一个链表，输出该链表中倒数第k个节点。 两个指针，相差为k，当前面的指针指到表尾，后面一个指针正好指到倒数第k个节点。
p1=head for(i=0;i<k;i++) { //先判断边界 p1 = p1->next } p2=head while(p1->next != null) { p2 = p2->next p1 = p1->next } -
反转链表。输入表头，输出新链表的表头。 遍历链表，得考虑链表断裂的问题。
-
合并两个排序的链表。两个递增排序的链表进行合并。 这个就是递归的方法，两个指针分别指向两个链表，比较大小。可使用递归。
-
复杂链表的复制。
-
两个链表的第一个公共节点。 分析链表，它肯定是Y型的，那么考虑反向遍历。 问题是单链表不能反向遍历，所以利用栈，当弹出的两个值不同了，则其上一个则为公共结点。 上面的解法需要用到栈，如果不用栈，考虑下一种： 先分别算出两个链表的长度，长的链表先走出差值的步数。 然后再同步走，就能找到公共节点。
树
- 前序、中序、后序遍历数。 分别是根左右，左根右，左右根的次序打印。
- 重建二叉树，给出前序遍历和中序遍历，重建出二叉树。
- 层序打印。 需要使用队列，把节点指针放入队列，然后打印根节点并放入左右节点到队列。
- 树的子结构 先比较根是否一样，如果一样，分别对比左右节点是否一样。如果为否，分别递归左右子节点。
- 树的镜像 和先序遍历类似，先把左右子节点对调，然后分别对左右节点递归。
- 输入一棵二叉树和一个整数，打印节点值为该整数的所有路径。 这个需要使用前序遍历，然后利用栈来保存其遍历的路径。满足条件则打印出来栈。
- 将搜索二叉树转换成排序的双向链表。 中序遍历搜索二叉树，得到排序。利用这个性质来。
- 求二叉树的深度。 考虑递归的方法。把二叉树分为左右两边，比较左右两边的最大深度就行，其深度为左/右最大深度+1. 所以递归到子节点算起。
- 寻找二叉搜索树中两个节点的最近公共祖先节点。 前序遍历该树，当前节点值位于两节点之间，即为其公共祖先。
动态规划问题
- 连续子数组的最大和。如{1,-2,3,10,-4,7,2,-5}，求其中一个或多个连续整数组的最大和。 一个思路就是从左开始连续求和，如果算出为负数了，那就抛弃掉，把下一个值当做第一个，重新开始计算。 假设f(i)为前i个的和，分两种情况，第一种情况是f(i-1)<=0，第二种是f(i-1)>0，第一种情况要抛弃掉前面的部分。