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;
}
网友评论