递归、常见

  1. 求斐波那契数列的第n项。 第一种,用递归。因为存在重复计算,效率很低。 第二种,非递归,考虑从小往大来算。

    one=0
    two=1
    N=0
    for(i=2;i<n;i++){
        N=one+two
    	two=N
    	one=two
    }
    
  2. 快排。 第一种,双指针法。

    #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;
    }
    
  3. 二分法查找 递归实现

    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;
    		}
    	}
    }
    

数组、字符串、位运算

  1. 在一个二维数组中,每一行都按照从左到右从上到下递增排序。请完成一个函数,输入一个整数,判断数组中是否存在该整数。 从右上角开始查找,小于右上角的删除该列,大于右上角的删除该行。

  2. 请实现一个函数,把字符串中每个空格都替换成%20. 需要先增加空间,然后从尾部开始移动。两个指针,一个指向原文尾,一个指向最末尾。

  3. 旋转数组的最小数字,比如{3,4,5,1,2}就是{1,2,3,4,5}的一个旋转,求其最小值为1. 分析得知,其也是一定程序的有序,若把其分成两块,指针p1始终指向前面的块,p2始终指向后面的块。 首先p1 p2位于首尾位置,先算index/2的位置的值,如果其大于第一个值,则属于前面的块,把p1指过来,如果其小于第一个值,则属于后面的块,把p2指过来。 依次直到两个指针位置相差为1,p2的值就是最小的。

  4. 实现一个函数,输入一个整数,输出该数二进制表示中1的个数。 *位运算中中,左移右边补零,右移左边如果是0补零,是1补1(0为无符号数值,1为有符号) *如果一个整数与1做与运算结果为1,则该整数最右一位为1,否则为0. 常规思路用该数与1与运算,如果是有符号数,会导致左边一直补1,造成死循环。 所以改成该数不变,把1依次左移,再与该数与运算,再统计。

  5. 输入数组n,依次打印出n位最大的十进制数。如输入3,打印出1~999. 这个考虑大数问题,所以不能先算出10^3再遍历。 换个思路,这其实是一个三位数的全排列,只不过前面的0不打印出来。 *c语言中,数字n+‘0’的意思,‘0’代表ascii中的48,‘1’为49,所以1+‘0’的意思是把1变成'1’。同理n-‘0’是把’n’变成n。 第一步:第一位可能出现的可能性,后面的为另一块。 第二部:后面这一块的第一位出现的可能性,后面的为另一块。

  6. 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)
        	} 
        }
    }
    
  7. 调整数组顺序使得奇数位于偶数前面。 有点类似快排里的双指针交换,两个指针依次靠近,前面的碰到偶数就停下等着后面的碰到奇数,然后交换。

  8. 顺时针打印矩阵。

  9. 字符串的所有排列。输入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
        }
    }
    
  10. 数组中出现次数超过一半的数字。 如果排序的话,超过一半一定在中位数。 或者换个思路,遍历的时候保存当前的数和出现的次数,如果下一个还是这个数则+1,否则-1.遍历后最后留下的便是。

  11. 查找最小的k个数。 思路1,弄一个k大小的堆,先填满k个数,然后遍历如果发现比堆最大的值小,则替换。这种方法为O(nlogk),但是这种方法支持大数。 思路2,想象下快排的思路,找到第k个数字,比它小的在左边,比他大的在右边,这样遍历一次就够了。

  12. 从1到n整数中1出现的次数。

  13. 把数组排列成最小的数。

  14. 判断丑数。丑数指只包含因子2、3、5的数,求从小到大第1500个丑数。

  15. 在字符串中找出第一次只出现一次的字符。 使用hashtable。

  16. 数组中的逆序对。数组中的两个数字,如果前面一个大于后面的,则组成一个逆序对。求所有的逆序对。 利用归并的思想,先给数组无限拆分成大小为1的子数组。 两两比较,找出所有逆序对,归并,排序(避免重复计算) 对长度为2的子数组再次两两比较,首先指针都位于末端,如果第一个大于第二个指针的值,构成逆序对,而且第一个和第二组里所有的值都构成逆序对,第一个指针左移。 如果不大于,第二个指针左移,再次比较。 上面每次比较完都要把比对完的数字放入新的辅助数组里,并保持有序。

  17. 数字在排序数组中出现的次数。 思路是首先得找到这个数字,用二分法速度快。 找到后却不知道这是第几个,可能前面后面都有。 所以思路要分成两块,第一块,找到第一个出现的位置。第二块找到最后一个出现的位置。 对于第一种情况,用二分查找改造一下,当找到为k时,判断其前一个如果不是k,则满足条件返回,否则把end改成k-1,再重新二分。 第二种情况类似处理。

  18. 数组中只出现一次的数字。

  19. 查找有序数组中和为s的两个数字。 两个指针,依次相向。

  20. 翻转句子,单词不变。 翻转两次,摇手法。

