力扣每月题解汇总-2026年05月

目录

力扣每日一题396-旋转函数

日期：2026-05-01

题意

给定整数数组 nums, 定义函数 F(k) 为将 nums 循环右移 k 位后的 SUM(i * nums[i]). 求 F(k) 的最大值.

思路

印象中咱们是有做过类似的题的. 可以先列几个式子出来观察一下, 可以发现 F(i) 加上整个数组的和后将最后一个数的倍率清零即为 F(i + 1), 可以想到做一个前缀和然后枚举最后一位数.

实现

class Solution {
using ll = long long;
static constexpr ll inf = 1e18;
public:
    int maxRotateFunction(vector<int>& nums) {
        ll cur = 0, all = 0;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            cur += i * nums[i];
            all += nums[i];
        }
        ll ans = cur;
        for (int i = n - 1; i >= 0; i--) {
            cur = cur + all - nums[i] * n;
            ans = max(ans, cur);
        }
        return ans;
    }
};

力扣每日一题788-旋转数字

日期：2026-05-02

题意

若一个数使其每个数位 180° 旋转后不为原数, 则称其为好, 如 2 翻转为 5, 6 翻转为 9. 求问 [1, n] 有多少好数.

思路

这道题难的同时不太难. 难在正解应该是数位 dp: 无 3/4/7 且含 2/5/6/9 的数的个数; 但不难在本题数据范围很小, 预处理一个暴力就好.

实现

static constexpr int N = 1e4;
static int good[N + 10];
int init = []() {
    auto check = [](int x) -> bool {
        bool ok = false;
        for ( ; x > 0; x /= 10) {
            int last = x % 10;
            if (last == 3 || last == 4 || last == 7) return false;
            else if (last == 2 || last == 5 || last == 6 || last == 9) ok = true;
        }
        return ok;
    };

    for (int i = 1; i <= N; i++) {
        good[i] = good[i - 1] + check(i);
    }
    return 0;
} ();

class Solution {
public:
    int rotatedDigits(int n) {
        return good[n];
    }
};

力扣每日一题796-旋转字符串

日期：2026-05-03

题意

给定俩字符串 s 与 goal. 每次操作可是的 s 循环左移一位, 问任意次操作后是否可使得两字符串相等.

思路

循环位移后相等, 那直接将两个 s 拼在一起, 其子串一定包含所有情况, 再找其内子串是否包含目标即可. 这里正解应该是 KMP, 但是注意到数据范围并不大, 所以偷懒选择了暴力.

实现

class Solution {
public:
    bool rotateString(string s, string goal) {
        return s.size() == goal.size() && (s + s).contains(goal);
    }
};

力扣每日一题48-旋转图像

日期：2026-05-04

题意

给定二维整数方形矩阵 matrix, 请在原地顺时针旋转该矩阵 90°.

思路

顺时针旋转是有技巧的, 不过我这里偷懒直接进行了一个四指针模拟.

实现

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        const int n = matrix.size();
        const int t = n / 2;
        for (int i = 0; i < t; i++) {
            int x1 = i, y1 = i;
            int x2 = i, y2 = n - i - 1;
            int x3 = n - i - 1, y3 = n - i - 1;
            int x4 = n - i - 1, y4 = i;
            for ( ; y1 < n - i - 1; ) {
                int num = matrix[x1][y1];
                matrix[x1][y1] = matrix[x4][y4];
                matrix[x4][y4] = matrix[x3][y3];
                matrix[x3][y3] = matrix[x2][y2];
                matrix[x2][y2] = num;
                y1++; x2++; y3--; x4--;
            }
        }
    }
};

力扣每日一题61-旋转链表

日期：2026-05-05

题意

给定链表头以及非负整数 k, 返回该链表循环右移 k 位后的链表.

思路

需要记录头节点 尾节点与倒数第 k 个节点, 首尾相连后从倒数第 k 个处断开. 但需注意 k 可能很大, 因此先得到总长取余后再做寻点.

