【题解】—— LeetCode一周小结46

🌟欢迎来到 我的博客 —— 探索技术的无限可能！

🌟博客的简介（文章目录）

---

【题解】—— 每日一道题目栏

---

上接：【题解】—— LeetCode一周小结45

11.切棍子的最小成本

题目链接：1547. 切棍子的最小成本

有一根长度为 n 个单位的木棍，棍上从 0 到 n 标记了若干位置。例如，长度为 6 的棍子可以标记如下：

给你一个整数数组 cuts ，其中 cuts[i] 表示你需要将棍子切开的位置。

你可以按顺序完成切割，也可以根据需要更改切割的顺序。

每次切割的成本都是当前要切割的棍子的长度，切棍子的总成本是历次切割成本的总和。对棍子进行切割将会把一根木棍分成两根较小的木棍（这两根木棍的长度和就是切割前木棍的长度）。请参阅第一个示例以获得更直观的解释。

返回切棍子的 最小总成本 。

示例 1：

输入：n = 7, cuts = [1,3,4,5]

输出：16

解释：按 [1, 3, 4, 5] 的顺序切割的情况如下所示：

第一次切割长度为 7 的棍子，成本为 7 。第二次切割长度为 6 的棍子（即第一次切割得到的第二根棍子），第三次切割为长度 4
的棍子，最后切割长度为 3 的棍子。总成本为 7 + 6 + 4 + 3 = 20 。 而将切割顺序重新排列为 [3, 5, 1, 4]
后，总成本 = 16（如示例图中 7 + 4 + 3 + 2 = 16）。

示例 2：

输入：n = 9, cuts = [5,6,1,4,2]

输出：22

解释：如果按给定的顺序切割，则总成本为 25 。总成本 <= 25 的切割顺序很多，例如，[4, 6, 5, 2, 1] 的总成本 =
22，是所有可能方案中成本最小的。

提示：

2 <= n <= 10^6

1 <= cuts.length <= min(n - 1, 100)

1 <= cuts[i] <= n - 1

cuts 数组中的所有整数都 互不相同

题解：
方法：记忆化搜索
        

