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

目录

力扣每日一题486-预测赢家

日期：2026-08-01

题意

给定整数数组 nums, 两位玩家轮流从其首或尾取数, 定义若最终先手玩家所取数之和大于等于另一玩家则称先手玩家获胜, 求问先手玩家是否必胜.

思路

好像没什么好的性质, 直接继续一个搜索吧.

实现

class Solution {
static constexpr int inf = 1e9;
public:
    bool predictTheWinner(vector<int>& nums) {
        int n = nums.size();
        vector vis(n, vector<int> (n, -inf));

        auto dfs = [&](this auto&& self, int l, int r) -> int {
            if (l > r) return 0;
            int& res = vis[l][r];
            if (res != -inf) return res;
            res = max(nums[l] - self(l + 1, r), nums[r] - self(l, r - 1));
            return res;
        };
        
        return dfs(0, n - 1) >= 0;
    }
};

力扣每日一题877-石子游戏

日期：2026-08-02

题意

给定正整数数组 piles 表示正偶数堆石子, 同时保证石子总数量为奇数. 两名玩家轮流从首或尾取走一堆石子, 最终总石子数多的玩家获胜. 求问是否先手必胜.

思路

那不是和昨天的题目完全一样吗, 仅需一个搜即可.
但注意到我的耗时表现并不佳, 查看别人题解发现: 保证有正偶数堆石子且总石子为奇数, 那么奇数位下标和与偶数位下标和必定不等, 且先手玩家存在策略必可全取大的那一部分.

实现

class Solution {
static constexpr int inf = 1e9;
public:
    bool stoneGame(vector<int>& piles) {
        int n = piles.size();
        vector vis(n, vector<int> (n, -inf));
        
        auto dfs = [&](this auto&& self, int l, int r) -> int {
            if (l > r) return 0;
            int& res = vis[l][r];
            if (res != -inf) return res;
            res = max(piles[l] - self(l + 1, r), piles[r] - self(l, r - 1));
            return res;
        };

        return dfs(0, n - 1) > 0;
    }
};

力扣每日一题1406-石子游戏III

日期：2026-08-03

题意

给定整数数组 nums, 表示多堆石子. 玩家轮流从首部取 1/2/3 堆石子直到取尽, 最终总石子数多的玩家胜利. 求问胜者.

思路

那和前两天的题意是很类似的呀, 只是从可从首尾取变成了仅从首部取, 以及单次可取多堆. 那还是不断地将问题变得更小, 那还是进行一个搜索就好.

实现

class Solution {
static constexpr int inf = 1e9;
public:
    string stoneGameIII(vector<int>& stoneValue) {
        int n = stoneValue.size();
        vector<int> vis(n, -inf);

        auto dfs = [&](this auto&& self, int u) -> int {
            if (u >= n) return 0;
            int& res = vis[u];
            if (res != -inf) return res;
            for (int i = 1, t = stoneValue[u]; i <= 3; i++) {
                res = max(res, t - self(u + i));
                t += u + i < n ? stoneValue[u + i] : 0;
            }
            return res;
        };

        int res = dfs(0);
        if (res == 0) return "Tie";
        return res > 0 ? "Alice" : "Bob";
    }
};

力扣每日一题3731-找出缺失的元素

日期：2026-08-04

题意

给定互不相同的正整数数组 nums, 表示缺失了未知数量的某个区间的所有数, 在保证最大最小值未缺失的情况下, 求问缺失了哪些数.

思路

那进行一个排序然后按序检查即可.

实现

class Solution {
public:
    vector<int> findMissingElements(vector<int>& nums) {
        int n = nums.size();
        ranges::sort(nums);
        vector<int> ans;
        for (int i = 0, cur = nums[0]; i < n; i++, cur++) {
            for ( ; cur < nums[i]; cur++) ans.push_back(cur);
        }
        return ans;
    }
};

力扣每日一题3310-移除可疑的方法

日期：2026-08-05

题意

给定一个有向图表示各个方法之间的调用关系. 已知方法 k 存在问题, 其直接或间接调用的方法均可能有问题, 若可以删除所有可疑方法则返回剩余的方法; 反之若无法删除所有可疑方法则返回所有方法.

