力扣每月题解汇总-2025年06月

目录

力扣每日一题2929-给小朋友们分糖果 II

日期：2025-06-01

题意

给定正整数n和limit

求将n颗糖果分给3个小朋友，每人所得不超过limit颗，有多少种方案数。

思路

正着推好像有点难，可以考虑正难则反。

求总分配方案数减去有人获得超limit颗的方案数显然比正着推简单一些。

总分配方案数显然是用隔板法，有种

有人获得超limit颗需要用到隔板法与一点容斥的想法：

首先是至少含一人获得超limit，显然应该是首先分配出limit + 1颗糖果再将剩下的分给三人，然后将这limit + 1颗糖果分给任意人即有

但显然至少一人含超limit的情况包含了至少两人含超与至少三人含超，并且存在重复计数，利用容斥的思想应该减去至少两人含超加上三人含超，由此可得答案。

至少两人含超limit颗糖果思想同上有

至少三人含超limit颗糖果有

至于这个容斥想法怎么来可以简单证明下：

记三个小朋友分别为 A B C
至少一个人含超过 limit 颗糖果有如下情况：
	A 含超过 limit 颗：A AB AC ABC
	B 含超过 limit 颗：B AB BC ABC
	C 含超过 limit 颗：C AC BC ABC
显然是存在重复计数的
至少两人含超过 limit 颗糖果有如下情况：
	AB 含超过 limit 颗：AB ABC
	AC 含超过 limit 颗：AC ABC
	BC 含超过 limit 颗：BC ABC
至少三人含超过 limit 颗糖果有如下情况：
	ABC 含超过 limit 颗：ABC

实现

class Solution {
using ll = long long;
public:
    long long distributeCandies(int n, int limit) {
        auto cal = [](int x) -> ll {
            if (x < 2) return 0;
            return 1ll * x * (x - 1) / 2;
        };

        return cal(n + 2) - 3 * cal(n - limit + 1) + 3 * cal(n - 2 * limit) - cal(n - 3 * limit - 1);
    }
};

力扣每日一题135-分发糖果

日期：2025-06-02

题意

给定数组ratings表示小朋友们的分数，小朋友们站成一排，要求给他们每人至少1颗糖果，且若某孩子分数大于相邻的孩子则其糖果数一定大于相邻分数较小的孩子，求最少需要多少糖果。

思路

贪心地想当然是先给最小的一颗糖，然后再慢慢根据大小关系往两边放。

就比较自然的可以想到建图然后按拓扑序分发糖果。

但是写完后发现好像没必要，正着跑一趟反着跑一趟与上一个小朋友比较大小关系即可，不知道为什么会标困难，可能也是受这个影响想复杂了。

实现

建图拓扑序：

class Solution {
public:
    int candy(vector<int>& ratings) {
        const int n = ratings.size();
        vector<vector<int>> e(n);
        vector<int> q, d(n), ans(n);
        for (int i = 0; i < n; i++) {
            if (i && ratings[i] < ratings[i - 1]) {
                e[i].push_back(i - 1);
                d[i - 1]++;
            }
            if (i != n - 1 && ratings[i] < ratings[i + 1]) {
                e[i].push_back(i + 1);
                d[i + 1]++;
            }
        }

        for (int i = 0; i < n; i++) {
            if (d[i] == 0) q.push_back(i);
            ans[i]++;
        }
        for (int cur = 0; cur < q.size(); cur++) {
            int x = q[cur];
            for (auto v : e[x]) {
                d[v]--;
                ans[v] = max(ans[v], ans[x] + 1);
                if (d[v] == 0) q.push_back(v);
            }
        }
        return accumulate(ans.begin(), ans.end(), 0);
    }
};

直接贪心：

class Solution {
public:
    int candy(vector<int>& ratings) {
        const int n = ratings.size();
        vector<int> ans(n, 1);
        for (int i = 1; i < n; i++) {
            if (ratings[i] > ratings[i - 1]) ans[i] = ans[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) ans[i] = max(ans[i], ans[i + 1] + 1);
        }
        return accumulate(ans.begin(), ans.end(), 0);
    }
};

力扣每日一题1298-你能从盒子里获得的最大糖果数

日期：2025-06-03

题意