实现

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (head == nullptr) return nullptr;
        int len = 1;
        ListNode* cur = head;
        for ( ; cur->next != nullptr; cur = cur->next, len++);
        cur->next = head;

        k %= len;
        k = len - k - 1;
        cur = head;
        for (int i = 0; i < k; i++, cur = cur->next); 
        ListNode* ans = cur->next;
        cur->next = nullptr;
        return ans;
    }
};

力扣每日一题1861-旋转盒子

日期：2026-05-06

题意

给定二维矩阵表示一个包含 石头 障碍 空格 的盒子. 将其顺时针旋转九十度, 受重力影响石头会下坠直到碰到另一石头或障碍, 返回其最终形态.

思路

没什么特别的, 就按照题意将所有石头右移直到碰到石头或另一障碍, 再进行旋转操作即可. 或先旋转再按题意完成下移操作也是一样的.

实现

class Solution {
public:
    vector<vector<char>> rotateTheBox(vector<vector<char>>& boxGrid) {
        int n = boxGrid.size(), m = boxGrid.back().size();
        vector ans(m, vector<char> (n, '.'));
        for (int i = 0; i < n; i++) {
            int last = m - 1;
            for (int j = m - 1; j >= 0; j--) {
                if (boxGrid[i][j] == '*') {
                    ans[j][n - i - 1] = '*';
                    last = j - 1;
                } else if (boxGrid[i][j] == '#') {
                    ans[last][n - i - 1] = '#';
                    last--;
                }
            }
        }
        return ans;
    }
};

力扣每日一题3660-跳跃游戏IX

日期：2026-05-07

题意

给定正整数数组 nums, 每次操作可以从每个位置向左跳到更大值, 也可以向右跳到更小值. 试问从每个位置出发, 任意操作次数后所能到达的最大值.

思路

显然当左边最大值仍小于右边最小值时, 当前位置答案为左侧最大值; 其余情况应与右侧相邻数答案一致. 进行一个 dp 即可.

实现

class Solution {
public:
    vector<int> maxValue(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans(n), pre(n);
        for (int i = 0; i < n; i++) {
            pre[i] = nums[i];
            if (i) pre[i] = max(pre[i], pre[i - 1]);
        }

        int suf = INT_MAX;
        for (int i = n - 1; i >= 0; i--) {
            if (pre[i] <= suf) ans[i] = pre[i];
            else ans[i] = ans[i + 1];
            suf = min(suf, nums[i]);
        }
        return ans;
    }
};

力扣每日一题3629-通过质数传送到达终点的最少跳跃次数

日期：2026-05-08

题意

给定一维正整数数组 nums, 初始位于下标 0, 目标为最后一个元素. 每次操作可以选择向左或右移动到相邻格, 或若当前数为质数则可传送至任意当前数的倍数. 求问到达目标所需最少操作次数.

思路

显然是进行一个质因子分解建图, 然后 bfs 即可. 但这里我赛时写的, 不知道为啥一直 TLE MLE, 就一通乱改成这样了.

实现

class Solution {
public:
    vector<int> get(int x) {
        vector<int> f;
        for (int i = 2; i * i <= x; i++) {
            if (x % i == 0) {
                f.push_back(i);
                while (x % i == 0) x /= i;
            }
        }
        if (x > 1) f.push_back(x);
        return f;
    }
    int minJumps(vector<int>& nums) {
        const int n = nums.size();
        int mx = ranges::max(nums);
        unordered_map<int, vector<int>> adj;
        for (int i = 0; i < n; i++) {
            for (auto p : get(nums[i])) {
                adj[p].push_back(i);
            }
        }

        queue<array<int, 2>> q;
        q.push({0, 0});
        vector<bool> ans(n);
        unordered_set<int> ust;
        while (!q.empty()) {
            auto [u, t] = q.front();
            q.pop();
            if (ans[u]) continue;
            if (u == n - 1) return t;
            ans[u] = true;
            if (u - 1 >= 0 && !ans[u - 1]) q.push({u - 1, t + 1});
            if (u + 1 < n && !ans[u + 1]) q.push({u + 1, t + 1});
            if (get(nums[u]).size() ==  1 && !ust.count(nums[u])) {
                for (const auto& v : adj[nums[u]]) {
                    if (!ans[v]) {
                        q.push({v, t + 1});
                    }
                }
                ust.insert(nums[u]);
                adj[nums[u]].clear();
            }
        }
        return n - 1;
    }
};

