快排
要点：非递归函数要仔细
public class QuickSort { public static int arr[] = {4,3,2,1,5,6,7,9,8,0,4}; public static void main(String[] args){ sort(); } public static int partition(int low,int high){ int key = arr[low]; while(low < high){ while(low = key) {high --;} arr[low] = arr[high]; while(low <= key) {low ++;} arr[high] = arr[low]; } arr[low] = key; return low; } public static void sort(){ if (arr == null || arr.length==0) return; Stack stack = new Stack (); int start = 0; int end = arr.length-1; int mid; stack.push(start); stack.push(end); while(!stack.isEmpty()){ end = stack.pop(); start = stack.pop(); mid = partition(start,end); if(start < mid-1){ stack.push(start); stack.push(mid-1); } if(end >mid+1){ stack.push(mid+1); stack.push(end); } } }} 青蛙跳台阶
1. 如果一次能够跳1或2个台阶，要跳n阶的台阶有多少种跳法
2. 如果一次能调n阶，跳n阶的有多少种跳法。
public static int recursion(int n){ if(n==0) return 0; else if(n==1) return 1; else if(n==2) return 2; else return recursion(n-1) + recursion(n-2) ;}public static int nonRecursion(int n){ if(n==0) return 0; int a = 0; int b = 1; int sum = 0; for(int i=1;i<=n;i++){ sum = a + b; a = b; b = sum; } return sum;} 第二个问题用数学归纳法：f(n) = 2f(n-1)
查找两个字符串中相同的数字
找出数组中两数相加等于指定数的所有组合
求最长回文串长度
返回单向链表倒数第n个节点
String to int
要点：1、判断是否过长。 2、是否是负数 3、数如何表示
/** * Created by TanZhen on 2015/7/17. * Java面试：将string转化为int * 本实现的缺点是没有考虑大数 */public class Str_to_Int { public static void main(String[] args){ try { System.out.println(str2int("-1234567890")); } catch (Exception e) { e.printStackTrace(); } } public static int str2int(String val) throws Exception { if(val.startsWith("-") && val.length()>11){ throw new Exception("errrrr"); } if(!val.startsWith("-") && val.length()>10){ throw new Exception("errrrr"); } int result = 0; if(val.startsWith("-")){ for(int i=1;i
堆排序插
入排序
归并排序
二分查找
翻转字符串
str_B中的所有字母是否都在 str_A中
查找单项链表的中间节点
判断单向链表是否是回文/字符串
单项链表的逆序实现
合并两个有序链表
全排列
组合
二叉树的广度优先遍历
二叉树的前序遍历
二叉树的后续遍历
二叉树的镜像
最长公共子序列
字符串的模式匹配（KMP）
将String字符串转换成数字
将汉字转化成数字（×）
链表奇偶位置调换
* 思想：每当一趟匹配过程中出现字符比较不等，不需要回溯i指针，
* 而是利用已经得到的“部分匹配”的结果将模式向右“滑动”尽可能远
* 的一段距离后，继续进行比较。