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

目录

力扣每日一题3330-找到初始输入字符串 I

日期：2025-07-01

题意

给出字符串word， Alice 在打这个字符串时可能在某个键停留过久使得该字符被输入多次，但 Alice 最多犯一次这样的错误，求 Alice 最初想输入的字符串的可能数量。

思路

若存在多个相邻相同的字符，则均可拆解为 Alice 失误，寻找所有相邻相同的子串长度即可。

实现

class Solution {
public:
    int possibleStringCount(string word) {
        int ans = 1;
        const int n = word.size();
        for (int i = 0; i < n; ) {
            int j;
            for (j = i + 1; j < n && word[j] == word[i]; j++);
            ans += j - i - 1;
            i = j;
        }
        return ans;
    }
};

力扣每日一题3333-找到初始输入字符串 II

日期：2025-07-02

题意

给出字符串word与整数k， Alice 在打这个字符串时可能在某个键停留过久使得该字符被输入多次，已知 Alice 最初所输入的字符串长度不小于k，求 Alice 最初想输入的字符串的可能数量。

思路

先不考虑长度问题，那么就和昨天的题非常类似，仅仅是 Alice 犯错次数变为无限多，那还是很好做的。也就是总的方案数是好求的。

最终字符串的长度大于某值的方案数似乎不太好做，但不大于某长度的就好做很多，进行一个分组dp即可。

实现

using ll = long long;
static constexpr int mod = 1e9 + 7;
class Solution {
public:
    int possibleStringCount(string word, int k) {
        const int n = word.size();
        if (n < k) return 0;
        ll ans = 1;
        vector<int> f;
        for (int i = 0; i < n; ) {
            int j;
            for (j = i + 1; j < n && word[i] == word[j]; j++);
            k--;
            if (j - i > 1) {
                ans = ans * (j - i) % mod;
                f.push_back(j - i - 1);
            }
            i = j;
        }

        if (k <= 0) return ans;
        const int m = f.size();
        vector<vector<int>> dp(m + 1, vector<int> (k));
        vector<int> pre(k + 1);
        ranges::fill(dp[0], 1);
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < k; j++) {
                pre[j + 1] = (pre[j] + dp[i][j]) % mod;
            }
            for (int j = 0; j < k; j++) {
                dp[i + 1][j] = (pre[j + 1] - pre[max(j - f[i], 0)]) % mod;
            }
        }

        return (ans - dp[m][k - 1] + mod) % mod;
    }
};

力扣每日一题3304-找出第 K 个字符 I

日期：2025-07-03

题意

给定字符串word = "a"以及整数k，对于每次操作，会将当前字符串复制一遍并将其内每个字符全部变为字母表顺序的下一个字符（其中'z'会变为'a'）后将其插入到当前字符串的末尾，求问第k个字符是什么。

思路

可以模拟一下这个过程有

初始[a]
第一次[a][a+1]
第二次[[a][a+1]][[a+1][a+2]]
第三次[[a][a+1][a+1][a+2]][[a+1][a+2][a+2][a+3]]
...

显然可以观察到字符串的长度是随操作次数成倍增长的，那就可以比较自然的想到对k进行一下二进制的回溯。

实现

class Solution {
public:
    char kthCharacter(int k) {
        int t = 0;
        while (k > 1) {
            t++;
            k -= (1 << __lg(k - 1));
        }
        return char(t % 26 + 'a');
    }
};

力扣每日一题3307-找出第 K 个字符 II

日期：2025-07-04

题意

给定字符串word = "a"以及整数k以及一个操作数组operations，对于每次操作，若operations[i] == 0表示该次操作将当前字符串直接复制加入到当前字符串末尾，若operations[i] == 1表示会将当前字符串复制一遍并将其内每个字符全部变为字母表顺序的下一个字符（其中'z'会变为'a'）后将其插入到当前字符串的末尾，求问第k个字符是什么。

思路

那很显然和昨天题意非常相似，只是多了个操作数组限制，当op[i] == 0时前后两截一致也就是不加，当op[i] == 1时与昨日一致，故不过多赘述。

实现

class Solution {
public:
    char kthCharacter(long long k, vector<int>& operations) {
        const int n = operations.size();
        k--;
        int t = 0;
        for (int i = min(50, n - 1); i >= 0; i--) {
            if (k >> i & 1) {
                t += operations[i];
            }
        }
        return char('a' + t % 26);
    }
};

力扣每日一题1394-找出数组中的幸运数

日期：2025-07-05

题意

给定数组arr，若某个数的出现频次与它的大小相等则称该数幸运。求arr中最大的幸运数。

思路

简单哈希记录下各个数出现的频率比较大小即可。

实现

class Solution {
public:
    int findLucky(vector<int>& arr) {
        unordered_map<int, int> cnt;
        int ans = -1;
        for (const auto& x : arr) cnt[x]++;
        for (auto [x, t] : cnt) {
            if (x == t) {
                ans = max(x, ans);
            }
        }
        return ans;
    }
};

力扣每日一题1865-找出和为指定值的下标对

日期：2025-07-06

题意

