上接：【题解】—— LeetCode一周小结2
15.删除排序链表中的重复元素 II
题目链接：82. 删除排序链表中的重复元素 II
给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。
示例 1：
输入：head = [1,2,3,3,4,4,5]
输出：[1,2,5]
示例 2：
输入：head = [1,1,1,2,3]
输出：[2,3]
提示：
链表中节点数目在范围 [0, 300] 内
-100 <= Node.val <= 100
题目数据保证链表已经按升序 排列
题解
如何去重？
创建一个虚拟节点指向链表的头部。一个引用指针 'cur’最初指向虚拟节点。
在循环内部，提取当前节点的值。检查下两个节点是否具有相同的值。
- 如果是真的，通过链表并删除具有相同值的节点，直到遇到不同值的节点。
- 如果下两个节点的值不同，则将 ‘cur’ 指针向前移动。
循环结束后，返回修改后的链表（不包含重复节点）。
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ // 解决方案类，用于删除单链表中的重复节点 class Solution { // 方法：删除给定链表中的重复节点 public ListNode deleteDuplicates(ListNode head) { // 创建一个虚拟节点，值为0，指向链表的头部 ListNode dummy = new ListNode(0, head); // 创建一个引用指针 'cur'，最初指向虚拟节点 ListNode cur = dummy; // 循环直到 'cur' 的下一个节点和下下个节点都不为空 while (cur.next != null && cur.next.next != null) { // 提取当前节点的值 int val = cur.next.val; // 检查下两个节点是否具有相同的值 if (cur.next.next.val == val) { // 如果是真的，通过链表并删除具有相同值的节点 while (cur.next != null && cur.next.val == val) cur.next = cur.next.next; } else { // 如果下两个节点的值不同，则将 'cur' 指针向前移动 cur = cur.next; } } // 返回修改后的链表（不包含重复节点） return dummy.next; } }
方法：递归
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ class Solution { public ListNode deleteDuplicates(ListNode head) { // 没有节点或者只有一个节点，必然没有重复元素 if (head == null || head.next == null) return head; // 当前节点和下一个节点，值不同，则head的值是需要保留的，对head.next继续递归 if (head.val != head.next.val) { head.next = deleteDuplicates(head.next); return head; } else { // 当前节点与下一个节点的值重复了，重复的值都不能要。 // 一直往下找，找到不重复的节点。返回对不重复节点的递归结果 ListNode notDup = head.next.next; while (notDup != null && notDup.val == head.val) { notDup = notDup.next; } return deleteDuplicates(notDup); } } }
16.统计整数数目
题目链接：2719. 统计整数数目
给你两个数字字符串 num1 和 num2 ，以及两个整数 max_sum 和 min_sum 。如果一个整数 x 满足以下条件，我们称它是一个好整数：
num1 <= x <= num2min_sum <= digit_sum(x) <= max_sum.
请你返回好整数的数目。答案可能很大，请返回答案对 109 + 7 取余后的结果。
注意，digit_sum(x) 表示 x 各位数字之和。
示例 1：
输入：num1 = “1”, num2 = “12”, min_num = 1, max_num = 8
输出：11
解释：总共有 11 个整数的数位和在 1 到 8 之间，分别是 1,2,3,4,5,6,7,8,10,11 和 12 。所以我们返回 11 。
示例 2：
输入：num1 = “1”, num2 = “5”, min_num = 1, max_num = 5
输出：5
解释：数位和在 1 到 5 之间的 5 个整数分别为 1,2,3,4 和 5 。所以我们返回 5 。
提示：
1 <= num1 <= num2 <= 1022
1 <= min_sum <= max_sum <= 400
提示1
设f(n，l，r)表示从1到n的整数个数，其位数之和介于I和r之间。
提示2
答案是f(数字2，最小和，最大和) -f(数字1，最小和，最大和)
提示3
你可以用数字dp来计算f (n，l，r)。
题解
方法：数位 DP
题目实际上求的是区间 [num1,…num2]中，数位和在 [min_sum,…max_sum]的数的个数。对于这种区间 [l,…r]的问题，我们可以考虑转化为求 [1,…r]和 [1,…l−1]的答案，然后相减即可。
对于 [1,…r]的答案，我们可以使用数位 DP 来求解。我们设计一个函数 dfs(pos,s,limit) 表示当前处理到第 pos 位，数位和为 s，当前数是否有上界限制 limit 的方案数。其中 pos 从高到低枚举。
对于 dfs(pos,s,limit)，我们可以枚举当前数位 iii 的值，然后递归计算dfs(pos+1,s+i,limit∧(i==up))，其中 up 表示当前数位的上界。如果 limit 为真，那么 up 就是当前数位的上界，否则 up 为 9。如果 pos 大于等于 num的长度，那么我们就可以判断 s 是否在 [min_sum,…max_sum]的范围内，如果在就返回 1，否则返回 0。
import java.math.BigInteger; class Solution { private final int mod = (int) 1e9 + 7; private Integer[][] f; private String num; private int min; private int max; public int count(String num1, String num2, int min_sum, int max_sum) { min = min_sum; max = max_sum; num = num2; f = new Integer[23][220]; int a = dfs(0, 0, true); num = new BigInteger(num1).subtract(BigInteger.ONE).toString(); f = new Integer[23][220]; int b = dfs(0, 0, true); return (a - b + mod) % mod; } private int dfs(int pos, int s, boolean limit) { if (pos >= num.length()) { return s >= min && s <= max ? 1 : 0; } if (!limit && f[pos][s] != null) { return f[pos][s]; } int ans = 0; int up = limit ? num.charAt(pos) - '0' : 9; for (int i = 0; i <= up; ++i) { ans = (ans + dfs(pos + 1, s + i, limit && i == up)) % mod; } if (!limit) { f[pos][s] = ans; } return ans; } }
两种数位 DP 模板
下面方法来自灵神，链接：两种数位 DP 模板
v1.0：两次记忆化搜索
把问题拆分成：
- 计算 ≤num2\le \textit{num}_2≤num2 的好整数个数，记作 aaa。
- 计算 ≤num1−1\le \textit{num}_1-1≤num1−1 的好整数个数，记作 bbb。
那么答案就是 a−ba-ba−b。
考虑到 num1\textit{num}_1num1 是个字符串，不方便减一，可以改为计算 ≤num1\le \textit{num}_1≤num1 的合法数字个数，再单独判断 num1\textit{num}_1num1 这个数是否合法。
把 v1.0 模板 中的参数 mask\textit{mask}mask 去掉，加上参数 sum\textit{sum}sum，表示数位和。在递归中，如果 sum>maxSum\textit{sum}>\textit{maxSum}sum>maxSum 则直接返回 000（因为 sum\textit{sum}sum 不可能变小）。递归到终点时，如果 sum≥minSum\textit{sum}\ge \textit{minSum}sum≥minSum，说明我们成功构造出一个好整数，返回 111，否则返回 000。
此外，由于前导零对数位和无影响（sum+0=sum\textit{sum}+0=\textit{sum}sum+0=sum），模板中的 isNum\textit{isNum}isNum 可以省略。
class Solution { private static final int MOD = 1_000_000_007; public int count(String num1, String num2, int minSum, int maxSum) { int ans = calc(num2, minSum, maxSum) - calc(num1, minSum, maxSum) + MOD; // 避免负数 int sum = 0; for (char c : num1.toCharArray()) { sum += c - '0'; } if (minSum <= sum && sum <= maxSum) { ans++; // num1 是合法的，补回来 } return ans % MOD; } private int calc(String s, int minSum, int maxSum) { int n = s.length(); int[][] memo = new int[n][Math.min(9 * n, maxSum) + 1]; for (int[] row : memo) { Arrays.fill(row, -1); } return dfs(0, 0, true, s.toCharArray(), minSum, maxSum, memo); } private int dfs(int i, int sum, boolean isLimit, char[] s, int minSum, int maxSum, int[][] memo) { if (sum > maxSum) { // 非法 return 0; } if (i == s.length) { return sum >= minSum ? 1 : 0; } if (!isLimit && memo[i][sum] != -1) { return memo[i][sum]; } int up = isLimit ? s[i] - '0' : 9; int res = 0; for (int d = 0; d <= up; d++) { // 枚举当前数位填 d res = (res + dfs(i + 1, sum + d, isLimit && (d == up), s, minSum, maxSum, memo)) % MOD; } if (!isLimit) { memo[i][sum] = res; } return res; } }
复杂度分析
- 时间复杂度：O(nmD)\mathcal{O}(nmD)O(nmD)，其中 nnn 为 nums2\textit{nums}_2nums2 的长度，m=min(9n,maxSum)m=\min(9n, \textit{maxSum})m=min(9n,maxSum)，D=10D=10D=10。动态规划的时间复杂度 === 状态个数 ×\times× 单个状态的计算时间。本题中状态个数等于 O(nm)\mathcal{O}(nm)O(nm)，单个状态的计算时间为 O(D)\mathcal{O}(D)O(D)，因此时间复杂度为 O(nmD)\mathcal{O}(nmD)O(nmD)。
- 空间复杂度：O(nm)\mathcal{O}(nm)O(nm)。
v2.0：一次记忆化搜索
v2.0 版本在 v1.0 的基础上做了改进，只需要一次记忆化搜索就能算出答案，效率更高。
仿照 isLimit\textit{isLimit}isLimit，再添加一个参数 limitLow\textit{limitLow}limitLow，表示是否受到下界 num1\textit{num}_1num1 的约束。为了让代码更清晰，原来的参数名 isLimit\textit{isLimit}isLimit 改名为 limitHigh\textit{limitHigh}limitHigh。此外，ddd 的最大值 up\textit{up}up 改名为 hi\textit{hi}hi，即 high\textit{high}high 的前两个字母。
为了方便计算，在 num1\textit{num}_1num1 前面添加前导零，使其长度和 num2\textit{num}_2num2 相等。
limitLow\textit{limitLow}limitLow 的用法类似 limitHigh\textit{limitHigh}limitHigh，如果为 limitLow=true\textit{limitLow}=\texttt{true}limitLow=true，那么 ddd 只能从 num1[i]\textit{num}_1[i]num1[i] 开始枚举，否则可以从 000 开始，这个值记作 lo\textit{lo}lo，即 low\textit{low}low 的前两个字母。如果 limitLow=true\textit{limitLow}=\texttt{true}limitLow=true 并且 d=lod=\textit{lo}d=lo，那么往下递归时，传入的 limitLow\textit{limitLow}limitLow 仍然为 true\texttt{true}true，否则为 false\texttt{false}false。
class Solution { public int count(String num1, String num2, int minSum, int maxSum) { int n = num2.length(); num1 = "0".repeat(n - num1.length()) + num1; // 补前导零，和 num2 对齐 int[][] memo = new int[n][Math.min(9 * n, maxSum) + 1]; for (int[] row : memo) { Arrays.fill(row, -1); } return dfs(0, 0, true, true, num1.toCharArray(), num2.toCharArray(), minSum, maxSum, memo); } private int dfs(int i, int sum, boolean limitLow, boolean limitHigh, char[] num1, char[] num2, int minSum, int maxSum, int[][] memo) { if (sum > maxSum) { // 非法 return 0; } if (i == num2.length) { return sum >= minSum ? 1 : 0; } if (!limitLow && !limitHigh && memo[i][sum] != -1) { return memo[i][sum]; } int lo = limitLow ? num1[i] - '0' : 0; int hi = limitHigh ? num2[i] - '0' : 9; int res = 0; for (int d = lo; d <= hi; d++) { // 枚举当前数位填 d res = (res + dfs(i + 1, sum + d, limitLow && d == lo, limitHigh && d == hi, num1, num2, minSum, maxSum, memo)) % 1_000_000_007; } if (!limitLow && !limitHigh) { memo[i][sum] = res; } return res; } }
复杂度分析
- 时间复杂度：O(nmD)\mathcal{O}(nmD)O(nmD)，其中 nnn 为 nums2\textit{nums}_2nums2 的长度，m=min(9n,maxSum)m=\min(9n, \textit{maxSum})m=min(9n,maxSum)，D=10D=10D=10。动态规划的时间复杂度 === 状态个数 ×\times× 单个状态的计算时间。本题中状态个数等于 O(nm)\mathcal{O}(nm)O(nm)，单个状态的计算时间为 O(D)\mathcal{O}(D)O(D)，因此时间复杂度为 O(nmD)\mathcal{O}(nmD)O(nmD)。
- 空间复杂度：O(nm)\mathcal{O}(nm)O(nm)。
17.最大字符串配对数目
题目链接：2744. 最大字符串配对数目
给你一个下标从 0 开始的数组 words ，数组中包含 互不相同 的字符串。
如果字符串 words[i] 与字符串 words[j] 满足以下条件，我们称它们可以匹配：
字符串 words[i] 等于 words[j] 的反转字符串。
0 <= i < j < words.length
请你返回数组 words 中的 最大 匹配数目。
注意，每个字符串最多匹配一次。
示例 1：
输入：words = [“cd”,“ac”,“dc”,“ca”,“zz”]
输出：2
解释：在此示例中，我们可以通过以下方式匹配 2 对字符串：
- 我们将第 0 个字符串与第 2 个字符串匹配，因为 word[0] 的反转字符串是 “dc” 并且等于 words[2]。
- 我们将第 1 个字符串与第 3 个字符串匹配，因为 word[1] 的反转字符串是 “ca” 并且等于 words[3]。 可以证明最多匹配数目是 2 。
示例 2：
输入：words = [“ab”,“ba”,“cc”]
输出：1
解释：在此示例中，我们可以通过以下方式匹配 1 对字符串：
- 我们将第 0 个字符串与第 1 个字符串匹配，因为 words[1] 的反转字符串 “ab” 与 words[0] 相等。 可以证明最多匹配数目是 1 。
示例 3：
输入：words = [“aa”,“ab”]
输出：0
解释：这个例子中，无法匹配任何字符串。
提示：
1 <= words.length <= 50
words[i].length == 2
words 包含的字符串互不相同。
words[i] 只包含小写英文字母。
题解
方法：哈希表
我们可以用哈希表 cnt来存储数组 words 中每个字符串的反转字符串出现的次数。
遍历数组 words，对于每个字符串 w，我们将其反转后的字符串的出现次数加到答案中，然后将 w 的出现次数加 1。
最后返回答案。
class Solution { public int maximumNumberOfStringPairs(String[] words) { Map<Integer, Integer> cnt = new HashMap<>(); int ans = 0; for (var w : words) { int a = w.charAt(0) - 'a', b = w.charAt(1) - 'a'; ans += cnt.getOrDefault(b << 5 | a, 0); cnt.merge(a << 5 | b, 1, Integer::sum); } return ans; } }
18.拿出最少数目的魔法豆
题目链接：2171. 拿出最少数目的魔法豆
给定一个 正整数 数组 beans ，其中每个整数表示一个袋子里装的魔法豆的数目。
请你从每个袋子中 拿出 一些豆子（也可以 不拿出），使得剩下的 非空 袋子中（即 至少还有一颗 魔法豆的袋子）魔法豆的数目 相等。一旦把魔法豆从袋子中取出，你不能再将它放到任何袋子中。
请返回你需要拿出魔法豆的 最少数目。
示例 1：
输入：beans = [4,1,6,5]
输出：4
解释：
- 我们从有 1 个魔法豆的袋子中拿出 1 颗魔法豆。 剩下袋子中魔法豆的数目为：[4,0,6,5]
- 然后我们从有 6 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为：[4,0,4,5]
- 然后我们从有 5 个魔法豆的袋子中拿出 1 个魔法豆。 剩下袋子中魔法豆的数目为：[4,0,4,4]
总共拿出了 1 + 2 + 1 = 4 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 4 个魔法豆更少的方案。
示例 2：
输入：beans = [2,10,3,2]
输出：7
解释：
- 我们从有 2 个魔法豆的其中一个袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为：[0,10,3,2]
- 然后我们从另一个有 2 个魔法豆的袋子中拿出 2 个魔法豆。 剩下袋子中魔法豆的数目为：[0,10,3,0]
- 然后我们从有 3 个魔法豆的袋子中拿出 3 个魔法豆。 剩下袋子中魔法豆的数目为：[0,10,0,0]
总共拿出了 2 + 2 + 3 = 7 个魔法豆，剩下非空袋子中魔法豆的数目相等。
没有比取出 7 个魔法豆更少的方案。
提示：
1 <= beans.length <= 105
1 <= beans[i] <= 105
题解
我们可以将 beans 从小到大排序后，枚举最终非空袋子中魔法豆的数目 v，将小于v 的魔法豆全部清空，大于 v 的魔法豆减少至 v，这样所有非空袋子中的魔法豆就都相等了。
由于拿出魔法豆 + 剩余魔法豆 = 初始魔法豆之和，我们可以考虑最多能剩下多少个魔法豆，从而计算出最少能拿出多少个魔法豆。
如图所示，可以保留蓝色矩形区域内的魔法豆。设 beans的长度为 n，以 n−i 为矩形底边长，v=beans[i]为矩形高，则矩形面积为(n−i)⋅v,最后用 ∑beans[i] 减去矩形面积的最大值，即为拿出魔法豆的最小值。
public class Solution { public long minimumRemoval(int[] beans) { Arrays.sort(beans); long sum = 0, mx = 0; int n = beans.length; for (int i = 0; i < n; i++) { sum += beans[i]; mx = Math.max(mx, (long) (n - i) * beans[i]); } return sum - mx; } }
19.使数组和小于等于 x 的最少时间
给你两个长度相等下标从 0 开始的整数数组 nums1 和 nums2 。每一秒，对于所有下标 0 <= i < nums1.length ，nums1[i] 的值都增加 nums2[i] 。操作 完成后 ，你可以进行如下操作：
选择任一满足 0 <= i < nums1.length 的下标 i ，并使 nums1[i] = 0 。
同时给你一个整数 x 。
请你返回使 nums1 中所有元素之和 小于等于 x 所需要的 最少 时间，如果无法实现，那么返回 -1 。
示例 1：
输入：nums1 = [1,2,3], nums2 = [1,2,3], x = 4
输出：3
解释： 第 1 秒，我们对 i = 0 进行操作，得到 nums1 = [0,2+2,3+3] = [0,4,6] 。
第 2 秒，我们对 i = 1 进行操作，得到 nums1 = [0+1,0,6+3] = [1,0,9] 。
第 3 秒，我们对 i = 2 进行操作，得到 nums1 = [1+1,0+2,0] = [2,2,0] 。
现在 nums1 的和为 4 。不存在更少次数的操作，所以我们返回 3 。
示例 2：
输入：nums1 = [1,2,3], nums2 = [3,3,3], x = 4
输出：-1
解释：不管如何操作，nums1 的和总是会超过 x 。
提示：
1 <= nums1.length <= 103
1 <= nums1[i] <= 103
0 <= nums2[i] <= 103
nums1.length == nums2.length
0 <= x <= 106
题解
方法：排序 + 动态规划
如果我们多次操作同一个数，那么只有最后一次操作是有意义的，其余的对该数的操作，只会使得其它数字增大。因此，我们最多对每个数操作一次，也即是说，操作次数在 [0,…n]之间。
我们不妨假设进行了 j 次操作，操作的数字下标分别为 i1,i2,⋯ ,ij ，那么对于这 j 次操作，每一次可以使得数组元素和减少的值为：
d1 =nums1 [i1 ]+nums2 [i1 ]×1
d2 =nums1 [i2 ]+nums2[i2 ]×2
⋯
dj =nums1 [ij ]+nums 2 [ij ]×j
从贪心的角度考虑，为了使得数组元素和的减少量最大，我们应当让 nums2中的较大元素尽可能放在后面操作。因此，我们可以对 nums1和 nums2按照 nums2的元素值从小到大进行排序。
接下来，我们考虑动态规划的实现。我们用 f[i][j] 表示对于数组 nums1的前 i个元素，进行 j 次操作，所能减少的数组元素和的最大值。我们可以得到如下的状态转移方程：
f[i][j] = max{f[i -1][j],f[i=1][j-1]+nums1[i]+nums2[i]xj}
最后，我们枚举 j，找到最小的满足 s1+s2×j−f[n][j]≤x的 j 即可。
class Solution { public int minimumTime(List<Integer> nums1, List<Integer> nums2, int x) { int n = nums1.size(); int[][] f = new int[n + 1][n + 1]; int[][] nums = new int[n][0]; for (int i = 0; i < n; ++i) { nums[i] = new int[] {nums1.get(i), nums2.get(i)}; } Arrays.sort(nums, Comparator.comparingInt(a -> a[1])); for (int i = 1; i <= n; ++i) { for (int j = 0; j <= n; ++j) { f[i][j] = f[i - 1][j]; if (j > 0) { int a = nums[i - 1][0], b = nums[i - 1][1]; f[i][j] = Math.max(f[i][j], f[i - 1][j - 1] + a + b * j); } } } int s1 = 0, s2 = 0; for (int v : nums1) { s1 += v; } for (int v : nums2) { s2 += v; } for (int j = 0; j <= n; ++j) { if (s1 + s2 * j - f[n][j] <= x) { return j; } } return -1; } }
20.按分隔符拆分字符串
题目链接：2788. 按分隔符拆分字符串
给你一个字符串数组 words 和一个字符 separator ，请你按 separator 拆分 words 中的每个字符串。
返回一个由拆分后的新字符串组成的字符串数组，不包括空字符串 。
注意
- separator 用于决定拆分发生的位置，但它不包含在结果字符串中。
- 拆分可能形成两个以上的字符串。
- 结果字符串必须保持初始相同的先后顺序。
示例 1：
输入：words = [“one.two.three”,“four.five”,“six”], separator = “.”
输出：[“one”,“two”,“three”,“four”,“five”,“six”]
解释：在本示例中，我们进行下述拆分：
“one.two.three” 拆分为 “one”, “two”, “three”
“four.five” 拆分为 “four”, “five”
“six” 拆分为 “six”
因此，结果数组为 [“one”,“two”,“three”,“four”,“five”,“six”] 。
示例 2：
输入：words = [“ e a s y easy easy”,“ p r o b l e m problem problem”], separator = “$”
输出：[“easy”,“problem”]
解释：在本示例中，我们进行下述拆分：
“ e a s y easy easy” 拆分为 “easy”（不包括空字符串）
“ p r o b l e m problem problem” 拆分为 “problem”（不包括空字符串）
因此，结果数组为 [“easy”,“problem”] 。
示例 3：
输入：words = [“|||”], separator = “|”
输出：[]
解释：在本示例中，“|||” 的拆分结果将只包含一些空字符串，所以我们返回一个空数组 [] 。
提示：
1 <= words.length <= 100
1 <= words[i].length <= 20
words[i] 中的字符要么是小写英文字母，要么就是字符串 “.,|$#@” 中的字符（不包括引号）
separator 是字符串 “.,|$#@” 中的某个字符（不包括引号）
题解
方法：模拟
我们遍历字符串数组 words，对于每个字符串 w，我们使用 separator 作为分隔符进行拆分，如果拆分后的字符串不为空，则将其加入答案数组。
import java.util.regex.Pattern; class Solution { public List<String> splitWordsBySeparator(List<String> words, char separator) { List<String> ans = new ArrayList<>(); for (var w : words) { for (var s : w.split(Pattern.quote(String.valueOf(separator)))) { if (s.length() > 0) { ans.add(s); } } } return ans; } }
21.分割数组的最大值
题目链接：410. 分割数组的最大值
给定一个非负整数数组 nums 和一个整数 k ，你需要将这个数组分成 k 个非空的连续子数组。
设计一个算法使得这 k 个子数组各自和的最大值最小。
示例 1：
输入：nums = [7,2,5,10,8], k = 2
输出：18
解释：
一共有四种方法将 nums 分割为 2 个子数组。
其中最好的方式是将其分为 [7,2,5] 和 [10,8] 。
因为此时这两个子数组各自的和的最大值为18，在所有情况中最小。
示例 2：
输入：nums = [1,2,3,4,5], k = 2
输出：9
示例 3：
输入：nums = [1,4,4], k = 3
输出：4
提示：
1 <= nums.length <= 1000
0 <= nums[i] <= 106
1 <= k <= min(50, nums.length)
题解
方法：二分查找
题目意思：
有一个数组，你要分割成m份，每一份都有一个和，这些和当中的最大值，现在你要让它最小。
思路：
我们可以假如这个值为x，即我们要在一个范围内，查找我们想要的这个值x。
范围：
x最小范围：大于等于整个数组的最大值
x最大范围：小于等于整个数组的和
所以二分查找的范围是[max(数组), sum(数组)]
二分查找过程：
假设中点mid就是 “每一个数组和中的最大值” 的最小值，那么每一个数组和必定<=mid。
接下来我们用这个值来对数组进行从头分割，一旦当前数组和>mid,就结束该数组，开启一个新数组
最后当你的查找范围只剩一个数的时候，结束二分查找
判读这个中点值是大了还是小了：
如果你用这个mid创建的数组数量，比m还多，说明你这个值定小了，所以二分查找取右半边
如果你用这个mid创建的数组数量，比m少了，说明你这个值定大了，所以二分查找取左半边
如果创建数组数量已经等于m了, 会发生什么？
如果创建数组数量已经等于m了,
但此时如果收敛范围仍然不止一个数，范围还是会继续收敛的，且取的是左半边，目的是让我们能最终找到一个确切的值，这个值恰好就是取得了最大值的那个数组的和(因为小于这个和的话，就不能通过创建数组数量=m的测试；而大于这个m的话，即使通过了创建数组数量=m的测试，范围也会继续向左边收敛，直到我们找到的就是这个和。)
对于这个附加部分的理解，可以试试用[1,7,2,8,5], m=3的例子手推一遍，也许可以帮助理解
java：
class Solution { public int splitArray(int[] nums, int m) { if(nums == null || nums.length < m) { return 0; } int left = getMax(nums), right = getSum(nums); while(left < right) { int mid = left + (right - left) / 2; if(computeM(nums, mid) <= m) { right = mid; } else { left = mid + 1; } } return left; } private int getMax(int[] nums) { return Arrays.stream(nums).max().getAsInt(); } private int getSum(int[] nums) { return Arrays.stream(nums).sum(); } /** * 假设这个中点mid就是 “每一个数组和中的最大值” 的最小值 * 那么可以分割为多少个连续的数组 */ private int computeM(int[] nums, int minMax) { int m = 1, sum = 0; for(int i : nums) { if(sum + i > minMax) { m++; sum = i; } else { sum += i; } } return m; } }
Python：
class Solution: def splitArray(self, nums: List[int], m: int) -> int: #二分查找 #指定二分查找范围 left, right = max(nums), sum(nums) #定义 测试中点是大还是小的 测试函数 def test_mid(mid): #初始化 num = 1 #num表示使用该mid我们会得到几个数组 s = 0 #s表示当前数组的和 for i in nums: if s+i > mid: #如果当前数组已经超过mid，要停止这个数组 s = i #这个数变为下一个数组的开头 num += 1 #会得到的数组数量+1 else: s += i return num > m #数组总数是否>m, 大于的话说明mid太小，二分查找取右边 #这里有一个注意点，如果num已经等于m了, 但此时如果left不等于right，范围还是会继续收敛的， #且取的是左半边，目的是让我们能最终找到一个确切的值，这个值恰好就是取得了最大值的那个数组的和 #(因为小于这个和的话，就不能通过num=m的测试；而大于这个m的话，即使通过了num=m的测试， #范围也会继续向左边收敛，直到我们找到的就是这个和)。 #进行二分查找 while left < right: #当left == right的时候就终止查找，返回任意一个 mid = (left + right) // 2 if_right = test_mid(mid) if if_right: left = mid+1 else: right = mid #num <= m的情况 return left
下接：【题解】—— LeetCode一周小结4
