数组中重复的数字

思路一：Hash 表，遍历数组，添加到 set 集合中，添加失败则返回。

思路二：因为范围在 0 到 n-1，根据数组下标，找到下标和元素值不相等的。

二维数组中的查找

剑指Offer - 图1

思路：从右上角开始寻找，如果目标值比当前值小，则往左走（因为当前列都比当前值大），如果目标值比当前值大，则往下走

替换空格

将空格变成%20

思路：

重建二叉树

二叉树的下一个节点

给定一颗二叉树的其中一个节点，请找出中序遍历的下一个节点

思路：一个节点，有右子树，返回的一定是右子树最左边的节点。没有右子树，返回的是父亲节点。

  1. public TreeNode inorderSuccess(TreeNode p){
  2.     //有右子树，返回的一定是右子树最左边的节点。
  3.     if(p.right !=null){
  4.         p = p.right;
  5.         while(p.left!=null) p= p.left;
  6.         return p;
  7.     }
  8.     //没有右子树，返回父亲节点
  9.     while(p.father!=null){
  10.         if(p==p.father.left)
  11.             return p.father;
  12.         p = p.father;
  13.     }
  14.     return null;
  15. }

旋转数组的最小数字

如：将【1,2,3,4,5】翻转为【3,4,5,1,2】，找到旋转后的数组的最小值。

思路：临界点，二分

矩阵中的路径

回溯算法，深度优先 dfs

机器人的运动范围

略，上个文件有

剪绳子

剑指Offer - 图2

思路：最值，dp

我们想要求长度为n的绳子剪掉后的最大乘积，可以从前面比n小的绳子转移而来。设dp[i] 为长度为 i 的最大乘积

从长度为 2 开始剪（因为剪 1 乘积没变化）剪了第一段后，剩下(i - j)长度可以剪也可以不剪。如果不剪的话长度乘积即为j * (i - j)；如果剪的话长度乘积即为j * dp[i - j]。取两者最大值max(j * (i - j), j * dp[i - j])

  1.     public int cuttingRope(int n) {
  2.         int[] dp = new int[n + 1];
  3.         dp[2] = 1;
  4.         for(int i = 3; i < n + 1; i++){
  5.             for(int j = 2; j < i; j++){
  6.                 dp[i] = Math.max(dp[i], Math.max(j * (i - j), j * dp[i - j]));
  7.             }
  8.         }
  9.         return dp[n];
  10.     }

思路 2：贪心，根据数学求最大值证明，(证明连接)(https://leetcode-cn.com/problems/jian-sheng-zi-lcof/solution/mian-shi-ti-14-i-jian-sheng-zi-tan-xin-si-xiang-by)尽可能分成长度为3的小段，乘积最大。

步骤如下：

如果 n == 2，返回 1，如果 n == 3，返回 2，两个可以合并成 n 小于 4 的时候返回 n - 1

如果 n == 4，返回 4

如果 n > 4，分成尽可能多的长度为 3 的小段，每次循环长度 n 减去 3，乘积 res 乘以 3；最后返回时乘以小于等于 4 的最后一小段

  1.     public int cuttingRope(int n) {
  2.         if(n < 4){
  3.             return n - 1;
  4.         }
  5.         int res = 1;
  6.         while(n > 4){
  7.             res *= 3;
  8.             n -= 3;
  9.         }
  10.         return res * n;
  11.     }