给定数组nums1与nums2，实现支持以下功能的数据结构：

  1. 将nums2下标为index的值增加val
  2. 求满足nums1[i] + nums2[j] == tot的下标对(i, j)的数量

注意：

  • 1 <= nums1.length <= 1000
  • 1 <= nums2.length <= 10^5

思路

显然该数据结构需要记录nums2以用于实现功能1。同时求和为某定值的下标对数，比较容易想到使用哈希记录某一数组各数值数量然后遍历另一数组实现，此处观察数据范围，不难想到应使用哈希记录nums2遍历nums1有着更好的效率。

实现

class FindSumPairs {
private:
    unordered_map<int, int> cnt;
    vector<int> a, b;
public:
    FindSumPairs(vector<int>& nums1, vector<int>& nums2) {
        a = nums1;
        b = nums2;
        for (const auto& x : nums2) cnt[x]++;
    }
    
    void add(int index, int val) {
        cnt[b[index]]--;
        b[index] += val;
        cnt[b[index]]++;
    }
    
    int count(int tot) {
        int res = 0;
        for (const auto& x : a) {
            if (cnt.count(tot - x)) res += cnt[tot - x];
        }
        return res;
    }
};

/**
 * Your FindSumPairs object will be instantiated and called as such:
 * FindSumPairs* obj = new FindSumPairs(nums1, nums2);
 * obj->add(index,val);
 * int param_2 = obj->count(tot);
 */

力扣每日一题1353-最多可以参加的会议数目

日期：2025-07-07

题意

给定数组events，其中event[i] = [startDat_i, endDay_i]表示第i个会议开始与结束的时间。每日最多可参加一个会议，求最多可以参加几个会议。（不必完整参加某个会议）

思路

显然是满足贪心性质的，对于每个当前未参加且可参加的会议，应当选择结束时间最早的会议，使用优先队列进行维护可参加的会议即可。

实现

class Solution {
public:
    int maxEvents(vector<vector<int>>& events) {
        int mx = 0;
        for (const auto& vec : events) {
            mx = max(mx, vec.back());
        }
        int ans = 0;
        const int n = events.size();
        vector<vector<int>> cnt(mx + 1);
        for (const auto& vec : events) {
            cnt[vec.front()].push_back(vec.back());
        }

        priority_queue<int, vector<int>, greater<>> pq;
        for (int i = 0; i <= mx; i++) {
            while (!pq.empty() && pq.top() < i) {
                pq.pop();
            }
            for (const auto& x : cnt[i]) {
                pq.push(x);
            }
            if (!pq.empty()) {
                ans++;
                pq.pop();
            }
        }

        return ans;
    }
};

力扣每日一题1751-最多可以参加的会议数目 II

日期：2025-07-08

题意

给定数组events与整数k，其中event[i] = [startDat_i, endDay_i, value_i]表示第i个会议开始与结束的时间以及其价值。若完整参加某一会议可得其价值，最多参加k个会议，求所能得到的最大总价值。

思路

首先考虑所有会议价值一致且无参加的会议数量限制，那么比较经典是将会议按结束时间排序进行贪心。

再考虑加入会议价值的影响，也不难想到使用dp，递推或递归地推出每一时刻结束前所能获得的最大价值。

最后是参加会议数量的限制，在前一思路的基础上加入已参与会议的数量维度即可。

实现

class Solution {
public:
    int maxValue(vector<vector<int>>& events, int k) {
        const int n = events.size();
        ranges::sort(events, [&](const auto& x, const auto& y) {
            return x[1] < y[1];
        });
        vector dp(n + 1, vector<int> (k + 1));
        for (int i = 0; i < n; i++) {
            int p = lower_bound(events.begin(), events.end(), events[i][0], [](const auto& x, int t) {
                return x[1] < t;
            }) - events.begin();
            for (int j = 1; j <= k; j++) {
                dp[i + 1][j] = max(dp[i][j], dp[p][j - 1] + events[i][2]);
            }
        }
        return dp[n][k];
    }
};

力扣每日一题3439-重新安排会议得到最多空余时间 I

日期：2025-07-09

题意

给定整数eventTime表示总时长，活动开始于t = 0结束于t = eventTime

同时给定两个数组startTime与endTime表示n个时间没有重叠的会议的开始与结束时间。

最多可以平移k个会议，使其保持原会议时长但改变其开始结束时间，同时保持所有会议相对顺序不变且无重叠。求可以得到的会议间最长连续空闲时间。

思路

发现这题之前赛时写过，但实在有点久远同时又是比赛过程，所以可能可能有些丑陋。但最近上班好累哦，实在懒得重写（

大概就是直接模拟将多个会议拼在一起往前平移或往后平移所能得到的最大空闲块即可。

实现

