剑指offer-中等篇

剪绳子

题目描述：给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],…,k[m]。请问k[0] x k[1] x … x k[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。

思路：

• 5<2x3，6<3x3，比6更大的数字我们就更不用考虑了，肯定要继续分。
• 其次看2和3的数量，2的数量肯定小于3个，为什么呢？因为2x2x2 < 3x3，那么题目就简单了。
• 直接用n除以3，根据得到的余数判断是一个2还是两个2还是没有2就行了。

public int cutRope(int target) {
  if(target == 2) return 1;
  if(target == 3) return 2;

  int x = target % 3;
  int y = target / 3;

  if(x == 0){
    return (int)Math.pow(3,y);
  }else if(x == 1){//7%3=2···1   2*2*3
    return 2*2*(int)Math.pow(3,y-1);
  }else{//8%3=2···2    3*3*2
    return 2*(int)Math.pow(3,y);
  }
}

把二叉树打印成多行

题目描述：从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

思路：用队列实现二叉树的层次遍历(标准写法)

ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
  if(pRoot == null) return new ArrayList();
  ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
  Queue<TreeNode> queue = new LinkedList<>();
  queue.add(pRoot);
  while(!queue.isEmpty()){
    ArrayList<Integer> list = new ArrayList<Integer>();
    int count = queue.size();
    for(int i = 0; i<count; i++){
      TreeNode node = queue.poll();
      list.add(node.val);
      if(node.left != null) queue.add(node.left);
      if(node.right != null) queue.add(node.right);
    }
    res.add(list);
  }  
  return res;
}

二叉树的下一个结点

题目描述：给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：判断当前节点的右子节点是否为空

public TreeLinkNode GetNext(TreeLinkNode pNode){
  if(pNode.right != null){//当前节点右子节点不为空
    TreeLinkNode node = pNode.right;
    while(node.left != null){//找到右子节点的最底层左子节点
      node = node.left;
    }
    return node;
  }else{//当前节点右子节点为空
    while(pNode.next != null){
      TreeLinkNode parent = pNode.next;//指向当前节点的父节点
      if(parent.left == pNode){//判断当前节点是否为父节点的左子节点
        return parent;
      }
      pNode = pNode.next;
    } 
  }
  return null;
}

链表中环的入口结点

题目描述：给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

思路：

public ListNode EntryNodeOfLoop(ListNode pHead){
  if(pHead == null || pHead.next == null) return null;
  ListNode fast = pHead;
  ListNode slow = pHead;
  do{
    fast = fast.next.next;
    slow = slow.next;
  }while(slow != fast);

  fast = pHead;
  while(fast != slow){
    fast = fast.next;
    slow = slow.next;
  }
  return fast;
}

字符流中第一个不重复的字符

题目描述：请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

如果当前字符流没有存在出现一次的字符，返回 # 字符。

思路：用数组统计字符出现的次数，并将字符按顺序加入队列，如果队列中字符出现的次数大于1，则出队；如果最后队列不为空，则出队的字符就是第一个出现的字符。

public class Solution {
  //Insert one char from stringstream
  int[] counts = new int[256];
  private Queue<Character> queue = new LinkedList<>();

  public void Insert(char ch){
    counts[ch]++;
    queue.add(ch);
    while(!queue.isEmpty() && counts[queue.peek()] > 1){
      queue.poll();
    }
  }

  //return the first appearence once char in current stringstream
  public char FirstAppearingOnce(){
    return queue.isEmpty() ? '#' : queue.peek();
  }
}

表示数值的字符串

题目描述：请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串”+100”,”5e2”,”-123”,”3.1416”和”-1E-16”都表示数值。 但是”12e”,”1a3.14”,”1.2.3”,”+-5”和”12e+4.3”都不是。

思路：用法JDK方法：Double.parseDouble()

public boolean isNumeric(char[] str) {
  //String string = String.valueOf(str);
  //return string.matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
  try{
    double res = Double.parseDouble(new String(str));  
  }
  catch(NumberFormatException e){
    return false;
  }
  return true;
}

数组中重复的数字

题目描述：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。

思路：

public boolean duplicate(int numbers[],int length,int [] duplication){
  if(numbers == null || numbers.length == 1) return false;
 	for(int i = 0;i<numbers.length; i++){
    while(numbers[i] != i){
      if(numbers[i] == numbers[numbers[i]]){
        duplication[0] = numbers[i];
        return true;
      }
      swap(numbers, i, numbers[i]);
    }
  }
  return false;
}

