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

目录

力扣每日一题368.最大整除子集

日期：2025-04-06

题意

给一个整数集合nums，找最大子集，满足子集元素两两之间一数为另一数的倍数。

形式化：找出nums子集ans满足 使得ans大小最大

思路

注意到

可以想到将集合升序排序后再进一步处理。

又注意到

即只需满足子集排序后相邻两数互为倍数可满足题设条件。

可以考虑使用dp记录当前数为子集最大值时满足条件的子集最大大小

实现代码

class Solution {
public:
    vector<int> largestDivisibleSubset(vector<int>& nums) {
        const int n = nums.size();
        ranges::sort(nums);
        vector<int> dp(n, 1), from(n);
        iota(from.begin(), from.end(), 0);
        int mx = 0, mxloc;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (nums[j] % nums[i]) continue;
                if (dp[j] < dp[i] + 1) {
                    dp[j] = dp[i] + 1;
                    from[j] = i;
                }
            }
            if (dp[i] > mx) {
                mx = dp[i];
                mxloc = i;
            }
        }
        vector<int> ans;
        for (int i = mxloc; ; i = from[i]) {
            ans.push_back(nums[i]);
            if (i == from[i]) break;
        }
        return ans;
    }
};

其他

搭建博客后担心实在无东西可写，于是想到了写写力扣的每日一题。

之前遇到较为麻烦的每日一题就会懒得写，在博客写这个也许既能让博客每日更新又能push我每天写题。

当前目标就先定为拿下四月全勤徽章吧。

力扣每日一题416-分割等和子集

日期：2025-04-07

题意

给出整数数组nums，判断其是否可分割为两个和相等的子集

思路

分割为两个等和数组，换言而止就是将 nums分割为子集a 与b使得：

注意到数据范围很小：

即满足

可以考虑使用dp判断是否存在子集和为

实现代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum & 1) return false;
        sum >>= 1;

        vector<bool> dp(sum + 1);
        dp[0] = true;
        for (const auto& x : nums) {
            for (int i = sum - x; i >= 0; i--) {
                if (!dp[i])continue;
                dp[i + x] = true;
            }
            if (dp.back()) return true;
        }
        return dp.back();
    }
};

力扣每日一题3396-使数组元素互不相同所需的最少操作次数

日期：2025-04-08

题意

给出一数组，每次操作可以删除数组头三个元素，问使得数组元素互不相同所需最少操作次数。

思路

注意到数据范围很小，数组大小与元素大小均在[1, 100]

可以考虑正着模拟删除操作，计算删除次数。

也可以考虑反着操作，从尾开始添加元素，得到最长无重后缀，未添加的元素个数即为要删除的元素个数。

实现

正着模拟删除

class Solution {
array<int, 101> vis;
public:
    int minimumOperations(vector<int>& nums) {
        vis.fill(0);
        int ans = 0, cnt = 0;
        for (const auto& x : nums) {
            if (vis[x] == 1) cnt++;
            vis[x]++;
        }
        for (int i = 0; cnt && i < nums.size() - 2; i += 3) {
            ans++;
            cnt -= (--vis[nums[i]]) == 1;
            cnt -= (--vis[nums[i + 1]]) == 1;
            cnt -= (--vis[nums[i + 2]]) == 1;
        }
        ans += cnt > 0;
        return ans;
    }
};

反着模拟添加

class Solution {
array<int, 101> vis;
public:
    int minimumOperations(vector<int>& nums) {
        vis.fill(0);
        for (int i = nums.size() - 1; i >= 0; i--) {
            if (vis[nums[i]]) {
                return (i + 1 + 2) / 3;
            }
            vis[nums[i]]++;
        }
        return 0;
    }
};

力扣每日一题3375-使数组的值全部为K的最少操作次数

日期：2025-04-09

题意

数h对于数组nums,若满足,则称h合法，即数组中大于h的数均相等。

每次操作可以选择任意合法h使得nums中所有大于h的元素变为h

求问将nums中所有数变为给定k值所需最少操作次数。

思路

当nums最小值小于k时显然是不存在合法操作的，因为不存在将元素值变大的操作。

可以发现每次操作使得最大值变为次大值时有最优，此题本质可转化为数组中大于k的元素种类数。