class Solution {
public:
    int maxFreeTime(int eventTime, int k, vector<int>& startTime, vector<int>& endTime) {
        vector<int> len(startTime.size());
        for (int i = 0; i < startTime.size(); i++) {
            len[i] = endTime[i] - startTime[i];
        }

        int start = 0, sum = 0, cnt = 0, lo = 0, l = 0;
        int ans = 0;
        for (int i = 0; i < startTime.size(); i++) {
            sum += len[i];
            cnt++;
            if (cnt < k) continue;
            if (cnt > k) {
                cnt--;
                sum -= len[lo];
                start = endTime[lo];
                l = endTime[lo];
                lo++;
            }
            ans = max({ans, (i < startTime.size() - 1 ? startTime[i + 1] - sum - l : eventTime - sum - l)});
        }
        return ans;
    }
};

力扣每日一题3440-重新安排会议得到最多空余时间 II

日期：2025-07-10

题意

给定整数eventTime表示总时长，活动开始于t = 0结束于t = eventTime

同时给定两个数组startTime与endTime表示n个时间没有重叠的会议的开始与结束时间。

最多可以平移1个会议，使其保持原会议时长但改变其开始结束时间，可以改变会议的相对顺序。求可以得到的会议间最长连续空闲时间。

思路

和昨天的题非常的像，只是条件变成了只能移动一个会议但可以改变会议的顺序。

可以想到，有两种方式可以得到最优，首先是不改变会议的相对顺序即按照昨天的做法不过k变为了1，另一种则是将每一个会议尝试放入其他会议之间，原位置前后的空闲时间。简单模拟两种操作取最优即可。

同样是好早之前写的（

实现

class Solution {
public:
    int maxFreeTime(int eventTime, vector<int>& startTime, vector<int>& endTime) {
        vector<array<int, 3>> len;
        const int n = startTime.size();
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                len.push_back({startTime[i], 0, 0});
            } else {
                len.push_back({startTime[i] - endTime[i - 1], i, i - 1});
            }
        }
        len.push_back({eventTime - endTime.back(), n - 1, n - 1});
        sort(len.begin(), len.end());
        int ans = len.back()[0];

        for (int i = 0; i < n; i++) {
            if (i == 0) {
                ans = max(ans, startTime[i + 1] - endTime[i] + startTime[i]);
            } else if (i == n - 1) {
                ans = max(ans, eventTime - endTime[i - 1] - endTime[i] + startTime[i]);
            } else {
                ans = max(ans, startTime[i] - endTime[i - 1] + startTime[i + 1] - endTime[i]);
            }
        }

        for (int i = 0; i < n; i++) {
            int l = endTime[i] - startTime[i];
            array<int, 3> tmp = {l, 0, 0};
            auto it = lower_bound(len.begin(), len.end(), tmp);
            while (it != len.end() && ((*it)[1] == i || (*it)[2] == i)) {
                it++;
            }
            if (it == len.end()) continue;
            if (i == 0) {
                ans = max(ans, startTime[i + 1]);
            } else if (i == n - 1) {
                ans = max(ans, eventTime - endTime[i - 1]);
            } else {
                ans = max(ans, startTime[i + 1] - endTime[i - 1]);
            }
        }
        return ans;
    }
};

力扣每日一题3169-无需开会的工作日

日期：2025-07-11

题意

给定整数days表示总天数，以及数组meetings其内记录每个会议的开始与结束时间（包含首尾）。

求没有会议的天数。

思路

比较自然可以想到使用差分，但发现数据范围有点太大并不好做。进一步观察可以想到将会议按开始时间排序，模拟合并求出有会议的天数，再反过来求无会议天数即可。

实现

class Solution {
public:
    int countDays(int days, vector<vector<int>>& meetings) {
        ranges::sort(meetings);
        int l = 1, r = 0;
        for (const auto& vec : meetings) {
            if (vec[0] > r) {
                days -= r - l + 1;
                l = vec[0];
            }
            r = max(r, vec[1]);
        }
        return days - (r - l + 1);
    }
};

力扣每日一题1900-最佳运动员的比拼回合

日期：2025-07-12

题意

给定整数n与firstPlayer与secondPlayer，表示n名运动员编号为1~n按升序排序。

每一回合令从前往后数的第i位选手与从后往前数的第i位选手对战，除firstPlayer与secondPlayer必胜外各位选手均可能胜或负。败者淘汰，胜者仍按升序进行排序。

求firstPlayer与secondPlayer最早与最晚的相遇回合数。

思路

可以进行一个推导发现规律。

实现

class Solution {
public:
    vector<int> earliestAndLatest(int n, int firstPlayer, int secondPlayer) {
        if (firstPlayer + secondPlayer == n + 1) return {1, 1};
        if (firstPlayer + secondPlayer > n + 1) {
            int t = firstPlayer;
            firstPlayer = n + 1 - secondPlayer;
            secondPlayer = n + 1 - t;
        }

        auto cal = [&](int n) -> int {
            int res = 1;
            if (firstPlayer + secondPlayer <= (n + 1) / 2) {
                while (firstPlayer + secondPlayer <= (n + 1) / 2) {
                    res++;
                    n = (n + 1) / 2;
                }

                if (secondPlayer - firstPlayer > 1) return res + 1;
            }
            if (secondPlayer - firstPlayer == 1) {
                res++;
                n = (n + 1) / 2;
                while (n & 1) {
                    res++;
                    n = (n + 1) / 2;
                }
                return res;
            }
            if (secondPlayer <= (n + 1) / 2) return res + 1;
            if (secondPlayer - firstPlayer == 2) {
                res++;
                n = (n + 1) / 2;
                while(n & 1) {
                    res++;
                    n = (n + 1) / 2;
                }
                return res;
            }
            if (firstPlayer % 2 == 0 && firstPlayer + secondPlayer == n) {
                res++;
            }
            return res + 1;
        };

        return {cal(n), min(bit_width(n - 1u), n + 1 -secondPlayer)};
    }
};