public static void swap(int numbers[],int i,int j){
  int temp = numbers[i];
  numbers[i] = numbers[j];
  numbers[j] = temp;
}

求1+2+3+…+n

题目描述：求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路：利用逻辑与得短路特性做为递归的终止条件。

public int Sum_Solution(int n) {
  int sum = n;
  boolean flag = n > 0 && (sum += Sum_Solution(n-1)) > 0;
  return sum;
}

孩子们的游戏(圆圈中最后剩下的数)

题目描述：让小朋友们围成一个大圈。然后，随机指定一个数 m，让编号为 0 的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续 0…m-1 报数 …. 这样下去 …. 直到剩下最后一个小朋友，可以不用表演。

思路：约瑟夫环，用链表来模拟游戏过程；

public int LastRemaining_Solution(int n, int m) {
  if(n == 0) return -1;
	LinkedList<Integer> list = new LinkedList<>();
  for(int i = 0; i<n; i++){
    list.add(i);
  }
  
  int beginIndex = 0;
  while(list.size() > 1){
    beginIndex = (beginIndex + m-1)%list.size();//循环
    list.remove(beginIndex);
  }
  return list.get(0);
}

扑克牌顺子

题目描述：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

思路：先统计大小王的个数，当成赖子，通过对抽到的牌进行排序，判断是否能 组成顺子。

public boolean isContinuous(int [] numbers) {
  if(numbers.length == 0) return false;
  int count = 0;
  Arrays.sort(numbers);
  //统计大小王个数
	while(numbers[count] == 0){
    count++;
  }

  //判断是否能组成顺子
	for(int i = count; i<numbers.length-1; i++){
    //如果重复的牌，则一定不能组成顺子
    if(numbers[i+1] == numbers[i]){
      return false;
    }
    count = count - (numbers[i+1]-numbers[i]-1); 
  }
  
  return count >= 0;
}

左旋转字符串

题目描述：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！

思路：1.先分别反转字符串；2.再整体反转；

public String LeftRotateString(String str,int n) {
	if(str == null || str.length() <= n) return str;
  char[] chars = str.toCharArray();
  swapString(chars, 0, n-1);
  swapString(chars, n, chars.length-1);
  swapString(chars, 0, chars.length-1);
  return new String(chars);
}

//反转从 i 到 j 的字符串
public void swapString(char[] str,int i,int j){
	while(i < j){
    char temp = str[i];
    str[i] = str[j];
    str[j] = temp;
    i++;
    j--;
  }
}

和为S的两个数字

题目描述：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。对应每个测试案例，输出两个数，小的先输出。

思路：利用双指针，从头和尾分别进行遍历判断（和相同时，两数差距越大，乘积越小）

public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
  ArrayList<Integer> res = new ArrayList<Integer>();
	int i = 0;
  int j = array.length-1;
  while(i < j){
    if(array[i] + array[j] == sum){
      res.add(array[i]);
      res.add(array[j]);
      return res;
    }else if(array[i] + array[j] < sum){
      i++;
    }else{
      j--;
    }
  }
  return res;
}

和为S的连续正数序列

题目描述：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

思路：

public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
  ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer> >();
	int L = 1;
  int R = 2;
  int curSum = 0;
  while(L < R){
    curSum = (L + R)*(R - L + 1)/2;
    if(curSum == sum){
      ArrayList<Integer> list = new ArrayList<Integer>();
      for(int i = L; i<=R; i++){
        list.add(i);
      }
      res.add(list);
      L++;
    }else if(curSum < sum){
      R++;
    }else{
      L++;
    }
  }
  return res;
}

数组中只出现一次的数字

题目描述：一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

思路：把所有的数异或，得到的结果即两个不同的数异或的结果，这个结果的二进制中的1，表现的是这两个不同的数的不同位。就按照这个结果中为1的位的位置划分，该位为1划分为一组，为0划分为一组。这样两个不同的数就被划分开了，再分别对这两组做异或操作，就找到了两个不同的数。

