// todo
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
思路
有一个数组，可以在数组元素前加上正负号来组成表达式，问表达式等于target的数目。
如果当前元素为正则累加，否则相减，递归直到所有元素都已列入表达式，如果累加结果等于target则返回1，否则返回0。
//todo 改为递推，或记忆化搜索
代码
/**
* @date 2024-06-30 20:07
*/
public class FindTargetSumWays494 {
public int findTargetSumWays(int[] nums, int target) {
return dfs(nums, 1, nums[0], target) + dfs(nums, 1, -nums[0], target);
}
public int dfs(int[] nums, int i, int res, int target) {
if (i == nums.length) {
return res - target == 0 ? 1 : 0;
}
return dfs(nums, i + 1, res + nums[i], target) + dfs(nums, i + 1, res - nums[i], target);
}
}
性能
2710.移除字符串中的尾随零
目标
给你一个用字符串表示的正整数 num ，请你以字符串形式返回不含尾随零的整数 num 。
示例 1：
输入：num = "51230100"
输出："512301"
解释：整数 "51230100" 有 2 个尾随零，移除并返回整数 "512301" 。示例 2：
输入：num = "123"
输出："123"
解释：整数 "123" 不含尾随零，返回整数 "123" 。说明：
- 1 <= num.length <= 1000
- num 仅由数字 0 到 9 组成
- num 不含前导零
思路
去掉字符串末尾的0。
代码
/**
* @date 2024-06-29 21:45
*/
public class RemoveTrailingZeros2710 {
public String removeTrailingZeros(String num) {
int n = num.length() - 1;
while (n >= 0 && num.charAt(n) == '0') {
n--;
}
return num.substring(0, n + 1);
}
}
性能
2742.给墙壁刷油漆
// todo
2734.执行子串操作后的字典序最小字符串
目标
给你一个仅由小写英文字母组成的字符串 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 * 10^5
- s 仅由小写英文字母组成
思路
求对一个字符串的 非空子串 进行操作后字典序最小的字符串，两个字符串 第一个不同的字母 在字母表 越先出现 其字典序就越小。字符串仅由小写字母组成，可进行的操作指将子串的每一个字母替换为其在字母表中的前一个字母，a 前面的字母定义为 z。
关键在于非空子串如何选，根据题意可知，如果子串不含字母 a 操作总能使字典序变小。字符串前面字符的字典序越小整个字符串的字典序就越小，因此可以从前向后遍历直到遇到字母 a 作为子串。如果字符串字母均为 a，操作总会使字典序变大，显然将最后一个 a 改为 z 可以使操作后的字符串字典序最小。
代码
/**
* @date 2024-06-27 0:05
*/
public class SmallestString2734 {
public String smallestString_v1(String s) {
int i = 0;
int n = s.length();
char[] chars = s.toCharArray();
while (i < n && chars[i] == 'a') {
i++;
}
while (i < n && chars[i] != 'a') {
chars[i++]--;
}
if (i == n && s.charAt(n - 1) == 'a') {
chars[n - 1] = 'z';
}
return new String(chars);
}
public String smallestString_v2(String s) {
int i = 0;
int n = s.length();
StringBuilder sb = new StringBuilder(s);
while (i < n && s.charAt(i) == 'a') {
i++;
}
if (i == n) {
sb.setCharAt(n - 1, 'z');
return sb.toString();
}
while (i < n && s.charAt(i) != 'a') {
sb.setCharAt(i, (char) (s.charAt(i++) - 1));
}
return sb.toString();
}
}
性能
使用 StringBuilder 显示用时更少，我试了一下与if判断的位置没关系，按道理来说直接数组访问比方法调用开销更小，new StringBuilder(s) 与 s.toCharArray 都进行了数组拷贝。我能想到的解释就是大家都用的StringBuilder，然后这段代码被JIT编译器优化。
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] <= 10^9
思路
有一个互不相同的正整数数组，问使得相邻元素可以被整除（对于相邻元素a % b == 0 || b % a == 0）的排列有多少种。
排列数的计算需要使用dfs，但如果不保存重复子问题的话会超时。
难点在于是否将保存的结果计入，例如 [2,6,3]，虽然dfs 2 -> 6 -> 3 与 6 -> 2 -> 3有重复的子问题3，但是后者不符合题目条件。
// todo
代码
性能
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 <= 10^4
- 1 <= n <= 5
grid[i][j]要么是 0 ，要么是 1 。
思路
有一个 m*n 的 二进制矩阵，任选k行，如果每一列的和不大于 k/2，则称为矩阵的好子集，返回任意一个好子集行标的集合。
在写这篇题解的时候才注意到是二进制矩阵，即元素值不是0就是1。这道题是根据提示写的，如果存在好子集则一定存在k为1或2的好子集，然后就根据好子集的要求循环判断。
当k为1时，好子集元素值全为0.当k为2时，任选两行遍历列判断是否有和大于1。
// todo 看一下题解
代码
/**
* @date 2024-06-25 0:28
*/
public class GoodSubsetofBinaryMatrix2732 {
public List<Integer> goodSubsetofBinaryMatrix(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
List<Integer> list = new ArrayList<>();
Queue<Integer> queue = new ArrayDeque<>();
here:
for (int i = 0; i < m; i++) {
queue.offer(i);
for (int j = 0; j < n; j++) {
if (grid[i][j] != 0) {
continue here;
}
}
list.add(i);
}
if (list.size() > 0) {
return list;
}
while (!queue.isEmpty()) {
int i = queue.poll();
here:
for (int j = i + 1; j < m; j++) {
for (int k = 0; k < n; k++) {
if (grid[i][k] + grid[j][k] > 1){
continue here;
}
}
list.add(i);
list.add(j);
return list;
}
}
return list;
}
}
性能
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 <= 10^4
- -10^9 <= nums[i] <= 10^9
思路
暴力解法需要针对每一个元素向后搜索，时间复杂度为O(n^2)。这里面有一些重复的操作，例如，数组 [5,4,3,2,1,6] 找下一个更大的元素，从 5 向后搜索 与从 4 向后搜索有重复的部分 3 2 1。单调栈的核是这样处理的，先将第一个元素下标压入栈中，指针移到下一个元素，如果栈顶对应元素大于等于当前元素则将当前元素下标也压入栈中，否则弹栈，记录 res[stack.pop()] = 当前元素，直到栈顶元素大于等于当前元素。
针对这个题目，栈中保存的下标对应的元素值从栈底到栈顶是单调递减的，如果遇到第一个更大元素就弹栈了，因此称为单调栈。
这样做的好处是避免了重复的查找，它将重复搜索的部分使用栈保存了起来，这样就变成了从后向前搜索。如果栈顶元素遇到了第一个更大的元素，那么它也是前面同样小于该值的第一个更大元素，从而避免了重复查找。
这里对循环数组的处理是将原数组拼接到后面，下标进行取模运算。
代码
/**
* @date 2024-06-24 0:18
*/
public class NextGreaterElements503 {
public int[] nextGreaterElements_v4(int[] nums) {
int n = nums.length;
int[] res = new int[n];
Arrays.fill(res, -1);
int[] stack = new int[n];
int top = -1;
for (int i = 0; i < 2 * n - 1; i++) {
int index = i % n;
while (top > -1 && nums[stack[top]] < nums[index]) {
res[stack[top--]] = nums[index];
}
if (i < n) {
stack[++top] = index;
}
}
return res;
}
}
性能
139.单词拆分
目标
给你一个字符串 s 和一个字符串列表 wordDict 作为字典。如果可以利用字典中出现的一个或多个单词拼接出 s 则返回 true。
注意：不要求字典中出现的单词全部都使用，并且字典中的单词可以重复使用。
示例 1：
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。示例 2：
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。注意，你可以重复使用字典中的单词。示例 3：
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false说明：
- 1 <= s.length <= 300
- 1 <= wordDict.length <= 1000
- 1 <= wordDict[i].length <= 20
- s 和 wordDict[i] 仅由小写英文字母组成
- wordDict 中的所有字符串 互不相同
思路
已知一个字符串列表 wordDict 和一个字符串 s，问能否用列表中的元素拼成该字符串，列表中的元素可以重复使用。
很明显需要使用动态规划来求解，假设当前列表元素 word 的长度为 l，子字符串 sub 的长度为 i，如果 sub.substring(0, i-l) 能由字典中的词拼成并且 word.equals(sub.substring(i-l, l)) 那么 sub 也能由字典中的词拼成。
代码
/**
* @date 2024-06-23 19:58
*/
public class WordBreak139 {
public boolean wordBreak(String s, List<String> wordDict) {
int n = s.length();
boolean[] dp = new boolean[n + 1];
dp[0] = true;
for (int i = 1; i <= n; i++) {
for (String word : wordDict) {
int length = word.length();
if (length <= i && dp[i - length] && word.equals(s.substring(i - length, i))) {
dp[i] = true;
}
}
}
return dp[n];
}
public boolean wordBreak_v1(String s, List<String> wordDict) {
int n = s.length();
char[] mem = new char[n + 1];
Arrays.fill(mem, '2');
return dfs(s, 0, wordDict, mem) == '1';
}
public char dfs(String s, int i, List<String> wordDict, char[] mem) {
int n = s.length();
if (i == n) {
return '1';
}
if (mem[i] != '2') {
return mem[i];
}
for (String word : wordDict) {
if (s.startsWith(word, i) && '1' == dfs(s, i + word.length(), wordDict, mem)) {
return mem[i] = '1';
}
}
return mem[i] = '0';
}
}
性能
最快的解法是使用记忆化搜索，可以剪枝缩小搜索范围。
2663.字典序最小的美丽字符串
// todo