力扣每日一题2410-运动员和训练师的最大匹配数

日期：2025-07-13

题意

给定数组player与trainers表示运动员与训练员的能力。若运动员的能力小于等于训练员则可互相匹配。运动员与训练员均尽可匹配一个。求最大匹配数。

思路

排序后使用双指针即可。

实现

class Solution {
public:
    int matchPlayersAndTrainers(vector<int>& players, vector<int>& trainers) {
        ranges::sort(players);
        ranges::sort(trainers);
        int ans = 0;
        const int n = players.size(), m = trainers.size();
        for (int i = 0, j = 0; i < n && j < m; ) {
            if (players[i] <= trainers[j]) {
                ans++;
                i++; j++;
            } else {
                j++;
            }
        }
        return ans;
    }
};

力扣每日一题1290-二进制链表转整数

日期：2025-07-14

题意

给定结点值均为0/1的链表，求其表示的二进制数字的十进制值。

思路

进行一个遍历链表得到二进制数再将其转换即可。

实现

class Solution {
public:
    int getDecimalValue(ListNode* head) {
        string s;
        for ( ; head != nullptr; head = head->next) {
            s += char('0' + head->val);
        }
        int ans = 0;
        for (int i = int(s.size()) - 1, base = 0; i >= 0; i--, base++) {
            ans |= (s[i] == '1') << base;
        }
        return ans;
    }
};

力扣每日一题3136-有效单词

日期：2025-07-15

题意

给定字符串word判断其是否长度至少为3且仅由大小写字母与数字组成且至少含一个元音字母且至少含一个辅音字母。

思路

遍历判断条件即可。

实现

class Solution {
public:
    bool isValid(string word) {
        if (word.size() < 3) return false;
        bool ok1 = false, ok2 = false;
        for (auto& ch : word) {
            if (isalpha(ch)) {
                ch = tolower(ch);
                if (ch == 'a' || ch == 'e' || ch == 'i' || ch == 'o' || ch == 'u') ok1 = true;
                else ok2 = true;
            } else if (!isdigit(ch)) return false;
        }
        return ok1 && ok2;
    }
};

力扣每日一题3201-找出有效子序列的最大长度 I

日期：2025-07-16

题意

给定数组nums，求满足以下条件的最长子序列的长度：任意相邻两个元素的和的奇偶性均相等。

思路

观察可以发现答案子序列应该为 全为偶数 或 全为奇数 或 奇数偶数相间 的形式。那么开变量记录一下遍历一趟返回最大值即可。

实现

class Solution {
public:
    int maximumLength(vector<int>& nums) {
        int ao = 0, ae = 0, o = 0, e = 0;
        for (const auto& x : nums) {
            if (x & 1) {
                ao++;
                o = max(o, e + 1);
            } else {
                ae++;
                e = max(e, o + 1);
            }
        }
        return max({ao, ae, o, e});
    }
};

力扣每日一题3202-找出有效子序列的最大长度 II

日期：2025-07-17

题意

给定数组nums与整数k，求满足以下条件的最长子序列的长度：子序列任意两个相邻数的和模k均相等。

思路

题目中k的数据范围并不大，可以考虑直接枚举两数之和的模大小，由此递推最大答案即可。

实现

class Solution {
public:
    int maximumLength(vector<int>& nums, int k) {
        vector<int> cnt(k);
        int ans = 0;
        for (int i = 0; i < k; i++) {
            fill(cnt.begin(), cnt.end(), 0);
            for (auto x : nums) {
                x %= k;
                cnt[x] = cnt[(i - x + k) % k] + 1;
                ans = max(ans, cnt[x]);
            }
        }
        return ans;
    }
};

力扣每日一题2163-删除元素后和的最小差值

日期：2025-07-18

题意

给定长度为3 * n的数组nums，将其中任意n个元素删除，记此时前n个数的和为sum_first后n个数的和为sum_second，求sum_first - sum_second的最小值

思路

转换一下思路，题目的意思可以转变为：选出前n个最小数，再取出这之后的n个最大数，将两部分做差求最值。注意前后必须有且仅有n个数即可，使用优先队列计算一下就好。

实现

