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

目录

力扣每日一题2071-你可以安排的最多任务数目

日期：2025-05-01

题意

给定n个任务m名工人，第i个任务完成需要力量tasks[i]，第j名工人力量为workers[j]；同时拥有pills个药丸，每个药丸可使一个工人力量提高strengh；每个工人最多可以完成一个任务使用一个药丸，求最多可以完成多少任务。

思路

我们首先考虑在不使用药丸的前提下，若需完成任意x个任务，是否可以完成。

显然应当选出前x小的任务与前x大的工人，若能一一对应完成即可。

那应当对workers与tasks进行排序，取出x个任务与工人，贪心地使最小的工人与最小的任务匹配。

如果加入k个药丸的条件呢？是否可以完成任意x个任务如何判断

那么一个工人所能完成的任务应该是一个区间[workers[i], workers[i] + strengh]，如果不使用药丸，该工人应该依旧选择与所能完成的最小任务匹配；如果使用药丸，贪心地应该选择能完成的最大任务匹配，使得药丸发挥最大作用，这个是基于直觉的guess，需要证明应该也不难。

如果可以考虑明白上面的事，那么你已经知道如何check给定的任务数x了！接下来就可以进行一个二分查找得到答案。

实现

class Solution {
public:
    int maxTaskAssign(vector<int>& tasks, vector<int>& workers, int pills, int strength) {
        ranges::sort(tasks);
        ranges::sort(workers);
        const int n = tasks.size(), m = workers.size();

        auto check = [&](int x) -> bool {
            int cnt = 0, cur = 0;
            deque<int> q;
            for (int i = m - x; i < m; i++) {
                for ( ; cur < n && tasks[cur] <= workers[i] + strength; cur++) {
                    q.push_back(tasks[cur]);
                }
                if (q.empty()) return false;
                if (q.front() <= workers[i]) {
                    q.pop_front();
                    continue;
                }
                if (cnt >= pills) return false;
                cnt++;
                q.pop_back();
            }
            return true;
        };

        int lo = 0, hi = min(n, m);
        while (lo < hi) {
            int mid = lo + hi + 1 >> 1;
            if (check(mid)) {
                lo = mid;
            } else {
                hi = mid - 1;
            }
        }
        return lo;
    }
};

力扣每日一题838-推多米诺

日期：2025-05-02

题意

给出字符串dominoes表示第0时刻排成一排的多米诺骨牌，其中：

  • dominoes[i] = 'L'表示初始时该牌向左倒
  • dominoes[i] = 'R'表示初始时刻该牌向右倒
  • dominoes[i] = '.'表示初始时刻该牌直立

每过一秒倒下的牌会使其倒下方向的下一张牌向同方向倒下（若下一张牌未倒下）；但若一张未倒下的牌同时收到左右两边相反方向的影响，其不会倒下。

求问给定牌的最终情况。

思路

比较简单的模拟题，第一想法是开个数组time记录其受到左右影响的时刻，哪个小往哪边倒，从左到右再从右到左模拟两趟即可。

但再观察一下发现，一片连续的未倒牌，其最终状态只受其两侧两个牌的状态影响：

  • L...L->LLLLL
  • L...R->L...R
  • R...R->RRRRR
  • R...L->RR.LL

那只需遍历一趟找到连续未倒牌，比较其左右两侧牌的状态即可。

实现

记录比较时间模拟：

class Solution {
public:
    string pushDominoes(string dominoes) {
        const int n = dominoes.size();
        vector<int> time(n);
        for (int i = 0, t = 0; i < n; i++) {
            if (dominoes[i] == 'R') {
                t = 1;
            } else if (dominoes[i] == '.') {
                if (t > 0) {
                    time[i] = t++;
                }
            } else {
                t = 0;
            }
        }
        for (int i = n - 1, t = 0; i >= 0; i--) {
            if (dominoes[i] == 'R') {
                t = 0;
            } else if (dominoes[i] == 'L') {
                t = 1;
            } else {
                if (t == 0) {
                    if (time[i]) dominoes[i] = 'R';
                    continue;
                }
                if (time[i] == 0) {
                    dominoes[i] = 'L';
                    t++;
                } else {
                    if (time[i] == t) {
                        t = 0;
                    } else if (time[i] > t) {
                        dominoes[i] = 'L';
                        t++;
                    } else {
                        dominoes[i] = 'R';
                        t = 0;
                    }
                }
            }
        }
        return dominoes;
    }
};

比较未倒牌左右：

class Solution {
public:
    string pushDominoes(string dominoes) {
        const int n = dominoes.size();
        for (int i = 0; i < n; i++) {
            if (dominoes[i] != '.') continue;
            int j = i + 1;
            for ( ; j < n && dominoes[j] == '.'; j++);
            if (i == 0 && j == n) continue;
            else if (i == 0 && dominoes[j] == 'L') {
                for ( ; i < j; i++) dominoes[i] = 'L';
            } else if (j == n && dominoes[i - 1] == 'R') {
                for ( ; i < j; i++) dominoes[i] = 'R';
            } else if (i != 0 && j != n) {
                if (dominoes[i - 1] == dominoes[j]) {
                    for ( ; i < j; i++) dominoes[i] = dominoes[j];
                } else if (dominoes[i - 1] == 'R' && dominoes[j] == 'L') {
                    int m1 = i + j + 1 >> 1, m2 = i + j >> 1;
                    for ( ; i < m2; i++) dominoes[i] = 'R';
                    for (i = m1; i < j; i++) dominoes[i] = 'L';
                }
            }
            i = j;
        }
        return dominoes;
    }
};

力扣每日一题1007-行相等的最少多米诺旋转

日期：2025-05-03

题意

有一排可分上下部分的多米诺骨牌，每张牌上下部分均分别写着[1, 6]的数字，每次操作可使得某张牌上下颠倒，求使得上部/下部所有数字相同的最小操作次数或判断其不可能。

思路