public void FindNumsAppearOnce(int [] array,int num1[] , int num2[]) {
	int binaryRes = 0;
  for(int i = 0; i<array.length; i++){
    binaryRes = binaryRes ^ array[i];
  }
  
  int index = getIndex1(binaryRes);
  for(int num : array){
    if(is1Index(num, index)){
      num1[0] = num1[0] ^ num;
    }else{
      num2[0] = num2[0] ^ num;
    }
  }
}

/**
* 返回 binaryRes 中第一位为1的位置
*/
private int getIndex1(int binaryRes){
  int index = 0;
  while(((binaryRes & 1) == 0) && index < 32){
    binaryRes = binaryRes>> 1;
    index++;
  }
  return index;	
}

/**
* 判断 num 的 index 位置是否为1
*/
private boolean is1Index(int num, int index){
  //index 位为1，则返回true
  return ((num >> index) & 1) == 1;
}

平衡二叉树

题目描述：输入一棵二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

思路:递归得到二叉树的高度，判断左子树与右子树的高度差，如果高度差超过1，则返回false

public class Solution {
  private boolean isBalanced = true;
  public boolean IsBalanced_Solution(TreeNode root) {
    depth(root);
    return isBalanced;
  }

  private int depth(TreeNode root){
    if(root == null) return 0;
    int leftDepth = depth(root.left);
    int rightDepth = depth(root.right);
    if(Math.abs(leftDepth - rightDepth) > 1){
      isBalanced = false;
    }
		return Math.max(leftDepth,rightDepth)+1;
  }
}

数字在排序数组中出现的次数

题目描述：统计一个数字在排序数组中出现的次数。

思路：有序数组，可以利用二分法

public int GetNumberOfK(int [] array , int k) {
  //int res = 0;
  //for(int num : array){
  //  if(num == k) res++;
  // }
  // return res;
  if(array.length == 0) return 0;
  int left = binarySearch(array, k);
  int right = binarySearch(array,  k+1);
  if(array[array.length-1] == k){
    return right-left+1;
  }else{
    return right-left;
  }
}

//返回数组中target中最左边的位置索引
public int binarySearch(int[] nums, int target) {
  int i = 0;
  int j = nums.length - 1;
  int mid = 0;
  while(i < j){
    mid = i + (j-i)/2;
    if(nums[mid] < target){
      i = mid + 1;
    }else{
      j = mid;
    }
  }
  return i;
}

两个链表的第一个公共结点

题目描述：输入两个链表，找出它们的第一个公共结点。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

思路：路程相等思想：当访问链表 A 的指针访问到链表尾部时，令它从链表 B 的头部重新开始访问链表 B；同样地，当访问链表 B 的指针访问到链表尾部时，令它从链表 A 的头部重新开始访问链表 A。这样就能控制访问 A 和 B 两个链表的指针能同时访问到交点。

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
  ListNode a = pHead1;
  ListNode b = pHead2;
  
  while(a != b){
    a = a == null ? pHead2 : a.next;
    b = b == null ? pHead1 : b.next;
  }
  
  return a;
}

整数中1出现的次数（从1到n整数中1出现的次数）

题目描述：求出113的整数中1出现的次数,并算出1001300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

思路：

个位

我们知道在个位数上，1会每隔10出现一次，例如1、11、21等等，我们发现以10为一个阶梯的话，每一个完整的阶梯里面都有一个1，例如数字22，按照10为间隔来分三个阶梯，在完整阶梯0-9，10-19之中都有一个1，但是19之后有一个不完整的阶梯，我们需要去判断这个阶梯中会不会出现1，易推断知，如果最后这个露出来的部分小于1，则不可能出现1（这个归纳换做其它数字也成立）。

我们可以归纳个位上1出现的个数为：

n/10 * 1+(n%10!=0 ? 1 : 0)

十位

现在说十位数，十位数上出现1的情况应该是10-19，依然沿用分析个位数时候的阶梯理论，我们知道10-19这组数，每隔100出现一次，这次我们的阶梯是100，例如数字317，分析有阶梯0-99，100-199，200-299三段完整阶梯，每一段阶梯里面都会出现10次1（从10-19），最后分析露出来的那段不完整的阶梯。我们考虑如果露出来的数大于19，那么直接算10个1就行了，因为10-19肯定会出现；如果小于10，那么肯定不会出现十位数的1；如果在10-19之间的，我们计算结果应该是k - 10 + 1。例如我们分析300-317，17个数字，1出现的个数应该是17-10+1=8个。