class Solution {
using ll = long long;
static constexpr ll inf = 1ll << 52;
public:
    long long minimumDifference(vector<int>& nums) {
        ll ans = inf;
        const int n = nums.size() / 3, m = nums.size();
        priority_queue<int> pq;
        ll sum = 0;
        vector<ll> pre(m);
        for (int i = 0; i < m; i++) {
            sum += nums[i];
            pq.push(nums[i]);
            if (pq.size() > n) {
                sum -= pq.top();
                pq.pop();
            }
            pre[i] = sum;
        }
        priority_queue<int, vector<int>, greater<>> pqt;
        sum = 0;
        for (int i = m - 1; i >= n - 1; i--) {
            if (i < m - n) ans = min(ans, pre[i] - sum);
            sum += nums[i];
            pqt.push(nums[i]);
            if (pqt.size() > n) {
                sum -= pqt.top();
                pqt.pop();
            }
        }
        return ans;
    }
};

力扣每日一题1233-删除子文件夹

日期：2025-07-19

题意

给定一份文件列表folder，若某一文件为另一文件的子目录则将其删除。

思路

进行简单模拟即可，为了提高效率可以考虑将其排序，显然子目录的字典序一定比父目录小。

实现

class Solution:
    def removeSubfolders(self, folder: List[str]) -> List[str]:
        folder.sort()
        ans = [folder[0]]
        for s in folder[1:]:
            if not (len(s) > len(ans[-1]) and ans[-1] == s[:len(ans[-1])] and s[len(ans[-1])] == '/'):
                ans.append(s);
        return ans;
class Solution {
public:
    vector<string> removeSubfolders(vector<string>& folder) {
        ranges::sort(folder);
        const int n = folder.size();
        vector<string> ans{folder.front()};
        for (int i = 1; i < n; i++) {
            if (ans.back().size() < folder[i].size() && ans.back() == folder[i].substr(0, ans.back().size()) && folder[i][ans.back().size()] == '/') {

            } else {
                ans.push_back(folder[i]);
            }
        }
        return ans;
    }
};

其他

决心成为传说中的 屁眼通红 高手，所以之后会仅可能地用 python 来写题

力扣每日一题1948-删除系统中的重复文件夹

日期：2025-07-20

题意

给定二维字符串数组paths其中paths[i]表示第i个文件的绝对路径目录。若两个文件夹非空且其子文件完全相同且子文件结构完全相同，则将两文件夹删除。返回不需删除的剩余文件目录。

思路

怎么快速地判断两个文件夹及其子结构是否相同，可以相等哈希是最快的比较方式，但是这个哈希值怎么计算呢。可以想到将其子目录结构转换为字符串，将所有子串排序以保证子树结构遍历顺序相同，再用()表示目录之间父子的关系。

力扣每日一题1957-删除字符使字符串变好

日期：2025-07-21

题意

给定字符串s，删除其中最少字符使得其内无连续三个及以上的相同字符。

思路

简单扫一遍删除多余符号即可。

实现

class Solution {
public:
    string makeFancyString(string s) {
        const int n = s.size();
        string ans;
        for (int i = 0, cnt = 0; i < n; i++) {
            if (++cnt < 3) ans += s[i];
            if (i < n - 1 && s[i] != s[i + 1]) cnt = 0;
        }
        return ans;
    }
};
class Solution:
    def makeFancyString(self, s: str) -> str:
        ans = []
        cnt = 0
        for i, ch in enumerate(s):
            cnt += 1
            if cnt < 3:
                ans.append(ch)
            if i < len(s) - 1 and s[i] != s[i + 1]:
                cnt = 0;
        return ''.join(ans)

力扣每日一题1695-删除子数组的最大得分

日期：2025-07-22

题意

给定正整数数组nums，从中删除一个不含相同元素的子数组，求所删子数组的最大和。

思路

应该是比较经典的题目了，印象中只是在面试里我就被问过两次类似的题目。

给定的数组均为整数，那么子数组显然是越长越可能出答案，那么怎么获得最长的不含重复元素的子数组呢。可以想到使用哈希记录该元素是否出现过以及最后出现的位置，求这段的和就可以考虑使用滑动窗口或前缀和求解。

实现

class Solution {
public:
    int maximumUniqueSubarray(vector<int>& nums) {
        const int n = nums.size();
        unordered_map<int, int> last;
        vector<int> pre(n + 1);
        int ans = 0;
        for (int i = 0, l = 0; i < n; i++) {
            pre[i + 1] = pre[i] + nums[i];
            if (last.count(nums[i]) && last[nums[i]] >= l) {
                l = last[nums[i]] + 1;
            }
            last[nums[i]] = i;
            ans = max(ans, pre[i + 1] - pre[l]);
        }
        return ans;
    }
};
class Solution:
    def maximumUniqueSubarray(self, nums: List[int]) -> int:
        n = len(nums)
        pre = [0] * (n + 1)
        last = defaultdict(int)
        l = 0
        ans = 0
        for i, num in enumerate(nums):
            pre[i + 1] = pre[i] + num
            if num in last and last[num] >= l:
                l = last[num] + 1
            last[num] = i
            ans = max(ans, pre[i + 1] - pre[l])
        return ans

力扣每日一题1717-删除子字符串的最大得分

日期：2025-07-23

题意

给定字符串s，可以进行任意次以下两种操作：

  • 删除s中的子串ab，得到分数x
  • 删除s中的子串ba，得到分数y

求可以得到的最大分数

思路