实现

class Solution {
public:
    int minOperations(vector<int>& nums, int k) {
        ranges::sort(nums);
        if (nums.front() < k) return -1;
        nums.erase(unique(nums.begin(), nums.end()), nums.end());
        return nums.size() - (nums.front() == k);
    }
};

力扣每日一题2999-统计强大整数的数目

日期：2025-04-10

题意

给定区间[start, finish] 、数位限制limit与后缀s，求区间范围内满足每一位数不超过limit且以s为后缀的数的个数。

思路

比较经典的数位dp。

首先考虑如何计算区间[0, finish]即 满足条件 的x个数。

在不考虑s为后缀仅考虑每一位限制为limit的条件情况下，从高位向低位递推

记表示finish第j位

当i=0时表示到第j位严格小于finish且满足限制limit的方案个数，当i=1时表示到第j位严格等于finish且满足限制limit的方案个数，可以推到出以下转移方程
$$
\left{

\right.
$$
再考虑如何满足以s为后缀

记 为s的第j位

同理可有
$$
\left{

\right.
$$
最终即为所求。

同理再求出范围[0, start)即[0, start - 1]内的方案数，两者相减即可得到[start, finish]内的方案数。

实现

class Solution {
public:
    using ll = long long;
    long long numberOfPowerfulInt(long long start, long long finish, int limit, string s) {
        reverse(s.begin(), s.end());
        auto cal = [&](ll t) -> ll {
            string num = to_string(t);
            reverse(num.begin(), num.end());
            vector dp(2, vector<ll> (max(num.size(), s.size()) + 1));
            dp[1][max(num.size(), s.size())] = 1;
            for (int i = num.size() - 1; i >= 0; i--) {
                int x = num[i] - '0';
                if (i >= s.size()) {
                    if (x > limit) {
                        dp[0][i] += (limit + 1) * (dp[0][i + 1] + dp[1][i + 1]);
                    } else {
                        dp[1][i] += dp[1][i + 1];
                        dp[0][i] += x * dp[1][i + 1] + (limit + 1) * dp[0][i + 1];
                    }
                } else {
                    int y = s[i] - '0';
                    if (x > y) {
                        dp[0][i] += dp[1][i + 1] + dp[0][i + 1];
                    } else if (x == y) {
                        dp[1][i] += dp[1][i + 1];
                        dp[0][i] += dp[0][i + 1];
                    } else {
                        dp[0][i] += dp[0][i + 1];
                    }
                }
            }
            return dp[0][0] + dp[1][0];
        };
        return cal(finish) - cal(start - 1);
    }
};

力扣每日一题2843-统计对称整数的数目

日期：2025-04-11

题意

2 * n位数字组成的整数x，若其前n与后n位数位和相等，则称其对称。

求给定范围[low, high]内对称数的个数。

思路

注意到数据范围很小 直接遍历计数即可。

但这样太不优雅了，若数据范围扩大该如何做呢，显然和昨天一样是可以通过数位dp来解决的，但尝试了一下感觉好麻烦哦，不想写，easy题有easy题的解法，摆了。

实现

class Solution {
public:
    static constexpr int mx = 20;
    int countSymmetricIntegers(int low, int high) {
        auto check = [](int x) -> bool {
            string s = to_string(x);
            int n = s.size();
            if (n & 1) return false;
            int sum = 0;
            for (int i = 0; i < n; i++) {
                sum += (i < n / 2 ? 1 : -1) * (s[i] - ' 0');
            }
            return sum == 0;
        };
        int ans = 0;
        for (int i = low; i <= high; i++) {
            if (check(i)) ans++;
        }
        return ans;
    }
};

力扣每日一题3272-统计好整数的数目

日期：2025-04-12

题意

若一个数x是回文整数且被k整除则称其为k回文整数。

若一个数y可以对其数位进行重排后变为k回文整数则称其为好整数（无前导零）。

对于给定的数位n与个位数k，求问有多少个n位数为好整数。

思路

首先考虑得到k回文整数再将其重排得到好整数

对于回文数，因为其前半部分与其后半部分反转后相同，故可以考虑枚举其前半部分。

能否整除k仅需计算一下即可。

而对于一个k回文整数有多少种合法重排方式，则是一个较为简单的排列组合问题，首先是第一位数不能为0,剩余位数可任意排序，又相同的数之间互换是相同的，故而可以推导出：

记为该数为i的数位个数

合法重排方案数

显然当均相等时得到的方案数相同，再考虑对其使用哈希去重即可

实现

array<int, 11> f;
int init = []() {
    f[0] = 1;
    for (int i = 1; i <= 10; i++) {
        f[i] = i * f[i - 1];
    }
    return 0;
}();
class Solution {
using ll = long long;
public:
    long long countGoodIntegers(int n, int k) {
        ll ans = 0;
        int b = pow(10, (n + 1) / 2 - 1);
        unordered_set<string> vis;
        array<int, 10> cnt;
        for (int i = b; i < b * 10; i++) {
            string s = to_string(i), t = s;
            if (n & 1) t.pop_back();
            reverse(t.begin(), t.end());
            s += t;
            if (stoll(s) % k) continue;
            ranges::sort(s);
            if (vis.count(s)) continue;
            vis.insert(s);
            cnt.fill(0);
            for (const auto& ch : s) cnt[ch - '0']++;
            ll res = (n - cnt[0]) * f[n - 1];
            for (int i = 0; i < 10; i++) {
                res /= f[cnt[i]];
            }
            ans += res;
        }
        return ans;
    }
};

力扣每日一题1922-统计好数字的数目

日期：2025-04-13

题意

若一个数字串满足偶数位均位偶数奇数位均为质数，则称其为好数字。

问长度为给定n的好数字个数（可前导零）。

思路

个位数的偶数共有5个0, 2, 4, 6, 8

个位数的质数共有4个2, 3, 5, 7

且允许存在前导零，那么显然这是一个简单的数学问题

记为even偶数位个数，odd为奇数位个数则有

方案数

唯一需要注意的是n较大 , 需用上快速幂，且答案较大需对1e9 + 7取模

实现

class Solution {
using ll = long long;
static constexpr ll mod = 1e9 + 7;
public:
    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;
    }
    int countGoodNumbers(long long n) {
        ll even = n / 2 + (n & 1), odd = n / 2;
        return powMod(5, even) * powMod(4, odd) % mod;
    }
};

力扣每日一题1534-统计好三元组

日期：2025-04-14

题意

给定数组arr，与三整数a、b、c，求满足以下条件的三元组(i, j, k)个数

​

思路

注意到数组大小范围很小仅有1e2，直接暴力即可。

当然也存在更加高效的做法，但我有点犯懒了，详细还是请见他人博客（

实现

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int ans = 0;
        for (int i = 0; i < arr.size(); i++) {
            for (int j = i + 1; j < arr.size(); j++) {
                if (abs(arr[i] - arr[j]) > a) continue;
                for (int k = j + 1; k < arr.size(); k++) {
                    if (abs(arr[j] - arr[k]) > b) continue;
                    if (abs(arr[i] - arr[k]) > c) continue;
                    ans++;
                }
            }
        }
        return ans;
    }
};