给定n个盒子与盒子的状态，盒子可能开着或关闭若关闭需用对应钥匙打开，同时盒子中有一些糖有一些钥匙甚至一些其他盒子；给出最开始所拥有的盒子，求最多可以获得多少糖果。

思路

就是简单的模拟，没什么思维难度也没什么代码实现难度，不知道为什么标困难，数据范围也小，应该是怎么写都可以的。

实现

class Solution {
public:
    int maxCandies(vector<int>& status, vector<int>& candies, vector<vector<int>>& keys, vector<vector<int>>& containedBoxes, vector<int>& initialBoxes) {
        const int n = status.size();
        vector<bool> box(n), key(n), done(n);
        vector<int> q;
        for (auto& x : initialBoxes) {
            box[x] = true;
            if (status[x]) q.push_back(x);
        }

        int ans = 0;
        for (int cur = 0; cur < q.size(); cur++) {
            int x = q[cur];
            if (done[x]) continue;
            done[x] = true;
            ans += candies[x];
            for (auto k : keys[x]) {
                key[k] = true;
                if (box[k] && !done[k]) q.push_back(k);
            }
            for (auto b : containedBoxes[x]) {
                box[b] = true;
                if ((key[b] || status[b]) && !done[b]) q.push_back(b);
            }
        }
        return ans;
    }
};

力扣每日一题3403-从盒子中找出字典序最大的字符串 I

日期：2025-06-04

题意

给定字符串word，要将其划分为numFriends个非空子串，问字典序最大的子串。

思路

数据范围是比较小的，怎么做都可以，直接枚举子串起点进行比较就好。

实现

class Solution {
public:
    string answerString(string word, int numFriends) {
        if (numFriends == 1) return word;
        const int n = word.size();
        string ans = word.substr(0, n - numFriends + 1);
        for (int i = 1; i < n; i++) {
            if (word[i] < ans.front()) continue;
            else if (word[i] == ans.front()) {
                string t = word.substr(i, n - i - max(numFriends - i - 1, 0));
                if (t > ans) ans = t;
            } else {
                ans = word.substr(i, n - i - max(numFriends - i - 1, 0));
            }
        }
        return ans;
    }
};

力扣每日一题1061-按字典序排列最小的等效字符串

日期：2025-06-05

题意

给定两等长字符串s1与s2，以及另一字符串baseStr

s1与s2相同位置的字符等价，即s1[i]与s2[i]等价

可将baseStr中的字符任意替换成与其等价的字符

求baseStr替换后字典序最小的结果。

思路

比较自然可以想到使用并查集，同一集合内的字符是可以互相替换的，要使得字典序最小，应将同一集合内的字符均替换为最小的字符。

实现

class Solution {
static constexpr int N = 26;
public:
    string smallestEquivalentString(string s1, string s2, string baseStr) {
        array<int, N> fa;
        ranges::iota(fa, 0);
        auto find = [&](this auto&& self, int u) -> int {
            if (fa[u] == u) return u;
            return fa[u] = self(fa[u]);
        };
        auto merge = [&](int x, int y) -> void {
            x = find(x); y = find(y);
            if (x == y) return;
            if (x > y) swap(x, y);
            fa[y] = x;
            return;
        };

        const int n = s1.size();
        for (int i = 0; i < n; i++) {
            merge(s1[i] - 'a', s2[i] - 'a');
        }
        for (auto& ch : baseStr) {
            ch = char(find(ch - 'a') + 'a');
        }
        return baseStr;
    }
};

力扣每日一题2434-使用机器人打印字典序最小的字符串

日期：2025-06-06

题意

给定字符串s与空白字符串t，以及初始也为空的字符串ans，每次操作可以将s的第一个字符移到t的尾部，或将t最后一个字符移动到ans的尾部，操作直到s和t变为空字符串。求可得到的字典序最小的ans

思路

可以发现这是一个入栈出栈得到字符串的问题，s是原始字符串，t就是栈，移动到t尾部等价于入栈，将t尾加入ans等价于出栈。

那还是比较经典的，若有还未入栈的字符含有比栈顶小的字符应一路入栈直到当前后缀中最小的字符入栈，再将该最小字符出栈；若未入栈的字符均大于栈顶字符，直接出栈即可。

加速寻找后缀最小可以使用后缀min。

实现