思路

换句话说就是不能有非可疑方法节点指向可疑方法. 做一个 bfs/dfs 找到所有可疑方法, 然后去掉它们的出边, 若还有可疑方法点入度不为 0 则不可删; 反之可删除所有可疑节点.

实现

class Solution {
public:
    vector<int> remainingMethods(int n, int k, vector<vector<int>>& invocations) {
        vector<int> d(n), ok(n, 1), vis(n);
        vector<vector<int>> adj(n);
        for (auto& e : invocations) {
            int u = e[0], v = e[1];
            d[v]++;
            adj[u].push_back(v);
        }

        vector<int> res;
        queue<int> q;
        q.push(k);
        while (!q.empty()) {
            int u = q.front();
            q.pop();
            if (vis[u]) continue;
            vis[u] = 1;
            res.push_back(u);
            for (auto& v : adj[u]) {
                d[v]--;
                if (!vis[v]) q.push(v);
            }
        }

        for (auto& x : res) {
            if (d[x]) {
                vector<int> ans(n);
                ranges::iota(ans, 0);
                return ans;
            }
            ok[x] = 0;
        }
        vector<int> ans;
        for (int i = 0; i < n; i++) {
            if (ok[i]) ans.push_back(i);
        }

        return ans;
    }
};

力扣每日一题3345-最小可整除数位乘积I

日期：2026-08-06

题意

给定两个正整数 n 和 t, 求最小的大于等于 n 且各数位之积能被 t 整除的数.

思路

好像没什么性质, 这个数据范围也只能是想到枚举了.

实现

class Solution {
public:
    int smallestNumber(int n, int t) {
        for ( ; ; n++) {
            int p = 1;
            for (int i = n; i; i /= 10) p *= i % 10;
            if (p % t == 0) return n;
        }
        return -1;
    }
};

力扣每日一题3348-最小可整除数位乘积II

日期：2026-08-07

题意

给定字符串 num 表示一个正整数, 求大于等于该数的最小无零且各数位之积被 t 整除的数.

思路

各数位积要被 t 整除, 则 t 一定不含非个位数的质因数. 那好像进行一个类似于数位 dp 的操作进行枚举即可.

实现

class Solution {
using ll = long long;
public:
    string smallestNumber(string num, ll t) {
        int cnt = 0;
        ll temp = t;
        for (int x : {2, 3, 5, 7}) {
            for ( ; temp % x == 0; cnt++, temp /= x);
        }
        if (temp > 1) return "-1";

        int p0 = max(cnt - int(num.size()) + 1, 1);
        num = string(p0, '0') + num;
        int n = num.size();
        string ans(n, '0');
        vector<unordered_set<ll>> vis(n);
        auto dfs = [&](this auto&& self, int i, ll t, bool p) -> bool {
            if (i == n) return t == 1;
            if (!p && !vis[i].insert(t).second) return false;
            if (p && i < p0 && self(i + 1, t, p)) return true;
            int low = p ? num[i] - '0' : 0;
            for (int j = max(1, low); j < 10; j++) {
                if (self(i + 1, t / gcd(t, j), p && j == low)) {
                    ans[i] = char('0' + j);
                    return true;
                }
            }
            return false;
        };
        dfs(0, t, true);

        int i = 0;
        for ( ; i < ans.size() && ans[i] == '0'; i++);
        return ans.substr(i);
    }
};

力扣每日一题3302-字典序最小的合法序列

日期：2026-08-08

题意

给定两个字符串 word1 与 word2; 定义几乎相同字符串为至多修改一个字符即可相同的字符串; 求问 word1 中下标字典序最小的子序列是 word2 几乎相同字符串的下标数组.

思路

应该是做一个最长后缀匹配, 然后从前往后枚举修改位置.

实现

