1.输入两个正整数，求其最大公约数。
2.最大间隔：给定一个递增序列，a1 <a2 <...<an 。定义这个序列的最大间隔为d=max{ai+1 - ai }(1≤i<n),现在要从a2 ,a3 ..an-1 中删除一个元素。问剩余序列的最大间隔最小是多少？注意：不加while True 和try except会错误 把break换成pass也错误。
3.二维数组中的查找
4.替换空格
5.从尾到头打印链表
6.打印出倒数第K个链表节点
7.合并2个排序的链表
8.树的子结构
9
9.TWO SUM
一：hash表法：map保存每一个不同数字最后出现的位置坐标，从下标0开始找，即使有重复数字，由于map中存的是最后一次出现的位置，那样即使有两个相同的值构成的数对也可以被找到。
问题：给定一个n个元素的集合S，找出S中满足条件的整数对A,B，使得A+B=K
假定集合S已经排好序的话，则上面这个问题可以在O（n）的时间内解决。使用2个索引值first和last，分别指向第一个元素和最后一个元素，设指向的第一个元素为A，则我们的任务就是找到对应于A的元素B，B=K-A。如果last指向的元素小于B，则first加1，指向后面的一个元素；如果last指向的元素大于B，则last减1。这样最终一步步逼近结果，时间复杂度为O（n）
二双指针法：
10平衡二叉树及树的深度
11.跳台阶，一次跳1个或者2个
12.变态跳台阶。一次可以跳1个，2个，。。。n个。先大致分析下，假设跳上第n个台阶有f(n)种方法，则f(1)=1,f(2)=2,f(3)=4,f(4)=8,可以得到f(n)=f(n-1)+f(n-2)+....+f(1)+1,而f(n-1)=f(n-2)+....+f(1)+1,两个式子相减，得到f(n) = 2f(n-1),很明显可以得到f(n)=2^(n-1)。
13.对于一个整数X，定义操作rev(X)为将X按数位翻转过来，并且去除掉前导0。例如:
如果 X = 123，则rev(X) = 321;
如果 X = 100，则rev(X) = 1.
现在给出整数x和y,要求rev(rev(x) + rev(y))为多少？也可以作为单独数字翻转321->123
14:将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。如果是合法的数值表达则返回该数字，否则返回0
15，定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
16.二维数组的查找
17：求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
解题思路：
1.需利用逻辑与的短路特性实现递归终止。 2.当n==0时，(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断，为false，然后直接返回0；
3.当n>0时，执行sum+=Sum_Solution(n-1)，实现递归计算Sum_Solution(n)。
18：用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
19：字符串排序：输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
20：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。
O(N)保存两个值：1.数组中的数字2.次数；遍历到下个数字时，若和之前保存的数一样，加一，否则减一；若次数为0，则保存下一个数，并将次数置1.所保存的数字即为所求。
21合并2个有序链表：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。
递归方法：
非递归方法：
22..二进制中1的个数
网友评论