力扣每日一题2179-统计数组中好三元组数目

日期：2025-04-15

题意

给定两[0, n - 1] 的排列nums1与nums2，求满足下列条件的三元组(i, j, k)的个数

i, j, k的出现顺序在nums1与nums2中均一致为顺序出现，记p1_i 为i在nums1中出现的位置，p2_i为i在nums2中出现的位置，即：

思路

注意到此处三元组仅关注数出现的顺序而与数的具体值无关，可以考虑将nums1 中的各个数值映射到其对应的出现顺序。

对于统计合法的三元组问题，可以考虑枚举中间值j再判断其前后满足条件的i与k数量，此处枚举j那么对于同一个j其合法的三元组个数即为：nums1 与 nums2 中均出现在 j 前的数的个数 * nums1 与 nums2 中均出现在 j 之后的数的个数

那么枚举nums2中的元素，将每个元素视作三元组的j，使用与nums1相同的映射函数P：

  • 小于P(nums2[j])的数即为在nums1中，于nums2[j]之前所出现过的数；

  • 而i < j | nums2[i]即是在nums2中，于nums2[j] 之前所出现过的数；

  • 大于P(nums2[j])的数即为在nums1中，于nums2[j]之后将出现的数；

  • 而i > j | nums2[i]即是在nums2中，于nums2[j] 之后将出现的数；

