map|math

lcr34

map<char,int> 处理order

tmp=word

按order sort lambda tmp;

return tmp==word;

class Solution {

    unordered_map<char, int> hash;

public:

    bool isAlienSorted(vector<string>& words, string order) {

        int n = order.size();

        for (int i = 0; i < n; i++) {

            hash[order[i]] = i;

        }

        vector<string> corr = words;

        // 自定义排序规则，按外星语字典序排序

        sort(corr.begin(), corr.end(), [&](const string& a, const string& b) {

            int lenA = a.size(), lenB = b.size();

            int minLen = min(lenA, lenB);

            for (int i = 0; i < minLen; i++) {

                // 逐个字符比较，按外星语顺序判断

                if (hash[a[i]] != hash[b[i]]) {

                    return hash[a[i]] < hash[b[i]];

                }

            }

            // 前面字符都相同，短单词更小

            return lenA < lenB;

        });

        return corr == words;

    }

};

lcp42.玩具套圈 abstract

先给玩具“按r 分门别类”map<int, set<int>> A[12]，再逐个圆圈排查能装下哪些玩具，最后算总数

统计能被圆圈完全覆盖的玩具数量

1. 整理玩具信息
用一个特殊结构 A 存储玩具：

按玩具的半径 r 分类（ A[r] ），同一半径的玩具再按x坐标分组（ A[r][x] ），每组里用集合存对应的y坐标。这样方便后续快速查找特定半径和x范围内的玩具。

2. 检查每个圆圈能覆盖的玩具
对每个圆圈，遍历所有可能被它覆盖的玩具半径 r （从1到圆圈半径 R ，因为玩具半径必须≤圆圈半径才可能被覆盖）。
对每个半径 r ，计算该圆圈能覆盖的x坐标范围，找到这个范围内的玩具x坐标，再进一步计算对应的y坐标范围。
最后在符合条件的x组里，找出y坐标在范围内的玩具，标记它们被覆盖（从集合中删除，避免重复统计），并计数。

3. 返回总覆盖数
所有圆圈检查完后，累计的被覆盖玩具数量就是结果。

class Solution

{
map<int, set<int>> A[12];

public:
int circleGame(vector<vector<int>>& toys, vector<vector<int>>& circles, int R)

{
int n = toys.size();
for (const vector<int> &vec : toys) A[vec[2]][vec[0]].insert(vec[1]);

        int ans = 0;
for (const vector<int> &vec : circles)

       {
for (int r = 1; r <= R; r++)

          for (int x = vec[0] - R + r; x <= vec[0] + R - r; x++)  //x范围

           if (A[r].count(x))

        {
int a = abs(vec[0] - x);
int b = (int) sqrt((R - r) * (R - r) - a * a + 1e-9);
int y1 = vec[1] - b, y2 = vec[1] + b;

                set<int> &st = A[r][x];

//遍历set查找
for (auto it = st.lower_bound(y1); it != st.end() && *it <= y2; )

               {
auto nxt = next(it);
st.erase(it);
ans++;
it = nxt;
}
}
}
return ans;
}
};

lc42

dp找每个元素的maxl和maxr，ret+=min

class Solution {
public:
int trap(vector<int>& height) {
int totalWater = 0;
int left = 0;
int right = height.size() - 1;
int leftMax = 0;
int rightMax = 0;

while (left < right) {
leftMax = max(leftMax, height[left]);
rightMax = max(rightMax, height[right]);

if (leftMax < rightMax) {
totalWater += leftMax - height[left];
left++;
} else {
totalWater += rightMax - height[right];
right--;
}
}

return totalWater;
}
};