排序|倒序遍历|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;
}
};