class Solution {
public:
    vector<int> validSequence(string word1, string word2) {
        int n = word1.size(), m = word2.size();
        vector<int> suf(n + 1);
        suf[n] = m;
        for (int i = n - 1, j = m - 1; i >= 0; i--) {
            if (j >= 0 && word1[i] == word2[j]) j--;
            suf[i] = j;
        }

        vector<int> ans;
        bool ok = true;
        for (int i = 0, j = 0; i < n; i++) {
            if (word1[i] == word2[j]) {
                ans.push_back(i);
                j++;
            } else if (ok && j >= suf[i + 1]) {
                ok = false;
                ans.push_back(i);
                j++;
            }
            if (j == m) return ans;
        }
        return {};
    }
};

力扣每日一题1140-石子游戏II

日期：2026-08-09

题意

给定正整数数组 piles 表示多堆石子, 初始 M=1, 每回合可以取走前 [1, 2M] 堆石子并令 M=max(M, 取走的堆数). 最终以总石子的数量多少定胜负, 求问先手玩家最多可获多少石子.

思路

和常见的轮流取数博弈没有太大的区别, 只是需要多一个状态条件记录当前的 M, 然后做一个 dfs 或 dp 即可.

实现

class Solution {
static constexpr int inf = 1e9;
public:
    int stoneGameII(vector<int>& piles) {
        int n = piles.size();
        vector vis(n, vector<int> (n, -inf));
        vector<int> p(n + 1);
        for (int i = 0; i < n; i++) p[i + 1] = p[i] + piles[i];

        auto dfs = [&](this auto&& self, int i, int m) -> int {
            if (i + 2 * m >= n) return p.back() - p[i];
            int& res = vis[i][m];
            if (res != -inf) return res;
            for (int x = 1; x <= 2 * m && i + x <= n; x++) {
                res = max(res, p[i + x] - p[i] - self(i + x, max(m, x)));
            }
            return res;
        };

        return (p.back() + dfs(0, 1)) / 2;
    }
};

力扣每日一题1510-石子游戏IV

日期：2026-08-10

题意

给定 n 颗石子, 轮流取走任意非零平方数个石子, 取走最后一颗石子的玩家获胜, 求问是否先手必胜.

思路

和之前写过的很多轮流取石子没有太大的区别, 进行一个 dfs 或者 dp 都是可以的. (若当前点仅能到达必胜点则该点为必败, 若能到达任意必败点则该点必胜).

实现

class Solution {
public:
    bool winnerSquareGame(int n) {
        vector<int> vis(n + 1, -1);
        auto dfs = [&](this auto&& self, int u) -> int {
            if (u <= 0) return 0;
            int& x = vis[u];
            if (x != -1) return x;
            for (int i = 1; i * i <= u; i++) {
                if (!self(u - i * i)) return x = 1;
            }
            return x = 0;
        };
        return dfs(n) == 1;
    }
};

力扣每日一题2996-大于等于顺序前缀和的最小缺失整数

日期：2026-08-11

题意

给定数组 nums, 若有 nums[:j] 均满足 nums[i] - nums[i - 1] == 1 则称其为顺序前缀. 求大于等于该数组最长顺序前缀和且该数组中没出现的最小整数.

思路

没啥好说的, 就按题意求最长顺序前缀和, 然后做个哈希找未出现的数即可.

实现

class Solution {
public:
    int missingInteger(vector<int>& nums) {
        unordered_set<int> cnt(nums.begin(), nums.end());

        int ans = nums.front();
        int n = nums.size();
        for (int i = 1; i < n; i++) {
            if (nums[i] - nums[i - 1] != 1) break;
            else ans += nums[i];
        }
        for ( ; cnt.count(ans); ans++);

        return ans;
    }
};

力扣每日一题2958-最多K个重复元素的最长子数组

日期：2026-08-12

题意

给定正整数数组 nums 与一个正整数 k, 求该数组中所有元素出现次数均小于等于 k 的最长子数组长度.

思路

那开一个哈希记录各元素出现次数, 然后做一个滑动窗口就好.

实现