class Solution {
public:
    string robotWithString(string s) {
        const int n = s.size();
        string ans, stk;
        vector<int> last(n + 1, n);
        for (int i = n - 1; i >= 0; i--) {
            if (last[i + 1] == n || s[i] <= s[last[i + 1]]) {
                last[i] = i;
            } else {
                last[i] = last[i + 1];
            }
        }
        for (int cur = 0; cur < n; ) {
            if (stk.empty() || stk.back() > s[last[cur]]) {
                ans += s[last[cur]];
                stk += s.substr(cur, last[cur] - cur);
                cur = last[cur] + 1;
            } else {
                ans += stk.back();
                stk.pop_back();
            }
        }
        reverse(stk.begin(), stk.end());
        ans += stk;
        return ans;
    }
};

力扣每日一题3170-删除星号以后字典序最小的字符串

日期：2025-06-07

题意

给定含*的字符串s，要求删除所有*，同时每次删除操作必须删除该*号左侧任意字典序最小的字母，求最终字典序最小的字符串。

思路

对于每次操作，应该删除当前*左侧最右的字典序最小字母，使用栈进行记录即可。

实现

class Solution {
static constexpr int N = 26;
public:
    string clearStars(string s) {
        vector<vector<int>> stk(N);
        const int n = s.size();
        int mask = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '*') {
                for (int j = 0; j < 26; j++) {
                    if (mask >> j & 1) {
                        s[stk[j].back()] = '*';
                        stk[j].pop_back();
                        if (stk[j].empty()) mask ^= 1 << j;
                        break;
                    }
                }
            } else {
                stk[s[i] - 'a'].push_back(i);
                mask |= 1 << (s[i] - 'a');
            }
        }
        s.erase(ranges::remove(s, '*').begin(), s.end());
        return s;
    }
};

力扣每日一题386-字典序排数

日期：2025-06-08

题意

给定整数n，按字典序返回范围[1, n]内所有整数

思路

按字典序进行枚举即可。

实现

class Solution {
public:
    vector<int> lexicalOrder(int n) {
        vector<int> ans(n);
        for (int i = 0, num = 1; i < n; i++) {
            ans[i] = num;
            if (num * 10 <= n) num *= 10;
            else {
                while (num % 10 == 9 || num + 1 > n) {
                    num /= 10;
                }
                num++;
            }
        }
        return ans;
    }
};

力扣每日一题440-字典序的第K小数字

日期：2025-06-09

题意

给定整数n和k，返回[1, n]中字典序第k小的数字

思路

不妨将数字当作字符串看待，那又比较自然的可以想到字典树。

是返回[1, n]范围内的数，故而可以得到一颗根节点有9条边其余点有10条边共有n + 1个结点的树。

将[1, n]的数按照字典序排序，显然是按照先序遍历该树得到，本题数据量较大不太可以直接遍历模拟得到，考虑使用子树结点数进行加速判断：假定当前处于任意结点，需要得到第k小的数，若其第一个子节点子树内所有结点数为x，若 显然所需点不在该子树内，若显然所需点在该子树内。

实现

class Solution {
using ll = long long;
public:
    int findKthNumber(int n, int k) {
        int p = 1;
        for (int i = n / 10; i > 0; i /= 10) p *= 10;

        auto cal = [&](int x) -> int {
            int sz = (p - 1) / 9;
            ll l = 1ll * p * x, r = 1ll * p * (x + 1);
            if (l <= n) {
                sz += min(r, n + 1ll) - l;
            }
            return sz;
        };

        int x = 1;
        k--;
        while (k) {
            int sz = cal(x);
            if (sz <= k) {
                k -= sz;
                x++;
            } else {
                p /= 10;
                x *= 10;
                k--;
            }
        }
        return x;
    }
};

力扣每日一题3442-奇偶频次间的最大差值 I

日期：2025-06-10

题意

给定小写字母字符串s，求diff = a1 - a2的最大值

其中a1为字符串中任意出现次数为奇数次的字符的出现次数

a2为字符串中任意出现次数为偶数次的字符的出现次数

思路

要使得diff最大，显然应该使得a1取得最大a2取得最小

也就是选取出现次数为奇数的最大，出现次数为偶数的最大，注意出现0次也就是未出现的字符应不考虑即可。

实现