力扣每日一题1914-循环轮转矩阵

日期：2026-05-09

题意

给定二维矩阵, 将其每层逆时针旋转 k 次, 返回结果.

思路

没什么特别的, 进行一个模拟就好.

实现

class Solution {
public:
    vector<vector<int>> rotateGrid(vector<vector<int>>& grid, int k) {
        int n = grid.size(), m = grid.back().size();
        vector<int> p((n + m) * 2);
        
        int t = min(n, m) / 2;
        for (int x = 0; x < t; x++) {
            int tn = n - x, tm = m - x;
            int loc = 0;
            for (int i = x; i < tm; i++) p[loc++] = grid[x][i];
            for (int i = x + 1; i < tn; i++) p[loc++] = grid[i][tm - 1];
            for (int i = tm - 2; i >= x; i--) p[loc++] = grid[tn - 1][i];
            for (int i = tn - 2; i > x; i--) p[loc++] = grid[i][x];

            int j = k % loc;
            reverse(p.begin(), p.begin() + j);
            reverse(p.begin() + j, p.begin() + loc);
            reverse(p.begin(), p.begin() + loc);
            
            loc = 0;
            for (int i = x; i < tm; i++) grid[x][i] = p[loc++];
            for (int i = x + 1; i < tn; i++) grid[i][tm - 1] = p[loc++];
            for (int i = tm - 2; i >= x; i--) grid[tn - 1][i] = p[loc++];
            for (int i = tn - 2; i > x; i--) grid[i][x] = p[loc++];
        }
        return grid;
    }
};

力扣每日一题2770-达到末尾下标所需的最大跳跃次数

日期：2026-05-10

题意

给定整数数组 nms 与 非负整数 target, 初始位于下标 0, 目标为数组尾, 每次移动可以跳到满足 i < j && -target <= nums[j] - nums[i] <= target 条件的下标 j. 求问所需最多的跳跃次数.

思路

每个位置可以由左侧在一个值域内的数得来, 贪心地应该选择其中的最大值. 显然是一个单点改区间查最大值的问题, 可以想到用线段树. 但注意到数据范围 2 <= len(nums) <= 1e3 && -1e9 <= nums[i] <= 1e9, 开线段树要先离散化, 同时数组长可以直接进行一个暴力. 因此直接选择进行一个平方级别的 dp.

实现

class Solution {
static constexpr int inf = 1e9;
public:
    int maximumJumps(vector<int>& nums, int target) {
        int n = nums.size();
        vector<int> ans(n, -inf);
        ans[0] = 0;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (abs(nums[i] - nums[j]) <= target) ans[i] = max(ans[i], ans[j] + 1);
            }
        }
        return ans.back() < 0 ? -1 : ans.back();
    }
};

力扣每日一题2553-分割数组中数字的数位

日期：2026-05-11

题意

给定正整数数组 nums, 将其每个数按数位拆分后按顺序返回.

思路

依题意进行一个模拟即可.

实现

class Solution {
public:
    vector<int> separateDigits(vector<int>& nums) {
        int n = nums.size();
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            string s = to_string(nums[i]);
            for (auto& ch : s) ans.push_back(ch - '0');
        }
        return ans;
    }
};

力扣每日一题1665-完成所有任务的最少初始能量

日期：2026-05-12

题意

给定任务数组 task[i] = [actual_i, minimum_i], 表示多个任务实际需要消耗的能量, 以及开始该任务至少需要多少能量. 可以按任意顺序完成任务, 求所需的最少能量.

思路

应该是进行一个排序, 然后贪心地去完成即可.

实现