class Solution {
public:
    int maxSubarrayLength(vector<int>& nums, int k) {
        unordered_map<int, int> cnt;
        int n = nums.size();
        int ans = 0;
        int p = 0;
        for (int l = 0, r = 0; r < n; r++) {
            int& t = cnt[nums[r]];
            t++;
            if (t > k) p++;
            else ans = max(ans, r - l + 1);

            for ( ; p && l < r; l++) {
                int& x = cnt[nums[l]];
                x--;
                if (x == k) p--;
            }
        }
        return ans;
    }
};

力扣每日一题2213-由单个字符重复的最长子字符串

日期：2026-08-13

题意

给定字符串 s, 以及两个长度相同的数组 queryCharacters 与 queryIndices 表示多个询问. 其中第 i 个询问表示持久化的将 s[queryIndices[i]] 修改为 queryCharacters[i] 后 s 中仅由单个字符组成的最长子字符串长度.

思路

那应该是一个比较经典的线段树问题, 我们需要维护每一块子字符串的 最(左/右)字符 最(左/右)仅由最(左/右)字符组成的最长子字符串长度 当前块长度 当前块最长答案. 然后手玩一下写一个对应的合并相邻块方法就好.

实现

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
};
struct Info {
    int L, R, left, right, len, mx;
};
Info operator+(Info a, Info b) {
    int tL = a.L, tR = b.R, tlen = a.len + b.len;
    int tleft = a.left, tright = b.right, tmx = max(a.mx, b.mx);
    if (a.R == b.L) {
        tmx = max(tmx, a.right + b.left);
        if (a.right == a.len) tleft = a.len + b.left;
        if (b.left == b.len) tright = a.right + b.len;
    }
    return Info{tL, tR, tleft, tright, tlen, tmx};
}

class Solution {
public:
    vector<int> longestRepeating(string s, string queryCharacters, vector<int>& queryIndices) {
        int n = s.size(), q = queryIndices.size();
        vector<int> ans(q);
        SegmentTree<Info> StT(n);
        for (int i = 0; i < n; i++) {
            int x = s[i] - 'a';
            StT.modify(i, Info{x, x, 1, 1, 1, 1});
        }

        for (int i = 0; i < q; i++) {
            int x = queryCharacters[i] - 'a';
            StT.modify(queryIndices[i], Info{x, x, 1, 1, 1, 1});
            ans[i] = StT.rangeQuery(0, n).mx;
        }

        return ans;
    }
};

力扣每日一题3090-每个字符最多出现两次的最长子字符串

日期：2026-08-14

题意

给定字符串 s, 求其中每个字符最多出现两次的最长子字符串的长度.

思路

那维护每个字符出现的次数做一个滑动窗口就好了.

实现

class Solution {
public:
    int maximumLengthSubstring(string s) {
        int ans = 0;
        int n = s.size();
        array<int, 26> cnt;
        cnt.fill(0);
        for (int l = 0, r = 0; r < n; r++) {
            if (++cnt[s[r] - 'a'] == 3) {
                for ( ; l < r; ) {
                    if (--cnt[s[l++] - 'a'] == 2) break;
                }
            }
            ans = max(ans, r - l + 1);
        }
        return ans;
    }
};

力扣每日一题3702-按位异或非零的最长子序列

日期：2026-08-15

题意

给定非负整数数组 nums, 求其最长异或和不为零的子序列长度.

思路

如果整个数组异或和不为零, 显然答案为数组长度; 若为零且含非零数则为数组长度减一 (全数组去掉任意非零数); 若为零且无非零数则为零.

实现

class Solution {
public:
    int longestSubsequence(vector<int>& nums) {
        int n = nums.size();
        int t = 0, p = 0;
        for (auto& x : nums) {
            t ^= x;
            p |= x != 0;
        }
        if (t != 0) return n;
        else if (p) return n - 1;
        else return 0;
    }
};

力扣每日一题2029-石子游戏IX

日期：2026-08-16

题意

给定正整数数组 stones 表示各个石子的价值. 两玩家轮流移除一个石子, 若某玩家某回合后所有已移除的石子价值和可以被 3 整除, 则该玩家落败; 若所有石子移除后仍未满足前一条件则先手玩家落败. 试问先手玩家是否必胜.

思路