那么现在可以归纳：十位上1出现的个数为：

• 设k = n % 100，即为不完整阶梯段的数字
• 归纳式为：(n / 100) * 10 + (if(k > 19) 10 else if(k < 10) 0 else k - 10 + 1)

百位

现在说百位1，我们知道在百位，100-199都会出现百位1，一共出现100次，阶梯间隔为1000，100-199这组数，每隔1000就会出现一次。这次假设我们的数为2139。跟上述思想一致，先算阶梯数 * 完整阶梯中1在百位出现的个数，即n/1000 * 100得到前两个阶梯中1的个数，那么再算漏出来的部分139，沿用上述思想，不完整阶梯数k199，得到100个百位1，100<=k<=199则得到k - 100 + 1个百位1。

那么继续归纳百位上出现1的个数：

• 设k = n % 1000
• 归纳式为：(n / 1000) * 100 + (if(k >199) 100 else if(k < 100) 0 else k - 100 + 1)

后面的依次类推….

完美！归纳式看起来已经很规整了。 来一个更抽象的归纳，设i为计算1所在的位数，i=1表示计算个位数的1的个数，10表示计算十位数的1的个数等等。

• k = n % (i * 10)
• count(i) = (n / (i * 10)) * i + (if(k > i * 2 - 1) i else if(k < i) 0 else k - i + 1)

好了，这样从10到10的n次方的归纳就完成了。

public int NumberOf1Between1AndN_Solution(int n) {
  if(n <= 0) return 0;
  int count = 0;
  for(int i = 1; i <= n; i *= 10){
    int div = i * 10;
    int k = n % div;
    if(k > 2*i-1){
      count = count + n/div*i + i;
    }else if(k < i){
      count = count + n/div*i + 0;
    }else{
      count = count + n/div*i + (k-i+1);
    }
  }
  return count;
}

连续子数组的最大和

题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)

思路：

public int FindGreatestSumOfSubArray(int[] array) {
  int dp = array[0];
  int res = array[0];
  for(int i = 1; i<array.length; i++){
    dp = Math.max(dp + array[i], array[i]);
    res = Math.max(res, dp); 
  }
  return res;
}

数组中出现次数超过一半的数字

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

思路：
法1：对数组进行排序，中间的数一定是出现次数超过数组长度一般的数，否则返回0；
法2：用HashMap统计每个数字出现的次数；

//方法一，时间复杂度nlogn
public int MoreThanHalfNum_Solution(int [] array) {
  Arrays.sort(array);

  int mid = array[array.length/2];

  int count = 0;
  for(int i = 0;i<array.length;i++){
    if(array[i] == mid){
      count++;
    }
  }

  return count>(array.length/2) ? mid : 0;
}

//方法二，时间复杂度n
public int MoreThanHalfNum_Solution(int [] array) {
  HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
  for(int i = 0; i<array.length; i++){
    if(!map.containsKey(array[i])){
      map.put(array[i],1);
    }else{
      int count = map.get(array[i]);
      map.put(array[i],++count);
    }
  }

  for(int key : map.keySet()){
    int count = map.get(key);
    if(count > array.length/2){
      return key;
    }
  }
  return 0;
}

二叉搜索树与双向链表

题目描述：输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

思路：中序遍历结果就是排序结果；中序递归；

private TreeNode pre = null;
private TreeNode head = null;
public TreeNode Convert(TreeNode root) {
  inOrder(root);
  return head;
}

private void inOrder(TreeNode node) {
  if (node == null) return;
  inOrder(node.left);

  node.left = pre;
  if (pre != null) pre.right = node;
  pre = node;
  if (head == null) head = node;

  inOrder(node.right);
}

栈的压入、弹出序列

题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

思路：用栈来模拟题目描述的过程；

public boolean IsPopOrder(int [] pushA,int [] popA) {
  if(pushA.length == 0 || popA.length == 0) return false;
  Stack<Integer> stack = new Stack<>();
  
  int index = 0;
  for(int i = 0; i < pushA.length; i++ ){
    stack.push(pushA[i]);
    while(!stack.isEmpty() && stack.peek() == popA[index]){
      stack.pop();
      index++;
    }
  }
  return stack.isEmpty();
}