注意到牌上数字的范围很小，可以考虑直接枚举是哪个数可以满足条件及最小操作次数；但这样常数，呃也不算大但不够优，可以再考虑开个数组记录各个数字出现次数及使其在上部或下部满足同排均相同的操作次数，如此遍历一趟即可。

没什么特别需要注意的地方。

实现

class Solution {
public:
    int minDominoRotations(vector<int>& tops, vector<int>& bottoms) {
        array<int, 7> num, tcnt, bcnt;
        num.fill(0); tcnt.fill(0); bcnt.fill(0);
        const int n = tops.size();
        for (int i = 0; i < n; i++) {
            if (tops[i] == bottoms[i]) {
                num[tops[i]]++;
            } else {
                num[tops[i]]++;
                num[bottoms[i]]++;
                tcnt[bottoms[i]]++;
                bcnt[tops[i]]++;
            }
        }
        int mn = n;
        for (int i = 1; i < 7; i++) {
            if (num[i] == n) mn = min({mn, tcnt[i], bcnt[i]});
        }
        return mn == n ? -1 : mn;
    }
};

力扣每日一题1128-等价多米诺骨牌对的数量

日期：2025-05-04

题意

给一组多米诺骨牌，每张牌上有两个数，可以任意次旋转使某张牌上数顺序交换，求相同牌的对数。

思路

可以任意次改变某牌上数的顺序，即牌上数顺序无关紧要，判断时令较小数在前或在后统一标准即可。

遍历一趟使用哈希记录各个牌型数量即可。

实现

class Solution {
public:
    int numEquivDominoPairs(vector<vector<int>>& dominoes) {
        array<int, 100> cnt;
        cnt.fill(0);
        int ans = 0;
        for (const auto& vec : dominoes) {
            int t = min(vec[0], vec[1]) * 10 + max(vec[0], vec[1]);
            ans += cnt[t];
            cnt[t]++;
        }
        return ans;
    }
};

力扣每日一题790-多米诺和托米诺平铺

日期：2025-05-05

题意

有两种瓷砖，形如：

种类1
.
.
种类2
..
.

两种瓷砖均可以任意旋转，求一个2 * n的的面板可以有几种不同的铺法。

思路

一个很经典的dp问题，为方便讨论，记以下称呼

平：
.
.
上凸：
..
.
下凸：
.
..

记

第i列为平有几种铺法

​为第i列为上凸有几种铺法

为第i列为下凸有几种铺法

显然有：

具体原因可以简单手绘得出，故不过多赘述。

仅需注意边界、溢出问题即可。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int numTilings(int n) {
        vector<int> f(n + 1), g(n + 1), h(n + 1);
        f[0] = 1;
        for (int i = 1; i <= n; i++) {
            f[i] = (1ll * f[i - 1] + g[i - 1] + h[i - 1]) % mod;
            if (i > 1) {
                f[i] = (f[i] + f[i - 2]) % mod;
                g[i] = (f[i - 2] + h[i - 1]) % mod;
                h[i] = (f[i - 2] + g[i - 1]) % mod;
            }
        }
        return f[n];
    }
};

力扣每日一题1920-基于排列构建数组

日期：2025-05-06

题意

给定排列nums，希望返回满足以下条件的ans

ans[i] = nums[nums[i]], 0 <= i < nums.size()

思路

开个ans简单地遍历一遍模拟一下即可，空间复杂度为O(n)，没什么难度

进阶：是否可以用O(1)的空间复杂度解决问题呢

如此只能是在nums上原地操作变换，即令nums[i] = nums[nums[i]]

但显然是不可以直接这么做的，因为直接替换nums[i]可能会影响后续的其他操作结果

但由于nums为排列即无重复数，可以注意到nums[i]与要替换nums[i]的nums[nums[i]]、nums[nums[i]]与要替换nums[nums[i]]的nums[nums[nums[i]]]…等等是必定会形成一个环的

即nums变换前后其实是由多个环组成的

那么仅需考虑同时操作变换同一个环内的数字，并记录标记哪些数操作过即可。

实现

简单实现

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            ans[i] = nums[nums[i]];
        }
        return ans;
    }
};

空间O(1)实现

class Solution {
public:
    vector<int> buildArray(vector<int>& nums) {
        const int n = nums.size();
        for (int i = 0; i < n; i++) {
            if (nums[i] < 0) continue;
            int x = nums[i], cur = i;
            while (nums[cur] != i) {
                int nxt = nums[cur];
                nums[cur] = ~nums[nxt];
                cur = nxt;
            }
            nums[cur] = ~x;
        }
        for (int i = 0; i < n; i++) {
            nums[i] = ~nums[i];
        }
        return nums;
    }
};

力扣每日一题3341-到达最后一个房间的最少时间 I

日期：2025-05-07

题意

给定n * m的方格，格子(i, j)必须在时刻moveTime[i][j]之后才可往其移动，每次移动耗时1，初始处于时刻0与左上角(0, 0)，求解到达右下角(n - 1, m - 1)的最早时刻。

思路

比较经典的最短路题，只需把当前时刻t与目的方格最小时刻moveTime[i][j]取max加一即max(t, moveTime[i][j]) + 1作为边权然后跑一下迪杰斯特拉即可。

实现