手玩一下可以发现，仅需要关注s中仅含ab的子串即可，其他字符可以视作分隔符将问题分割为多个小问题。

每个仅含ab的子串显然删除次数其实与删除方式是无关的，显然应该进行贪心首先尽可能多地用得分高的方式，再用得分较低的方式删除。

实现

class Solution {
public:
    int maximumGain(string s, int x, int y) {
        const int n = s.size();
        char a = 'a', b = 'b';
        if (x < y) {
            swap(x, y);
            swap(a, b);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] != a && s[i] != b) continue;
            int ca = 0, cb = 0;
            for ( ; i < n && (s[i] == a || s[i] == b); i++) {
                if (s[i] == a) {
                    ca++;
                } else {
                    if (ca) {
                        ca--;
                        ans += x;
                    } else {
                        cb++;
                    }
                }
            }
            ans += min(ca, cb) * y;
        }
        return ans;
    }
};
class Solution:
    def maximumGain(self, s: str, x: int, y: int) -> int:
        n = len(s)
        a, b = 'a', 'b'
        if x < y:
            x, y = y, x
            a, b = b, a
        ans = i = 0
        while i < n:
            if s[i] != a and s[i] != b:
                i += 1
                continue
            ca = cb = 0
            while i < n and (s[i] == a or s[i] == b):
                if s[i] == a:
                    ca += 1
                else:
                    if ca > 0:
                        ans += x
                        ca -= 1
                    else:
                        cb += 1
                i += 1
            ans += min(ca, cb) * y
        return ans

力扣每日一题2322-从树中删除边的最小分数

日期：2025-07-24

题意

给定一棵树以及树上各点权值nums。任意删除树的两条边，获取所得三个连通块中的所有节点异或值，求这三异或值最大值与最小值的最小差值

思路

注意到点数的数据范围其实是不大的 3 <= n <= 1e3

那直接枚举所删除的两条边即可。快速求删边所得的连通块异或和可以使用dfs求得各点的子树异或和。各点的父子关系可以dfs时顺带处理深度以及dfs序即可判断。

实现

class Solution:
    def minimumScore(self, nums: List[int], edges: List[List[int]]) -> int:
        n = len(nums)
        adj = [[] for _ in range(n)]
        for u, v in edges:
            adj[u].append(v)
            adj[v].append(u)

        f = [0] * n
        d = [0] * n
        sz = [1] * n
        p = [0] * n
        tot = 0
        def dfs(u: int, fa: int):
            nonlocal tot
            f[u] = nums[u]
            p[u] = tot
            tot += 1
            for v in adj[u]:
                if v == fa:
                    continue
                d[v] = d[u] + 1
                dfs(v, u)
                f[u] ^= f[v]
                sz[u] += sz[v]
        
        dfs(0, -1)
        ans = 1e9
        for i in range(n - 1):
            for j in range(i + 1, n - 1):
                u, v = edges[i]
                x, y = edges[j]
                if d[u] > d[v]:
                    u, v = v, u
                if d[x] > d[y]:
                    x, y = y, x
                if p[v] <= p[y] <= p[v] + sz[v] - 1:
                    p0 = f[0] ^ f[v]
                    p1 = f[v] ^ f[y]
                    p2 = f[y]
                elif p[y] <= p[v] <= p[y] + sz[y] - 1:
                    p0 = f[0] ^ f[y]
                    p1 = f[y] ^ f[v]
                    p2 = f[v]
                else:
                    p0 = f[0] ^ f[v] ^ f[y]
                    p1 = f[v]
                    p2 = f[y]
                ans = min(ans, max(p0, p1, p2) - min(p0, p1, p2))
        return ans
class Solution {
public:
    int minimumScore(vector<int>& nums, vector<vector<int>>& edges) {
        const int n = nums.size();
        vector<vector<int>> adj(n);
        for (const auto& e : edges) {
            int u = e[0], v = e[1];
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        
        vector<int> f(n), d(n), sz(n, 1), p(n);
        int tot = 0;
        auto dfs = [&](this auto&& self, int u, int fa) -> void {
            f[u] = nums[u];
            p[u] = tot++;
            for (const auto& v : adj[u]) {
                if (v == fa) continue;
                d[v] = d[u] + 1;
                self(v, u);
                f[u] ^= f[v];
                sz[u] += sz[v];
            }
        };
        dfs(0, -1);

        int ans = 1e9;
        for (int i = 0; i < n - 1; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                int u = edges[i][0], v = edges[i][1];
                int x = edges[j][0], y = edges[j][1];
                if (d[u] > d[v]) swap(u, v);
                if (d[x] > d[y]) swap(x, y);
                int p0, p1, p2;
                if (p[v] <= p[y] && p[v] + sz[v] - 1 >= p[y]) {
                    p0 = f[0] ^ f[v];
                    p1 = f[v] ^ f[y];
                    p2 = f[y];
                } else if (p[y] <= p[u] && p[y] + sz[y] - 1 >= p[v]) {
                    p0 = f[0] ^ f[y];
                    p1 = f[y] ^ f[v];
                    p2 = f[v];
                } else {
                    p0 = f[0] ^ f[v] ^ f[y];
                    p1 = f[v];
                    p2 = f[y];
                }
                ans = min(ans, max({p0, p1, p2}) - min({p0, p1, p2}));
            }
        }
        return ans;
    }
};