合并两个排序的链表

题目描述：输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

思路：

public ListNode Merge(ListNode list1,ListNode list2) {
  ListNode newHead = new ListNode(-1);
  ListNode temp = newHead;
  
  while(list1 != null && list2 != null){
    if(list1.val < list2.val){
      temp.next = list1;
      temp = temp.next;
      list1 = list1.next;
    }else{
      temp.next = list2;
      temp = temp.next;
      list2 = list2.next;
    }
  }
  //如果 后续还有节点，直接接在新链表的末尾即可
  if(list1 != null) temp.next = list1;
  if(list2 != null) temp.next = list2;
  
  return newHead.next;
}

反转链表

题目描述：输入一个链表，反转链表后，输出新链表的表头。

思路：头插法：

public ListNode ReverseList(ListNode head) {
  //头插法
  ListNode newHead = new ListNode(-1);
  
  while(head != null){
    ListNode next = head.next;
    head.next = newHead.next;
    newHead.next = head;
    head = next;
  }
  return newHead.next;
}

数值的整数次方

题目描述：给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0。

思路：
法1：暴力法；
法2：递归法，时间复杂度logN；

public double Power(double base, int exponent) {
  double res = 1;
  if(exponent>0){
    for(double i = 0;i<exponent;i++){
      res = res*base;
    }
  }else{
    for(double i = exponent;i<0;i++){
      res = res*base;
    }
    res = 1/res;
  }
  return res;
}

public double Power(double base, int exponent) {
  
}

二进制中1的个数

题目描述：输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路：n&(n-1)：相当于把n二进制最后的1变为0

n       : 10110100
n-1     : 10110011
n&(n-1) : 10110000

public int NumberOf1(int n) {
  int res = 0;
  while(n != 0){
    res++;
    n = n&(n-1);
  }
  return res;
}

矩形覆盖

题目描述：我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？

比如n=3时，2*3的矩形块有3种覆盖方法：

思路：斐波那契数列

public int RectCover(int target) {
  int pre = 0;
  int cur = 1;
  int res = 0;
  for(int i = 1; i<=target; i++){
    res = pre + cur;
    pre = cur;
    cur = res;
  }
  return res;
}

跳台阶

题目描述：一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

思路：斐波那契数列：跳 n 阶台阶，可以先跳 1 阶台阶，再跳 n-1 阶台阶；或者先跳 2 阶台阶，再跳 n-2 阶台阶，故有递推公式f(n) = f(n-1) + f(n-2)

public int JumpFloor(int target) {
  int pre = 0;
  int cur = 1;
  int res = 0;
  for(int i = 1; i<=target; i++){
    res = pre + cur;
    pre = cur;
    cur = res;
  }
  return res;
}

斐波那契数列

题目描述：大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。

思路：斐波那契数列：f(n) = f(n-1) + f(n-2)

public int Fibonacci(int n) {
  if(n <= 1) return n;
  int res = 0;
  int pre = 0;
  int cur = 1;
  for(int i = 2;i<=n;i++){
    res = pre + cur;
    pre = cur;
    cur = res;
  }
  return res;
}

旋转数组的最小数字

题目描述：把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。输入一个非递减排序的数组的一个旋转，输出旋转数组的最小元素。例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。

思路：采用二分法；若中间的元素大于 j 指针的元素，说明旋转点在 mid 和 j 之间；否则在 i 和 mid 之间；

特例：如果数组元素允许重复，会出现一个特殊的情况：nums[l] == nums[m] == nums[h]，此时无法确定解在哪个区间，需要切换到顺序查找。例如对于数组 {1,1,1,0,1}，l、m 和 h 指向的数都为 1，此时无法知道最小数字 0 在哪个区间。

public int minNumberInRotateArray(int [] array) {
  if(array.length == 0) return 0;
  int i = 0;
  int j = array.length - 1;
  while(i < j){
    int mid = i + (j - i)/2;
    if(array[mid] == array[i] && array[mid] == array[j]){
      for(int k = 0; k<array.length-1; k++){
        if(array[k] > array[k+1] ) {
          return array[k+1];
        }
      }
      return array[0];
    }
    
    if(array[mid] > array[j]){
      i = mid + 1;
    }else{
      j = mid;
    }
  }
  return array[i];
}

重建二叉树

题目描述：输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

思路：