🌟欢迎来到 我的博客 —— 探索技术的无限可能！
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
给你一个 二进制 字符串 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+1 int 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] >= target int 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
给你一个 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
给你一个 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) { // 正中间的数必须是 0 ans += 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; } }
