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

目录

力扣每日一题3010-将数组分成最小总代价的子数组I

日期：2026-02-01

题意

定义一个数组的代价为该数组的首元素。给定整数数组 nums ，将其完整划分为三个连续且无交集的子数组，使得这三个子数组总代价最小。

思路

第一个子数组的代价是无法改变的，是首个元素大小。那么问题就变成了求除首元素外 最小元素 与 次小元素 的和加上首元素。那么有许多方法，直接排序或维护两个数遍历都是可以的，这里我是直接调库了。

实现

class Solution {
public:
    int minimumCost(vector<int>& nums) {
        nth_element(nums.begin() + 1, nums.begin() + 2, nums.end());
        return accumulate(nums.begin(),nums.begin() + 3, 0);
    }
};

力扣每日一题3013-将数组分成最小总代价的子数组II

日期：2026-02-02

题意

定义数组的代价为数组的首元素大小。给定正整数数组 nums，要将其分割为 k 个连续且互不相交的子数组，同时第二个子数组的首元素与最后一个子数组的首元素距离不超过 dist。求这些子数组的总最小代价。

思路

和昨天的题目还是非常类似的，只是分割为 3 个改为了 k 个，同时限制了第二个与最后一个的距离。但思想还是非常类似的，首先第一个子数组的代价是固定的，同时第二个子数组与最后一个子数组的距离有限制，那么问题就转换为了除第一个数之外，所有的长度为 dist 的子数组中前 k - 1 小的数的和的最小值。

求各个子段的前 k - 1 小的数，可以想到使用对顶堆进行滑动窗口，在维护一下大顶堆中的和即可。

实现

class Solution {
using ll = long long;
static constexpr ll inf = 1e18;
public:
    ll minimumCost(vector<int>& nums, int k, int dist) {
        ll ans = inf;
        ll cur = 0;
        int sz = 0;
        priority_queue<int> big;
        priority_queue<int, vector<int>, greater<>> small;
        unordered_map<int, int> del;
        auto _deal = [&]() -> void {
            while (!big.empty() && del.count(big.top()) && del[big.top()]) {
                del[big.top()]--;
                big.pop();
            }
            while (!small.empty() && del.count(small.top()) && del[small.top()]) {
                del[small.top()]--;
                small.pop();
            }
        };
        auto _add = [&](int x) -> void {
            _deal();
            if (sz == k - 1) {
                if (big.top() <= x) {
                    small.push(x);
                } else {
                    cur += x - big.top();
                    small.push(big.top());
                    big.pop();
                    _deal();
                    big.push(x);
                }
            } else {
                big.push(x);
                cur += x;
                sz++;
            }
        };
        auto _del = [&](int x) -> void {
            _deal();
            if (big.top() < x) {
                del[x]++;
            } else {
                del[x]++;
                cur -= x - small.top();
                big.push(small.top());
                small.pop();
            }
            _deal();
        };

        int n = nums.size();
        for (int l = 1, r = 1; r < n; r++) {
            _add(nums[r]);
            if (r - l > dist) _del(nums[l++]);
            if (r - l == dist) ans = min(ans, cur);
        }

        return ans + nums.front();
    }
};

力扣每日一题3637-三段式数组I

日期：2026-02-03

题意

若一个数组先严格递增再严格递减最后再严格递增，则称其为 三段式数组。给定整数数组 nums ，判断其是否为三段式数组。

思路

数据范围不大，题也不难，应该是有很多写法的，这里我是写了一个状态机。

实现

class Solution {
public:
    bool isTrionic(vector<int>& nums) {
        const int n = nums.size();
        int cur = 0;
        for (int i = 1; i < n; i++) {
            if (nums[i] > nums[i - 1] && cur == 0) cur = 1;
            else if (nums[i] > nums[i - 1] && cur == 1) continue;
            else if (nums[i] < nums[i - 1] && cur == 1) cur = 2;
            else if (nums[i] < nums[i - 1] && cur == 2) continue;
            else if (nums[i] > nums[i - 1] && cur == 2) cur = 3;
            else if (nums[i] > nums[i - 1] && cur == 3) continue;
            else cur = 4;
        }
        return cur == 3;
    }
};

力扣每日一题3640-三段式数组II

日期：2026-02-04

题意

若一个数组先严格递增再严格递减最后再严格递增，则称其为三段式数组。给定整数数组 nums ，求其内和最大的三段式子数组。

思路