class Solution {
public:
    int minimumEffort(vector<vector<int>>& tasks) {
        int n = tasks.size();
        int ans = 0;

        ranges::sort(tasks, [&](const auto& x, const auto& y) {
            return x[0] - x[1] < y[0] - y[1];
        });
        for (int i = 0, t = 0; i < n; i++) {
            ans = max(ans, t + tasks[i][1]);
            t += tasks[i][0];
        }

        return ans;
    }
};

力扣每日一题1674-使数组互补的最少操作次数

日期：2026-05-13

题意

给定偶长的正整数数组 nums[i], 每次操作可任选一个数将其变为 [1, limit] 范围内的整数. 求使得 nums[i] + nums[len(nums) - 1 - i] 结果均相等所需的最少操作次数. 保证 1 <= nums[i] <= limit <= 1e5

思路

为方便记 nums[i] 与 nums[len(nums) - 1 - i] 中的较小数为 X 较大数为 Y. 显然对于令两者和为区间 [X + 1, X + limit] 与 [Y + 1, Y + limit] 的数所需操作次数为 1, 但需要注意由于 X >= 1 && Y <= limit 这两个区间是必定有交的, 且和为 X + Y 所需操作次数为 0; 其余区间所需操作次数为 2. 由此可以发现是很多个区间加问题, 由此可以想到用差分.

实现

class Solution {
public:
    int minMoves(vector<int>& nums, int limit) {
        int n = nums.size();
        int m = limit * 2;
        vector<int> f(m + 2);
        f[2] = n;
        for (int i = 0, j = n - 1; i < j; i++, j--) {
            int x = nums[i], y = nums[j];
            if (x > y) swap(x, y);
            f[x + 1]--;
            f[y + limit + 1]++;
            f[x + y]--;
            f[x + y + 1]++;
        }

        int ans = n;
        for (int i = 2; i <= m; i++) {
            f[i] += f[i - 1];
            ans = min(ans, f[i]);
        }
        return ans;
    }
};

力扣每日一题2784-检查数组是否是好的

日期：2026-05-14

题意

给定正整数数组 nums, 判断其是否包含 [1, len(nums)] 范围内的所有数, 且除 len(nums) 出现两次外其余数均出现且仅出现一次.

思路

实现

class Solution {
public:
    bool isGood(vector<int>& nums) {
        ranges::sort(nums);
        int n = nums.size();
        if (nums.back() != n - 1) return false;
        for (int i = n - 2; i >= 0; i--) {
            if (nums[i] != i + 1) return false;
        }
        return true;
    }
};

力扣每日一题153-寻找旋转排序数组中的最小值

日期：2026-05-15

题意

给定一个被循环右移一定次数的升序数组 nums, 求其最小值, 期望复杂度为 log(len(nums))

思路

那应该就是进行一个二分, 只是 mid 应与最后一个值比较, 我们手玩一下不难想到 check 方法.

实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = lo + hi >> 1;
            if (nums[mid] > nums.back()) {
                lo = mid + 1;
            } else {
                hi = mid;
            }
        }
        return nums[lo];
    }
};

力扣每日一题154-寻找旋转排序数组中的最小值II

日期：2026-05-16

题意

给定一个被循环右移一定次数的非严格升序数组 nums, 求其最小值, 期望复杂度为 log(len(nums))

思路

只是比昨天的条件多了个数组内可能有重复值的条件, 那还是一样的思路, 仅相等值时特殊处理.

实现

class Solution {
public:
    int findMin(vector<int>& nums) {
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = (lo + hi) / 2;
            if (nums[mid] == nums[hi]) hi--;
            else if (nums[mid] > nums[hi]) lo = mid + 1;
            else hi = mid;
        }
        return nums[lo];
    }
};

力扣每日一题1306-跳跃游戏III

日期：2026-05-17

题意

给定非负整数数组 arr, 初始位于下标 start, 当位于下标 i 时可以选择跳到下标 i + arr[i] 或 i - arr[i]. 求问是否可以到达任意值为零的下标处.

思路

依题意进行一个搜即可, 很常规.

实现