取并操作即可得到nums1 与 nums2 中均出现在 nums2[j] 前的数的个数 与 nums1 与 nums2 中均出现在 nums2[j] 之后的数的个数

如何快速维护得到小于某个值且在之前出现过的值的个数呢，比较自然的可以想到树状数组，当然线段树等其他数据结构也是可行的。

实现

template<typename T>
class Fenwick {
private:
    int n;
    vector<T> a;
public:
    Fenwick(int x) {
        n = x;
        a.resize(x + 1);
    }
    void add(int x, T val) {
        for ( ; x <= n; x += (x & -x)) {
            a[x] += val;
        }
    }
    T query(int x) {
        T res = 0;
        for ( ; x > 0; x -= (x & -x)) {
            res += a[x];
        }
        return res;
    }
};
class Solution {
using ll = long long;
public:
    long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
        ll ans = 0;
        const int n = nums1.size();
        vector<int> p(n);
        for (int i = 0; i < n; i++) {
            p[nums1[i]] = i;
        }

        Fenwick<int> f(n);
        for (int i = 0; i < n; i++) {
            int t = f.query(p[nums2[i]]);
            ans += 1ll * t * (n - 1 - p[nums2[i]] - i + t);
            f.add(p[nums2[i]] + 1, 1);
        }
        return ans;
    }
};

力扣每日一题2537-统计好子数组的数目

日期：2025-04-16

题意

给定数组nums与定值k，求该nums中至少有k对相等数的子数组数目

即有多少子数组arr至少含有k对(i, j)满足i < j 且 arr[i]==arr[j]

思路

求满足条件的子数组个数，比较经典的思路就是双指针进行一个滑动窗口。

维护区间内相等数的对数可以考虑使用哈希记录各个数出现的次数。

枚举窗口的右端点，对于每个右端点其最左不满足条件的位置左侧所有位置均满足条件。

实现

class Solution {
using ll = long long;
public:
    long long countGood(vector<int>& nums, int k) {
        ll ans = 0;
        unordered_map<int, int> cnt;
        for (int l = 0, r = 0, p = 0; r < nums.size(); r++) {
            p += cnt[nums[r]];
            cnt[nums[r]]++;
            while (p >= k) {
                cnt[nums[l]]--;
                p -= cnt[nums[l]];
                l++;
            }
            ans += l;
        }
        return ans;
    }
};

力扣每日一题2176-统计数组中相等且可以被整除的数对

日期：2025-04-17

题意

给定数组nums与定值k，求满足以下条件的下标 (i, j) 对数

0 <= i < j < nums.size()

nums[i] == nums[j]

i * j % k == 0

思路

首先这道题的数据范围比较小，是可以直接暴力进行的（没有预处理等操作暴力反而还更快些）

但这样不太优雅，我们假定数据范围比较大时应该如何做呢

首先考虑什么情况下 i * j % k == 0呢

显然若i % k == 0 || j % k == 0时等式是成立的

但若i、j均不为k的倍数呢，是否有可能乘积被k 整除，举例发现是可行的比如6 % 4 != 0, 10 % 4 != 0, 6 * 10 % 4 == 0

可以发现：

若j % t == 0 可得i * j % k == 0

那么枚举j再计算符合nums[i] == nums[j] 且 i % t == 0的条件的i个数即可

此处使用哈希记录j之前的值为nums[j]及其对应下标的因数，如此只需统计cnt[(nums[j], t)]即可

注意unordered_map的键值不能直接使用pair<>需要重载其运算符，或将nums[j] 与 t合并为一个数再进行哈希计算

实现

暴力实现

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int ans = 0;
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                if (nums[i] == nums[j] && i * j % k == 0) ans++;
            }
        }
        return ans;
    }
};

其他实现

constexpr int N = 100;
vector<vector<int>> factors(N + 1);
int init = []() {
    for (int i = 1; i <= N; i++) {
        for (int j = i; j <= N; j += i) {
            factors[j].push_back(i);
        }
    }
    return 0;
} ();