力扣每日一题3487-删除后的最大子数组元素和

日期：2025-07-25

题意

给定数组nums，可以删除其中任意元素但不能使其为空。求删除后可以得到的数组内元素各不相同且和最大的子数组和。

思路

相当于将所有负数删除并去重后得到的数组和，但需要注意若数组所有元素均为负数答案为最大的负数。

实现

class Solution:
    def maxSum(self, nums: List[int]) -> int:
        ans = 0
        cnt = 0
        vis = [0] * 101
        for i in nums:
            if i >= 0 and vis[i] == 0:
                vis[i] = 1
                ans += i
                cnt += 1
        if cnt == 0:
            return max(nums)
        return ans
class Solution {
public:
    int maxSum(vector<int>& nums) {
        array<int, 101> vis;
        int ans = 0, cnt = 0, mx = -100;
        for (const auto& x : nums) {
            if (x >= 0 && vis[x] == 0) {
                vis[x]++;
                cnt++;
                ans += x;
            } else mx = max(mx, x);
        }
        if (cnt == 0) return mx;
        return ans;
    }
};

力扣每日一题3480-删除一个冲突对后最大子数组数目

日期：2025-07-26

题意

给定整数n 表示有 [1, n] 的顺序排列 nums。同时给定数组 conflictingPairs 表示一些冲突对 conflictingPairs[i] = [a, b] 表示 a 与 b 不能出现同一子数组中。

现在可以任意删除一对冲突对，求删除后不冲突的 nums 子数组最大个数。

思路

枚举左端点，手玩一下可以发现性质。

实现

class Solution:
    def maxSubarrays(self, n: int, conflictingPairs: List[List[int]]) -> int:
        f = [n + 1] * (n + 1)
        g = [n + 1] * (n + 1)
        for l, r in conflictingPairs:
            if l > r:
                l, r = r, l
            if r < f[l]:
                g[l] = f[l]
                f[l] = r
            elif r < g[l]:
                g[l] = r
        
        ans = e = mx = 0
        b0 = b1 = n + 1
        for i in range(n, 0, -1):
            pre = b0
            if f[i] < b0:
                b1 = b0
                b0 = f[i]
            elif f[i] < b1:
                b1 = f[i]
            if g[i] < b0:
                b1 = b0
                b0 = g[i]
            elif g[i] < b1:
                b1 = g[i]
            ans += b0 - i
            if b0 != pre:
                e = 0
            e += b1 - b0
            mx = max(mx, e)
        return ans + mx

---

## 力扣每日一题2210-统计数组中峰和谷的数量

> 日期：2025-07-27

### 题意

给定数组`nums`。如果某数两侧第一个与其不等的数均大于或小于该数，则称其为峰或谷。求`nums`内峰和谷的数量。

### 思路

遍历一趟模拟着求就好，两侧均大于或小于等价于两侧与该数的差值同号。

### 实现