class Solution {
using ll = long long;
static constexpr array<int, 2> nxt[] = {
    {1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        const int n = moveTime.size(), m = moveTime.back().size();
        const int e = n * m - 1;

        auto cal1 = [&](int x, int y) -> int {
            return x * m + y;
        };
        auto cal2 = [&](int x) -> pair<int, int> {
            return {x / m, x % m};
        };
        auto across = [&](int x, int y) -> bool {
            return x < 0 || x >= n || y < 0 || y >= m;
        };

        vector<bool> vis(n * m);
        priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<>> pq;
        pq.push({0, 0});
        while (!pq.empty()) {
            auto [c, t] = pq.top();
            pq.pop();
            if (vis[t]) continue;
            if (t == e) return c;
            vis[t] = true;
            auto [x, y] = cal2(t);
            for (auto [tx, ty] : nxt) {
                int nx = tx + x, ny = ty + y;
                if (across(nx, ny)) continue;
                int nt = cal1(nx, ny);
                pq.push({max(c, 1ll * moveTime[nx][ny]) + 1, nt});
            }
        }
        return -1;
    }
};

力扣每日一题3342-到达最后一个房间的最少时间 II

日期：2025-05-08

题意

给定n * m的方格，格子(i, j)必须在时刻moveTime[i][j]之后才可往其移动，第奇数次移动耗时1第偶数次移动耗时2，初始处于时刻0与左上角(0, 0)，求解到达右下角(n - 1, m - 1)的最早时刻。

思路

就是昨日题目的变种，移动耗时不再固定为1而是与当前移动次数的奇偶性有关。

那还是比较经典的最短路问题，比较朴素的思想是额外增加一个变量用以记录当前移动的次数。

稍加观察可以注意到，初始位于(0, 0)则移动到(i, j)所需步数奇偶性一定是与i + j相同的，即记当前步数为t一定有：

实现

class Solution {
static constexpr array<int, 2> nxt[] = {
    {1, 0}, {-1, 0}, {0, 1}, {0, -1}
};
public:
    int minTimeToReach(vector<vector<int>>& moveTime) {
        const int n = moveTime.size(), m = moveTime.back().size();
        const int e = n * m - 1;

        auto cal1 = [&](int x, int y) -> int {
            return x * m + y;
        };
        auto cal2 = [&](int x) -> pair<int, int> {
            return {x / m, x % m};
        };
        auto across = [&](int x, int y) -> bool {
            return x < 0 || x >= n || y < 0 || y >= m;
        };

        vector<bool> vis(n * m);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
        pq.push({0, 0});
        while (!pq.empty()) {
            auto [c, t] = pq.top();
            pq.pop();
            if (vis[t]) continue;
            if (t == e) return c;
            vis[t] = true;
            auto [x, y] = cal2(t);
            for (auto [tx, ty] : nxt) {
                int nx = tx + x, ny = ty + y;
                if (across(nx, ny)) continue;
                int nt = cal1(nx, ny);
                pq.push({max(c, moveTime[nx][ny]) + 1 + ((x + y) & 1), nt});
            }
        }
        return -1;
    }
};

力扣每日一题3343-统计平衡排列的数目

日期：2025-05-09

题意

若一个数字字符串奇数位和与偶数位和相同，则称其平衡。

给定一数字字符串num，求其有多少种排列平衡。

答案mod 1e9 + 7， 2 <= num.size() <= 80

思路

记有n个数，和为sum，数位为i的个数有

显然奇数位与偶数位分别有与个

要使得奇数位和与偶数位和相等即将n个数分为大小为与的两个和为的集合，再对集合进行排序

记数位为i的数有个放进了第一个集合，则另一个集合有个数位为i的数放进来第二个集合

假定每个数均不同则共有种排列方式

再考虑去掉数位相同造成的重复排列有

那么有几种划分集合的方法呢，比较自然可以想到dp(以前感觉这种话就是懒得详写，轮到自己写了发现真的是

记为待划分的数为i，第一个集合还缺j个数，第一个集合的和还差k有

显然有递推式

其中t表示数i有t个填到集合一，剩余填到集合二

接着进行一个dp计数即可。

实现

using ll = long long;

constexpr int mod = 1e9 + 7;
constexpr int mx = 40;

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;
}

ll fac[mx + 1], nfac[mx + 1];
auto init = []() -> int {
    fac[0] = 1;
    for (int i = 1; i <= mx; i++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    nfac[mx] = powMod(fac[mx], mod - 2);
    for (int i = mx - 1; i >= 0; i--) {
        nfac[i] = nfac[i + 1] * (i + 1) % mod;
    }
    return 0;
} ();

class Solution {
public:
    int countBalancedPermutations(string num) {
        array<int, 10> cnt;
        cnt.fill(0);
        int sum = 0;
        for (const auto& ch : num) {
            cnt[ch - '0']++;
            sum += ch - '0';
        }
        if (sum & 1) return 0;

        const int n = num.size();
        const int t = n / 2, tot = sum / 2;
        vector dp(t + 1, vector<ll> (tot + 1));
        dp[t][tot] = 1;
        for (int i = 0; i < 10; i++) {
            vector ndp(t + 1, vector<ll> (tot + 1));
            for (int j = 0; j <= t; j++) {
                for (int k = 0; k <= tot; k++) {
                    int tmx = min({j, cnt[i], i > 0 ? (k / i) : cnt[i]});
                    for (int x = 0; x <= tmx; x++) {
                        if (cnt[i] - x > mx) continue;
                        ndp[j - x][k - x * i] += dp[j][k] * nfac[x] % mod * nfac[cnt[i] - x] % mod;
                        ndp[j - x][k - x * i] %= mod;
                    }
                }
            }
            swap(dp, ndp);
        }
        return dp[0][0] * fac[t] % mod * fac[n - t] % mod;
    }
};

力扣每日一题2918-数组的最小相等和

日期：2025-05-10

题意

给定两由非负整数组成的数组nums1与nums2

必须将两数组中的所有0替换为正整数，且使得两数组之和相同。

求最小相等和，或表明其无法实现。

思路

可以发现当两个数组均有0时是一定可以实现的，最小和应贪心地使所有0替换为1取较大数组和；

若均无0则简单比较两数组和即可；

若仅有某一数组含0，且0均转换为最小正整数1后含0数组和仍大于另一数组则无解。

实现

class Solution {
using ll = long long;
public:
    long long minSum(vector<int>& nums1, vector<int>& nums2) {
        ll sum1 = 0, sum2 = 0;
        int cnt1 = 0, cnt2 = 0;
        for (const auto& x : nums1) {
            sum1 += x;
            if (x == 0) cnt1++;
        }
        for (const auto& x : nums2) {
            sum2 += x;
            if (x == 0) cnt2++;
        }
        if ((cnt1 == 0 && sum2 + cnt2 > sum1) || (cnt2 == 0 && sum1 + cnt1 > sum2)) return -1;
        return max(sum1 + cnt1, sum2 + cnt2);
    }
};

力扣每日一题1550-存在连续三个奇数的数组

日期：2025-05-11

题意

给定数组arr，判断其内是否包含连续三个奇数。

思路

比较简单，遍历一遍判断一下就好。

实现

class Solution {
public:
    bool threeConsecutiveOdds(vector<int>& arr) {
        const int n = arr.size();
        for (int i = 1; i < n - 1; i++) {
            if (!(arr[i] & 1)) continue;
            if (arr[i - 1] & arr[i + 1] & 1) return true;
        }
        return false;
    }
};

力扣每日一题2094-找出 3 位偶数

日期：2025-05-12

题意

给定个位数数组digits，可从中任选3个数，按任意顺序排序并组成一个三位数，求所有满足以下条件的不同整数

  • 无前导零
  • 为偶数

思路

三位偶数的个数并不多，可以考虑枚举三位偶数，再判断给出的digits是否可以拼出该数即可。

实现

class Solution {
public:
    vector<int> findEvenNumbers(vector<int>& digits) {
        array<int, 10> cnt;
        cnt.fill(0);
        for (const auto& x : digits) {
            cnt[x]++;
        }

        auto check = [&](int x) -> bool {
            array<int, 3> t;
            bool res = true;
            for (int i = 0; i < 3; i++) {
                t[i] = x % 10;
                x /= 10;
                res &= (--cnt[t[i]] >= 0);
            }
            for (int i = 0; i < 3; i++) cnt[t[i]]++;
            return res;
        };

        vector<int> ans;
        for (int i = 100; i < 1000; i += 2) {
            if (check(i)) ans.push_back(i);
        }
        return ans;
    }
};

力扣每日一题3335-字符串转换后的长度 I

日期：2025-05-13

题意

给定小写字符串s与变换次数t，每次变换会使s中各字符发生如下变化:

a -> b

b -> c

…

唯有z特殊

z -> ab

求解t次变换之后字符串s的最终长度。

思路

我们仅关心字符串的最终长度而不关心其最终形态，且相同字符的变换是相同的，故可以简单的开个数组对各个字符的数量进行模拟计算。

同时本题是数据削弱版 故而可以直接模拟即可。

若数据范围较大，可以将操作转换为矩阵乘法，采用矩阵快速幂即可。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
public:
    int lengthAfterTransformations(string s, int t) {
        array<int, 26> f;
        f.fill(0);
        for (const auto& ch : s) {
            f[ch - 'a']++;
        }
        for (int i = 0; i < t; i++) {
            int x = f.back();
            for (int i = 25; i > 0; i--) {
                f[i] = f[i - 1];
            }
            f[0] = x;
            f[1] = f[1] + x;
            if (f[1] >= mod) f[1] -= mod;
        }
        return accumulate(f.begin(), f.end(), 0ll) % mod;
    }
};

力扣每日一题3337-字符串转换后的长度 II

日期：2025-05-14

题意

给定小写字符串s与变换次数t以及长度为26的变换规则nums

每次比那换为将s[i]变换为字母表中后续的nums[s[i] - 'a']各连续字符，如若有nums[0] = 2; nums[25] = 3则有：

a -> bc

z -> abc

求t次变换后s 的长度

思路

注意到此题为昨日题目的升级版，区别在于变换规则不定且t最大可为1e9

我们且先不考虑完整的26个字母，考虑下仅有abc三个字符互相变换的情况，记与分别为某次变换前后a的的数量

我们设变换规则为

a -> bc
b -> a
c -> ac

那么显然有

​

不难将其转换为矩阵乘法的形式：

那么聪明的你显然不难发现，t次变换不过如下：

那么显然可以使用快速幂的知识将这个运算进行优化。

同时也不难将这个计算方法推广到26个字母与给定的任意变换规则。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
static constexpr int sz = 26;
using ll = long long;
using Matrix = array<array<int, sz>, sz>;

Matrix mul(const Matrix& x, const Matrix& y) {
    Matrix res;
    for (auto& arr : res) arr.fill(0);
    for (int i = 0; i < sz; i++) {
        for (int j = 0; j < sz; j++) {
            if (x[i][j] == 0) continue;
            for (int k = 0; k < sz; k++) {
                res[i][k] = (res[i][k] + 1ll * x[i][j] * y[j][k]) % mod;
            }
        }
    }
    return res;
}
Matrix powMod(Matrix a, int b) {
    Matrix res;
    for (int i = 0; i < sz; i++) {
        res[i].fill(0);
        res[i][i] = 1;
    }
    while (b) {
        if (b & 1) {
            res = mul(res, a);
        }
        a = mul(a, a);
        b >>= 1;
    }
    return res;
}

public:
    int lengthAfterTransformations(string s, int t, vector<int>& nums) {
        Matrix m;
        for (auto& arr : m) arr.fill(0);
        for (int i = 0; i < sz; i++) {
            for (int j = 1; j <= nums[i]; j++) {
                m[(i + j) % sz][i]++;
            }
        }
        Matrix mt = powMod(m, t);

        array<int, sz> cnt;
        cnt.fill(0);
        for (const auto& ch : s) cnt[ch - 'a']++;

        int ans = 0;
        for (int i = 0; i < sz; i++) {
            ll res = 0;
            for (int j = 0; j < sz; j++) {
                res += 1ll * mt[i][j] * cnt[j];
            }
            ans = (ans + res) % mod;
        }
        return ans;
    }
};