class Solution {
public:
    int maxDifference(string s) {
        array<int, 26> cnt;
        for (const auto& ch : s) {
            cnt[ch - 'a']++;
        }
        int mx = 0, mn = INT_MAX;
        for (const auto& i : cnt) {
            if (i & 1) mx = max(mx, i);
            else if (i) mn = min(mn, i);
        }
        return mx - mn;
    }
};

力扣每日一题3345-奇偶频次间的最大差值 II

日期：2025-06-11

题意

给定由['0', '4']组成的字符串s与整数k，求s的子串subs中freq[a] - freq[b]的最大值，其中：

  • subs长度至少为k
  • freq表示该字符在subs中出现的次数
  • freq[a]为奇数
  • freq[b]为偶数

思路

显然应该使用滑动窗口与前缀最小。

实现

class Solution {
static constexpr int inf = 1e9;
static constexpr int N = 5;
public:
    int maxDifference(string s, int k) {
        int ans = -inf;
        const int n = s.size();
        for (int x = 0; x < N; x++) {
            for (int y = 0; y < N; y++) {
                if (x == y) continue;
                array<int, N> cur, pre;
                cur.fill(0); pre.fill(0);
                array<array<int, 2>, 2> mn;
                for (auto& i : mn) i.fill(inf);
                int left = 0;
                for (int i = 0; i < n; i++) {
                    cur[s[i] - '0']++;
                    while (i + 1 - left >= k && cur[x] > pre[x] && cur[y] > pre[y]) {
                        int& t = mn[pre[x] & 1][pre[y] & 1];
                        t = min(t, pre[x] - pre[y]);
                        pre[s[left++] - '0']++;
                    }
                    ans = max(ans, cur[x] - cur[y] - mn[cur[x] & 1 ^ 1][cur[y] & 1]);
                }
            }
        }
        return  ans;
    }
};

力扣每日一题3423-循环数组中相邻元素的最大差值

日期：2025-06-12

题意

给定循环数组nums，求相邻元素最大绝对差值。

思路

直接遍历求即可

实现

class Solution {
public:
    int maxAdjacentDistance(vector<int>& nums) {
        int ans = -200;
        const int n = nums.size();
        for (int i = 1; i <= n; i++) {
            ans = max(ans, abs(nums[i % n] - nums[i - 1]));
        }
        return ans;
    }
};

力扣每日一题2616-最小化数对的最大差值

日期：2025-06-13

题意

给定整数数组nums与整数p，找出p对不同下标对(i, j)使得abs(nums[i] - nums[j])最大值最小时的最大值。每个下标在p对下标对中仅出现一次。

思路

使得最大值最小，显然进行二分即可。

实现

class Solution {
public:
    int minimizeMax(vector<int>& nums, int p) {
        ranges::sort(nums);
        const int n = nums.size();

        auto check = [&](int x) -> bool {
            int t = 0;
            for (int i = 0; i < n - 1; i++) {
                if (nums[i + 1] - nums[i] <= x) {
                    t++;
                    i++;
                }
            }
            return t >= p;
        };

        int lo = 0, hi = nums.back() - nums.front();
        while (lo < hi) {
            int mid = lo + hi >> 1;
            if (check(mid)) hi = mid;
            else lo = mid + 1;
        }
        return lo;
    }
};

力扣每日一题2566-替换一个数字后的最大差值

日期：2025-06-14

题意

给定一个整数num，可以将其中某一个数字全部替换为另一数字，求可以得到的最大值与最小值的差值。

思路

比较显然是可以贪心的，得最大值应该使得最靠前非9的数变为9，得最小值应该是最靠前非0的数变为0，直接进行模拟即可。

实现

class Solution {
public:
    int minMaxDifference(int num) {
        string s = to_string(num);
        string t = s;
        const int n = s.size();
        for (int i = 0, b = -1; i < n; i++) {
            if (s[i] == '9') continue;
            if (b == -1) {
                b = s[i] - '0';
                s[i] = '9';
            } else if (b == s[i] - '0') s[i] = '9';
        }
        for (int i = 0, b = -1; i < n; i++) {
            if (t[i] == '0') continue;
            if (b == -1) {
                b = t[i] - '0';
                t[i] = '0';
            } else if (b == t[i] - '0') t[i] = '0';
        }
        return stoi(s) - stoi(t);
    }
};

力扣每日一题1432-改变一个整数能得到的最大差值

日期：2025-06-15

题意