class Solution {public int minCost(int n, int[] cuts) {Arrays.sort(cuts);int m = cuts.length + 2;int[] newCuts = new int[m];System.arraycopy(cuts, 0, newCuts, 1, m - 2);newCuts[m - 1] = n;int[][] memo = new int[m][m];return dfs(0, m - 1, newCuts, memo);}private int dfs(int i, int j, int[] cuts, int[][] memo) {if (i + 1 == j) { // 无需切割return 0;}if (memo[i][j] > 0) { // 之前计算过return memo[i][j];}int res = Integer.MAX_VALUE;for (int k = i + 1; k < j; k++) {res = Math.min(res, dfs(i, k, cuts, memo) + dfs(k, j, cuts, memo));}return memo[i][j] = res + cuts[j] - cuts[i];}
}

---

12.统计满足 K 约束的子字符串数量 I

题目链接：3258. 统计满足 K 约束的子字符串数量 I

给你一个 二进制 字符串 s 和一个整数 k。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

字符串中 0 的数量最多为 k。
字符串中 1 的数量最多为 k。
返回一个整数，表示 s 的所有满足 k 约束 的
子字符串
的数量。

示例 1：

输入：s = “10101”, k = 1

输出：12

解释：

s 的所有子字符串中，除了 “1010”、“10101” 和 “0101” 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = “1010101”, k = 2

输出：25

解释：

s 的所有子字符串中，除了长度大于 5 的子字符串外，其余子字符串都满足 k 约束。

示例 3：

输入：s = “11111”, k = 1

输出：15

解释：

s 的所有子字符串都满足 k 约束。

提示：

1 <= s.length <= 50

1 <= k <= s.length

s[i] 是 ‘0’ 或 ‘1’。

题解：
方法：滑动窗口
        

class Solution {public int countKConstraintSubstrings(String S, int k) {char[] s = S.toCharArray();int ans = 0;int left = 0;int[] cnt = new int[2];for (int i = 0; i < s.length; i++) {cnt[s[i] & 1]++;while (cnt[0] > k && cnt[1] > k) {cnt[s[left] & 1]--;left++;}ans += i - left + 1;}return ans;}
}

---

13.统计满足 K 约束的子字符串数量 II

题目链接：3261. 统计满足 K 约束的子字符串数量 II

给你一个 二进制 字符串 s 和一个整数 k。

另给你一个二维整数数组 queries ，其中 queries[i] = [li, ri] 。

如果一个 二进制字符串 满足以下任一条件，则认为该字符串满足 k 约束：

字符串中 0 的数量最多为 k。
字符串中 1 的数量最多为 k。
返回一个整数数组 answer ，其中 answer[i] 表示 s[li…ri] 中满足 k 约束 的
子字符串
的数量。

示例 1：

输入：s = “0001111”, k = 2, queries = [[0,6]]

输出：[26]

解释：

对于查询 [0, 6]， s[0…6] = “0001111” 的所有子字符串中，除 s[0…5] = “000111” 和
s[0…6] = “0001111” 外，其余子字符串都满足 k 约束。

示例 2：

输入：s = “010101”, k = 1, queries = [[0,5],[1,4],[2,3]]

输出：[15,9,3]

解释：

s 的所有子字符串中，长度大于 3 的子字符串都不满足 k 约束。

提示：

1 <= s.length <= 105

s[i] 是 ‘0’ 或 ‘1’

1 <= k <= s.length

1 <= queries.length <= 105

queries[i] == [li, ri]

0 <= li <= ri < s.length

所有查询互不相同

题解：
方法：滑动窗口+前缀和+二分查找
        

class Solution {public long[] countKConstraintSubstrings(String S, int k, int[][] queries) {char[] s = S.toCharArray();int n = s.length;int[] left = new int[n];long[] sum = new long[n + 1];int[] cnt = new int[2];int l = 0;for (int i = 0; i < n; i++) {cnt[s[i] & 1]++;while (cnt[0] > k && cnt[1] > k) {cnt[s[l++] & 1]--;}left[i] = l; // 记录合法子串右端点 i 对应的最小左端点 l// 计算 i-left[i]+1 的前缀和sum[i + 1] = sum[i] + i - l + 1;}long[] ans = new long[queries.length];for (int i = 0; i < queries.length; i++) {int ql = queries[i][0];int qr = queries[i][1];// 如果区间内所有数都小于 ql，结果是 j=qr+1int j = lowerBound(left, ql - 1, qr + 1, ql);ans[i] = sum[qr + 1] - sum[j] + (long) (j - ql + 1) * (j - ql) / 2;}return ans;}// 返回在开区间 (left, right) 中的最小的 j，满足 nums[j] >= target// 如果没有这样的数，返回 right// 原理见 https://www.bilibili.com/video/BV1AP41137w7/private int lowerBound(int[] nums, int left, int right, int target) {while (left + 1 < right) { // 区间不为空// 循环不变量：// nums[left] < target// nums[right] >= targetint mid = left + (right - left) / 2;if (nums[mid] < target) {left = mid; // 范围缩小到 (mid, right)} else {right = mid; // 范围缩小到 (left, mid)}}return right;}
}

方法：预处理
        

class Solution {public long[] countKConstraintSubstrings(String S, int k, int[][] queries) {char[] s = S.toCharArray();int n = s.length;int[] left = new int[n];long[] sum = new long[n + 1];int[] cnt = new int[2];int l = 0;for (int i = 0; i < n; i++) {cnt[s[i] & 1]++;while (cnt[0] > k && cnt[1] > k) {cnt[s[l++] & 1]--;}left[i] = l;sum[i + 1] = sum[i] + i - l + 1;}int[] right = new int[n];l = 0;for (int i = 0; i < n; i++) {while (l < n && left[l] < i) {l++;}right[i] = l;}long[] ans = new long[queries.length];for (int i = 0; i < queries.length; i++) {int ql = queries[i][0];int qr = queries[i][1];int j = Math.min(right[ql], qr + 1);ans[i] = sum[qr + 1] - sum[j] + (long) (j - ql + 1) * (j - ql) / 2;}return ans;}
}

---

14.统计好节点的数目

题目链接：3249. 统计好节点的数目

现有一棵 无向 树，树中包含 n 个节点，按从 0 到 n - 1 标记。树的根节点是节点 0 。给你一个长度为 n - 1 的二维整数数组 edges，其中 edges[i] = [ai, bi] 表示树中节点 ai 与节点 bi 之间存在一条边。

如果一个节点的所有子节点为根的
子树
包含的节点数相同，则认为该节点是一个 好节点。

返回给定树中 好节点 的数量。

子树 指的是一个节点以及它所有后代节点构成的一棵树。

示例 1：

输入：edges = [[0,1],[0,2],[1,3],[1,4],[2,5],[2,6]]

输出：7

说明：

树的所有节点都是好节点。

示例 2：

输入：edges = [[0,1],[1,2],[2,3],[3,4],[0,5],[1,6],[2,7],[3,8]]

输出：6

说明：

树中有 6 个好节点。上图中已将这些节点着色。

示例 3：

输入：edges =
[[0,1],[1,2],[1,3],[1,4],[0,5],[5,6],[6,7],[7,8],[0,9],[9,10],[9,12],[10,11]]

输出：12

解释：

除了节点 9 以外其他所有节点都是好节点。

提示：

2 <= n <= 105

edges.length == n - 1

edges[i].length == 2

0 <= ai, bi < n

输入确保 edges 总表示一棵有效的树。

题解：
方法：深度优先搜索
        

class Solution {public int countGoodNodes(int[][] edges) {int n = edges.length + 1;List<Integer>[] g = new ArrayList[n];Arrays.setAll(g, i -> new ArrayList<>());for (int[] e : edges) {int x = e[0];int y = e[1];g[x].add(y);g[y].add(x);}dfs(0, -1, g);return ans;}private int ans;private int dfs(int x, int fa, List<Integer>[] g) {int size = 1;int sz0 = 0;boolean ok = true;for (int y : g[x]) {if (y == fa) {continue; // 不能递归到父节点}int sz = dfs(y, x, g);if (sz0 == 0) {sz0 = sz; // 记录第一个儿子子树的大小} else if (sz != sz0) { // 存在大小不一样的儿子子树ok = false; // 注意不能 break，其他子树 y 仍然要递归}size += sz;}ans += ok ? 1 : 0;return size;}
}

---

15.最少翻转次数使二进制矩阵回文 I

题目链接：3239. 最少翻转次数使二进制矩阵回文 I

给你一个 m x n 的二进制矩阵 grid 。

如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。

你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。

请你返回 最少 翻转次数，使得矩阵 要么 所有行是 回文的 ，要么所有列是 回文的 。

示例 1：

输入：grid = [[1,0,0],[0,0,0],[0,0,1]]

输出：2

解释：

将高亮的格子翻转，得到所有行都是回文的。

示例 2：

输入：grid = [[0,1],[0,1],[0,0]]

输出：1

解释：

将高亮的格子翻转，得到所有列都是回文的。

示例 3：

输入：grid = [[1],[0]]

输出：0

解释：

所有行已经是回文的。

提示：

m == grid.length

n == grid[i].length

1 <= m * n <= 2 * 105

0 <= grid[i][j] <= 1

题解：
方法：回文
        

class Solution {public int minFlips(int[][] grid) {int m = grid.length;int n = grid[0].length;int diffRow = 0;for (int[] row : grid) {for (int j = 0; j < n / 2; j++) {if (row[j] != row[n - 1 - j]) {diffRow++;}}}int diffCol = 0;for (int j = 0; j < n; j++) {for (int i = 0; i < m / 2; i++) {if (grid[i][j] != grid[m - 1 - i][j]) {diffCol++;}}}return Math.min(diffRow, diffCol);}
}

---

16.最少翻转次数使二进制矩阵回文 II

题目链接：3240. 最少翻转次数使二进制矩阵回文 II

给你一个 m x n 的二进制矩阵 grid 。

如果矩阵中一行或者一列从前往后与从后往前读是一样的，那么我们称这一行或者这一列是 回文 的。

你可以将 grid 中任意格子的值 翻转 ，也就是将格子里的值从 0 变成 1 ，或者从 1 变成 0 。

请你返回 最少 翻转次数，使得矩阵中 所有 行和列都是 回文的 ，且矩阵中 1 的数目可以被 4 整除 。

示例 1：

输入：grid = [[1,0,0],[0,1,0],[0,0,1]]

输出：3

解释：

示例 2：

输入：grid = [[0,1],[0,1],[0,0]]

输出：2

解释：

示例 3：

输入：grid = [[1],[1]]

输出：2

解释：

提示：

m == grid.length

n == grid[i].length

1 <= m * n <= 2 * 105

0 <= grid[i][j] <= 1

题解：
方法：贪心
        

class Solution {public int minFlips(int[][] a) {int m = a.length;int n = a[0].length;int ans = 0;for (int i = 0; i < m / 2; i++) {for (int j = 0; j < n / 2; j++) {int cnt1 = a[i][j] + a[i][n - 1 - j] + a[m - 1 - i][j] + a[m - 1 - i][n - 1 - j];ans += Math.min(cnt1, 4 - cnt1); // 全为 1 或全为 0}}if (m % 2 > 0 && n % 2 > 0) {// 正中间的数必须是 0ans += a[m / 2][n / 2];}int diff = 0;int cnt1 = 0;if (m % 2 > 0) {// 统计正中间这一排for (int j = 0; j < n / 2; j++) {if (a[m / 2][j] != a[m / 2][n - 1 - j]) {diff++;} else {cnt1 += a[m / 2][j] * 2;}}}if (n % 2 > 0) {// 统计正中间这一列for (int i = 0; i < m / 2; i++) {if (a[i][n / 2] != a[m - 1 - i][n / 2]) {diff++;} else {cnt1 += a[i][n / 2] * 2;}}}return ans + (diff > 0 ? diff : cnt1 % 4);}
}

---

17.适龄的朋友

题目链接：825. 适龄的朋友

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

ages[y] <= 0.5 * ages[x] + 7
ages[y] > ages[x]
ages[y] > 100 && ages[x] < 100
否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

示例 1：

输入：ages = [16,16]

输出：2

解释：2 人互发好友请求。

示例 2：

输入：ages = [16,17,18]

输出：2

解释：产生的好友请求为 17 -> 16 ，18 -> 17 。

示例 3：

输入：ages = [20,30,100,110,120]

输出：3

解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

提示：

n == ages.length

1 <= n <= 2 * 104

1 <= ages[i] <= 120

题解：
方法：计数+滑动窗口
        

class Solution {public int numFriendRequests(int[] ages) {int[] cnt = new int[121];for (int age : ages) {cnt[age]++;}int ans = 0;int ageY = 0;int cntWindow = 0;for (int ageX = 0; ageX < cnt.length; ageX++) {cntWindow += cnt[ageX];if (ageY * 2 <= ageX + 14) { // 不能发送好友请求cntWindow -= cnt[ageY];ageY++;}if (cntWindow > 0) { // 存在可以发送好友请求的用户ans += cnt[ageX] * cntWindow - cnt[ageX];}}return ans;}
}

下接：【题解】—— LeetCode一周小结47

---