```cpp
class Solution {
public:
    int countHillValley(vector<int>& nums) {
        int ans = 0;
        int pre = nums[0];
        const int n = nums.size();
        for (int i = 1; i < n - 1; i++) {
            int cur = nums[i];
            int nxt = nums[i + 1];
            if (cur == nxt) continue;
            if ((pre - cur) * (nxt - cur) > 0) ans++;
            pre = cur;
        }
        return ans;
    }
};
class Solution:
    def countHillValley(self, nums: List[int]) -> int:
        ans = 0
        pre = nums[0]
        n = len(nums)
        for i in range(1, n - 1):
            cur = nums[i]
            nxt = nums[i + 1]
            if cur == nxt:
                continue
            if (pre - cur) * (nxt - cur) > 0:
                ans += 1
            pre = cur
        return ans

力扣每日一题2044-统计按位或能得到最大值的子集数目

日期：2025-07-28

题意

给定数组nums，找出nums中子集按位或的最大值，并返回能得出最大值的不同非空子集数量。

len(nums) <= 16

思路

数据范围并不大，直接dfs枚举子集即可。

实现

class Solution {
public:
    int countMaxOrSubsets(vector<int>& nums) {
        const int n = nums.size();
        int mx = 0;
        int cnt = 0;
        auto dfs = [&](this auto&& self, int cur, int loc) -> void {
            if (loc == n) {
                if (cur > mx) {
                    mx = cur;
                    cnt = 1;
                } else if (cur == mx) cnt++;
                return;
            }
            self(cur | nums[loc], loc + 1);
            self(cur, loc + 1);
        };
        dfs(0, 0);
        return cnt;
    }
};
class Solution:
    def countMaxOrSubsets(self, nums: List[int]) -> int:
        n = len(nums)
        cnt = mx = 0
        def dfs(cur: int, loc: int) -> None:
            nonlocal cnt, mx
            if loc == n:
                if cur > mx:
                    mx = cur
                    cnt = 1
                elif cur == mx:
                    cnt += 1
                return
            dfs(cur | nums[loc], loc + 1)
            dfs(cur, loc + 1)
        dfs(0, 0)
        return cnt

力扣每日一题2411-按位或最大的最小子数组长度

日期：2025-07-29

题意

给定非负整数数组nums。对于nums中的每一个数，求出以其为起点可以得到按位或最大值的最小非空子数组的长度。

思路

首先考虑按位或可以得到的最大值怎么求，显然是子数组越长越可能得到最大值，那么一路或到尾显然是可以得到最大值的。那么怎么求最早出现也就是最短的呢。显然一个数与另一个数无论或几次结果都是不变的，那很自然可以想到ST表上二分。

但这有点火箭毛毛虫了，因为或运算有个很好的性质，在正int的范围内，最多是可以变换31次的，那直接从前往后遍历，从后往前更新即可。

实现

st表加二分实现

template<class T> 
struct ST {
	int n, logn;
	vector<int> LOG;
	vector<vector<T>>st;
	ST (int x) {
		n = x;
		logn = __lg(n);
		LOG.resize(n + 1);
		st.resize(n, vector<T> (logn + 1));
		for (int i = 2; i <= n; i++) {
			LOG[i] = LOG[i / 2] + 1;
		}
	}
	void set(int i, T x) {
		st[i][0] = x;
	}
	void build() {
		for (int i = 1; i <= logn; i++) {
			for (int j = 0; j + (1 << i) - 1 < n; j++) {
				st[j][i] = st[j][i - 1] | st[j + (1 << (i - 1))][i - 1];
			}
		}
	}
	T query(int l, int r) {
		int len = LOG[r - l + 1];
		return st[l][len] | st[r - (1 << len) + 1][len];
	}
};

class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        const int n = nums.size();
        ST<int> st(n);
        for (int i = 0; i < n; i++) {
            st.set(i, nums[i]);
        }
        st.build();

        vector<int> ans(n);
        for (int i = 0; i < n; i++) {
            int x = st.query(i, n - 1);
            int lo = i, hi = n - 1;
            while (lo < hi) {
                int mid = lo + hi >> 1;
                if (st.query(i, mid) == x) hi = mid;
                else lo = mid + 1;
            }
            ans[i] = lo - i + 1;
        }
        return ans;
    }
};
class Solution {
public:
    vector<int> smallestSubarrays(vector<int>& nums) {
        const int n = nums.size();
        vector<int> ans(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = i - 1; j >= 0 && (nums[j] | nums[i]) != nums[j]; j--) {
                nums[j] |= nums[i];
                ans[j] = i - j + 1;
            }
        }
        return ans;
    }
};
class Solution:
    def smallestSubarrays(self, nums: List[int]) -> List[int]:
        n = len(nums)
        ans = [1] * n
        for i in range(0, n):
            for j in range(i - 1, -1, -1):
                if (nums[j] | nums[i]) == nums[j]:
                    break
                nums[j] |= nums[i]
                ans[j] = i - j + 1
        return ans

力扣每日一题2419-按位与最大的最长子数组

日期：2025-07-30

题意

给定正整数数组nums。求nums中按位与可以得到最大值的最长非空子数组的长度。

思路

与前几天的按位或略有不同，或是子数组越长越有可能出最大值，而与则是越长值越小，即 Misplaced &x & y \leq x

所以不难想到按位与可以得到的最大值为nums中的最大值，而答案就是连续出现的最大值个数。

实现

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        i = ans = mx = 0
        n = len(nums)
        while i < n:
            j = i + 1
            while j < n and nums[i] == nums[j]:
                j += 1
            if nums[i] > mx:
                mx = nums[i]
                ans = j - i
            elif nums[i] == mx:
                ans = max(ans, j - i)
            i = j
        return ans
class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        i = ans = mx = 0
        n = len(nums)
        while i < n:
            j = i + 1
            while j < n and nums[i] == nums[j]:
                j += 1
            if nums[i] > mx:
                mx = nums[i]
                ans = j - i
            elif nums[i] == mx:
                ans = max(ans, j - i)
            i = j
        return ans

力扣每日一题2683-相邻值的按位异或

日期：2025-07-31

题意

数组derived是由同样长度的数组original相邻值异或得到的，即derived[i] = original[i] ^ original[i + 1]。对于给定的0/1数组derived，判断其是否存在有效的original数组。

思路

什么情况下derived[i] == 1呢，显然是derived[i] != derived[i + 1]时；而当derived[i] == derived[i + 1]时，derived[i] == 0。由此可以推出每一个数与其他数是否相等。

那么什么时候不存在对应的original数组呢，显然是当出现矛盾时。不难想到遍历数组得到异或和，即可判断是否存在矛盾，是否存在对应数组。

实现

class Solution:
    def doesValidArrayExist(self, derived: List[int]) -> bool:
        same = True
        for i in derived:
            if i == 1:
                same = not same
        return same
                
class Solution {
public:
    bool doesValidArrayExist(vector<int>& derived) {
        bool same = true;
        for (const auto& x : derived) {
            same ^= x;
        }
        return same;
    }
};