class Solution {
public:
    int countPairs(vector<int>& nums, int k) {
        int ans = 0;
        auto cal = [](int x, int f) -> int {
            return x << 8 | f;
        };
        unordered_map<int, int> cnt;
        for (int i = 0; i < nums.size(); i++) {
            int t = k / gcd(i, k);
            ans += cnt[cal(nums[i], t)];
            if (i && nums[i] == nums[0]) ans++;
            for (auto f : factors[i]) {
                cnt[cal(nums[i], f)]++;
            }
        }
        return ans;
    }
};

力扣每日一题2364-统计坏数对的数目

日期：2025-04-18

题意

给定数组nums，求满足以下条件的数对(i, j)个数

思路

这几天的每日一题都是类似的求数对或求三元组个数，应该可以感受到求不等于是没有求等于对数方便的。

那么可以考虑正难则反，求出满足下列条件的数对(i, j)个数，再取补集即可。

好像还是不是很好做，对于给定的i 或 j还是需要枚举另一个数进行筛选

但是发现可以将式子移项变形

就可以发现此时比较好做了，只需枚举每个数，记录其下标与其值之差即可。

实现

class Solution {
using ll = long long;
public:
    long long countBadPairs(vector<int>& nums) {
        unordered_map<int, int> cnt;
        ll ans = ll(nums.size()) * (ll(nums.size()) - 1) / 2;
        for (int i = 0; i < nums.size(); i++) {
            ans -= cnt[i - nums[i]];
            cnt[i - nums[i]]++;
        }
        return ans;
    }
};

力扣每日一题2563-统计公平数对的数目

日期：2025-04-19

题意

给定数组nums与定值lower和upper，求满足以下条件的数对(i, j)个数

思路

考虑固定nums[j]那么什么样的nums[i]满足条件呢，移项发现

不难发现nums[i]越大lower - nums[i]与upper - nums[i]越小

那么比较好实现的就是二分得到第一个满足条件的与最后一个不满足条件的

实现

class Solution {
using ll = long long;
public:
    long long countFairPairs(vector<int>& nums, int lower, int upper) {
        ranges::sort(nums);
        ll ans = 0;
        const int n = nums.size();
        for (int i = 0; i < n; i++) {
            int r = upper_bound(nums.begin(), nums.begin() + i, upper - nums[i]) - nums.begin();
            int l = lower_bound(nums.begin(), nums.begin() + i, lower - nums[i]) - nums.begin();
            ans += r - l;
        }
        return ans;
    }
};

力扣每日一题781-森林中的兔子

日期：2025-04-20

题意

给定整数数组answers,其中answers[i]表示第i只兔子回答问题"还有多少只兔子与你颜色相同"的答案。

求问兔子总数量的最小可能值

思路

并没有什么算法上的知识，就是一个比较简单的数学思维题。

如果有1只兔子回答1，显然答案是2，因为问题是还有多少只也就是除你外有多少只与你同色

如果有2只兔子回答1，显然答案是2，因为2只同色的问同样的问题答案相同是符合题意的

如果有3只兔子回答1，显然答案是4，若3只兔子颜色相同那么它们的回答是不可能为1的，使得总数最小可以贪心的将其中两只配对，另一只独立，问题就变为了前两个问题的和

…

不难推出，回答为x的兔子，只可能与回答x的其他兔子同色，最多可以与另外x只回答均为x的兔子组成一个有x + 1只兔子的同色组

记录各个回答的兔子个数，然后贪心地计算答案即可。

实现

class Solution {
public:
    int numRabbits(vector<int>& answers) {
        unordered_map<int, int> cnt;
        for (const auto& x : answers) {
            cnt[x]++;
        }
        int ans = 0;
        for (const auto& [x, t] : cnt) {
            ans += (t + x) / (x + 1) * (x + 1);
        }
        return ans;
    }
};

力扣每日一题2145-统计隐藏数组数目

日期：2025-04-21

题意

给定某隐藏数组的差分数组differences与定值上界upper及定值lower，求满足最大最小值不超过给定上下界的合法隐藏数组的个数。

思路

对差分数组求前缀和即可获知隐藏数组各数与第一个数的差值，也因此易得隐藏数组最大最小值的相对差值。

又对于给定的差分结果，确定一个数即可确定整个隐藏数组。

根据给定的上下界upper与lower计算结果即可。

实现