力扣每日一题2900最长相邻不相等子序列 I

日期：2025-05-15

题意

给定等长的字符串数组words与二进制数组groups；

求任意最长递增序列I满足groups[I[i]] != groups[I[i + 1]]返回word[I]

思路

显然满足贪心性质，进行一趟遍历即可。

实现

class Solution {
public:
    vector<string> getLongestSubsequence(vector<string>& words, vector<int>& groups) {
        vector<string> ans;
        const int n = groups.size();
        for (int i = 0, cur = -1; i < n; i++) {
            if (cur != groups[i]) {
                cur = groups[i];
                ans.push_back(words[i]);
            }
        }
        return ans;
    }
};

力扣每日一题2901-最长相邻不相等子序列 II

日期：2025-05-16

题意

给定等长的字符串数组words与整数数组groups；

求任意最长递增序列I满足以下条件：

  • groups[I[i]] != groups[I[i + 1]]
  • words[I[i]]与words[I[i + 1]]的汉明距离为1

返回word[I]

思路

数组的长度范围并不大，最大仅有

因此其实怎么写基本都是可以的，进行一个的dp即可

实现

class Solution {
public:
    vector<string> getWordsInLongestSubsequence(vector<string>& words, vector<int>& groups) {
        auto check = [](const string& x, const string& y) -> bool {
            if (x.size() != y.size()) return false;
            int dif = 0;
            for (int i = 0; i < x.size(); i++) {
                if (x[i] != y[i]) dif++;
            }
            return dif == 1;
        };

        const int n = words.size();
        vector<int> len(n, 1), from(n, -1);
        int mxloc = 0;
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 1; j < n; j++) {
                if (len[i] <= len[j] && groups[i] != groups[j] && check(words[i], words[j])) {
                    len[i] = len[j] + 1;
                    from[i] = j;
                }
            }
            if (len[i] > len[mxloc]) mxloc = i;
        }

        vector<string> ans;
        for (int i = mxloc; i != -1; i = from[i]) {
            ans.push_back(words[i]);
        }
        return ans;
    }
};