栈和队列

  1. 用两个栈实现队列。实现appendTail和deleteHead方法。

    插入方法:始终插入到栈1. 删除方法:如果栈2有值则弹出,直到为空后,把栈1都出栈并写到栈2,并弹出队列头。

  2. 用两个队列实现一个栈。 维持一个队列为空。

    插入方法:如果两个队列都是空,随便插入到一个队列中。否则插入到有值的队列中。 删除方法:把有值的队列挨个都删掉,但是前n-1个进入另一个队列,这时该队列相当于弹出栈顶了。

  3. 实现一个得到栈的最小值的函数。 使用辅助栈,push的时候,同时push到辅助栈,如果该值大于辅助栈栈顶的值,则再次push栈顶的值一次,如果该值小于辅助栈栈顶的值,则push该值进入辅助栈。 pop的时候,同时也把辅助栈pop了。 min直接取辅助栈栈顶即可。

  4. 栈的压入弹出序列。?

  5. 约瑟夫问题。

链表

  1. 输入一个链表表头,从尾到头打印每个节点的值。 使用栈。

  2. 在O(1)时间删除链表节点。给定一个表头节点head,给定一个节点指针 按照链表,只能从表头依次遍历到该节点再删除。 但是我们知道该节点就知道其下一个节点,所以可以先把下一个节点的值复制到该节点,再把其next指针指向下一个节点的next的地址。

  3. 输入一个链表,输出该链表中倒数第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
    }
    
  4. 反转链表。输入表头,输出新链表的表头。 遍历链表,得考虑链表断裂的问题。

  5. 合并两个排序的链表。两个递增排序的链表进行合并。 这个就是递归的方法,两个指针分别指向两个链表,比较大小。可使用递归。

  6. 复杂链表的复制。

  7. 两个链表的第一个公共节点。 分析链表,它肯定是Y型的,那么考虑反向遍历。 问题是单链表不能反向遍历,所以利用栈,当弹出的两个值不同了,则其上一个则为公共结点。 上面的解法需要用到栈,如果不用栈,考虑下一种: 先分别算出两个链表的长度,长的链表先走出差值的步数。 然后再同步走,就能找到公共节点。

  1. 前序、中序、后序遍历数。 分别是根左右,左根右,左右根的次序打印。
  2. 重建二叉树,给出前序遍历和中序遍历,重建出二叉树。
  3. 层序打印。 需要使用队列,把节点指针放入队列,然后打印根节点并放入左右节点到队列。
  4. 树的子结构 先比较根是否一样,如果一样,分别对比左右节点是否一样。如果为否,分别递归左右子节点。
  5. 树的镜像 和先序遍历类似,先把左右子节点对调,然后分别对左右节点递归。
  6. 输入一棵二叉树和一个整数,打印节点值为该整数的所有路径。 这个需要使用前序遍历,然后利用栈来保存其遍历的路径。满足条件则打印出来栈。
  7. 将搜索二叉树转换成排序的双向链表。 中序遍历搜索二叉树,得到排序。利用这个性质来。
  8. 求二叉树的深度。 考虑递归的方法。把二叉树分为左右两边,比较左右两边的最大深度就行,其深度为左/右最大深度+1. 所以递归到子节点算起。
  9. 寻找二叉搜索树中两个节点的最近公共祖先节点。 前序遍历该树,当前节点值位于两节点之间,即为其公共祖先。

动态规划问题

  1. 连续子数组的最大和。如{1,-2,3,10,-4,7,2,-5},求其中一个或多个连续整数组的最大和。 一个思路就是从左开始连续求和,如果算出为负数了,那就抛弃掉,把下一个值当做第一个,重新开始计算。 假设f(i)为前i个的和,分两种情况,第一种情况是f(i-1)<=0,第二种是f(i-1)>0,第一种情况要抛弃掉前面的部分。