class Solution {
public:
    bool canReach(vector<int>& arr, int start) {
        int n = arr.size();
        vector<bool> vis(n);
        vector<int> q{start};
        for (int i = 0; i < q.size(); i++) {
            int x = q[i];
            if (vis[x]) continue;
            vis[x] = true;
            if (arr[x] == 0) return true;
            int nxt = x + arr[x];
            if (nxt >= 0 && nxt < n && !vis[nxt]) q.push_back(nxt);
            nxt = x - arr[x];
            if (nxt >= 0 && nxt < n && !vis[nxt]) q.push_back(nxt);
        }
        return false;
    }
};

力扣每日一题1345-跳跃游戏IV

日期：2026-05-18

题意

给定正整数数组 arr, 初始位于下标 0, 目标为最后一个下标. 每次操作可以选择向左或向右移动到相邻格, 或选择跳跃到与当前所在格元素值相同的位置. 求问所需最小操作数.

思路

那实际就是类昨天的题加上跳跃到相同元素操作的题嘛, 同样是进行一个搜索就好, 我们应该是有做过很多次类似的题的.

实现

class Solution {
public:
    int minJumps(vector<int>& arr) {
        int n = arr.size();
        vector<int> dis(n, n - 1);
        dis[0] = 0;
        unordered_map<int, vector<int>> pos;
        unordered_set<int> p;
        for (int i = 0; i < n; i++) pos[arr[i]].push_back(i);

        queue<int> q;
        q.push(0);
        while (!q.empty()) {
            int x = q.front();
            q.pop();
            int nxt = x - 1;
            if (nxt >= 0 && nxt < n && dis[nxt] > dis[x] + 1) {
                q.push(nxt);
                dis[nxt] = dis[x] + 1;
            }
            nxt = x + 1;
            if (nxt >= 0 && nxt < n && dis[nxt] > dis[x] + 1) {
                q.push(nxt);
                dis[nxt] = dis[x] + 1;
            }

            if (!p.count(arr[x])) {
                p.insert(arr[x]);
                for (int v : pos[arr[x]]) {
                    if (dis[v] > dis[x] + 1) {
                        q.push(v);
                        dis[v] = dis[x] + 1;
                    }
                }
            }
        }

        return dis.back();
    }
};

力扣每日一题2540-最小公共值

日期：2026-05-19

题意

给定两个非降序整数数组 nums1 与 nums2, 求两数组的最小公共数.

思路

既然两数组有序, 进行一个双指针遍历即可.

实现

class Solution {
public:
    int getCommon(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        for (int i = 0, j = 0; i < n && j < m; ) {
            if (nums1[i] == nums2[j]) return nums1[i];
            else if (nums1[i] < nums2[j]) i++;
            else j++;
        }
        return -1;
    }
};

力扣每日一题2657-找到两个数组的前缀公共数组

日期：2026-05-20

题意

给定等长排列数组 A 与 B, 求这两数组的前缀公共数组.

思路

那进行一个哈哈的希用来记录各数组前缀出现过的数, 再求一下公共即可.

实现

class Solution {
using ull = unsigned long long;
public:
    vector<int> findThePrefixCommonArray(vector<int>& A, vector<int>& B) {
        int n = A.size();
        ull a = 0, b = 0;
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            a |= 1ll << A[i];
            b |= 1ll << B[i];
            ans[i] = popcount(a & b);
        }
        return ans;
    }
};

力扣每日一题3043-最长公共前缀的长度

日期：2026-05-21

题意

给定两正整数数组 arr1 与 arr2, 求两数组任出一数所组成的数对的最长公共前缀长度.

思路

求公共前缀可以想到给 arr1 建棵 trie, 然后 arr2 逐元素遍历 trie 即可.

实现

