1.完全平方数（279 - 中）
题目描述：给定正整数 n，找到若干个完全平方数（比如 1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
示例 :
输入：n = 12 输出：3 解释：12 = 4 + 4 + 4
思路：本题要求使用最少的数量，可以建立一个数组，元素的最大平方数不超过n，我们只需倒序进行搜索即可，使用深度优先遍历。
- 终止条件：n = 0，即n全部用完，更新最小值，注意当i<0，直接返回。
- 递归函数传入参数：（数组， 当前剩余值， 当前进行到的索引值，当前使用的完全平方数的个数）
注意：这里有两个优化
- 使用乘法加速获取当前元素的下一步的起始最大次数，如示例，12/4 = 3，在4这个完全平方数，下一次最大的次数为3。
- 倒序遍历过程中，对于完全平方数大于当前最小值ans的情况，进行剪枝。
代码实现：
private int ans = Integer.MAX_VALUE; public int numSquares(int n) { int num = (int)Math.sqrt(n); int[] nums = new int[num]; for (int i = 0; i < num; i++) { nums[i] = (i + 1) * (i + 1); } dfs(nums, n, nums.length - 1, 0); return ans == Integer.MAX_VALUE ? -1 : ans; } private void dfs(int[] nums, int n, int i, int count) { if (n == 0) { ans = Math.min(ans, count); return; } if (i < 0) return; int start = n / nums[i]; for (int k = start; k >= 0 && k + count < ans; --k) { dfs(nums, n - k * nums[i], i - 1, k + count); } }
2.平方数之和（633 - 中）
题目描述：给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a^2 + b^2 = c 。
示例 :
输入：c = 5 输出：true 解释：1 * 1 + 2 * 2 = 5
思路：本题主要由两种解法，一种是类似两数之和的哈希解法，构建平方数数组；另一个则是像最大矩形面积的双指针解法，利用双指针寻找可能范围内的元素（最优解）。
注意：注意其中一个数可能是0，所以平方数组和循环条件要考虑边界。
代码实现：
// hash public boolean judgeSquareSum(int c) { int n = (int)Math.sqrt(c); int[] nums = new int[n + 1]; Set<Integer> set = new HashSet<>(); for (int i = 0; i <= n; ++i) { nums[i] = i * i; set.add(nums[i]); } for (int num : nums) { if (set.contains(c - num)) { return true; } } return false; } // 双指针 public boolean judgeSquareSum(int c) { int l = 0, r = (int)Math.sqrt(c); while (l <= r) { if (l * l + r * r == c) { return true; } else if (l * l + r * r > c) { r--; } else { l++; } } return false; }
3.鸡蛋掉落（887 - 难）
题目描述：给你 k 枚相同的鸡蛋，并可以使用一栋从第 1 层到第 n 层共有 n 层楼的建筑。
已知存在楼层 f ，满足 0 <= f <= n ，任何从 高于 f 的楼层落下的鸡蛋都会碎，从 f 楼层或比它低的楼层落下的鸡蛋都不会破。
每次操作，你可以取一枚没有碎的鸡蛋并把它从任一楼层 x 扔下（满足 1 <= x <= n）。如果鸡蛋碎了，你就不能再次使用它。如果某枚鸡蛋扔下后没有摔碎，则可以在之后的操作中 重复使用 这枚鸡蛋。
请你计算并返回要确定 f 确切的值 的 最小操作次数 是多少？
示例 :
输入：k = 1, n = 2 输出：2 解释： 鸡蛋从 1 楼掉落。如果它碎了，肯定能得出 f = 0 。 否则，鸡蛋从 2 楼掉落。如果它碎了，肯定能得出 f = 1 。 如果它没碎，那么肯定能得出 f = 2 。 因此，在最坏的情况下我们需要移动 2 次以确定 f 是多少。
思路：这是一个经典动态规划问题，可以看一下李永乐老师的双蛋问题，比较通俗易懂。
dp[i][j]：使用i个鸡蛋，有j层楼梯（注意：这里j不表示高度，代表区间）的情况下，的最少实验的次数（约束条件）。- 第一个鸡蛋扔到第x层楼，两种状态：碎
dp[i - 1][x- 1]或者没碎dp[i][j - x]，最终枚举所有扔鸡蛋的情况，即枚举x。 - 对于上边找x的过程，我们可以通过二分查找进行优化。
dp[i - 1][x- 1]是一个随x（层数）的增加而单调递增的函数，相反，dp[i][j - x]随着层数x单调递减，我们的目标找这两函数的交点，类似于数组中找山峰/峡谷（最大/最小值），那么显然就是二分提升效率了。 - 第一个鸡蛋在哪里扔（也算一次操作），这也是状态转移方程中为什么+1.
代码实现：
public int superEggDrop(int k, int n) { // k 鸡蛋数 n 为楼层数 int[][] dp = new int[k + 1][n + 1]; for (int i = 1; i <= k; ++i) { dp[i][1] = 1; } for (int i = 1; i <= n; ++i) { dp[1][i] = i; } for(int i = 2; i <= k; ++i){ for(int j = 2; j <= n; ++j){ // 未使用二分的解法 x为所选楼层 // int min = Integer.MAX_VALUE; // for(int x = 1; x <= j; ++x){ // min = Math.min(min, Math.max(dp[i - 1][x - 1], dp[i][j - x])); // } // dp[i][j] = 1 + min; // 改用二分查找(第一次扔的层数，替换枚举) int l = 1, r = j; while(l + 1 < r){ int mid = l + r >> 1; if(dp[i-1][mid-1] > dp[i][j-mid]){ r = mid; } else { l = mid; } } int leftVal = Math.max(dp[i - 1][l - 1], dp[i][j - l]); int rightVal = Math.max(dp[i - 1][r - 1], dp[i][j - r]); dp[i][j] = 1 + Math.min(leftVal, rightVal); } } // for(int[] d:dp){ // System.out.println(Arrays.toString(d)); // } return dp[k][n]; }
4.打印从1到最大的n位数（补充）
题目描述：输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 :
输入: n = 1 输出: [1,2,3,4,5,6,7,8,9]
代码实现：
public int[] printNumbers(int n) { int x = (int)Math.pow(10, n); int[] nums = new int[x - 1]; for (int i = 0; i < x - 1; ++i) { nums[i] = i + 1; } return nums; }
5.自除数（728 - 易）
题目描述：自除数 是指可以被它包含的每一位数除尽的数。还有，自除数不允许包含 0 。128 是一个自除数，因为 128 % 1 == 0，128 % 2 == 0，128 % 8 == 0。
给定上边界和下边界数字，输出一个列表，列表的元素是边界（含边界）内所有的自除数。
示例 :
输入： 上边界left = 1, 下边界right = 22 输出： [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 15, 22]
代码实现：
public List<Integer> selfDividingNumbers(int left, int right) { List<Integer> ans = new ArrayList<>(); for (int i = left; i <= right; ++i) { if (selfDividingNumbers(i)) { ans.add(i); } } return ans; } // 是否为自除数 public boolean selfDividingNumbers(int num) { int i = num; while (i > 0) { int x = i % 10; if (x == 0 || num % x != 0) { return false; } i /= 10; } return true; }
6.各位相加（258 - 易）
题目描述：给定一个非负整数 num，反复将各个位上的数字相加，直到结果为一位数。
进阶: 你可以不使用循环或者递归，且在 O(1) 时间复杂度内解决这个问题吗？
示例 :
输入: 38 输出: 2 解释: 各位相加的过程为：3 + 8 = 11, 1 + 1 = 2。 由于 2 是一位数，所以返回 2。
思路：本题迭代比较简单，引入一个辅助变量tmp即可。
对于进阶问题，参考@wangliang大佬：
涉及数学上一个名词，数根。数根可以计算模运算的同余，对于非常大的数字的情况下可以节省很多时间。
数字根可作为一种检验计算正确性的方法。例如，两数字的和的数根等于两数字分别的数根的和。
另外，数根也可以用来判断数字的整除性，如果数根能被3或9整除，则原来的数也能被3或9整除。
上边的应用转化一下：
- 能够被9整除的整数，各位上的数字加起来也必然能被9整除，所以，连续累加起来，最终必然就是9。
- 不能被9整除的整数，各位上的数字加起来，结果对9取模，和初始数对9取摸，是一样的，所以，连续累加起来，最终必然就是初始数对9取摸。
看下边一个规律：
原数: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 数根: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3
结合上边的规律，对于给定的 n 有三种情况。
- n 是 0 ，数根就是 0。
- n 不是 9 的倍数，数根就是 n 对 9 取余，即 n % 9。
- n 是 9 的倍数，数根就是 9。
原数是 n，树根就可以表示成 (n-1) % 9 + 1，可以结合下边的过程理解。
原数: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 偏移: 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 取余: 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8 0 1 2 数根: 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3 4 5 6 7 8 9 1 2 3
为什么要先偏移，再加1呢？假设如果可以被 9 整除，直接取模得到是0，按照数根的应用应该是9才对，我们可以进行偏移之后，再进行取余+1.
代码实现：
public int addDigits(int num) { if (num < 9) return num; int tmp = num; while (tmp > 9) { num = tmp; tmp = 0; while (num > 0) { tmp += num % 10; num /= 10; } } return tmp; } // 是否为自除数 public int addDigits(int num) { return (num - 1) % 9 + 1; }
7.范围求和II（598 - 易）
题目描述：给定一个初始元素全部为 0，大小为 m*n 的矩阵 M 以及在 M 上的一系列更新操作。
操作用二维数组表示，其中的每个操作用一个含有两个正整数 a 和 b 的数组表示，含义是将所有符合 0 <= i < a 以及 0 <= j < b 的元素 M[i][j] 的值都增加 1。
在执行给定的一系列操作后，你需要返回矩阵中含有最大整数的元素个数。
示例 :
输入: m = 3, n = 3 operations = [[2,2],[3,3]] 输出: 4 解释: 初始状态, M = [[0, 0, 0], [0, 0, 0], [0, 0, 0]] 执行完操作 [2,2] 后, M = [[1, 1, 0], [1, 1, 0], [0, 0, 0]] 执行完操作 [3,3] 后, M = [[2, 2, 1], [2, 2, 1], [1, 1, 1]] M 中最大的整数是 2, 而且 M 中有4个值为2的元素。因此返回 4。
思路：分析一下题目。可以确定的是最大值一定是 M[0][0] ，范围一定是数组中最小的行和最小的列。有了上边两个结论，因为本题只是统计个数。
注意：复用了变量m 和 n。
代码实现：
public int maxCount(int m, int n, int[][] ops) { for (int[] r : ops) { m = Math.min(m, r[0]); n = Math.min(n, r[1]); } return m * n; }
