转载请注明原文地址：http://www.cnblogs.com/ygj0930/p/6424179.html
1：二维数组查数
输入一个行、列均是递增的二维数组，和一个数。求该数是否在二维数组中。
解法一：这种查找类题目，第一时间想到用map、list等。此处可以先对二维数组遍历，把 每个元素——i+“，”+j（行列坐标） 作为映射转存到Hashmap中，然后对所查的数用
map.get(num)即可。
解法二：由于行列都是递增的，我们就利用这个规律来解题。首先用num与右上角元素比：若相等，则返回true；若num大于这个元素，则说明num在这个元素的下方，而一行的最右元素是该行的最大值了，所以第一行排除掉了，数组行数减一，继续查找；若num小于右上角元素，则说明num在右上角元素的左边，而一列的第一个是该列的最大值，所以最右列排除，列数减一，继续查找......重复以上三步，每步要么减一行要么减一列缩小查找范围，直至找到或者遍历完整个数组。
boolean find(int[][] nums,int num){ boolean res=false; int rows=nums.length; int cols=nums[0].length; while(rows>=0 && clos>=0){ if(nums[rows-1][cols-1]==num){ res=true; break; }else if(nums[rows-1][cols-1]>num){ cols--; }else{ --rows; } } return res; }
2.替换字符串中空格（或其他东西）
此题，要求把字符串中的空格替换成别的东西，比如 %20 这样的字符。
法一：无空间限制，不在原字符串上操作的解法。
用Java来做的话，我们可以新开一个字符串数组，用split(str," ")把原字符串按空格拆分，保存到字符串数组中。然后遍历这个数组，用一个builder来append个个字符串，两两之间插入 %20 取代空格即可。这里要注意考虑特殊情况：原字符串开头、结尾有无空格。可以设置headnull,lastnull两个变量来先统计原字符串头尾的空格数。
法二：有空间限制，只能在原字符串上操作。
设计到内存方面的操作，此法用C++来做。首先遍历原字符串，统计空格数目count；然后计算出取代内容需要多少空间，得出替换后的总空间；p2指针指向替换后字符串末尾，p1指向替换前字符串末尾，p1每遍历一个字符，就移动到p2处，然后p1,p2前移动；若p1遍历到空格，则p2从后往前依次写入0,2,%（每写一个p2前一1位）......直到p1==p2==字符串首地址。
3：倒序输出链表值
链表一般都是顺序遍历比较容易，这里需要倒序输出链表值。如果真的把链表指针反转方向重新构造链表就真是太死脑筋了。我们只需顺序遍历链表，把每个结点的值先存放在数组或栈中。然后再按照倒序输出即可。这种 后进先出 的典型题目应该第一时间就想到栈。
4：由前序遍历，中序遍历重建二叉树
首先重温二叉树的遍历方式：
前序遍历：根左右
中序遍历：左根右
后序遍历：左右根
由上面规律可得，知道前序遍历，便可以知道根节点的值，由根节点的值可以划分中序遍历得到左右子树，而左右子树的前序遍历的第一位又是子树的根......依次往复，相互求取即可重建二叉树。所以，用递归。
public TreeNode rebuidTree(int[] pre,int[] in,int preStart,int preEnd,int inStart,int inEnd){ //由前序遍历第一个数值建立当前结点 TreeNode newNode=new TreeNode(pre[preStart]); //递归边界判断：如果前序遍历序列开始等于结束说明到了叶子层了，直接返回这个结点作为叶子 if(preStart==preEnd && inStart==inEnd){ return newNode; } //未到底层，则递归。 int currRoot = -1; //先求出当前的前序遍历序列的根结点在中序遍历序列中的位置 for(int i=inStart;i<=inEnd;++i){ if(in[i]==pre[preStart]){ currRoot=i; break; } } //从而划分中序遍历得当前结点的左右子树。并求出左右子树序列的长度 int leftLength=currRoot-inStart; int rightLength=inEnd-currRoot; //如果左子树序列不为0，则递归建立左子树 if(leftLength>0){ //序列仍然是一开始的序列，子树的序列是通过下标来控制的 newNode.left=rebuidTree(pre, in, preStart+1, preStart+leftLength, inStart, currRoot-1); } //右子树序列不为0，递归建立右子树 if(rightLength>0) { newNode.right=rebuidTree(pre, in, preStart+leftLength+1, preEnd, currRoot+1, inEnd); } //把当前结点返回上一层作为上一层的子节点 return newNode; }
后序遍历+中序遍历重建二叉树同样解法，只是每次由后序遍历的最后一个元素得当前根结点。
5：用两个栈实现一个队列，要求完成“先入先出”功能
由于栈是“后入先出”的，要实现先入先出就需要 后入先出再后入先出。我们来模拟一下两个栈的工作情景：
增加元素，则入栈s1；
删除第一个入的元素：则把s1中元素全部pop()出，依次存入s2。此时，s2中元素的顺序与原来在s1时相反，栈顶的元素是先入s1的元素。此时把s2栈顶元素pop()出，即模拟了队列的先入先出。而如果期间有增加的话，入s1栈，因为s2中是比s1的早入栈的，所以执行删除的话还是s2弹出。直到s2为空，才从s1依次弹出再压入s2。
6：旋转数组的最小值
把一个递增数组的前若干个元素挪到数组的末尾，得到旋转数组：1，2，3，4，5——3，4，5，1，2。给定一个选择数组，求数组中最小值。
法一：暴力搜索，用min记录当前最小值直至遍历结束得到数组最小值。
法二：用Java的Arrays.sort(int[])把数组排序，第一个元素就是。
法三：真正底层的解法——双指针（双下标夹迫法）。用index1指向数组第一个元素，index2指向最后一个，midindex=(index1+index2)/2。若nums[index1]<nums[midindex]，说明nums[midindex]位于前面的递增数组中，则最小值在minindex~index2之间，令index1=midindex，重复以上步骤；如果nums[index1]>nums[midindex]，说明nums[index]在后面的递增数组中，最小值位于index1~midindex之间，令index2=midindex，重复以上步骤；如果index1+1=index2了，说明index1与index2以及迫近到最小值以及其相邻值了，取两下标所指最小的就是最小值。
7：优化斐波那契数列解法
我们知道，传统的递归实现斐波那契数列容易出现的一个问题就是重复求值，当n越大重复的次数越多。
优化方法一：传统解法的问题是重复求值，那我们不让他重复求就行了——递归过程中求出的f(n)存入数组中，在每次递归时，先从数组中取f(n)，有则返回，无才递归求值，并且在得到返回值后把f(n)存如数组以供下一次递归到这个值时直接取用。
优化方法二：我们知道斐波那契数列是f(n)=f(n-1)+f(n-2)，而f(0)=0,f(1)=1。那么对于f(n)，我们完全可以从0,1开始逐步直到f(n-1)+f(n-2)从而得到f(n)。
public int betterFibonacci(int n){ int res=0; if(n==0){ res=0; return res; } if(n==1){ res=1; return res; } int n_2=0; int n_1=1; for(int i=2;i<=n;++i){ res=n_1+n_2;//当前项等于前两项之和 //更新位置,当前项作为下一N的前一项 n_2=n_1; n_1=res; } return res; }
8：统计二进制数中1的个数
传统解法：每次用最低位&1判断最低位是不是1，是则count++，然后右移。这种解法只能在整数是正整数时可用。如果是负整数，右移的时候左边补1，到后面会导致全部是1而导致死循环。
优化解法：传统解法引起死循环的原因是负数右移的时候左边补1。那我们不让他右移就好了——我们把 1 逐位左移与所求二进制数各位取&来求1的个数。
public int count_1(int n){ int count=0; int index_of_1=1; //32位机的就循环32次 for(int i=1;i<=32;i++){ if(index_of_1 & n){ count++; } index_of_1<<=1; } return count; }
最优解法：n&(n-1)等同于消去n的二进制数的最右边的1。
如果一个数的二进制的最低位是1，那么n-1就是把二进制数最低位取反为0，前面的不变；
如果最低位是0，那么n-1就是n的二进制数从次低位开始借1，直到借到1，被借的位1变0，然后从被借位之后的全部取反。
那么我们可以看到：n与n-1的二进制数的区别在于：从被借位（包括被借位）开始往后的全是相反的。那么n&(n-1)的话就是把n的二进制数的最后一个1（包括这个1）往后的位全部与自身的非做与运算，结果就是n的二进制数的最后一个1以及其后的位全部取0，而后面的位本就是0，那么真正的变化只是最低位的1变成了0而已。也就是说，执行一次n&(n-1)就相当于把n的最右边的1消去。所以统计n的二进制表示的1的个数，只需统计n&(n-1)这个操作做了几次即可。
public int best_count_1(int n){ int count=0; while(n!=0){ n=n&(n-1); ++count; } return count; }
9：求一个数的n次方
传统解法：按最原始的方法做n次乘法。
优化解法：类似于上面优化斐波那契数列的做法，把已经求过的方幂保存起来，在后面用到的时候直接取方幂即可，不用再重复做乘法运算。
递归解法：如果是偶次方n，我们可以看到：num^n=num^(n/2)*num(n/2)，也就是说可以直接递归求 num^(n/(2^x))，x=1,2... 即可。如果n是奇数，也相当于num*num^(n-1)而已，同样可以用递归来求。
double pow(double num,int n){ if(n==0){ return 1; } if(n==1){ return num; } //用n>>1作为递归的指数。相当于n/2，但右移比除法快. double half_pow=pow(num, n>>1); double res=half_pow*half_pow; //此时对n次方作奇偶判断：如果为奇数，还需要再乘以一次num才是结果 //这里用位运算来判断：直接看最后一位是不是1即可直到奇偶。这比n%2==1快4倍 if((n & 1)==1){ res*=num; } return res; }
10：打印1到n位最大数
传统解法：n位最大数就是10^n-1。比如3位最大数就是10^3-1=999。for循环1~(10^n-1)打印即可。问题在于：n很大时，int或者long都存放不了这么大的数，会溢出。
优化解法：题目要求的是打印出数而不是求出这些数，我们可以用字符串来模拟出每一个数。我们知道，n位十进制数其实就是n长的0~9序列的全排列而已。我们用代码模拟出各位0~9出现的情况即可。至于前导0在输出时不打印即可。
public void Print_1_to_MaxOfN(int n){ if(n<=0){ return; } //定义一个n位的char数组来模拟n位数的全排列 char[] numbers=new char[n]; //最高位的的可能情况：0~9 for(int i=0;i<10;++i){ numbers[0]=(char) (i+'0'); //最高位已定，告知下一位当前位curr_index已确定，递归地模拟下一位的可能情况 Print_Ditgit_Recursively(numbers,n,0); } } public void Print_Ditgit_Recursively(char[] numbers,int length,int curr_index){ if(curr_index==length-1){//index从0开始,所以length-1就是最末位了 //当前位就是最后一位了，则可以对numbers进行输出了 PrintNumbers(numbers); return; } //若还不是最后一位，则对下一位进行确定，并递归下去 for(int i=0;i<10;++i){ numbers[curr_index+1]=(char) (i+'0'); Print_Ditgit_Recursively(numbers, length, curr_index+1); } } public void PrintNumbers(char[] numbers){ boolean isStart=false; for(char ch:numbers){ //前导零不打印，直到遇到非0的即开始 if(!isStart && ch!='0'){ isStart=true; } if(isStart){ System.out.print(ch); System.out.print(" "); } } }
这里注意： numbers[curr_index+1]=(char) (i+'0');这种要对数组的下一个坐标赋值的情况，不能贪方便用 nums[++curr_index]，这样的话for循环的条件要修改成i<length-2才行。如果是i<length-1，则最好一个是++curr_index就越界了。切记切记