class Solution {
public:
    int longestCommonPrefix(vector<int>& arr1, vector<int>& arr2) {
        vector<array<int, 10>> trie(arr1.size() * 10);
        int tot = 0;
        for (int x : arr1) {
            string s = to_string(x);
            int u = 0;
            for (auto& ch : s) {
                int& v = trie[u][ch - '0'];
                if (v == 0) v = ++tot;
                u = v;
            }
        }

        int ans = 0;
        for (int x : arr2) {
            string s = to_string(x);
            int res = 0, u = 0;
            for (auto& ch : s) {
                int v = trie[u][ch - '0'];
                if (v == 0) break;
                u = v;
                res++;
            }
            ans = max(ans, res);
        }
        return ans;
    }
};

力扣每日一题33-搜索旋转排序数组

日期：2026-05-22

题意

给定被循环右移一定次数的升序数组 nums, 试问该数组内是否含数 target 若含返回其下标, 期望复杂度为 log(len(nums))

思路

那题意和 15 号的是几乎差不多的, 进行一个二二的分即可.

实现

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int lo = 0, hi = nums.size() - 1;
        while (lo < hi) {
            int mid = lo + hi >> 1;
            if (nums[mid] > nums.back()) {
                if (target > nums[mid]) lo = mid + 1;
                else if (target <= nums.back()) lo = mid + 1;
                else hi = mid;
            } else {
                if (target <= nums[mid]) hi = mid;
                else if (target > nums.back()) hi = mid;
                else lo = mid + 1;
            }
        }
        return nums[lo] == target ? lo : -1;
    }
};

力扣每日一题1752-检查数组是否经排序和轮转得到

日期：2026-05-23

题意

给定一正整数数组 nums, 判断其是否可以通过相同元素组成的非降序数组循环左右移得到.

思路

一个非降序数组循环左右移动, 则变为两段非降序数组且首段头必然大于等于尾端尾. 写一个状态机好了.

实现

class Solution {
public:
    bool check(vector<int>& nums) {
        int n = nums.size();
        int ok = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] < nums[i - 1]) {
                if (ok == 0) {
                    if (nums[0] >= nums.back()) ok = 1;
                    else {
                        ok = -1;
                        break;
                    }
                } else {
                    ok = -1;
                    break;
                }
            }
        }
        return ok != -1;
    }
};

力扣每日一题1340-跳跃游戏V

日期：2026-05-24

题意

给定整数数组 arr 与一个正整数 d. 每步操作可从当前位置 i 跳到满足 i - d <= x <= i + d 且 i 到 x 之间所有数均小于 arr[i] 的位置 x. 可任选一处出发, 求问可访问的最多下标个数.

思路

注意到数据范围实在不很大 1 <= len(arr) <= 1000, 那其实怎么乱搞都是可以的, 这里为了方便就换 python 写了个记搜.

实现

class Solution:
    def maxJumps(self, arr: List[int], d: int) -> int:
        n = len(arr)

        @cache
        def dfs(x):
            res = 1
            for i in range(x + 1, min(x + d + 1, n)):
                if arr[i] >= arr[x]:
                    break
                res = max(res, dfs(i) + 1)
            for i in range(x - 1, max(x - d - 1, -1), -1):
                if (arr[i] >= arr[x]):
                    break
                res = max(res, dfs(i) + 1)
            return res
        return max(dfs(x) for x in range(n))

力扣每日一题1871-跳跃游戏VII

日期：2026-05-25

题意

给定二进制字符 s 以及两个正整数 minJump 与 maxJump. 在 s 上做跳跃, 位于下标 i 时可以跳到 [i + minJump, i + maxJump] 范围内的字符 ‘0’ 处. 初始位于下标 0, 问是否可以到达最后一个字符处.

思路

i 可以跳到 [i + minJump, i + maxJump], 换言而止 i 可以由 [i - maxJump, i - minJump] 之间的 0 处来到, 也就是说这个区间内只要有一点可达则 i 可达, 维护区间是否有可达点, 可以想到用区间和维护, 区间和就可以想到用前缀和来做.

实现

class Solution {
public:
    bool canReach(string s, int minJump, int maxJump) {
        int n = s.size();
        vector<int> pre(n + 1);
        pre[1] = 1;
        for (int i = 0; i < n; i++) {
            int t = s[i] == '0' && pre[max(0, i - minJump + 1)] > pre[max(0, i - maxJump)];
            pre[i + 1] += pre[i] + t;
        }
        return pre[n] > pre[n - 1];
    }
};