导致被移除的石子总价值被 3 整除则落败, 那所有数都可以模 3 处理, 同时状态也可以压缩到三种: 模 3 余数为 0/1/2; 若状态为 1 选择 2 则失败, 若为 1 选择 1 则状态反转为 2; 若状态为 2 选择 1 则失败, 若为 2 选择 2 则状态反转为 1. 而任意状态下选择 0 均保持原状态.
开局无法选择 0, 其余情况下可以任意选 0; 接下来若状态非零则必选当前状态同数直到无数可选. 由此枚举先手玩家开局所选开始模拟一下即可.

实现

class Solution {
public:
    bool stoneGameIX(vector<int>& stones) {
        int n = stones.size();
        array<int, 3> cnt;
        cnt.fill(0);
        for (auto& x : stones) {
            cnt[x % 3]++;
        }

        if (cnt[1]) {
            int t = 1 + 2 * min(cnt[1] - 1, cnt[2]) + cnt[0] + (cnt[1] - 1 > cnt[2]);
            if (t < n && (t & 1)) return true;
        }
        if (cnt[2]) {
            int t = 1 + 2 * min(cnt[2] - 1, cnt[1]) + cnt[0] + (cnt[2] - 1 > cnt[1]);
            if (t < n && (t & 1)) return true;
        }
        return false;
    }
};

力扣每日一题1563-石子游戏V

日期：2026-08-17

题意

给定正整数数组 stoneValue, 表示一行石头的价值. 每回合 Alice 将该行石头分为连续的两段. 若两段的价值和不同则丢弃掉价值较大的那段, 并得分较小段的分数和; 若两段价值和相同则由 Alice 选定丢弃某一段, 并得分另一段和. 游戏进行直到仅剩一颗石子. 求问 Alice 可得最大总分数.

思路

划分是本数组分为两段连续的子数组, 那每次操作后问题都变成了一个相同但更小的子问题. 很显然是满足 dfs/dp 的.

实现

class Solution {
public:
    int stoneGameV(vector<int>& stoneValue) {
        int n = stoneValue.size();
        vector<int> pre(n + 1);
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + stoneValue[i];
        }
        vector vis(n + 1, vector<int> (n + 1));
        
        auto dfs = [&](this auto&& self, int l, int r) -> int {
            if (r - l == 1) return 0;
            int& res = vis[l][r];
            if (res) return res;

            for (int i = l + 1; i < r; i++) {
                int L = pre[i] - pre[l];
                int R = pre[r] - pre[i];
                if (L == R) res = max(res, max(self(l, i), self(i, r)) + L);
                else if (L > R) res = max(res, self(i, r) + R);
                else res = max(res, self(l, i) + L);
            }
            return res;
        };
        return dfs(0, n);
    }
};

力扣每日一题3471-找出最大的几近缺失整数

日期：2026-08-18

题意

给定整数数组与一个整数 k. 若某个数仅在该数组中的所有长度为 k 的子数组中出现一次则称其为’几近缺失’数. 求该数组的最大几近缺失数.

思路

极端一点想, 若 k 与数组长度一致则显然所有数仅出现一次应选最大值; 若 k 为 1 则选仅出现一次且最大的数; 若 k 不为极端值则答案仅由可能为首尾端点, 再判断两数是否在数组中出现不止一次, 然后取可行的较大值即可.

实现

class Solution {
public:
    int largestInteger(vector<int>& nums, int k) {
        int n = nums.size();
        if (n == k) return ranges::max(nums);
        if (k == 1) {
            unordered_map<int, int> cnt;
            for (auto& x : nums) cnt[x]++;
            int ans = -1;
            for (auto [x, t] : cnt) {
                if (t == 1) ans = max(ans, x);
            }
            return ans;
        }
        if (nums.front() == nums.back()) return -1;
        int f = 1, g = 1;
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] == nums.front()) f = 0;
            if (nums[i] == nums.back()) g = 0;
        }
        if (f && g) return max(nums.front(), nums.back());
        else if (f) return nums.front();
        else if (g) return nums.back();
        return -1;
    }
};