给定一个整数num，可以将其中某一个数字全部替换为另一数字，求可以得到的最大值与最小值的差值。但不可以转为有前导0的数

思路

显然就是做题的题加上不能有前导零的条件，进行贪心即可。

实现

class Solution {
public:
    int maxDiff(int num) {
        string s = to_string(num);
        string t = s;
        const int n = s.size();
        for (int i = 0, b = -1; i < n; i++) {
            if (s[i] == '9') continue;
            if (b == -1) {
                b = s[i] - '0';
                s[i] = '9';
            } else if (b == s[i] - '0') s[i] = '9';
        }
        if (t.front() != '1') {
            for (int i = n - 1; i >= 0; i--) {
                if (t[i] == t.front()) t[i] = '1';
            }
        } else {
            for (int i = 0, b = -1; i < n; i++) {
                if (t[i] <= '1') continue;
                if (b == -1) {
                    b = t[i] - '0';
                }
                if (t[i] - '0' == b) t[i] = '0';
            }
        }
        return stoi(s) - stoi(t);
    }
};

力扣每日一题2016-增量元素之间的最大差值

日期：2025-06-16

题意

给定数组nums，求满足以下条件的nums[j] - nums[i]的最大值

思路

对于同一个i显然应该选择其后最大的nums[j]才能使得nums[j] - nums[i]最大，因此不难想到使用后缀最大即可。

实现

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

力扣每日一题3405-统计恰好有 K 个相等相邻元素的数组数目

日期：2025-06-17

题意

对于给定的三个正整数n、m、k，称满足以下条件的数组arr为好数组

  • arr的长度为n
  • arr的元素均为[1, m]
  • arr中恰好有k对满足arr[i] == arr[i - 1]的下标

求好数组arr的构造数

思路

仔细观察可以发现该题其实就是个数学题，进行一个推式子即可

首先长为n的数组共有n - 1对相邻元素，要求恰好有k对相邻元素相同，也就是说有n - 1 - k对相邻元素不同。也就是说有会有n - 1 - k个数将整个数组分割为n - k段，每段元素相同。

计算分割方案与分割后填色数即可。

实现

static constexpr int mod = 1e9 + 7;
static constexpr int N = 1e5;
int f[N + 1], nf[N + 1];

int powMod(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) {
            res = 1ll * res * a % mod;
        }
        a = 1ll * a * a % mod;
        b >>= 1;
    }
    return res;
}
int C(int n, int k) {
    return 1ll * f[n] * nf[k] % mod * nf[n - k] % mod;
}

int init = []() -> int {
    f[0] = 1;
    for (int i = 1; i <= N; i++) {
        f[i] = 1ll * f[i - 1] * i % mod;
    }
    nf[N] = powMod(f[N], mod - 2);
    for (int i = N; i > 0; i--) {
        nf[i - 1] = 1ll * nf[i] * i % mod;
    }
    return 0;
} ();


class Solution {
public:
    int countGoodArrays(int n, int m, int k) {
        return 1ll * C(n - 1, k) * m % mod * powMod(m - 1, n - k - 1) % mod;
    }
};

力扣每日一题2966-划分数组并满足最大差限制

日期：2025-06-18

题意

给定长度为3的倍数的数组nums，以及一个正整数k，要求把数组分割为长度均为3的子数组，要求子数组中任意两数差均小于等于k

思路

什么样的子数组满足任意两数差均小于等于k呢，显然是最大最小值差值小于等于k的，因此不难想到首先进行排序，贪心地不断连续选取3个数为一组即可。

实现

class Solution {
public:
    vector<vector<int>> divideArray(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<vector<int>> ans;
        ranges::sort(nums);
        for (int i = 2; i < n; i += 3) {
            if (nums[i] - nums[i - 2] <= k) {
                ans.push_back({nums[i], nums[i - 1], nums[i - 2]});
            } else {
                return {};
            }
        }
        return ans;
    }
};

力扣每日一题2294-划分数组使最大差为 K

日期：2025-06-19

题意

给定数组nums与整数k，将nums划分为子序列，使得每个子序列最大值与最小值的差值不超过k，求所需划分的最少子序列数。

思路

显然符合贪心性质，直接排序开贪即可。

实现

class Solution {
public:
    int partitionArray(vector<int>& nums, int k) {
        ranges::sort(nums);
        const int n = nums.size();
        int cnt = 1;
        for (int l = 0, i = 0; i < n; i++) {
            if (nums[i] - nums[l] <= k) continue;
            cnt++;
            l = i;
        }
        return cnt;
    }
};

