2663. 字典序最小的美丽字符串(Hard)
如果一个字符串满足以下条件，则称其为 美丽字符串 ：
它由英语小写字母表的前 k 个字母组成。
它不包含任何长度为 2 或更长的回文子字符串。
给你一个长度为 n 的美丽字符串 s 和一个正整数 k 。
请你找出并返回一个长度为 n 的美丽字符串，该字符串还满足：在字典序大于 s 的所有美丽字符串中字典序最小。如果不存在这样的字符串，则返回一个空字符串。
对于长度相同的两个字符串 a 和 b ，如果字符串 a 在与字符串 b 不同的第一个位置上的字符字典序更大，则字符串 a 的字典序大于字符串 b 。
例如，“abcd” 的字典序比 “abcc” 更大，因为在不同的第一个位置（第四个字符）上 d 的字典序大于 c 。
示例 1：
输入：s = “abcz”, k = 26
输出：“abda”
解释：字符串 “abda” 既是美丽字符串，又满足字典序大于 “abcz” 。
可以证明不存在字符串同时满足字典序大于 “abcz”、美丽字符串、字典序小于 “abda” 这三个条件。
示例 2：
输入：s = “dc”, k = 4
输出：“”
解释：可以证明，不存在既是美丽字符串，又字典序大于 “dc” 的字符串。
提示：
1 <= n == s.length <= 1e5
4 <= k <= 26
s 是一个美丽字符串
贪心，灵神题解：
class Solution {
public:
string smallestBeautifulString(string s, int k) {
k += 'a';
int n = s.length();
int i = n - 1; // 从最后一个字母开始
s[i]++; // 先加一
while (i < n) {
if (s[i] == k) { // 需要进位
if (i == 0) { // 无法进位
return "";
}
// 进位
s[i] = 'a';
s[--i]++;
} else if (i && s[i] == s[i - 1] || i > 1 && s[i] == s[i - 2]) {
s[i]++; // 如果 s[i] 和左侧的字符形成回文串，就继续增加 s[i]
} else {
i++; // 反过来检查后面是否有回文串
}
}
return s;
}
};
题解：贪心（Python/Java/C++/Go）
520. 检测大写字母我们定义，在以下情况时，单词的大写用法是正确的：
全部字母都是大写，比如 “USA” 。
单词中所有字母都不是大写，比如 “leetcode” 。
如果单词不只含有一个字母，只有首字母大写， 比如 “Google” 。
给你一个字符串 word 。如果大写用法正确，返回 true ；否则，返回 false 。
示例 1：
输入：word = “USA”
输出：true
示例 2：
输入：word = “FlaG”
输出：false
提示：
1 <= word.length <= 100
word 由小写和大写英文字母组成
简单字符串模拟：
class Solution {
public:
bool detectCapitalUse(string word) {
int cnt = ranges::count_if(word, [](char c) { return isupper(c); });
return cnt == 0 || cnt == word.length() || cnt == 1 && isupper(word[0]);
}
};
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 <= 1e4
-1e9 <= nums[i] <= 1e9
经典单调栈：
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
int n = nums.size();
vector<int> ans(n, -1);
stack<int> st;
for (int i = 0; i < 2 * n; i++) {
while (!st.empty() && nums[st.top()] < nums[i % n]) {
ans[st.top()] = nums[i % n];
st.pop();
}
st.push(i % n);
}
return ans;
}
};
2732. 找到矩阵中的好子集(Hard)
给你一个下标从 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 <= 1e4
1 <= n <= 5
grid[i][j] 要么是 0 ，要么是 1 。
太难了，根本不会，抄了灵神题解，至今没搞懂：
class Solution {
public:
vector<int> goodSubsetofBinaryMatrix(vector<vector<int>>& grid) {
vector<int> a[1 << 5];
vector<int> ans;
int m = grid.size();
int n = grid[0].size();
for (int i = 0; i < m; i++) {
int s = 0;
for (auto c : grid[i])
s = (s << 1) + c;
if (s == 0) {
ans.push_back(i);
return ans;
}
a[s].push_back(i);
}
for (int i = 0; i < (1 << n); i++) {
if (a[i].size() == 0)
continue;
for (int j = i + 1; j < (1 << n); j++) {
if (a[j].size() == 0)
continue;
if ((i & j) == 0) {
ans.push_back(a[i][0]);
ans.push_back(a[j][0]);
sort(ans.begin(), ans.end());
return ans;
}
}
}
return ans;
}
};
题解如下：严格证明+三种计算方法
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] <= 1e9
中等题还是不会，状压dp看了题解后有一些思路但是还是没写出来：
class Solution {
public:
int MOD = 1e9 + 7; // 模数
int specialPerm(vector<int>& nums) {
int cache[1 << nums.size()][nums.size()]; // 记忆化
memset(cache, -1, sizeof(cache));
int mask = 0;
function<int(int)> backtracking = [&](int tail) -> int {
// BaseCase: 所有数字都被选中，1个合法排列
int if_end = 1;
for (int i = 0; i < nums.size(); i++) {
if (((1 << i) & mask) == 0) {
if_end = 0;
break;
}
}
if (if_end == 1)
return 1;
// Induction：存在未选中数字，进行回溯搜索
int ans = 0;
for (int i = 0; i < nums.size(); i++) {
if ((mask & (1 << i)) == 0 &&
(tail == -1 || nums[i] % tail == 0 ||
tail % nums[i] == 0)) {
mask |= (1 << i); // 修改状态
if (cache[mask][i] == -1) { // 记忆化
cache[mask][i] = backtracking(nums[i]); // 向下搜索
}
ans = (ans + cache[mask][i]) %
MOD; // 利用已有记忆化结果，节省重复运算
mask ^= (1 << i); // 恢复状态
}
}
return ans;
};
return backtracking(-1); // 开始记忆化回溯
}
};
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 * 1e5
s 仅由小写英文字母组成
简单贪心：
class Solution {
public:
string smallestString(string s) {
int opear = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] != 'a') {
opear = 1;
s[i] = s[i] - 1;
} else {
if (i != s.size() - 1) {
if (opear == 0)
continue;
else
break;
} else {
if (opear == 0)
s[i] = 'z';
}
}
}
return s;
}
};
2742. 给墙壁刷油漆(Hard)
给你两个长度为 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] <= 1e6
1 <= time[i] <= 500
看出来要用dp，但是dp还是不熟练，01背包dp：
class Solution {
public:
int paintWalls(vector<int>& cost, vector<int>& time) {
int n = cost.size();
vector<vector<int>> memo(
n, vector<int>(n * 2 + 1, -1)); // -1 表示没有计算过
auto dfs = [&](auto&& dfs, int i, int j) -> int {
if (j > i) { // 剩余的墙都可以免费刷
return 0;
}
if (i < 0) { // 上面 if 不成立，意味着 j < 0，不符合题目要求
return INT_MAX / 2; // 防止加法溢出
}
// 注意 res 是引用
int& res = memo[i][j + n]; // 加上偏移量 n，防止出现负数
if (res != -1) { // 之前计算过
return res;
}
return res = min(dfs(dfs, i - 1, j + time[i]) + cost[i],
dfs(dfs, i - 1, j - 1));
};
return dfs(dfs, n - 1, 0);
}
};
灵神题解：两种方法：状态优化 / 转换成 0-1 背包