力扣每日一题1386-安排电影院座位

日期：2026-08-19

题意

给定正整数 n 表示一个 n * 10 的电影院, 其中 reservedSeats 表示已被预订的位置. 若一个四人组仅能连续的坐 [2, 3, 4, 5]/[4, 5, 6, 7]/[6, 7, 8, 9], 问最多还可以坐多少个四人组.

思路

2~9 无预定的排可以坐两组; 若有预定但三个可选位其一均无预定则可坐一组; 数据范围不大, 仅有 10 列, 可以考虑用二进制位表示是否有约以简便计算.

实现

class Solution {
public:
    int maxNumberOfFamilies(int n, vector<vector<int>>& reservedSeats) {
        unordered_map<int, int> vis;
        for (auto& reserved : reservedSeats) {
            int r = reserved[0], s = reserved[1];
            if (s > 1 && s < 10) vis[r] |= 1 << s;
        }
        
        int ans = 2 * (n - vis.size());
        int p2345 = 4 | 8 | 16 | 32;
        int p4567 = 16 | 32 | 64 | 128;
        int p6789 = 64 | 128 | 256 | 512;
        for (auto [_, x] : vis) {
            int l = p2345 & x;
            int m = p4567 & x;
            int r = p6789 & x;
            if (l == 0 && r == 0) ans += 2;
            else if (l == 0 || m == 0 || r == 0) ans++;
        }
        return ans;
    }
};

力扣每日一题3069-将元素分配到两个数组中I

日期：2026-08-20

题意

给定整数数组 nums以及两个初始为空的数组 arr1 与 arr2; 将 nums 第一个数分配给 arr1 第二个数分配给 arr2. 此后若 arr1 的最后一个数大于 arr2 的最后一个数则将 nums 中下一个数插入 arr1 中; 反之插入到 arr2 中. 返回 arr1 + arr2.

思路

没啥意思, 直接按题意模拟就好.

实现

class Solution {
public:
    vector<int> resultArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> arr1{nums[0]}, arr2{nums[1]};
        for (int i = 2; i < n; i++) {
            if (arr1.back() > arr2.back()) arr1.push_back(nums[i]);
            else arr2.push_back(nums[i]);
        }
        arr1.insert(arr1.end(), arr2.begin(), arr2.end());
        return arr1;
    }
};

力扣每日一题3116-单面值组合的第K小金额

日期：2026-08-21

题意

给定正整数数组 coins 表示一些不同面额的硬币, 各面额硬币均可使用无限枚但不能组合不同面额的硬币, 求问可组成的金额中第 k 大的数是多少.

思路

如果给定一个值 x 问是第几大, 应该怎么做呢. 对于数 t 的倍数, 在 [1, x] 中应该是出现了 x // t 次; 但这么加和的话, 任意多数的公倍数均被我们重复计算了; 那应该是对任意数对组成的 lcm 的贡献做一个容斥, 即可得知 x 是第几大.
那以上就是 check 的方法, 就可以做一个二分.

实现