力扣每日一题75-颜色分类

日期：2025-05-17

题意

给定数组nums表示小球序列，其中红白蓝球分别用0、1、2表示，希望使用原地排序使小球按红白蓝顺序摆放。

思路

原地排序，有且仅有3种不同元素，那么维护中间元素即1区间的左右端点枚举一下即可。

实现

class Solution {
public:
    void sortColors(vector<int>& nums) {
        int p1 = 0, p2 = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] == 1) {
                swap(nums[i], nums[p2++]);
            } else if (nums[i] == 0) {
                swap(nums[i], nums[p1]);
                if (p1 < p2) {
                    swap(nums[i], nums[p2]);
                }
                p1++;
                p2++;
            }
        }
    }
};

力扣每日一题1931-用三种不同颜色为网格涂色

日期：2025-05-18

题意

给定m * n的网格，使用三种不同的颜色进行涂色，要求无相邻的网格颜色相同，求合法涂色的方案数。

思路

注意到m的范围是比较小的而，可以考虑一次填一列的色，那么每次填色的方案数显然是的。

可以通过预处理得到所有合法同时填一列颜色的方案，并得出哪些方案是不可以相邻的，问题就转换为了经典的一维填色方案数，使用dp即可。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
using ll = long long;
public:
    int colorTheGrid(int m, int n) {
        int pm = 1;
        for (int i = 0; i < m; i++) pm *= 3;
        vector<int> a;
        for (int i = 0; i < pm; i++) {
            bool ok = true;
            for (int j = 0, last = -1, x = i; j < m; j++) {
                if (last == x % 3) {
                    ok = false;
                    break;
                }
                last = x % 3;
                x /= 3;
            }
            if (ok) a.push_back(i);
        }

        const int an = a.size();
        vector<vector<int>> adj(an);
        for (int i = 0; i < an; i++) {
            for (int j = i + 1; j < an; j++) {
                bool ok = true;
                for (int k = 0, x = a[i], y = a[j]; k < m; k++) {
                    if (x % 3 == y % 3) {
                        ok = false;
                        break;
                    }
                    x /= 3; y /= 3;
                }
                if (ok) {
                    adj[i].push_back(j);
                    adj[j].push_back(i);
                }
            }
        }

        vector f(an, vector<int> (n));
        for (int i = 0; i < an; i++) f[i][0]++;
        for (int i = 1; i < n; i++) {
            for (int j = 0; j < an; j++) {
                for (const auto& v : adj[j]) {
                    f[j][i] += f[v][i - 1];
                    if (f[j][i] >= mod) f[j][i] -= mod;
                }
            }
        }

        ll ans = 0;
        for (int i = 0; i < an; i++) ans += f[i].back();
        return ans % mod;
    }
};

力扣每日一题3024-三角形类型

日期：2025-05-19

题意

给定三条边长度，判断其是否可构成三角形可构造成什么三角形。

思路

简单的数学判断，if-else一下就好。

实现

class Solution {
public:
    string triangleType(vector<int>& nums) {
        ranges::sort(nums);
        if (nums[0] + nums[1] <= nums.back()) return "none";
        if (nums.front() == nums.back()) return "equilateral";
        if (nums.front() == nums[1] || nums[1] == nums.back()) return "isosceles";
        return "scalene";
    }
};

力扣每日一题3355-零数组变换 I

日期：2025-05-20

题意

给定非负整数数组nums与二维操作数组queries，对于每次操作给出范围[l, r]，每次操作可任选构成下标子集，使得选中的nums[i]减1，求问是否可使得nums转换为零数组。

思路

首先我们可以想到对于每个操作都贪心地对范围所有元素进行减一操作，若元素可减至小于等于0显然是可行的，只需减至0后不再选取其即可。

那么什么情况是不合法的呢，显然是操作覆盖次数小于nums[i]的。

对于区间加减，覆盖次数大小，可以自然的想到使用差分。

实现

class Solution {
public:
    bool isZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        const int n = nums.size();
        vector<int> f(n + 1);
        for (const auto& vec : queries) {
            f[vec.front()]++;
            f[vec.back() + 1]--;
        }
        for (int i = 0; i < n; i++) {
            if (i) f[i] += f[i - 1];
            if (f[i] < nums[i]) return false;
        }
        return true;
    }
};