class Solution {
using ll = long long;
public:
    int numberOfArrays(vector<int>& differences, int lower, int upper) {
        ll mn = 0, mx = 0;
        ll cur = 0;
        for (const auto& x : differences) {
            cur += x;
            mn = min(mn, cur);
            mx = max(mx, cur);
        }
        return max(upper - lower - (mx - mn) + 1, 0ll);
    }
};

力扣每日一题2338-统计理想数组的数目

日期：2025-04-22

题意

给定值n与maxValue

称满足以下条件的数组arr为理想数组：

  • 长度为n
  • 每个元素在[1, maxValue]
  • 每个元素均可被前一个元素整除即arr[i] % arr[i - 1] == 0

求不同理想数组数目

思路

每个元素均可被前一个元素整除，也就是每个数均为上一个元素的倍数。

当数组内的最大值即最后一个元素固定时，有多少个满足条件的理想数组呢。可以考虑将最大值质因数分解得到：

那么是不是在数组的n个位置中相对前一个元素，分别乘了

次次次

那么问题就转化为了在n个盒子放a个红球，b个黄球...k个蓝球允许有盒子空出，允许多个球在同一盒子的问题。

显然不同颜色的球的方法是互相独立的互相之间可以直接乘算。

那么在n个盒子中放x个同样的球允许放空有多少种方法呢，这里我参考了灵茶山艾府大佬的题解，讲的非常好

可以转化为在n个盒子中放x + n个相同的球，不允许放空；在放完结束后从每个盒子中各拿出一个球即为n个盒子放x个球允许放空。

那么如何做在n个盒子中放x + n个相同的球，不允许放空呢，显然是有x + n个球x + n - 1个空隙中插入n - 1个挡板的方案即

故只需预处理出组合数与质因式分解的结果再进行方案数计算即可。

实现

constexpr int mod = 1e9 + 7;
constexpr int MX = 1e4;
vector<int> primes;
int minp[MX + 1];
vector<vector<int>> pi(MX + 1);
constexpr int MK = __lg(MX) + 1;
int C[MX + MK + 1][MX + 1];

int init = []() {
    for (int i = 2; i <= MX; i++) {
        if (minp[i] == 0) {
            minp[i] = i;
            primes.push_back(i);
        }
        for (const auto& p : primes) {
            if (p * i > MX) break;
            minp[p * i] = p;
            if (minp[i] == p) break;
        }
    }

    for (int i = 2; i <= MX; i++) {
        int x = i, mp = minp[i];
        while (x != 1) {
            int cnt = 0;
            for ( ; x % mp == 0; x /= mp, cnt++);
            pi[i].push_back(cnt);
            mp = minp[x];
        }
    }

    for (int i = 0; i <= MX + MK; i++) {
        C[i][0] = 1;
        for (int j = 1; j <= min(i, MX); j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % mod;
        }
    }
    return 0;
} ();

class Solution {
public:
    int idealArrays(int n, int maxValue) {
        int ans = 0;
        for (int i = 1; i <= maxValue; i++) {
            int res = 1;
            for (const auto& x : pi[i]) {
                res = 1ll * res * C[x + n - 1][n - 1] % mod;
            }
            ans = (ans + res) % mod;
        }
        return ans;
    }
};

力扣每日一题1399-统计最大组的数目

日期：2025-04-23

题意

给定整数n，将[1, n]中所有数位和相同的分作一组，求大小并列最大的组的数目

思路

首先这道题的数据范围很小

可以考虑直接暴力枚举[1, n]计算其数位和然后统计对应组的大小。

进阶一些可以考虑数位dp，但比较常规便不过多赘述，仅列出递推公式：

记为递推到第位数位和为前几位是（）否（）等于对应数位的方案个数

为十进制下第位的数

为第位所填的数

实现

数位dp实现