class Solution {
using ll = long long;
static constexpr ll inf = 1ll << 52;
public:
    ll findKthSmallest(vector<int>& coins, int k) {
        int n = coins.size();
        int p = 1 << n;
        vector<vector<ll>> nums(n + 1);
        for (int i = 1; i < p; i++) {
            ll t = 1;
            for (int j = 0; j < n; j++) {
                if (i >> j & 1) t = lcm(t, 1ll * coins[j]);
            }
            nums[popcount(1ull * i)].push_back(t);
        }

        auto check = [&](ll x) -> bool {
            ll cnt = 0;
            for (int i = 1, d = 1; i <= n; i++, d *= -1) {
                for (auto t : nums[i]) {
                    cnt += x / t * d;
                }
            }
            return cnt >= k;
        };

        ll lo = 1, hi = inf;
        while (lo < hi) {
            ll mid = (lo + hi) / 2;
            if (check(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
};

力扣每日一题3622-判断整除性

日期：2026-08-22

题意

给定正整数 n, 求问其是否可被其((各数位之和)与(各数位之积)的和)整除.

思路

求该数各数位之和与之积然后判断即可.

实现

class Solution {
public:
    bool checkDivisibility(int n) {
        int sum = 0, prod = 1;
        for (int t = n; t; t /= 10) {
            sum += t % 10;
            prod *= t % 10;
        }
        return n % (sum + prod) == 0;
    }
};

力扣每日一题1927-求和游戏

日期：2026-08-23

题意

给定偶长的数字字符串 num, 其中有部分数位为 ?. 两人轮流向问号中填数, 若最终字符左半段数位之和不等于右半段数位之和则先手玩家获胜, 反之后手玩家获胜. 求问是否为先手必胜.

思路

手玩了一下, 认为应该是仅和两侧之和差与两侧问号数之差有关, guess 了一个不太会证明的结论…

实现

class Solution {
public:
    bool sumGame(string num) {
        int n = num.size();
        n /= 2;
        int sum = 0, cnt = 0;
        for (int i = 0; i < n; i++) {
            if (num[i] == '?') cnt++;
            else sum += num[i] - '0';
            if (num[i + n] == '?') cnt--;
            else sum -= num[i + n] - '0';
        }
        return 2 * sum + 9 * cnt != 0;
    }
};

力扣每日一题1872-石子游戏VIII

日期：2026-08-24

题意

给定整数数组 stones 表示一排石子中各石子的价值; 两人轮流操作, 每次操作至少移除头两颗石子, 所得分数为所移除石子的价值和, 同时往头部再放回一颗价值为本回合所得分数的石子, 直到只剩最后一颗石子. 两人均采取使分数最高的最佳策略, 求问先手玩家与后手玩家最终的分数差.

思路

和之前的几次取石子操作没什么区别呀, 就是取出头几颗, 问题变为镜像的较小问题. 那进行一个 dfs/dp 就好.

实现

class Solution {
static constexpr int inf = 1e9;
public:
    int stoneGameVIII(vector<int>& stones) {
        int n = stones.size();
        vector<int> vis(n, -inf), pre(n + 1);
        for (int i = 0; i < n; i++) pre[i + 1] = pre[i] + stones[i];

        auto dfs = [&](this auto&& self, int u) -> int {
            int& res = vis[u];
            if (res != -inf) return res;
            if (u == n - 1) return res = pre.back();
            return res = max(self(u + 1), pre[u + 1] - self(u + 1));
        };
        return dfs(1);
    }
};

力扣每日一题3718-缺失的最小倍数

日期：2026-08-25

题意

给定正整数数组 nums 与一个正整数 k, 求该数组中最小的缺失的 k 的正整数倍数.

思路

做个哈希或者排序, 然后从小往大找就好.

实现

class Solution {
public:
    int missingMultiple(vector<int>& nums, int k) {
        ranges::sort(nums);
        int ans = k;
        for (int x : nums) {
            if (x < ans) continue;
            else if (x == ans) ans += k;
            else break;
        }
        return ans;
    }
};

力扣每日一题2904-最短且字典序最小的美丽子字符串

日期：2026-08-26

题意

给定零一字符串 s, 求其中最短且字典序最小的正好含 k 个 1 的子字符串.

思路

做一个滑动窗口, 维护窗口中的 1 数量以及最小满足题意的长度与对应最小子串.

实现

class Solution {
public:
    string shortestBeautifulSubstring(string s, int k) {
        int n = s.size();
        int mn = n + 1;
        string ans = "";
        for (int l = 0, r = 0, t = 0; r < n; r++) {
            t += s[r] == '1';
            if (t == k) {
                for ( ; l < n && t == k; l++) t -= s[l] == '1';
                if (mn > r - l + 2) {
                    ans = s.substr(l - 1, r - l + 2);
                    mn = r - l + 2;
                } else if (mn == r - l + 2) {
                    ans = min(ans, s.substr(l - 1, r - l + 2));
                }
            }
        }
        return ans;
    }
};

力扣每日一题3720-大于目标字符串的最小字典序排列

日期：2026-08-27

题意

给定两个等长字符串 s 和 target, 求 s 的字典序最小且严格大于 target 的排列.

思路

那应该是枚举 s 与 target 开始不一致且 s 大于 target 的位置.

实现

class Solution {
public:
    string lexGreaterPermutation(string s, string target) {
        array<int, 26> cnt;
        cnt.fill(0);
        for (auto& ch : s) cnt[ch - 'a']++;
        int n = s.size();
        for (int i = 0; i < n; i++) {
            int ch = target[i] - 'a';
            if (cnt[ch] > 0) {
                cnt[ch]--;
                continue;
            }
            string ans = target.substr(0, i);
            for (int j = ch + 1; j < 26; j++) {
                if (cnt[j]) {
                    ans += char(j + 'a');
                    cnt[j]--;
                    for (int k = 0; k < 26; k++) {
                        ans += string(cnt[k], char(k + 'a'));
                    }
                    return ans;
                }
            }
            
            for (int j = i - 1; j >= 0; j--) {
                int cur = ans[j] - 'a';
                cnt[cur]++;
                for (int k = cur + 1; k < 26; k++) {
                    if (cnt[k]) {
                        ans = ans.substr(0, j);
                        ans += char(k + 'a');
                        cnt[k]--;
                        for (int o = 0; o < 26; o++) {
                            ans += string(cnt[o], char(o + 'a'));
                        }
                        return ans;
                    }
                }
            }
            return "";
        }
        if (next_permutation(target.begin(), target.end())) {
            return target;
        }
        return "";
    }
};

力扣每日一题3734-大于目标字符串的最小字典序回文排列

日期：2026-08-28

题意

给定两个等长字符串 s 与 target, 求 s 的字典序最小且严格大于 target 的回文排列.

思路

旅游中, 摸了….

实现

旅游中, 摸了…

力扣每日一题2948-交换得到字典序最小的数组

日期：2026-08-29

题意

给定正整数数组 nums 以及一个正整数 limit, 若两下标满足 abs(nums[i] - nums[j]) < limit 则可将两数交换; 求问任意操作过后, 可以得到的字典序最小的数组.

思路

旅游中, 摸了…

实现

旅游中, 摸了…

力扣每日一题2091-从数组中移除最大值和最小值

日期：2026-08-30

题意

给定整数数组 nums, 每次操作可以删除首个元素或者末尾元素, 求问欲将原始数组中最大值与最小值删去, 最少需要多少次操作.

思路

首先找出最大最小值的位置, 答案仅有三种可能: 从最右删到较左的最值; 从最左删到较右的最值; 从两边分别删掉左右的最值.

实现

class Solution {
public:
    int minimumDeletions(vector<int>& nums) {
        int mn = INT_MAX, mx = INT_MIN;
        int p1, p2;
        int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] < mn) {
                mn = nums[i];
                p1 = i;
            }
            if (nums[i] > mx) {
                mx = nums[i];
                p2 = i;
            }
        }

        if (p1 > p2) swap(p1, p2);
        return min({p2 + 1, n - p1, p1 + 1 + n - p2});
    }
};

力扣每日一题2058-找出临界点之间的最小和最大距离

日期：2026-08-31

题意

给定链表, 求链表中相距最近与最远的极值点的距离.

思路

需要求最近与最远, 那么在遍历时维护一下上一个与第一个极值点出现的位置即可.

实现

/**
 * 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:
    vector<int> nodesBetweenCriticalPoints(ListNode* head) {
        int mn = INT_MAX, mx = INT_MIN;
        int first = -1, last = -1;
        for (int i = 0, pre = -1; head != nullptr; head = head->next, i++) {
            if (pre != -1 && head->next != nullptr) {
                int nxt = head->next->val, cur = head->val;
                if ((pre > cur && nxt > cur) || (pre < cur && nxt < cur)) {
                    if (first != -1) {
                        mn = min(mn, i - last);
                        mx = max(mx, i - first);
                    } else {
                        first = i;
                    }
                    last = i;
                }
            }
            pre = head->val;
        }
        
        if (mn == INT_MAX) return {-1, -1};
        return {mn, mx};
    }
};