力扣每日一题3120-统计特殊字母的数量I

日期：2026-05-26

题意

给定字符串 word, 统计其中大小写均出现过的字母的个数.

思路

进行一个哈希记录就好.

实现

class Solution {
static constexpr int N = 26;
public:
    int numberOfSpecialChars(string word) {
        array<int, N> vis;
        vis.fill(0);
        for (auto& ch : word) {
            if (isupper(ch)) vis[ch - 'A'] |= 2;
            else vis[ch - 'a'] |= 1;
        }
        return ranges::count(vis, 3);
    }
};

力扣每日一题3121-统计特殊字母的数量II

日期：2026-05-27

题意

给定字符串 word, 统计其中大小写均出现过且所有小写均出现在对应大写字母之前的字母的个数.

思路

昨天的题目加上小写均在大写前的条件, 那还是进行一个哈希就好, 只是加上了一个类似于状态机的判断.

实现

class Solution {
static constexpr int N = 26;
public:
    int numberOfSpecialChars(string word) {
        array<int, N> vis;
        vis.fill(0);
        for (auto& ch : word) {
            if (isupper(ch)) vis[ch - 'A'] |= 2;
            else if (vis[ch - 'a'] & 2) vis[ch - 'a'] = 4;
            else vis[ch - 'a'] |= 1;
        }
        return ranges::count(vis, 3);
    }
};

力扣每日一题3093-最长公共后缀查询

日期：2026-05-28

题意

给定俩字符串数组 wordsContainer 与 wordsQuery, 求问对于 wordsQuery 中的每个字符串, wordsContainer 中哪个字符串与其有最长的公共后缀. 若有多个候选结果, 返回最短且最早出现的那一个.

思路

最长公共后缀应该是没学过什么的, 但翻转每个字符串就变成了最长公共前缀, 可以想到先对所有字符串按长度与先后顺序进行排序, 然后建棵字典树, 然后顺序查询即可.

实现

static constexpr int N = 5e6;
vector<array<int, 27>> trie(N);
static int tot = 0;
void init() {
    tot = 0;
    trie[0].fill(0);
}
void add(string& s, int loc) {
    int u = 0;
    for (auto& ch : s) {
        int& v = trie[u][ch - 'a'];
        if (v == 0) {
            v = ++tot;
            trie[v].fill(0);
            trie[v][26] = loc;
        }
        u = v;
    }
}
int query(string& s) {
    int u = 0, res = -1;
    for (auto& ch : s) {
        int& v = trie[u][ch - 'a'];
        if (v == 0) break;
        res = trie[v][26];
        u = v;
    }
    return res;
}

class Solution {
public:
    vector<int> stringIndices(vector<string>& wordsContainer, vector<string>& wordsQuery) {
        init();
        int n = wordsContainer.size(), q = wordsQuery.size();
        vector<int> p(n), ans(q);
        ranges::iota(p, 0);
        ranges::sort(p, [&](int x, int y) {
            if (wordsContainer[x].size() != wordsContainer[y].size()) return wordsContainer[x].size() < wordsContainer[y].size();
            return x < y;
        });
        for (auto& i : p) {
            ranges::reverse(wordsContainer[i]);
            add(wordsContainer[i], i);
        }
        for (int i = 0; i < q; i++) {
            ranges::reverse(wordsQuery[i]);
            int res = query(wordsQuery[i]);
            ans[i] = res == -1 ? p[0] : res;
        }
        return ans;
    }
};

力扣每日一题3300-替换为数位和以后的最小元素

日期：2026-05-29

题意

给定整数数组 nums, 将其每位数转换为各数位之和, 求转换后数组内的最小值.

思路

按题意进行转换后取最小即可.

实现

class Solution {
public:
    int minElement(vector<int>& nums) {
        int ans = INT_MAX;
        for (int& x : nums) {
            int res = 0;
            for ( ; x > 0; x /= 10) res += x % 10;
            ans = min(ans, res);
        }
        return ans;
    }
};