class Solution {
public:
    int countLargestGroup(int n) {
        string s = to_string(n);
        reverse(s.begin(), s.end());
        const int N = s.size();
        vector dp(2, vector<vector<int>> (N + 1, vector<int> (9 * N + 1)));
        dp[1][N][0] = 1;
        for (int i = N; i > 0; i--) {
            for (int j = 0; j <= (N - i) * 9; j++) {
                if (dp[0][i][j] == 0 && dp[1][i][j] == 0) continue;
                for (int k = 0; k <= 9; k++) {
                    if (k < s[i - 1] - '0') {
                        dp[0][i - 1][j + k] += dp[0][i][j] + dp[1][i][j];
                    } else if (k == s[i - 1] - '0') {
                        dp[1][i - 1][j + k] += dp[1][i][j];
                        dp[0][i - 1][j + k] += dp[0][i][j];
                    } else {
                        dp[0][i - 1][j + k] += dp[0][i][j];
                    }
                }
            }
        }
        int mx = 0, ans = 0;
        for (int i = 1; i <= 9 * N; i++) {
            int t = dp[0][0][i] + dp[1][0][i];
            if (mx < t) {
                mx = t;
                ans = 1;
            } else if (mx == t) {
                ans++;
            }
        }
        return ans;
    }
};

力扣每日一题2799-统计完全子数组的数目

日期：2025-04-24

题意

给定数组nums，称不同元素的数目与整个nums不同元素的个数相同的子数组为完全子数组。求nums中完全子数组个数。

思路

思路与2025-04-16的2537-统计好子数组的数目其实是高度类似的

进行一个滑动窗口，枚举窗口的右端点，对于每个右端点其最左不满足条件的位置左侧所有位置均满足条件。

使用哈希简单计数即可。

实现

class Solution {
public:
    int countCompleteSubarrays(vector<int>& nums) {
        unordered_set<int> st(nums.begin(), nums.end());
        int cnt = st.size();
        int ans = 0, cur = 0;
        unordered_map<int, int> f;
        for (int l = 0, r = 0; r < nums.size(); r++) {
            f[nums[r]]++;
            if (f[nums[r]] == 1) cur++;
            while (l <= r && cur == cnt) {
                f[nums[l]]--;
                if (f[nums[l]] == 0) cur--;
                l++;
            }
            ans += l;
        }
        return ans;
    }
};

力扣每日一题2845-统计趣味子数组的数目

日期：2025-04-25

题意

给定整数数组nums，以及整数modulo和k。

记数组内满足x % modulo == k的个数为cnt

若nums的某子数组满足cnt % modulo == k则称其为趣味子数组，求nums内的趣味子数组个数。

思路

首先可以发现我们仅关注满足x % modulo == k的x的个数，因此我们可以将所有nums内模modulo为k的数记为1其他数则记为0;

完成转换后什么样的子数组满足cnt % modulo == k呢，显然需要满足

那么是不是可以联想到前缀和，再结合一下模运算的性质，可以得出结果。

实现

class Solution {
using ll = long long;
public:
    long long countInterestingSubarrays(vector<int>& nums, int modulo, int k) {
        ll ans = 0;
        unordered_map<int, int> cnt;
        int pre = 0;
        for (const auto& x : nums) {
            cnt[pre]++;
            pre += x % modulo == k;
            if (pre >= modulo) pre -= modulo;
            ans += cnt[(pre - k + modulo) % modulo];
        }
        return ans;
    }
};

力扣每日一题2444-统计定界子数组的数目

日期：2025-04-26

题意

给定数组nums与两整数minK与maxK

若某数组满足以下条件则称其为定界子数组

求nums中定界子数组个数

思路

又是求满足条件的子数组个数，最近的每日一题都是这种题，那写到这应该还是比较熟悉的。比较自然的可以想到使用滑动窗口求解。

枚举右端点，那么有多少个左端点是可以符合条件的呢？

首先区间的最大值需要为maxK且最小值需为minK故而左端点一定是在当前右端点左侧离右端点最近的值为minK的左侧与最近的值为maxK的左侧，即两者取min

同时区间内不能存在[minK, maxK]的值，所以合法左端点最远可以取到当前右端左侧最近的不属于[minK, maxK]的位置。

实现

class Solution {
using ll = long long;
public:
    long long countSubarrays(vector<int>& nums, int minK, int maxK) {
        ll ans = 0;
        for (int i = 0, mx = -1, mn = -1, no = -1; i < nums.size(); i++) {
            if (nums[i] == minK) mn = i;
            if (nums[i] == maxK) mx = i;
            if (nums[i] > maxK || nums[i] < minK) no = i;
            ans += max(min(mx, mn) - no, 0);
        }
        return ans;
    }
};