一个三段式数组需要维护四个点：首 尾 两个递增递减的转折点。我们可以维护这四个点进行一个滑动窗口，需注意到当前子段结束后当前最后一段可以作为下一个窗口的最后一段。那么求子段和就可以进行一个前缀和优化。

同时因为数组内可能为负，因此需要额外注意处理首尾递增段的长度。

实现

class Solution {
using ll = long long;
static constexpr ll inf = 1ll << 52;
public:
    long long maxSumTrionic(vector<int>& nums) {
        const int n = nums.size();
        vector<ll> pre(n + 1);
        for (int i = 0; i < n; i++) {
            pre[i + 1] = pre[i] + nums[i];
        }

        ll ans = -inf;
        int l = 0, r = 0, p = 0, q = 0;
        for ( ; r < n; ) {
            for ( ; p + 1 < n && nums[p + 1] > nums[p]; ) {
                p++;
                r = max(r, p);
                q = max(q, p);
            }
            if (l == p) {
                l = p = q = r = l + 1;
                continue;
            }
            for ( ; l + 1 < p && nums[l] < 0; l++);
            for ( ; q + 1 < n && nums[q + 1] < nums[q]; ) {
                q++;
                r = max(r, q);
            }
            if (p == q) {
                l = p = q = r = p + 1;
                continue;
            }
            for ( ; r + 1 < n && nums[r + 1] > nums[r]; ) {
                if (l < p && p < q && q < r) {
                    ans = max(ans, pre[r + 1] - pre[l]);
                }
                r++;
                if (l < p && p < q && q < r) {
                    ans = max(ans, pre[r + 1] - pre[l]);
                }
            }
            if (r == q) {
                l = p = q = r = q + 1;
                continue;
            }
            l = q;
            p = r;
            q = r;
            r = r + 1;
        }
        return ans;
    }
};

力扣每日一题3379-转换数组

日期：2026-02-05

题意

给定循环整数数组 nums ，返回答案数组 result 满足以下条件

  • 若 nums[i] > 0 则 result[i] = nums[i + nums[i]]
  • 若 nums[i] < 0 则 result[i] = nums[i - abs(nums[i])]
  • 若 nums[i] == 0 则 result[i] = nums[i]

思路

按题意模拟即可，注意各种取模操作不要越界就好。

实现

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

力扣每日一题3634-使数组平衡的最少移除数目

日期：2026-02-06

题意

给定整数数组 nums 和一个整数 k ，若一个数组最大元素的值不超过最小元素的 k 倍，则称其平衡。你可任意删除 nums 中元素，求使 nums 平衡需要删的最少元素个数。

思路

显然应该对数组进行排序后做一个滑动窗口，枚举最小找最大或反过来都是可以的。这里我是看数据范围不大在赛时写偷懒，就直接进行了多次二分。

实现

class Solution {
public:
    int minRemoval(vector<int>& nums, int k) {
        ranges::sort(nums);
        const int n = nums.size();
        int ans = n - 1;
        for (int i = 0; i < n; i++) {
            int suf = n - (ranges::upper_bound(nums, 1ll * nums[i] * k) - nums.begin());
            ans = min(ans, suf + i);
        }
        return ans;
    }
};

力扣每日一题1653-使字符串平衡的最少删除次数

日期：2026-02-07

题意

给定仅由字符 a 与 b 组成的字符串 s ，每次操作可删除其内任意字符。求使得 s 满足不存在任意 i < j && s[i] == 'b' && s[j] == 'a' 的最小操作次数。

思路

显然是要让 s 变为前半段全 a 后半段全 b 的形态。那么我们可以枚举这个分界点，删除该分界点之前的所有 b 与分界点之后的所有 a ，那也就是做一个前后缀和。

实现

class Solution {
public:
    int minimumDeletions(string s) {
        int n = s.size();
        vector<int> suf(n + 1);
        for (int i = n - 1; i >= 0; i--) {
            suf[i] = suf[i + 1] + (s[i] == 'a');
        }
        int pre = 0;
        int ans = n;
        for (int i = 0; i <= n; i++) {
            ans = min(ans, pre + suf[i]);
            if (i < n) pre += s[i] == 'b';
        }
        return ans;
    }
};

力扣每日一题110-平衡二叉树

日期：2026-02-08

题意

给定一棵二叉树，判断它是否为平衡二叉树。

思路

进行一个 dfs，判断求出每个结点左右子树深度然后比较差值即可。