力扣每日一题3443-K 次修改后的最大曼哈顿距离

日期：2025-06-20

题意

初始位于坐标原点(0, 0)，给定由NSWE组成的字符串，分别表示向北南西东走一格，最多可以修改字符串的k个字符，求移动过程中离原点的最大曼哈顿距离。

思路

贪心地进行模拟即可。

实现

class Solution {
public:
    int maxDistance(string s, int k) {
        int x = 0, y = 0;
        const int n = s.size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == 'N') {
                y++;
            } else if (s[i] == 'S') {
                y--;
            } else if (s[i] == 'E') {
                x++;
            } else {
                x--;
            }
            ans = max(ans, abs(x) + abs(y) + min(2 * k, i + 1 - abs(x) - abs(y)));
        }
        return ans;
    }
};

力扣每日一题3085-成为 K 特殊字符串需要删除的最少字符数

日期：2025-06-21

题意

给定字符串word与整数k，可以任意删除word中的字符，需使得word中的任意两种字符出现次数差值不超过k，求需要删除的最小次数。

思路

显然至少存在一种字符不需要删除，进行枚举贪心即可。

实现

class Solution {
static constexpr int N = 26;
public:
    int minimumDeletions(string word, int k) {
        array<int, N> cnt;
        for (const auto& ch : word) cnt[ch - 'a']++;
        ranges::sort(cnt);

        int mx = 0;
        for (int i = 0; i < N; i++) {
            int tmp = 0;
            for (int j = i; j < N; j++) {
                tmp += min(cnt[j], cnt[i] + k);
            }
            mx = max(mx, tmp);
        }
        return word.size() - mx;
    }
};

力扣每日一题2138-将字符串拆分为若干长度为 k 的组

日期：2025-06-22

题意

给定字符串s与整数k与字符fill，需将s分割为长度均为k的子串，长度不足k的用字符fill填充。

思路

简单模拟即可。

实现

class Solution {
public:
    vector<string> divideString(string s, int k, char fill) {
        const int n = s.size();
        vector<string> ans;
        for (int i = 0; i < n; i += k) {
            ans.push_back(s.substr(i, k));
            if (i + k >= n) {
                while (ans.back().size() < k) ans.back() += fill;
            }
        }
        return ans;
    }
};

力扣每日一题2081-k 镜像数字的和

日期：2025-06-23

题意

定义k镜像数字为在十进制与k进制下均为回文数字的正整数

对于给定的整数k与n，求出前n小的k镜像数字之和。

思路

注意到n与k的数据范围不大，直接预处理作答即可。

实现

using ll = long long;
static constexpr int MX = 30;
static constexpr int K = 10;
ll ans[K][MX + 10];

bool check(ll x, int k) {
    string s;
    while (x) {
        s += char(x % k + '0');
        x /= k;
    }
    for (int l = 0, r = int(s.size()) - 1; l <= r; l++, r--) {
        if (s[l] != s[r]) return false;
    }
    return true;
}
bool over() {
    bool res = true;
    for (int i = 2; i < K && res; i++) {
        res &= ans[i][0] >= MX;
    }
    return res;
}

int init = []() {
    for (int b = 1; ; b *= 10) {
        for (int i = b; i < b * 10; i++) {
            string s = to_string(i);
            string r = s;
            reverse(r.begin(), r.end());
            s.pop_back();
            s += r;
            ll u = stoll(s);
            for (int k = 2; k < K; k++) {
                if (ans[k][0] >= MX) continue;
                if (check(u, k)) ans[k][++ans[k][0]] = u;
            }
        }
        for (int i = b; i < b * 10; i++) {
            string s = to_string(i);
            string r = s;
            reverse(r.begin(), r.end());
            s += r;
            ll u = stoll(s);
            for (int k = 2; k < K; k++) {
                if (ans[k][0] >= MX) continue;
                if (check(u, k)) ans[k][++ans[k][0]] = u;
            }
        }
        if (over()) break;
    }
    for (int k = 2; k < 10; k++) {
        for (int i = 2; i <= MX; i++) {
            // cout << k << ' ' << i << ' ' << ans[k][i] << '\n';
            ans[k][i] += ans[k][i - 1];
        }
    }
    return 0;
} ();