力扣每日一题3161-物块放置查询

日期：2026-05-30

题意

在一无限长数轴上操作, 给定一组询问, 含两种操作: 操作一为在指定位置插入一块无体积的障碍物; 操作二查询原点到指定位置之间是否可以放得下长度为 sz 的物体, 仅查询不放置. 返回所有操作二的查询结果.

思路

那每次询问就是求最长区间长度是否大于等于 sz. 可以想到使用线段数进行连续区间长度的维护. 这里线段树板子是我较早时期写的, 为 1-index 但我又懒得新写了…

实现

template<class T>
struct SegmentTree {
    static int n;
    vector<T> a, tr1;
    SegmentTree(int x) {
        n = x;
        a.resize(x + 1);
        tr1.resize((x + 1) << 2);
    }
 
    void set(int i, T x) {
        a[i] = x;
    }
    void build(int p = 1, int l = 1, int r = n) {
        if (l == r) {
            tr1[p] = a[l];
            return;
        }
        int mid = (l + r) / 2;
        build(p << 1, l, mid);
        build(p << 1 | 1, mid + 1, r);
        tr1[p] = max(tr1[p << 1], tr1[p << 1 | 1]);
    }
    void update(int l, int r, T x, int p = 1, int cl = 1, int cr = n) {
        if (cl == cr) {
            tr1[p] = x;
            return;
        }
        int mid = (cl + cr) / 2;
        if (l <= mid) update(l, r, x, p << 1, cl, mid);
        if (r > mid) update(l, r, x, p << 1 | 1, mid + 1, cr);
        tr1[p] = max(tr1[p << 1], tr1[p << 1 | 1]);
        return;
    }
    T query(int l, int r, int p = 1, int cl = 1, int cr = n) {
        if (cl >= l && cr <= r) {
            return tr1[p];
        }
        int mid = (cl + cr) / 2;
        T ans = numeric_limits<T>::lowest();
        if (l <= mid) {
            ans = max(ans, query(l, r, p << 1, cl, mid));
        }
        if (r > mid) {
            ans = max(ans, query(l, r, p << 1 | 1, mid + 1, cr));
        }
        return ans;
    }
};

template<class T>
int SegmentTree<T>::n = 0;

class Solution {
public:
    vector<bool> getResults(vector<vector<int>>& queries) {
        int mx = 0;
        for (auto& q : queries) mx = max(mx, q[1]);
        mx++;
        SegmentTree<int> StT(mx + 1);
        StT.set(1, 0);
        StT.set(mx + 1, mx);
        StT.build();
        set<int> st{0, mx};

        vector<bool> ans;
        for (auto& q : queries) {
            int op = q[0], x = q[1];
            if (op == 1) {
                auto it = st.lower_bound(x);
                int l = *prev(it), r = *it;
                st.insert(x);
                StT.update(x + 1, x + 1, x - l);
                StT.update(r + 1, r + 1, r - x);
            } else {
                int sz = q[2];
                auto it = st.lower_bound(x);
                int l = *prev(it);
                int res = max(StT.query(1, l + 1), x - l);
                ans.push_back(res >= sz);
            }
        }
        return ans;
    }
};

力扣每日一题2126-摧毁小行星

日期：2026-05-31

题意

给定正整数 mass 表示行星初始质量, 给定正整数数组 asteroids 表示一堆小行星质量; 可任意调整小行星撞向行星的顺序, 若某小行星质量小于等于行星, 则小行星被摧毁且行星质量增加相应值, 反之行星则被摧毁. 求问是否可将所有小行星摧毁.

思路

显然进行一个贪贪的心, 从小到达开撞就好.

实现

class Solution {
public:
    bool asteroidsDestroyed(int mass, vector<int>& asteroids) {
        ranges::sort(asteroids);
        for (auto& x : asteroids) {
            if (x > mass) return false;
            mass += x;
            if (mass >= asteroids.back()) return true;
        }
        return true;
    }
};