实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    bool isBalanced(TreeNode* root) {
        auto dfs = [](this auto&& self, TreeNode* u) -> int {
            if (u == nullptr) return 0;
            int l = self(u->left);
            int r = self(u->right);
            if (l == -1 || r == -1 || abs(l - r) > 1) return -1;
            return max(l, r) + 1;
        };
        return dfs(root) != -1;
    }
};

力扣每日一题1382-将二叉搜索树变平衡

日期：2026-02-09

题意

给定一棵二叉搜索树，返回与其结点值相同的二叉搜索平衡树。

思路

搜索树是对于每个结点其左子树的结点值均小于该点值且右子树的结点值均大于该结点值。可以想到用中序遍历得到该树所有结点值升序排序结果，每次取中点做根，左边部分做左子树右边部分做右子树，递归构造即可。

实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    TreeNode* balanceBST(TreeNode* root) {
        vector<int> node;
        auto dfs1 = [&](this auto&& self, TreeNode* u) -> void {
            if (u == nullptr) return;
            self(u->left);
            node.push_back(u->val);
            self(u->right);
        };
        dfs1(root);
        auto dfs2 = [&](this auto&& self, int l, int r) -> TreeNode* {
            if (l > r) return nullptr;
            int mid = (l + r) / 2;
            return new TreeNode(node[mid], self(l, mid - 1), self(mid + 1, r));
        };
        return dfs2(0, node.size() - 1);
    }
};

力扣每日一题3719-最长平衡子数组I

日期：2026-02-10

题意

给定整数数组 nums ，求不同偶数数量等于不同奇数数量的最长子数组长度。

思路

首先应该可以联想到与二进制字符串中01数相同的最大子段，我们是令 1 表示加一，0 表示减一，做了一个前缀和。

这里进行了升级，同一个数对某个区间的贡献仅有一次。可以想到固定右端点枚举左端点，若某个数首次出现，其右所有点都应加上该数贡献；若非首次出现则抵消先前贡献即可。

实现

static constexpr int inf = 1e9;

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void 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 modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(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);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    void half(int p, int l, int r) {
        if (info[p].act == 0) {
            return;
        }
        if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
            apply(p, {-(info[p].min + 1) / 2});
            return;
        }
        int m = (l + r) / 2;
        push(p);
        half(2 * p, l, m);
        half(2 * p + 1, m, r);
        pull(p);
    }
    void half() {
        half(1, 0, n);
    }
    
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
    
    void maintainL(int p, int l, int r, int pre) {
        if (info[p].difl > 0 && info[p].maxlowl < pre) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainL(2 * p, l, m, pre);
        pre = std::max(pre, info[2 * p].max);
        maintainL(2 * p + 1, m, r, pre);
        pull(p);
    }
    void maintainL() {
        maintainL(1, 0, n, -1);
    }
    void maintainR(int p, int l, int r, int suf) {
        if (info[p].difr > 0 && info[p].maxlowr < suf) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainR(2 * p + 1, m, r, suf);
        suf = std::max(suf, info[2 * p + 1].max);
        maintainR(2 * p, l, m, suf);
        pull(p);
    }
    void maintainR() {
        maintainR(1, 0, n, -1);
    }
};

struct Tag {
    int x = 0;
    void apply(const Tag &t) & {
        x += t.x;
    }
};

struct Info {
    int x = 0;
    int mn = 0;
    int mx = 0;
    void apply(const Tag &t) & {
        x += t.x;
        mn += t.x;
        mx += t.x;
    }
};

Info operator+(const Info &a, const Info &b) {
    return {-inf, min(a.mn, b.mn), max(a.mx, b.mx)};
}

class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        int n = nums.size();
        LazySegmentTree<Info, Tag> StT(n + 1);
        unordered_map<int, int> last;

        int ans = 0, cur = 0;
        StT.modify(0, {0, 0, 0});
        for (int i = 1; i <= n; i++) {
            int v = nums[i - 1];
            int p = (v & 1) ? 1 : -1;
            auto it = last.find(v);
            if (it == last.end()) {
                cur += p;
                StT.rangeApply(i, n, {p});
            } else {
                StT.rangeApply((*it).second, i, {-p});
            }
            last[v] = i;

            int j = StT.findFirst(0, n, [&](const auto& x) {
                return x.mn <= cur && x.mx >= cur;
            });
            if (j >= 0) ans = max(ans, i - j);
        }

        return ans;
    }
};

力扣每日一题3721-最长平衡子数组II