力扣每日一题3356-零数组变换 II

日期：2025-05-21

题意

给定非负整数数组nums与二维操作数组queries，对于每次操作给出范围[l, r, val]，每次操作可将[l, r]内的每个数独立地减[0, val]，求问若顺序地执行操作queries最少多少次操作可以使得nums变为零数组或判断不可能。

思路

二分

可以发现当操作次数越多时越有可能将nums转变为零数组，那么求最小次数显然可以进行一个二分。直接使用昨日代码进行 check 即可。

线段树

若想在线的做这道题，显然需要的操作是不断进行区间减与区间最大值查询，那就自然地想到使用带懒标记的线段树。

实现

二分实现

class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        const int n = nums.size(), q = queries.size();
        vector<int> f(n + 1);
        auto check = [&](int x) -> bool {
            fill(f.begin(), f.end(), 0);
            for (int i = 0; i < x; i++) {
                f[queries[i][0]] += queries[i].back();
                f[queries[i][1] + 1] -= queries[i].back();
            }
            for (int i = 0; i < n; i++) {
                if (i) f[i] += f[i - 1];
                if (f[i] < nums[i]) return false;
            }
            return true;
        };

        int lo = 0, hi = q + 1;
        while (lo < hi) {
            int mid = lo + hi >> 1;
            if (check(mid)) {
                hi = mid;
            } else {
                lo = mid + 1;
            }
        }

        return lo > q ? -1 : lo;
    }
};

线段树实现