力扣每日一题3392-统计符合条件长度为 3 的子数组数目

日期：2025-04-27

题意

给定数组nums，求长度为3且第一个数与第三个数的和为第二个数的一半的子数组个数。

思路

很明显就是求nums[i] == (nums[i - 1] + nums[i + 1]) * 2的个数，直接暴力即可，稍微注意以下边界就好。

实现

class Solution {
public:
    int countSubarrays(vector<int>& nums) {
        int ans = 0;
        const int n = nums.size();
        for (int i = 1; i < n - 1; i++) {
            if (nums[i] & 1) continue;
            ans += nums[i] / 2 == nums[i - 1] + nums[i + 1];
        }
        return ans;
    }
};

力扣每日一题2302-统计得分小于 K 的子数组数目

日期：2025-04-28

题意

给定数组nums与整数上界k

求nums内区间和乘区间长度严格小于k的非空子数组个数

思路

又又又是求数组内满足条件的子区间个数

那写了这么多相似的题，应该很自然的可以想到使用滑动窗口，枚举右端点

唯一差异是先前的多是区间越长越可能合法，这题是区间越小越可能合法，那就是改 寻第一个不满足的左端点 为 寻第一个满足的左端点，统计方向改变即可。

仅需维护当前窗口和即可。

实现

class Solution {
using ll = long long;
public:
    long long countSubarrays(vector<int>& nums, long long k) {
        ll ans = 0;
        ll cur = 0;
        for (int l = 0, r = 0; r < nums.size(); r++) {
            cur += nums[r];
            while (l <= r && cur * (r - l + 1) >= k) {
                cur -= nums[l++];
            }
            ans += r - l + 1;
        }
        return ans;
    }
};

力扣每日一题2962-统计最大元素出现至少 K 次的子数组

日期：2025-04-29

题意

给定数组nums与定值k，求nums最大值至少出现k次的子数组个数。

思路

这个月全是这种类似的题啊，完全没有什么讲的想法与必要。

找满足条件的子区间个数，滑动窗口，枚举右端点找最左不满足的左端点就好。

实现

class Solution {
using ll = long long;
public:
    long long countSubarrays(vector<int>& nums, int k) {
        ll ans = 0;
        const int n = nums.size();
        int mx = ranges::max(nums);
        for (int l = 0, r = 0, cur = 0; r < n; r++) {
            cur += nums[r] == mx;
            while (l <= r && cur >= k) {
                cur -= nums[l++] == mx;
            }
            ans += l;
        }
        return ans;
    }
};

力扣每日一题1295-统计位数为偶数的数字

日期：2025-04-30

题意

给定数组nums，求nums中数位个数为偶数的数的个数。

思路

直接遍历nums求每个数的位数即可。

实现

class Solution {
public:
    int findNumbers(vector<int>& nums) {
        int ans = 0;
        for (const auto& x : nums) {
            ans += (to_string(x).size() & 1) == 0;
        }
        return ans;
    }
};

其他

也是顺利拿下2025-04的力扣全勤了，也是结束了写博客的第一个月。

做下来后感觉其实也没什么特别难的题，琢磨琢磨、看看别人题解琢磨琢磨总是能做出来的；以及感觉这个月好多都是给定数组求满足条件的子区间个数，有点写闷了。

以前看别人题解，总是嫌别人写得太简单跳步太多，后来轮到自己写，会犯懒不想写得太详细，会有我都会了大家应该也会的想法；这确实是不太好的，但我有点把握不好啰嗦和详细清晰的度，也有点平衡不好花费的时间与详实程度。争取在未来的博客中得到改进吧。

目前为止，我的博客还是没什么人看的，虽然主要原因是我还没买域名也没配置可以在搜索引擎检索到更没和多少人讲；博客配置也还存在些问题，比如多行Latex公式还是会挤在一起，图片还贴不上，争取下个月折腾完善一下吧。

然后好像就没什么特别的感想了，五一将至，祝大家节日快乐假期愉快，love。

文末是当前博客访问人数与四月徽章留作纪念，至于贴图问题，应该可能大概2025-05可以解决吧。（报告，贴图问题已于2025-05-03解决）

访问数

四月徽章