class Solution {
public:
    long long kMirror(int k, int n) {
        return ans[k][n];
    }
};

力扣每日一题2200-找出数组中的所有 K 近邻下标

日期：2025-06-24

题意

给定数组nums与整数key和k。求nums中所有与值为key距离不超过k的下标集合，升序返回。

思路

记录已经加入答案集合的右边界，遍历寻找值为key的下标即可。

实现

class Solution {
public:
    vector<int> findKDistantIndices(vector<int>& nums, int key, int k) {
        const int n = nums.size();
        vector<int> ans;
        for (int i = 0, l = 0; i < n; i++) {
            while (i - l > k) l++;
            if (nums[i] == key) {
                while (l < n && abs(i - l) <= k) ans.push_back(l++);
            }
        }
        return ans;
    }
};

力扣每日一题2040-两个有序数组的第 K 小乘积

日期：2025-06-25

题意

给定两个升序数组nums1与nums2以及一个整数k，求第k小的nums1[i] * nums2[j]。

思路

比较显然是一个二分。

列出矩阵，其中matrix[i][j]表示nums1[i] * nums2[j]的结果，由于两个数组均为升序排序，故可得一些性质，由此二分答案即可。

实现

class Solution {
using ll = long long;
public:
    long long kthSmallestProduct(vector<int>& nums1, vector<int>& nums2, long long k) {
        const int n = nums1.size(), m = nums2.size();
        int x = ranges::lower_bound(nums1, 0) - nums1.begin();
        int y = ranges::lower_bound(nums2, 0) - nums2.begin();
    
        auto check = [&](ll mid) -> bool {
            ll cnt = 0;

            if (mid < 0) {
                for (int i = 0, j = y; i < x && j < m && cnt < k; ) {
                    if (1ll * nums1[i] * nums2[j] > mid) j++;
                    else {
                        cnt += m - j;
                        i++;
                    }
                }
                for (int i = x, j = 0; i < n && j < y && cnt < k; ) {
                    if (1ll * nums1[i] * nums2[j] > mid) i++;
                    else {
                        cnt += n - i;
                        j++;
                    }
                }
            } else {
                cnt = 1ll * x * (m - y) + 1ll * (n - x) * y;
                for (int i = 0, j = y - 1; i < x && j >= 0 && cnt < k; ) {
                    if (1ll * nums1[i] * nums2[j] > mid) i++;
                    else {
                        cnt += x - i;
                        j--;
                    }
                }
                for (int i = x, j = m - 1; i < n && j >= y && cnt < k; ) {
                    if (1ll * nums1[i] * nums2[j] > mid) j--;
                    else {
                        cnt += j - y + 1;
                        i++;
                    }
                }
            }

            return cnt >= k;
        };

        array<ll, 4> tmp = {1ll * nums1.front() * nums2.front(), 1ll * nums1.front() * nums2.back(), 1ll * nums1.back() * nums2.front(), 1ll * nums1.back() * nums2.back()};
        auto [lo, hi] = ranges::minmax(tmp);
        while (lo < hi) {
            ll mid = lo + hi >> 1;
            if (check(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }
        return lo;
    }
};

力扣每日一题2311-小于等于 K 的最长二进制子序列

日期：2025-06-26

题意

给定二进制字符串s与整数k，求字符串s子序列的最大长度，要求该子序列的对应二进制数不大于k，允许存在前导零。

思路

显然贪心即可：

允许存在前导零，那显然应该将所有0加入答案。

对于1，可以发现最好情况下将其加入答案使得答案加一，最坏情况下需要删除1到多个0才可将其加入答案子序列。

那么从后往前贪即可得到最长答案，注意别爆数据范围即可。

实现

class Solution {
public:
    int longestSubsequence(string s, int k) {
        const int n = s.size();
        int ans = 0;
        for (int i = n - 1, cur = 0; i >= 0; i--) {
            if (s[i] == '0') ans++;
            else {
                if (ans >= 30) continue;
                if ((cur | (1 << ans)) <= k) {
                    cur |= 1 << ans;
                    ans++;
                }
            }
        }
        return ans;
    }
};

力扣每日一题2014-重复 K 次的最长子序列

日期：2025-06-27

题意

给定字符串s与整数k，求最长且字典序最大且在s中出现k次的子序列。

注意到

思路

好像有点难，但注意到数据范围有暗示s.size() <= 8 * k，那也就是说答案子序列最长为8，进行一个枚举复杂度是可以接受的，故筛出至少出现k次的字符，进行枚举对应子序列即可。

实现

class Solution {
public:
    string longestSubsequenceRepeatedK(string s, int k) {
        const int n = s.size();
        vector<array<int, 26>> nxt(n);
        array<int, 26> cnt, tmp;
        cnt.fill(0); tmp.fill(n);
        for (const auto& ch : s) cnt[ch - 'a']++;
        for (int i = n - 1; i >= 0; i--) {
            tmp[s[i] - 'a'] = i;
            nxt[i] = tmp;
        }

        string a;
        for (int i = 25; i >= 0; i--) {
            a.insert(a.end(), cnt[i] / k, char(i + 'a'));
        }
        const int m = a.size();
        vector<bool> vis(m);

        string ans;
        auto check = [&](const string& x) -> void {
            if (x.size() < ans.size() || (x.size() == ans.size() && x <= ans)) return;
            int cur = 0, t = k;
            while (t--) {
                for (const auto& ch : x) {
                    if (cur >= n) return;
                    cur = nxt[cur][ch - 'a'] + 1;
                }
            }
            if (cur == n + 1) return;
            ans = x;
        };
        string x;
        auto dfs = [&](this auto&& self) -> void {
            check(x);
            if (x.size() == m) return;
            for (int i = 0; i < m; i++) {
                if (vis[i] || (i && a[i - 1] == a[i] && !vis[i - 1])) continue;
                x += a[i];
                vis[i] = true;
                self();
                x.pop_back();
                vis[i] = false;
            }
        };
        dfs();

        return ans;
    }
};

力扣每日一题2099-找到和最大的长度为 K 的子序列

日期：2025-06-28

题意

给定整数数组nums与整数k，求nums中长度为k的和最大的子序列。

思路

贪心选出前k大的数即可。

实现

class Solution {
public:
    vector<int> maxSubsequence(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<int> p(n);
        ranges::iota(p, 0);
        ranges::sort(p, [&](const int& x, const int& y) {
            return nums[x] > nums[y];
        });
        p.resize(k);
        ranges::sort(p);
        for (auto& i : p) i = nums[i];
        return p;
    }
};

力扣每日一题1498-满足条件的子序列数目

日期：2025-06-29

题意

给定数组nums与整数target，求nums中满足最大最小值之和不超过target的子序列的个数。

思路

需要求的是子序列，所以其顺序是无所谓的，故而考虑直接排序，这样最大最小值就方便直接选择。

使得最大最小值之和不超过某一定值，若x + y不超过某值，显然若z < y则必有x + z不超过对应值。故而可以直接使用双指针，记录若选出当前最小值，最大值可以选哪个，再计算出对应子序列数量即可。

实现

using ll = long long;
static constexpr int mod = 1e9 + 7;
ll powMod(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

static constexpr int N =  1e5;
ll p[N + 10];
int init = []() {
    p[0] = 1;
    for (int i = 1; i <= N; i++) {
        p[i] = (p[i - 1] << 1) % mod;
    }
    return 0;
} ();

class Solution {
public:
    int numSubseq(vector<int>& nums, int target) {
        ranges::sort(nums);
        ll ans = 0;
        for (int l = 0, r = int(nums.size()) - 1 ; l <= r; ) {
            if (nums[l] + nums[r] > target) {
                r--;
            } else {
                // ans = (ans + powMod(2, r - l)) % mod;
                ans += p[r - l];
                if (ans > mod) ans -= mod;
                l++;
            }
        }
        return ans;
    }
};

力扣每日一题594-最长和谐子序列

日期：2025-06-30

题意

给定数组nums。求nums中最大最小值只差为1的最长子序列长度。

思路

令每个数作为最小值，判断其值加一是否存在以及对应数的数量即可。

实现

class Solution {
public:
    int findLHS(vector<int>& nums) {
        unordered_map<int, int> cnt;
        for (const auto& x : nums) cnt[x]++;
        int mx = 0;
        for (auto [x, t] : cnt) {
            if (cnt.count(x + 1)) {
                mx = max(mx, t + cnt[x + 1]);
            }
        }
        return mx;
    }
};