template<class Info, class Tag>
struct SegmentTree {
    int n;
    vector<Info> info;
    vector<Tag> tag;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(vector<Info>(n_, v_));
    }
    template<class T>
    void init(vector<T> init_) {
        n = init_.size();
        info.assign(4 << __lg(n), Info());
        tag.assign(4 << __lg(n), Tag());
        auto build = [&](this auto&& self, int p, int l, int r) -> void {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            self(2 * p, l, m);
            self(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 apply(int p, const Tag &v) {
        info[p].apply(v);
        tag[p].apply(v);
    }
    void push(int p) {
        apply(2 * p, tag[p]);
        apply(2 * p + 1, tag[p]);
        tag[p] = Tag();
    }
    void set(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            set(2 * p, l, m, x, v);
        } else {
            set(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void set(int p, const Info &v) {
        set(1, 0, n, p, v);
    }
    Info query(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;
        push(p);
        return query(2 * p, l, m, x, y) + query(2 * p + 1, m, r, x, y);
    }
    Info query(int l, int r) {
        return query(1, 0, n, l, r);
    }
    void update(int p, int l, int r, int x, int y, const Tag &v) {
        if (l >= y || r <= x) {
            return;
        }
        if (l >= x && r <= y) {
            apply(p, v);
            return;
        }
        int m = (l + r) / 2;
        push(p);
        update(2 * p, l, m, x, y, v);
        update(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void update(int l, int r, const Tag &v) {
        return update(1, 0, n, l, r, v);    
    }
};

struct Tag {
    int add = 0;
    void apply(Tag t) {
        add += t.add;
    }
};

struct Info {
    int mi = 0;
    void apply(Tag t) {
        mi -= t.add;
    }
};

Info operator+(const Info &a, const Info &b) {
    if (a.mi >= b.mi) {
        return a;
    } else {
        return b;
    }
}

using S = SegmentTree<Info, Tag>;

class Solution {
public:
    int minZeroArray(vector<int>& nums, vector<vector<int>>& queries) {
        const int n = nums.size(), q = queries.size();
        S StT(n);
        for (int i = 0; i < n; i++) {
            StT.set(i, {nums[i]});
        }
        if (StT.query(0, n).mi <= 0) return 0;
        for (int i = 0; i < q; i++) {
            const auto& vec = queries[i];
            StT.update(vec[0], vec[1] + 1, {vec[2]});
            if (StT.query(0, n).mi <= 0) return i + 1;
        }
        return -1;
    }
};

力扣每日一题3362-零数组变换 III

日期：2025-05-22

题意

给定非负整数数组nums与二维操作数组queries，对于每次操作给出范围[l, r]，每次操作可任选构成下标子集，使得选中的nums[i]减1，求问最多可删除多少操作仍能将nums转换为零数组。

思路

删除操作好像不太好处理，那么可以考虑正难则反：最少选择多少操作可使得nums转换为零数组呢

显然是可以满足贪心性质的，对于每个仍大于零的数，我们希望选择左端在其左而右端尽可能右的操作，那么可以使用优先队列维护满足条件的右端点，使用差分维护当前数值。

实现

class Solution {
public:
    int maxRemoval(vector<int>& nums, vector<vector<int>>& queries) {
        ranges::sort(queries, [&](const auto& x, const auto& y) {
            return x.front() < y.front();
        });
        const int n = nums.size(), q = queries.size();
        vector<int> f(n + 1);
        priority_queue<int> pq;
        int cnt = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            if (i) f[i] += f[i - 1];
            while (cur < q && queries[cur].front() <= i) {
                pq.push(queries[cur++].back());
            }
            while (f[i] < nums[i] && !pq.empty()) {
                int r = pq.top();
                pq.pop();
                if (r < i) continue;
                f[i]++;
                f[r + 1]--;
                cnt++;
            }
            if (f[i] < nums[i]) return -1;
        }
        return q - cnt;
    }
};

力扣每日一题3068-最大节点价值之和

日期：2025-05-23

题意

给定一棵树及其结点权值nums与正整数k，每次操作可以任选一条边使其两端点权值异或k，可以进行任意次操作，求问最大权值和。

思路

比较自然是可以想到树形dp的，但是仔细一想异或的性质可以发现存在更加简单的写法：

只要两点间存在路径，一定存在操作使得仅两点权值异或k而其余值不受影响，故而可以简单地为结点权值异或前后大小差排序进行贪心。

实现

class Solution {
using ll = long long;
public:
    long long maximumValueSum(vector<int>& nums, int k, vector<vector<int>>& edges) {
        const int n = nums.size();
        ll ans = 0;
        for (int i = 0; i < n; i++) {
            ans += nums[i];
            nums[i] = (nums[i] ^ k) - nums[i];
        }
        ranges::sort(nums, greater());
        for (int i = 1; i < n; i += 2) {
            if (nums[i] + nums[i - 1] > 0) {
                ans += nums[i] + nums[i - 1];
            } else {
                break;
            }
        }
        return ans;
    }
};

力扣每日一题2942-查找包含给定字符的单词

日期：2025-05-24

题意

给定字符串数组words与字符x，寻找所有含x的字符串下标

思路

进行一个暴力即可。

实现

class Solution {
public:
    vector<int> findWordsContaining(vector<string>& words, char x) {
        vector<int> ans;
        for (int i = 0; i < words.size(); i++) {
            if (words[i].find(x) != string::npos) ans.push_back(i);
        }
        return ans;
    }
};

力扣每日一题2131-连接两字母单词得到的最长回文串

日期：2025-05-25

题意

给定由长度为2的字符串组成的字符串数组words，可任选并按任意顺序连接其中字符串，求所能组成最长回文串长度。

思路

给定一个回文串，显然往两边同时添加相反字符串是不会破坏回文性质的。

所有可选字符串长度均为2，那首先考虑回文对称轴在不同字符串之间，显然是贪心的将相反的字符串不断添加到已有回文串左右；

再考虑如果存在可选回文串即s[0] == s[1]，显然可以将其加入回文串的中间，使回文串对称轴位于该字符串中间。

进行一个贪心模拟就好。

实现

class Solution {
static constexpr int N = 26;
public:
    int longestPalindrome(vector<string>& words) {
        vector f(N, vector<int> (N));
        int ans = 0;
        for (const auto& s : words) {
            f[s.front() - 'a'][s.back() - 'a']++;
        }
        int t = 0;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (i == j) {
                    ans += (f[i][j] - (f[i][j] & 1)) << 1;
                    if (f[i][j] & 1) t = 2;
                } else {
                    ans += min(f[i][j], f[j][i]) << 1;
                }
            }
        }
        return ans + t;
    }
};

力扣每日一题1857-有向图中最大颜色值

日期：2025-05-26

题意

给定一个有向图，以及图上各节点的颜色colors，若图有环返回-1；

记路径颜色值为路径中出现次数最多的颜色的出现次数。

求各合法路径的最大颜色值。

思路

首先假定图无环，该怎么求路径最大颜色值呢；

若有一条路径可得最大颜色值，且存在一个不在该路径上的点可达该路径起点，显然将路径起点改为该点一定不劣。也就是说从各入度为0的点出发一定不劣，比较自然的可以想到使用拓扑排序。

拓扑排序同时也可以解决判断有无环问题，由此可解。

实现

class Solution {
static constexpr int N = 26;
public:
    int largestPathValue(string colors, vector<vector<int>>& edges) {
        const int n = colors.size();
        vector<int> d(n);
        vector<vector<int>> e(n);
        for (const auto& vec : edges) {
            e[vec.front()].push_back(vec.back());
            d[vec.back()]++;
        }

        vector<int> q; int cur = 0;
        for (int i = 0; i < n; i++) {
            if (d[i] == 0) q.push_back(i);
        }
        vector<array<int, N>> f(n);
        int ans = 0;
        for ( ; cur < q.size(); cur++) {
            int x = q[cur];
            f[x][colors[x] - 'a']++;
            ans = max(ans, f[x][colors[x] - 'a']);
            for (const auto& v : e[x]) {
                for (int i = 0; i < N; i++) {
                    f[v][i] = max(f[v][i], f[x][i]);
                }
                d[v]--;
                if (d[v] == 0) {
                    q.push_back(v);
                }
            }
        }

        if (count(d.begin(), d.end(), 0) != n) return -1;
        return ans;
    }
};

力扣每日一题2894-分类求和并作差

日期：2025-05-27

题意

给定整数n与m

记num1为[1, n]无法被m整除的数的和

记num2为[1, n]被m整除的数的和

求num1 - num2

思路

可以发现本题的数据范围很小可以直接继续暴力求解。

但同时也可以直接进行数学推导：

注意到[1, n]的数不是被m整除就是无法被m整除

也就是

同时,被m整除的数均形如

故而

不难得出结果

实现

class Solution {
public:
    int differenceOfSums(int n, int m) {
        int ans = (1 + n) * n >> 1;
        int t = n / m;
        ans -= (1 + t) * t * m;
        return ans;
    }
};

力扣每日一题3372-连接两棵树后最大目标节点数目 I

日期：2025-05-28

题意

给定两棵大小分别为n和m的树，以及正整数k

若两点间距离不超过k则称两点互为目标结点。

求数组answer，其中answer[i]表示将第一二棵树的任意结点相连，第一棵树的结点i的最大目标结点数。

思路

对于给定的某点应该如何连接两棵树使得其目标结点数最大呢

显然第一棵树应选择该点；而第二棵树所选择的点与第一棵树选取的点无关，应都选择含距离不超过k - 1点最多的点。

使用bfs求对应距离的点数即可。

实现

class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2, int k) {
        const int n = edges1.size() + 1, m = edges2.size() + 1;
        vector<vector<int>> adj1(n), adj2(m);
        for (const auto& vec : edges1) {
            adj1[vec.front()].push_back(vec.back());
            adj1[vec.back()].push_back(vec.front());
        }
        for (const auto& vec : edges2) {
            adj2[vec.front()].push_back(vec.back());
            adj2[vec.back()].push_back(vec.front());
        }

        if (k == 0) return vector<int> (n, 1);
        int mx = 0;
        for (int i = 0; i < m; i++) {
            int t = 0;
            vector<array<int, 3>> q {{i, -1, 0}}; int cur = 0;
            for ( ; cur < q.size(); cur++) {
                auto [u, fa, d] = q[cur];
                if (d >= k) break;
                t++;
                for (auto v : adj2[u]) {
                    if (v == fa) continue;
                    q.push_back({v, u, d + 1});
                }
            }
            mx = max(mx, t);
        }

        vector<int> ans(n, mx);
        for (int i = 0; i < n; i++) {
            int t = 0;
            vector<array<int, 3>> q {{i, -1, 0}}; int cur = 0;
            for ( ; cur < q.size(); cur++) {
                auto [u, fa, d] = q[cur];
                if (d > k) break;
                t++;
                for (auto v : adj1[u]) {
                    if (v == fa) continue;
                    q.push_back({v, u, d + 1});
                }
            }
            ans[i] += t;
        }
        return ans;
    }
};

力扣每日一题3373-连接两棵树后最大目标节点数目 II

日期：2025-05-29

题意

给定两棵大小分别为n和m的树

若两点间距离为偶数则称两点互为目标结点。

求数组answer，其中answer[i]表示将第一二棵树的任意结点相连，第一棵树的结点i的最大目标结点数。

思路

那好像，和昨天的也没什么太大区别啊，不知道为什么昨天给标中等今天标困难了。

同样的，对第一棵树的每个节点 第一棵树内的目标结点数是固定的，这个可以简单的用类似换根的思路求出来：若结点u目标结点即距离为偶数的点数目为x个，距u距离为奇数的点数应为n - x个，因所有点离它的距离非奇即偶；若v与u直接相邻，所有点离v的距离相对离u的距离一定是加减一的，故离v奇距离的点数为x个，偶距离的为n - x个。

再考虑连接第二棵树造成的影响，同理，以任意点为根求出距其奇偶距离的点数，显然与其直接相连目标结点可增加距其奇距离数，与其相邻结点相连可增加其偶距离数。

实现

class Solution {
public:
    vector<int> maxTargetNodes(vector<vector<int>>& edges1, vector<vector<int>>& edges2) {
        const int n = edges1.size() + 1, m = edges2.size() + 1;
        vector<vector<int>> adj1(n), adj2(m);
        for (const auto& e : edges1) {
            adj1[e.front()].push_back(e.back());
            adj1[e.back()].push_back(e.front());
        }
        for (const auto& e : edges2) {
            adj2[e.front()].push_back(e.back());
            adj2[e.back()].push_back(e.front());
        }

        int cnt = 0;
        auto dfs1 = [&](this auto&& self, int u, int fa, int tag) -> void {
            if (tag) cnt++;
            for (auto v : adj2[u]) {
                if (v == fa) continue;
                self(v, u, tag ^ 1);
            }
        };
        dfs1(0, -1, 1);
        cnt = max(cnt, m - cnt);

        vector<int> ans(n);
        auto dfs = [&](this auto&& self, int u, int fa, int tag) -> void {
            if (tag) ans[0]++;
            for (auto v : adj1[u]) {
                if (v == fa) continue;
                self(v, u, tag ^ 1);
            }
        };
        auto dfs2 = [&](this auto&& self, int u, int fa) -> void {
            for (auto v : adj1[u]) {
                if (v == fa) continue;
                ans[v] = n - ans[u];
                self(v, u);
            }
            ans[u] += cnt;
        };
        dfs(0, -1, 1);
        dfs2(0, -1);
        return ans;
    }
};

力扣每日一题2359-找到离给定两个节点最近的节点

日期：2025-05-30

题意

给定有向图，每个点至多含一条出边，对于给定两点node1与node2，求这两点均能到达且距两点距离较大值最小的点。

思路

求两点均可达且较大距离最小，可以考虑先求出两点到所有其他点所需距离，再遍历所有点判断即可；

求两点到其他点距离可以考虑bfs，但注意到该题每个点至多一条出边，那简单循环一下即可。

实现

class Solution {
public:
    int closestMeetingNode(vector<int>& edges, int node1, int node2) {
        const int n = edges.size();
        vector<int> dis1(n, n), dis2(n, n);
        for (int cur = 0; node1 != -1 && dis1[node1] == n; node1 = edges[node1]) {
            dis1[node1] = cur++;
        }
        for (int cur = 0; node2 != -1 && dis2[node2] == n; node2 = edges[node2]) {
            dis2[node2] = cur++;
        }

        int mn = n, ans = -1;
        for (int i = 0; i < n; i++) {
            if (max(dis1[i], dis2[i]) < mn) {
                mn = max(dis1[i], dis2[i]);
                ans = i;
            }
        }
        return ans;
    }
};

力扣每日一题909-蛇梯棋

日期：2025-05-31

题意

给定大小为n * n的矩阵board，初始位于1目标为n * n。每次可走[1, 6]格，若目的格点board值不为-1则传送至目标格点值处，反之若目标格点board值为-1则到达目标格点，不会连续传送即：若通过传送到达点x且x处board值不为-1不会继续进行传送而是停留在x点处。

求问到达终点最少走几次。

思路

可以考虑直接BFS求出到各点最少移动步数。

只需注意格点编号类似于’Z’字型，注意进行转换即可。

实现

class Solution {
public:
    int snakesAndLadders(vector<vector<int>>& board) {
        const int n = board.size();
        
        auto cal = [&](int a) -> int {
            int x = a / n, y = a % n;
            if (x & 1) return board[n - 1 - x][n - 1 - y];
            return board[n - 1 - x][y];
        };
        
        vector<int> q{0};
        vector<bool> vis(n * n);
        for (int cur = 0; !q.empty(); cur++) {
            vector<int> nq;
            for (auto x : q) {
                if (x == n * n - 1) return cur;
                for (int t = x + 1; t <= x + 6; t++) {
                    if (t >= n * n) break;
                    int y = cal(t);
                    if (y == -1) y = t;
                    else y--;
                    if (!vis[y]) {
                        vis[y] = true;
                        nq.push_back(y);
                    }
                }
            }
            swap(q, nq);
        }
        return -1;
    }
};