🌟欢迎来到 我的博客 —— 探索技术的无限可能！
24.下一个更大元素 II
题目链接：503. 下一个更大元素 II
给定一个循环数组 nums （ nums[nums.length - 1] 的下一个元素是 nums[0] ），返回 nums 中每个元素的 下一个更大元素 。
数字 x 的 下一个更大的元素 是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1 。
示例 1:
输入: nums = [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
示例 2:
输入: nums = [1,2,3,4,3]
输出: [2,3,4,-1,4]
提示:
1 <= nums.length <= 104
-109 <= nums[i] <= 109
题解：
方法：单调栈
public class Solution { public int[] nextGreaterElements(int[] nums) { int n = nums.length; int[] ans = new int[n]; Arrays.fill(ans, -1); Deque<Integer> st = new ArrayDeque<>(); for (int i = 2 * n - 1; i >= 0; i--) { int x = nums[i % n]; while (!st.isEmpty() && x >= st.peek()) { // 由于 x 的出现，栈顶元素永远不会是左边元素的「下一个更大元素」 st.pop(); } if (i < n && !st.isEmpty()) { ans[i] = st.peek(); } st.push(x); } return ans; } }
25.找到矩阵中的好子集
题目链接：2732. 找到矩阵中的好子集
给你一个下标从 0 开始大小为 m x n 的二进制矩阵 grid 。
从原矩阵中选出若干行构成一个行的 非空 子集，如果子集中任何一列的和至多为子集大小的一半，那么我们称这个子集是 好子集。
更正式的，如果选出来的行子集大小（即行的数量）为 k，那么每一列的和至多为 floor(k / 2) 。
请你返回一个整数数组，它包含好子集的行下标，请你将其 升序 返回。
如果有多个好子集，你可以返回任意一个。如果没有好子集，请你返回一个空数组。
一个矩阵 grid 的行 子集 ，是删除 grid 中某些（也可能不删除）行后，剩余行构成的元素集合。
示例 1：
输入：grid = [[0,1,1,0],[0,0,0,1],[1,1,1,1]]
输出：[0,1]
解释：我们可以选择第 0 和第 1 行构成一个好子集。
选出来的子集大小为 2 。
- 第 0 列的和为 0 + 0 = 0 ，小于等于子集大小的一半。
- 第 1 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 2 列的和为 1 + 0 = 1 ，小于等于子集大小的一半。
- 第 3 列的和为 0 + 1 = 1 ，小于等于子集大小的一半。
示例 2：
输入：grid = [[0]]
输出：[0]
解释：我们可以选择第 0 行构成一个好子集。
选出来的子集大小为 1 。
- 第 0 列的和为 0 ，小于等于子集大小的一半。
示例 3：
输入：grid = [[1,1,1],[1,1,1]]
输出：[]
解释：没有办法得到一个好子集。
提示：
m == grid.length
n == grid[i].length
1 <= m <= 104
1 <= n <= 5
grid[i][j] 要么是 0 ，要么是 1 。
题解：
class Solution { public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) { Map<Integer, Integer> g = new HashMap<>(); for (int i = 0; i < grid.length; ++i) { int mask = 0; for (int j = 0; j < grid[0].length; ++j) { mask |= grid[i][j] << j; } if (mask == 0) { return List.of(i); } g.put(mask, i); } for (var e1 : g.entrySet()) { for (var e2 : g.entrySet()) { if ((e1.getKey() & e2.getKey()) == 0) { int i = e1.getValue(), j = e2.getValue(); return List.of(Math.min(i, j), Math.max(i, j)); } } } return List.of(); } }
26.特别的排列
题目链接：2741. 特别的排列
给你一个下标从 0 开始的整数数组 nums ，它包含 n 个 互不相同 的正整数。如果 nums 的一个排列满足以下条件，我们称它是一个特别的排列：
对于 0 <= i < n - 1 的下标 i ，要么 nums[i] % nums[i+1] == 0 ，要么 nums[i+1] % nums[i] == 0 。
请你返回特别排列的总数目，由于答案可能很大，请将它对 109 + 7 取余 后返回。
示例 1：
输入：nums = [2,3,6]
输出：2
解释：[3,6,2] 和 [2,6,3] 是 nums 两个特别的排列。
示例 2：
输入：nums = [1,4,3]
输出：2
解释：[3,1,4] 和 [4,1,3] 是 nums 两个特别的排列。
提示：
2 <= nums.length <= 14
1 <= nums[i] <= 109
题解：
方法：状压 DP
public class Solution { public int specialPerm(int[] nums) { int n = nums.length; int u = (1 << n) - 1; long[][] memo = new long[u][n]; for (long[] row : memo) { Arrays.fill(row, -1); // -1 表示没有计算过 } long ans = 0; for (int i = 0; i < n; i++) { ans += dfs(u ^ (1 << i), i, nums, memo); } return (int) (ans % 1_000_000_007); } private long dfs(int s, int i, int[] nums, long[][] memo) { if (s == 0) { return 1; // 找到一个特别排列 } if (memo[s][i] != -1) { // 之前计算过 return memo[s][i]; } long res = 0; for (int j = 0; j < nums.length; j++) { if ((s >> j & 1) > 0 && (nums[i] % nums[j] == 0 || nums[j] % nums[i] == 0)) { res += dfs(s ^ (1 << j), j, nums, memo); } } return memo[s][i] = res; // 记忆化 } }
27.执行子串操作后的字典序最小字符串
给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：
选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，‘b’ 用 ‘a’ 替换，‘a’ 用 ‘z’ 替换。
返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。
子字符串 是字符串中的一个连续字符序列。
现有长度相同的两个字符串 x 和 字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果 x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。
示例 1：
输入：s = “cbabc”
输出：“baabc”
解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。
示例 2：
输入：s = “acbbc”
输出：“abaab”
解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。
示例 3：
输入：s = “leetcode”
输出：“kddsbncd”
解释：我们选择整个字符串执行操作。
可以证明最终得到的字符串是字典序最小的。
提示：
1 <= s.length <= 3 * 105
s 仅由小写英文字母组成
题解：
方法：贪心
class Solution { public String smallestString(String S) { char[] s = S.toCharArray(); int n = s.length; for (int i = 0; i < n; i++) { if (s[i] > 'a') { // 继续向后遍历 for (; i < n && s[i] > 'a'; i++) { s[i]--; } return new String(s); } } // 所有字母均为 a s[n - 1] = 'z'; return new String(s); } }
28.给墙壁刷油漆
题目链接：2742. 给墙壁刷油漆
给你两个长度为 n 下标从 0 开始的整数数组 cost 和 time ，分别表示给 n 堵不同的墙刷油漆需要的开销和时间。你有两名油漆匠：
一位需要 付费 的油漆匠，刷第 i 堵墙需要花费 time[i] 单位的时间，开销为 cost[i] 单位的钱。
一位 免费 的油漆匠，刷 任意 一堵墙的时间为 1 单位，开销为 0 。但是必须在付费油漆匠 工作 时，免费油漆匠才会工作。
请你返回刷完 n 堵墙最少开销为多少。
示例 1：
输入：cost = [1,2,3,2], time = [1,2,3,2]
输出：3
解释：下标为 0 和 1 的墙由付费油漆匠来刷，需要 3 单位时间。同时，免费油漆匠刷下标为 2 和 3 的墙，需要 2 单位时间，开销为
0 。总开销为 1 + 2 = 3 。
示例 2：
输入：cost = [2,3,4,2], time = [1,1,1,1]
输出：4
解释：下标为 0 和 3 的墙由付费油漆匠来刷，需要 2 单位时间。同时，免费油漆匠刷下标为 1 和 2 的墙，需要 2 单位时间，开销为
0 。总开销为 2 + 2 = 4 。
提示：
1 <= cost.length <= 500
cost.length == time.length
1 <= cost[i] <= 106
1 <= time[i] <= 500
题解：
方法：动态规划
public class Solution { public int paintWalls(int[] cost, int[] time) { int n = cost.length; int[][] memo = new int[n][n * 2]; for (int[] row : memo) { Arrays.fill(row, -1); // -1 表示没有计算过 } return dfs(n - 1, 0, cost, time, memo); } private int dfs(int i, int j, int[] cost, int[] time, int[][] memo) { if (j > i) { // 剩余的墙都可以免费刷 return 0; } if (i < 0) { // 上面 if 不成立，意味着 j < 0，不符合题目要求 return Integer.MAX_VALUE / 2; // 防止加法溢出 } int k = j + memo.length; // 加上偏移量，防止出现负数 if (memo[i][k] != -1) { // 之前计算过 return memo[i][k]; } int res1 = dfs(i - 1, j + time[i], cost, time, memo) + cost[i]; int res2 = dfs(i - 1, j - 1, cost, time, memo); return memo[i][k] = Math.min(res1, res2); } }
29.移除字符串中的尾随零
题目链接：2710. 移除字符串中的尾随零
给你一个用字符串表示的正整数 num ，请你以字符串形式返回不含尾随零的整数 num 。
示例 1：
输入：num = “51230100”
输出：“512301”
解释：整数 “51230100” 有 2 个尾随零，移除并返回整数 “512301” 。
示例 2：
输入：num = “123”
输出：“123”
解释：整数 “123” 不含尾随零，返回整数 “123” 。
提示：
1 <= num.length <= 1000
num 仅由数字 0 到 9 组成
num 不含前导零
题解：
方法：遍历
class Solution { public String removeTrailingZeros(String num) { int i = num.length() - 1; while (num.charAt(i) == '0') { --i; } return num.substring(0, i + 1); } }
30.目标和
题目链接：494. 目标和
给你一个非负整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1：
输入：nums = [1,1,1,1,1], target = 3
输出：5
解释：一共有 5 种方法让最终目标和为 3 。
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
示例 2：
输入：nums = [1], target = 1
输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
题解：
方法：动态规划
class Solution { private int[] nums; private int[][] memo; public int findTargetSumWays(int[] nums, int target) { int s = 0; for (int x : nums) { s += x; } s -= Math.abs(target); if (s < 0 || s % 2 == 1) { return 0; } int m = s / 2; // 背包容量 this.nums = nums; int n = nums.length; memo = new int[n][m + 1]; for (int[] row : memo) { Arrays.fill(row, -1); // -1 表示没有计算过 } return dfs(n - 1, m); } private int dfs(int i, int c) { if (i < 0) { return c == 0 ? 1 : 0; } if (memo[i][c] != -1) { // 之前计算过 return memo[i][c]; } if (c < nums[i]) { return memo[i][c] = dfs(i - 1, c); // 只能不选 } return memo[i][c] = dfs(i - 1, c) + dfs(i - 1, c - nums[i]); // 不选 + 选 } }