日期：2026-02-11

题意

给定整数数组 nums ，求不同偶数数量等于不同奇数数量的最长子数组长度。

思路

是的，与 昨天 的题目是一样的，只是数据范围进行了扩大: len(nums) 1500 -> 1e5。但我们昨天的做法还是可行的。

实现

static constexpr int inf = 1e9;

template<class Info, class Tag>
struct LazySegmentTree {
    int n;
    std::vector<Info> info;
    std::vector<Tag> tag;
    LazySegmentTree() : n(0) {}
    LazySegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    LazySegmentTree(std::vector<T> init_) {
        init(init_);
    }
    void init(int n_, Info v_ = Info()) {
        init(std::vector(n_, v_));
    }
    template<class T>
    void init(std::vector<T> init_) {
        n = init_.size();
        info.assign(4 << std::__lg(n), Info());
        tag.assign(4 << std::__lg(n), Tag());
        std::function<void(int, int, int)> build = [&](int p, int l, int r) {
            if (r - l == 1) {
                info[p] = init_[l];
                return;
            }
            int m = (l + r) / 2;
            build(2 * p, l, m);
            build(2 * p + 1, m, r);
            pull(p);
        };
        build(1, 0, n);
    }
    void pull(int p) {
        info[p] = info[2 * p] + info[2 * p + 1];
    }
    void 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 modify(int p, int l, int r, int x, const Info &v) {
        if (r - l == 1) {
            info[p] = v;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        if (x < m) {
            modify(2 * p, l, m, x, v);
        } else {
            modify(2 * p + 1, m, r, x, v);
        }
        pull(p);
    }
    void modify(int p, const Info &v) {
        modify(1, 0, n, p, v);
    }
    Info rangeQuery(int p, int l, int r, int x, int y) {
        if (l >= y || r <= x) {
            return Info();
        }
        if (l >= x && r <= y) {
            return info[p];
        }
        int m = (l + r) / 2;
        push(p);
        return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
    }
    Info rangeQuery(int l, int r) {
        return rangeQuery(1, 0, n, l, r);
    }
    void rangeApply(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);
        rangeApply(2 * p, l, m, x, y, v);
        rangeApply(2 * p + 1, m, r, x, y, v);
        pull(p);
    }
    void rangeApply(int l, int r, const Tag &v) {
        return rangeApply(1, 0, n, l, r, v);
    }
    void half(int p, int l, int r) {
        if (info[p].act == 0) {
            return;
        }
        if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
            apply(p, {-(info[p].min + 1) / 2});
            return;
        }
        int m = (l + r) / 2;
        push(p);
        half(2 * p, l, m);
        half(2 * p + 1, m, r);
        pull(p);
    }
    void half() {
        half(1, 0, n);
    }
    
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findFirst(2 * p, l, m, x, y, pred);
        if (res == -1) {
            res = findFirst(2 * p + 1, m, r, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findFirst(int l, int r, F &&pred) {
        return findFirst(1, 0, n, l, r, pred);
    }
    template<class F>
    int findLast(int p, int l, int r, int x, int y, F &&pred) {
        if (l >= y || r <= x) {
            return -1;
        }
        if (l >= x && r <= y && !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        push(p);
        int res = findLast(2 * p + 1, m, r, x, y, pred);
        if (res == -1) {
            res = findLast(2 * p, l, m, x, y, pred);
        }
        return res;
    }
    template<class F>
    int findLast(int l, int r, F &&pred) {
        return findLast(1, 0, n, l, r, pred);
    }
    
    void maintainL(int p, int l, int r, int pre) {
        if (info[p].difl > 0 && info[p].maxlowl < pre) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainL(2 * p, l, m, pre);
        pre = std::max(pre, info[2 * p].max);
        maintainL(2 * p + 1, m, r, pre);
        pull(p);
    }
    void maintainL() {
        maintainL(1, 0, n, -1);
    }
    void maintainR(int p, int l, int r, int suf) {
        if (info[p].difr > 0 && info[p].maxlowr < suf) {
            return;
        }
        if (r - l == 1) {
            info[p].max = info[p].maxlowl;
            info[p].maxl = info[p].maxr = l;
            info[p].maxlowl = info[p].maxlowr = -inf;
            return;
        }
        int m = (l + r) / 2;
        push(p);
        maintainR(2 * p + 1, m, r, suf);
        suf = std::max(suf, info[2 * p + 1].max);
        maintainR(2 * p, l, m, suf);
        pull(p);
    }
    void maintainR() {
        maintainR(1, 0, n, -1);
    }
};

struct Tag {
    int x = 0;
    void apply(const Tag &t) & {
        x += t.x;
    }
};

struct Info {
    int x = 0;
    int mn = 0;
    int mx = 0;
    void apply(const Tag &t) & {
        x += t.x;
        mn += t.x;
        mx += t.x;
    }
};

Info operator+(const Info &a, const Info &b) {
    return {-inf, min(a.mn, b.mn), max(a.mx, b.mx)};
}

class Solution {
public:
    int longestBalanced(vector<int>& nums) {
        int n = nums.size();
        LazySegmentTree<Info, Tag> StT(n + 1);
        unordered_map<int, int> last;

        int ans = 0, cur = 0;
        StT.modify(0, {0, 0, 0});
        for (int i = 1; i <= n; i++) {
            int v = nums[i - 1];
            int p = (v & 1) ? 1 : -1;
            auto it = last.find(v);
            if (it == last.end()) {
                cur += p;
                StT.rangeApply(i, n, {p});
            } else {
                StT.rangeApply((*it).second, i, {-p});
            }
            last[v] = i;

            int j = StT.findFirst(0, n, [&](const auto& x) {
                return x.mn <= cur && x.mx >= cur;
            });
            if (j >= 0) ans = max(ans, i - j);
        }

        return ans;
    }
};

力扣每日一题3713-最长的平衡子串I

日期：2026-02-12

题意

给定小写字母字符串 s ，找出最长的 子串中所有不同字符出现次数相同的子串 的长度

思路

和前两天的题目非常类似，但又很不同，又二十六种字符，重复出现有重复贡献，同时要排除未出现字符的影响。好像是有点难做的，好在数据范围不大 1 <= len(s) <= 1e3 ，那咱们简单范围简单做，进行一个平方的枚举范围就好。

实现

class Solution {
public:
    int longestBalanced(string s) {
        int n = s.size();

        int ans = 0;
        array<int, 26> cnt;
        for (int i = 0; i < n; i++) {
            cnt.fill(0);
            for (int j = i; j < n; j++) {
                cnt[s[j] - 'a']++;
                int cur = j - i + 1;
                if (cur < ans) continue;
                bool ok = true;
                for (int k = 0, t = 0; k < 26; k++) {
                    if (cnt[k] == 0) continue;
                    else if (t == 0) t = cnt[k];
                    else if (cnt[k] != t) ok = false;
                }
                if (ok) ans = max(ans, cur);
            }
        }

        return ans;
    }
};

力扣每日一题3714-最长的平衡子串II

日期：2026-02-13

题意

给定仅包含 a b c 的字符串 s ，找出最长的 子串中所有不同字符出现次数都相同的 子串的长度。

思路

和昨天题目是非常类似的，只是字符串长度扩大到了 1e5 ，但字符范围缩小到了 abc。那我们昨天的平方的做法是行不通了的，自然是想到从缩小了的范围去考虑。

答案总共有三种情况，首先是仅包含一种字符，然后是仅包含两种字符，最后是包含 abc 三种。第一种比较简单不过多讲解；第二种我们做过类似的，实际上就是令某个字符视作 +1 另一字符视作 -1，找区间和为 0 的子串，我们这里需要枚举三种不同的选字符方式；第三种实际上也仅为第二种的扩展 cnt_a == cnt_b == cnt_c ，我们将其拆开为 cnt_a == cnt_b && cnt_b == cnt_c ，也就是找两组数区间和均为 0 的子串。

实现

class Solution {
using ll = long long;
public:
    int longestBalanced(string s) {
        int ans = 0;
        int n = s.size();
        
        for (int i = 0, j; i < n; i = j) {
            for (j = i + 1; j < n && s[j] == s[i]; j++);
            ans = max(ans, j - i);
        }

        auto cal = [&](char x, char y) -> void {
            for (int i = 0; i < n; i++) {
                unordered_map<int, int> last;
                last[0] = i - 1;
                int cur = 0;
                for ( ; i < n && (s[i] == x || s[i] == y); i++) {
                    cur += s[i] == x ? 1 : -1;
                    if (last.count(cur)) {
                        ans = max(ans, i - last[cur]);
                    } else {
                        last[cur] = i;
                    }
                }
            }
        };
        cal('a', 'b');
        cal('a', 'c');
        cal('b', 'c');

        unordered_map<ll, int> last;
        last[1ll * n << 20 | n] = -1;
        array<int, 3> cnt;
        cnt.fill(0);
        for (int i = 0; i < n; i++) {
            cnt[s[i] - 'a']++;
            ll p = 1ll * (cnt[0] - cnt[1] + n) << 20 | (cnt[1] - cnt[2] + n);
            if (last.count(p)) {
                ans = max(ans, i - last[p]);
            } else {
                last[p] = i;
            }
        }

        return ans;
    }
};

力扣每日一题799-香槟塔

日期：2026-02-14

题意

给定金字塔形香槟塔，初始全为空，往最顶的玻璃杯倒入 poured 杯香槟，求问第 query_row 行 第 query_glass 个杯子中有多少酒。

思路

数据范围不很大 1 <= query_row, query_glass <= 100 ，我们直接就倒酒的这个流程进行模拟就好。

实现

class Solution {
public:
    double champagneTower(int poured, int query_row, int query_glass) {
        vector f(query_row + 2, vector<double> (query_glass + 2));
        f[0][0] = poured;
        for (int i = 0; i <= query_row; i++) {
            for (int j = 0; j <= query_glass; j++) {
                if (f[i][j] > 1) {
                    f[i + 1][j] += (f[i][j] - 1) / 2;
                    f[i + 1][j + 1] += (f[i][j] - 1) / 2;
                }
            }
        }
        return min(f[query_row][query_glass], 1.0);
    }
};

力扣每日一题67-二进制求和

日期：2026-02-15

题意

给定两二进制字符串 a 与 b ，以二进制字符串的形式返回它们的和。

思路

没什么特别的，进行一个二进制求和模拟即可。

实现

class Solution {
public:
    string addBinary(string a, string b) {
        if (a.size() < b.size()) swap(a, b);
        int n = a.size(), m = b.size();
        ranges::reverse(a);
        ranges::reverse(b);
        for (int i = 0; i < m - 1; i++) {
            a[i] += b[i] - '0';
            if (a[i] > '1') {
                a[i] -= 2;
                a[i + 1] += 1;
            }
        }
        a[m - 1] += b[m - 1] - '0';
        for (int i = m - 1; i < n - 1; i++) {
            if (a[i] > '1') {
                a[i] -= 2;
                a[i + 1] += 1;
            }
        }
        if (a.back() > '1') {
            a.back() -= 2;
            a += '1';
        }
        
        ranges::reverse(a);
        return a;
    }
};

力扣每日一题190-颠倒二进制位

日期：2026-02-16

题意

颠倒给定 32 位有符号整数的二进制位。

思路

可以直接逐位进行模拟，但这里其实是有个库函数 __builtin_bitreverse32 的，所以可以直接偷偷懒。

实现

class Solution {
public:
    int reverseBits(int n) {
        return __builtin_bitreverse32(n);
    }
};

力扣每日一题401-二进制手表

日期：2026-02-17

题意

有一个二进制手表，小时用四个灯 8 4 2 1 表示，分钟用六个灯 32 16 8 4 2 1 表示，若有 turnedOn 个灯亮着，求问所有可能表示的时间。

思路

数据范围显然很小，直接进行枚举判断即可。

实现

class Solution {
public:
    vector<string> readBinaryWatch(int turnedOn) {
        vector<string> ans;
        for (unsigned i = 0; i <12; i++) {
            for (unsigned j = 0; j < 60; j++) {
                if (popcount(i) + popcount(j) == turnedOn) {
                    if (j < 10) ans.push_back({to_string(i) + ":0" + to_string(j)});
                    else ans.push_back({to_string(i) + ":" + to_string(j)});
                }
            }
        }
        return ans;   
    }
};

力扣每日一题693-交替位二进制数

日期：2026-02-18

题意

给定正整数 n ，判断其二进制表示是否总为 0 1 交替出现。

思路

可以想到右移一位使得相邻位对上，而相邻位为 0 1 交替即代表异或结果为 1。因此若该数满足条件，则该数与其右移一位的数异或后可得一个低位均为 1 的数。验证该结果是否均为 1 即可。可以使其加一，则必为一个与原数无共同位的二的幂次。

实现

class Solution {
public:
    bool hasAlternatingBits(int n) {
        unsigned x = (n >> 1) ^ n;
        return !(x & (x + 1));
    }
};

力扣每日一题696-计数二进制子串

日期：2026-02-19

题意

给定 01 字符串 s ，返回其中具有相同数量的 01 的非空连续子字符串的数量，同时要求子字符串的所有 0 与所有 1 是成组连续的。

思路

很自然想到滑动窗口，找当前连续 0 的数量与连续 1 的数量，贡献为两者间的较小值。

实现

class Solution {
public:
    int countBinarySubstrings(string s) {
        int n = s.size();
        int ans = 0;
        for (int i = 0, j = 0, k = 0; i < n; i = j, j = k) {
            for ( ; j < n && s[j] == s[i]; j++);
            for (k = j; k < n && s[k] == s[j]; k++);
            ans += min(j - i, k - j);
        }
        return ans;
    }
};

力扣每日一题761-特殊的二进制字符串

日期：2026-02-20

题意

若一个二进制字符串 01 数量相等且该字符串任意前缀中的 1 数量均大于等于 0 数量则称该字符串特殊。现给定特殊二进制字符串 s ，每次操作可以任意交换一对相邻特殊字符子串的位置。问可得字典序最大的字符串。

思路

一个特殊字符串应该由一个或多个特殊子串组成。同时相邻特殊子串间可以互换位置，那么其内子串可以通过类似冒泡排序的方式得到最大字典序。由此我们可以想到递归的去处理给定字符串。

实现

class Solution {
public:
    string makeLargestSpecial(string s) {
        int n = s.size();
        if (n <= 2) return s;

        vector<string> t;
        int l = 0, cur = 0;
        for (int i = 0; i < n; i++) {
            if (s[i] == '1') cur++;
            else {
                cur--;
                if (cur == 0) {
                    t.push_back("1" + makeLargestSpecial(s.substr(l + 1, i - l - 1)) + "0");
                    l = i + 1;
                }
            }
        }

        ranges::sort(t, greater());
        string res;
        for (const auto& p : t) res += p;
        return res;
    }
};

力扣每日一题762-二进制表示中质数个计算置位

日期：2026-02-21

题意

求给定区间 [left, right] 内，二进制表示下 1 的个数为质数的数的个数。

思路

数据范围实在不大 1 <= left, right <= 1e6 ，那其实怎么做包括暴力都是可以的，这里我是预处理范围内的个数的前缀和。

实现

static constexpr int N = 1e6;
static const unordered_set<int> p = {
    2, 3, 5, 7, 11, 13, 17, 19
};
int pre[N + 1];
auto init = []() {
    for (unsigned i = 1, cur = 0; i <= N; i++) {
        if (p.count(popcount(i))) cur++;
        pre[i] = cur;
    }
    return 0;
} ();

class Solution {
public:
    int countPrimeSetBits(int left, int right) {
        return pre[right] - pre[left - 1];
    }
};

力扣每日一题868-二进制间距

日期：2026-02-22

题意

给定正整数 n，找到其二进制表示下相邻 1 之间的最大距离。

思路

没什么特别的，遍历其二进制位记录上一个 1 的位置即可。

实现

class Solution {
public:
    int binaryGap(int n) {
        int ans = 0;
        int last = -1;
        for (int i = 0; i < 31; i++) {
            if (n >> i & 1) {
                if (last != -1) ans = max(ans, i - last);
                last = i;
            }
        }
        return ans;
    }
};

力扣每日一题1461-检查一个字符串是否包含所有长度为 K 的二进制子串

日期：2026-02-23

题意

给定二进制字符 s 和一个正整数 k。判断是否所有长度为 k 的二进制字符串均为 s 的子串。

思路

长度为 k 的二进制字符串有 种，这里 1 <= k <= 20 范围并不大，同时也确实没什么好的方法，只能是取 s 中所有长度为 k 的子串去重后看数量是否一致。

实现

class Solution {
public:
    bool hasAllCodes(string s, int k) {
        int n = s.size();
        int cnt = 0;
        vector<bool> vis(1 << k);
        int mask = (1 << k) - 1;
        int cur = 0;
        for (int i = 0; i < n; i++) {
            cur <<= 1;
            cur |= s[i] == '1';
            cur &= mask;
            if (i >= k - 1 && !vis[cur]) {
                if (++cnt > mask) return true;
                vis[cur] = true;
            }
        }
        return cnt > mask;
    }
};

力扣每日一题1022-从根到叶的二进制数之和

日期：2026-02-24

题意

给定一棵每个结点值为 0/1 的二叉树。以根为高位，求所有叶子结点表示的数的和。

思路

进行一个 dfs 求和即可。

实现

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int sumRootToLeaf(TreeNode* root) {
        int ans = 0;

        auto dfs = [&](this auto&& self, TreeNode* root, int cur = 0) -> void {
            if (root == nullptr) return;
            cur <<= 1;
            cur |= root->val;
            if (root->left == nullptr && root->right == nullptr) {
                ans += cur;
            } else {
                self(root->left, cur);
                self(root->right, cur);
            }
        };
        dfs(root);

        return ans;
    }
};

力扣每日一题1356-根据数字二进制下1的数目排序

日期：2026-02-25

题意

给定整数数组 arr ，按二进制表示下含 1 的数量进行升序排序，若含 1 量相同则按大小升序排序。

思路

简单排序题，按题意排序即可。

实现

class Solution {
public:
    vector<int> sortByBits(vector<int>& arr) {
        ranges::sort(arr, [&](const auto& x, const auto& y) {
            int nx = popcount(unsigned(x));
            int ny = popcount(unsigned(y));
            if (nx == ny) return x < y;
            return nx < ny;
        });
        return arr;
    }
};

力扣每日一题1404-将二进制表示减到1的步骤数

日期：2026-02-26

题意

给定二进制表示的数组 s ，重复以下操作直到该数变为 1 ：

  • 若当前数为偶数则该数除以 2
  • 若当前数位奇数则该数加 1

求所需操作的次数。

思路

按题意进行模拟即可。

实现

class Solution {
public:
    int numSteps(string s) {
        int n = s.size();
        int ans = 0, t = 0;
        for (int i = n - 1; i > 0; i--) {
            if (t) {
                if (s[i] == '0') ans += 2;
                else ans++;
            } else {
                if (s[i] == '0') ans++;
                else {
                    ans += 2;
                    t = 1;
                }
            }
        }
        return ans + t;
    }
};

力扣每日一题3666-使二进制字符串全为1的最少操作次数

日期：2026-02-27

题意

给定二进制字符串 s 与一个正整数 k 。每次操作必须选择恰好 k 个不同 s 的字符，使其 01 翻转。判断 s 是否可以转为全 1 ，若可以返回最少操作次数。

思路

每次可以增加或减少 k 个 0 ，但不能减少到负数也不能增加到超过总长。也就是有个类似于 “弹回” 的操作，这题就非常眼熟了，应该是初学 bfs 的某道很经典的题。这题也没什么复杂的内容，只是注意到同一操作可达剩余 0 数的奇偶性相同，稍微做了些优化。

实现

class Solution {
public:
    int minOperations(string s, int k) {
        const int n = s.size();
        vector<int> dis(n + 1, -1);
        set<int> st[2];
        for (int i = 0; i <= n; i++) {
            st[i & 1].insert(i);
        }

        int cnt = count(s.begin(), s.end(), '0');
        vector<int> q;
        q.push_back({cnt});
        dis[cnt] = 0;
        st[cnt & 1].erase(cnt);
        for (int i = 0; i < q.size(); i++) {
            int x = q[i];
            int l = abs(x - k);
            int r = (x + k <= n ? x + k : n - (x + k - n));
            // cout << x << ' ' << l << ' ' << r << '\n';
            auto& t = st[l & 1];
            for (auto it = t.lower_bound(l); it != t.end(); ) {
                if (*it > r) break;
                if (dis[*it] == -1) {
                    q.push_back(*it);
                    dis[*it] = dis[x] + 1;
                    t.erase(it++);
                }
            }
        }
        return dis[0];
    }
};

力扣每日一题1680-连接连续二进制数字

日期：2026-02-28

题意

给定正整数 n，将 1 到 n 的二进制表示依次连接起来，返回其表示的十进制数对 1e9 + 7 取模的结果。

思路

两个十进制数 a 与 b 连接为 ab 实际就是 a * (10 ** len(b)) + b

两个二进制数相连也是类似的道理 a * (2 ** len(b)) + b

同时我们知道对一个数取模，加或乘的前后模数学上是等价的。由此进行一个模拟即可。

实现

class Solution {
static constexpr int mod = 1e9 + 7;
using ll = long long;
public:
    int concatenatedBinary(int n) {
        ll ans = 0;
        for (int i = 1, len = 0; i <= n; i++) {
            if ((i & (i - 1)) == 0) len++;
            ans = ans << len | i;
            ans %= mod;
        }
        return ans;
    }
};