排序|倒序遍历|set
10.02
sort+hash分组
class Solution {
/*
变位分组
输入：["eat", "tea", "tan", "ate", "nat", "bat"],
输出：
[
["ate","eat","tea"],
["nat","tan"],
["bat"]
]
*/
public:
vector<vector<string>> groupAnagrams(vector<string>& strs)
{
int n=strs.size();
vector<vector<string>> ret;
unordered_map<string,vector<string>> hash;
for(auto& s:strs)
{
string t=s;
sort(t.begin(),t.end());
hash[t].push_back(s);
}
for(auto& [a,b]:hash)
{
ret.push_back(b);
}
return ret;
}
};
lc2017
算两行前缀和，遍历第一个机器人下移的列，取第二个机器人能拿的左右区域最大值里的最小值。
class Solution {
public:
long long gridGame(vector<vector<int>>& grid) {
/* 1、此题的目标是让乙的分数最小，所以甲的最优策略并不是自己先获取一个最大分数。
2、从乙的角度考虑，我们发现其实甲拿完以后，乙只有两个选择：要么横向走到底，再往下走；要么第一步往下走，再横向走到底
3、发现这个结论就好办了，遍历甲每一个向下的位置，同时求乙的分数，取最小值即可 */
int i, size = grid[0].size();
vector<long long> presum0(size, 0), presum1(size, 0);
getPresum(grid, presum0, presum1);
long long minSum = presum0[size - 1] - grid[0][0];
for (i = 1; i < size; ++i) {
minSum = min(minSum, max(presum0[size - 1] - presum0[i], presum1[i - 1])); //1的后缀 0的前缀 取最大
}
return minSum;
}
void getPresum(vector<vector<int>>& grid, vector<long long>& presum0, vector<long long>& presum1) {
int i, size = grid[0].size();
presum0[0] = grid[0][0];
presum1[0] = grid[1][0];
for (i = 1; i < size; ++i) {
presum0[i] = presum0[i - 1] + grid[0][i];
presum1[i] = presum1[i - 1] + grid[1][i];
}
}
};
lc2375
d倒序填充
遇到连续降序段就倒着填数，升序段顺着填数，拼出最小字典序的数字串
class Solution {
public:
string smallestNumber(string pattern) {
int n = pattern.size();
string res(n+1,'a');
int num = 1; // 从1开始填充数字
int i = 0;
while (i <= n)
{
if (i < n && pattern[i] == 'D') {
// 找到连续'D'的结束位置
int j = i;
while (j < n && pattern[j] == 'D')
j++;
// 倒序填充当前D段（长度为j-i+1）
for (int k = j; k >= i; k--) {
res[k]='0' + num;
num++;
}
i = j + 1; // 跳过已处理的D段
}
else
{
// 处理'I'或末尾，直接填充
res[i]='0' + num;
num++;
i++;
}
}
return res;
}
};
lcp52
- 逆序遍历操作
- set 的有序性快速定位区间节点
- 染红时累加计数
- 处理后立即删除避免重复统计，确保每个节点只按最后一次操作计算颜色。
class Solution {
public:
int getNumber(TreeNode* root, vector<vector<int>>& ops) {
set<int> s;
auto dfs = [&](this auto&& dfs,TreeNode* node)
{
if (!node) return;
dfs(node->left);
s.insert(node->val);
dfs(node->right);
};
dfs(root);
int ret = 0;
for (int i = ops.size() - 1; i >= 0; --i) {
int type = ops[i][0];
auto l = s.lower_bound(ops[i][1]), r = s.upper_bound(ops[i][2]);
if (type == 1)
ret += distance(l, r);
s.erase(l, r);
}
return ret;
}
};