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

目录

力扣每日一题118-杨辉三角

日期：2025-08-01

题意

给定非负整数numRows，生成杨辉三角的前numRows行。

思路

这道题是hot100的原题，本身难度也没有很大，只要知道杨辉三角的定义我想就是不难写的。

简单的双层循环模拟杨辉三角的计算过程即可。

实现

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = [[1] * (i + 1) for i in range(numRows)]
        for i in range(2, numRows):
            for j in range(1, i):
                ans[i][j] = ans[i - 1][j] + ans[i - 1][j - 1]
        return ans
class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        ans.push_back({1});
        for (int i = 1; i < numRows; i++) {
            vector<int> tmp(ans.back().size() + 1);
            for (int j = 0; j <= i; j++) {
                if (j == 0 || j == i) tmp[j] = 1;
                else {
                    tmp[j] = (ans.back()[j - 1] + ans.back()[j]);
                }
            }
            ans.push_back(tmp);
        }
        return ans;
    }
};

力扣每日一题2561-重排水果

日期：2025-08-02

题意

给定两个等长数组basket1和basket2。可以进行任意次以下操作：

  • 交换basket1[i]与basket2[j]，操作的代价为min(basket1[i], basket2[j])

求欲使两数组内容相同的最小代价。

思路

手玩一下不难发现其实是很符合贪心性质的。

首先是不能使两数组相同的情况，必然是有某个数有奇数个。

再考虑可以使得两数组相同的情况，每个数均有偶数个，又两数组等长，若basket1中缺某数一定会多出另一个数，basket2也是同理。每次交换可以处理两个数。可以想到将两数中多的数列出来，每次操作交换一侧最大另一侧的最小。又可选择某侧最小值换过去再换回来，取代价最小即可。

呃，好像讲得是有点乱，还请看代码吧。

实现

class Solution:
    def minCost(self, basket1: List[int], basket2: List[int]) -> int:
        cnt = defaultdict(int)
        for x in basket1:
            cnt[x] += 1
        for x in basket2:
            cnt[x] -= 1
        
        a, b = [], []
        for num, t in cnt.items():
            if t & 1:
                return -1
            if t > 0:
                a.extend([num] * (t // 2))
            elif t < 0:
                b.extend([num] * (-t // 2))
        
        a.sort()
        b.sort(reverse=True)
        mn = min(min(basket1), min(basket2))
        ans = 0
        for i in range(len(a)):
            ans += min(a[i], b[i], mn * 2)
        return ans
class Solution {
using ll = long long;
public:
    long long minCost(vector<int>& basket1, vector<int>& basket2) {
        int mn = 1e9;
        unordered_map<int, array<int, 2>> cnt;
        for (const auto& x : basket1) {
            cnt[x][0]++;
            mn = min(mn, x);
        }
        for (const auto& x : basket2) {
            cnt[x][1]++;
            mn = min(mn, x);
        }
        vector<int> a, b;
        for (const auto& [num, arr] : cnt) {
            const auto& [x, y] = arr;
            if ((x + y) & 1) return -1;
            if (x > y) a.insert(a.end(), (x - y) >> 1, num);
            else if (x < y) b.insert(b.end(), (y - x) >> 1, num);
        }
        ranges::sort(a);
        ranges::sort(b, greater());
        ll ans = 0;
        for (int i = 0; i < a.size(); i++) {
            ans += min({a[i], b[i], mn << 1});
        }
        return ans;
    }
};

力扣每日一题2106-摘水果

日期：2025-08-03

题意

位于无限长的横坐标轴上。给定数组fruits表示每堆水果所在的位置以及数量，初始位于位置startPos，最多可以移动k步。求可以获得的最大水果数。

思路

手玩一下可以发现来回走是会浪费步数的，所以只可能先向左再向右或反过来先向右再向左可能得到最大值。

那么使用滑动窗口维护可达位置内的水果数量，取最大值即为答案。

实现

class Solution {
public:
    int maxTotalFruits(vector<vector<int>>& fruits, int startPos, int k) {
        const int n = fruits.size();
        int lt = ranges::lower_bound(fruits, startPos - k, {}, [&](const auto& x) {
            return x[0];
        }) - fruits.begin();

        int rt = lt;
        int ans = 0;
        for ( ; rt < n && fruits[rt][0] <= startPos; rt++) ans += fruits[rt][1];

        int cur = ans;
        for ( ; rt < n && fruits[rt][0] <= startPos + k; rt++) {
            cur += fruits[rt][1];
            for ( ; startPos - 2 * fruits[lt][0] + fruits[rt][0] > k && 2 * fruits[rt][0] - startPos - fruits[lt][0] > k; lt++) {
                cur -= fruits[lt][1];
            }
            ans = max(ans, cur);
        }
        return ans;
    }
};
class Solution:
    def maxTotalFruits(self, fruits: List[List[int]], startPos: int, k: int) -> int:
        n = len(fruits)
        lt = bisect_left(fruits, [startPos - k])
        rt = lt
        ans = 0
        while rt < n and fruits[rt][0] <= startPos:
            ans += fruits[rt][1]
            rt += 1
        
        cur = ans
        while rt < n and fruits[rt][0] <= startPos + k:
            cur += fruits[rt][1]
            while startPos + fruits[rt][0] - fruits[lt][0] * 2 > k and fruits[rt][0] * 2 - fruits[lt][0] - startPos > k:
                cur -= fruits[lt][1]
                lt += 1
            rt += 1
            ans = max(ans, cur)
        return ans

力扣每日一题904-水果成篮

日期：2025-08-04

题意

给定数组fruits表示一排果树的种类。有且仅有两个篮子，每个篮子仅可装一种水果但没有数量上限。可以任选一个位置开始向右摘水果，必须恰好摘一个所经过的水果，若无法装下则停止。求最多可以摘多少水果。

思路

简单来说就是仅包含小于等于两种数的最长子数组。直接使用滑动窗口即可，由于种类上限较少，可以仅开4个变量进行维护（两个篮子所装种类及数量）。若种类上限较多可以考虑使用哈希维护。

实现

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        array<int, 2> a {-1, 0}, b {-1, 0};
        int ans = 0;
        const int n = fruits.size();
        for (int l = 0, r = -1; r + 1 < n; ) {
            if (a[0] == fruits[r + 1]) {
                a[1]++;
                r++;
            } else if (b[0] == fruits[r + 1]) {
                b[1]++;
                r++;
            } else if (b[0] == -1) {
                b = {fruits[++r], 1};
            } else if (a[0] == -1) {
                a = {fruits[++r], 1};
            } else if (r + 1 < n) {
                for ( ; b[1] && a[1]; l++) {
                    if (fruits[l] == a[0]) a[1]--;
                    else b[1]--;
                }
                if (b[1] == 0) b[0] = -1;
                else a[0] = -1;
            }
            ans = max(ans, a[1] + b[1]);
        }
        return ans;
    }
};
class Solution:
    def totalFruit(self, fruits: List[int]) -> int:
        a = [-1, 0]
        b = [-1, 0]
        n = len(fruits)
        ans = l = 0
        r = -1
        while r + 1 < n:
            if a[0] == fruits[r + 1]:
                a[1] += 1
                r += 1
            elif b[0] == fruits[r + 1]:
                b[1] += 1
                r += 1
            elif b[0] == -1:
                b = [fruits[r + 1], 1]
                r += 1
            elif a[0] == -1:
                a = [fruits[r + 1], 1]
                r += 1
            else:
                while a[1] > 0 and b[1] > 0:
                    if fruits[l] == a[0]:
                        a[1] -= 1
                    else:
                        b[1] -= 1
                    l += 1
                if b[1] == 0:
                    b[0] = -1
                else:
                    a[0] = -1
            ans = max(ans, a[1] + b[1])
        return ans

力扣每日一题3477-水果成篮 II

日期：2025-08-05

题意

给定数组 fruits 与 baskets，分别表示不同种类水果的数量以及每个篮子的容量。需要按顺序将水果放进最左可以放进所有该种水果的篮子，不同水果不可混放。求会有多少种水果无法放进篮子。

思路

注意到本题的数据范围是不大的，n == len(fruits) == len(baskets) <= 100 ，那么其实直接暴力模拟即可。

但是数据范围稍大些呢，问题其实是可以转换为多个求最左含大于某数的位置的问题，同时带修改，那么可以想到使用线段树维护区间最大值，然后使用线段树上二分即可。

这里我只有cpp线段树二分的板子，所有只用cpp实现了线段树上二分的代码，python就偷懒暴力了。

实现

cpp 与 线段树二分

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(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());
        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 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;
        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;
        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);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        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 || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        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);
    }
};
struct Info {
    int mx;
};
Info operator+(Info a, Info b) {
    return {max(a.mx, b.mx)};
}

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        const int n = fruits.size();
        SegmentTree<Info> SgT(n);
        for (int i = 0; i < n; i++) {
            SgT.modify(i, {baskets[i]});
        }
        int ans = n;
        for (const auto& x : fruits) {
            int loc = SgT.findFirst(0, n, [&](const auto& p) {
                return p.mx >= x;
            });
            if (loc == -1) continue;
            SgT.modify(loc, {0});
            ans--;
        }
        return ans;
    }
};

python 与 暴力

class Solution:
    def numOfUnplacedFruits(self, fruits: List[int], baskets: List[int]) -> int:
        ans = n = len(fruits)
        for x in fruits:
            for i in range(n):
                if baskets[i] >= x:
                    ans -= 1
                    baskets[i] = 0
                    break
        return ans

力扣每日一题3479-水果成篮 III

日期：2025-08-06

题意

给定数组 fruits 与 baskets，分别表示不同种类水果的数量以及每个篮子的容量。需要按顺序将水果放进最左可以放进所有该种水果的篮子，不同水果不可混放。求会有多少种水果无法放进篮子。

思路

是和做题完全一样的题，只是数据范围增强到了1e5那就为无法直接暴力，可以使用线段树二分，不过由于昨天我已经是这么写的了，就不过多赘述。

实现

template<class Info>
struct SegmentTree {
    int n;
    std::vector<Info> info;
    SegmentTree() : n(0) {}
    SegmentTree(int n_, Info v_ = Info()) {
        init(n_, v_);
    }
    template<class T>
    SegmentTree(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());
        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 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;
        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;
        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);
    }
    template<class F>
    int findFirst(int p, int l, int r, int x, int y, F pred) {
        if (l >= y || r <= x || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        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 || !pred(info[p])) {
            return -1;
        }
        if (r - l == 1) {
            return l;
        }
        int m = (l + r) / 2;
        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);
    }
};
struct Info {
    int mx;
};
Info operator+(Info a, Info b) {
    return {max(a.mx, b.mx)};
}

class Solution {
public:
    int numOfUnplacedFruits(vector<int>& fruits, vector<int>& baskets) {
        const int n = fruits.size();
        SegmentTree<Info> SgT(n);
        for (int i = 0; i < n; i++) {
            SgT.modify(i, {baskets[i]});
        }
        int ans = n;
        for (const auto& x : fruits) {
            int loc = SgT.findFirst(0, n, [&](const auto& p) {
                return p.mx >= x;
            });
            if (loc == -1) continue;
            SgT.modify(loc, {0});
            ans--;
        }
        return ans;
    }
};

力扣每日一题3363-最多可收集的水果数目

日期：2025-08-07

题意

给定 n * n 大小的网格，以及二维数组 fruits 表示每个格子内的水果数。有三个小朋友分别位于 (0, 0), (0, n - 1), (n - 1, 0) 其中

  • (0, 0) 的人每次可以往右、下、右下移动一格
  • (0, n - 1) 的人每次可以往左下、下、右下移动一格
  • (n - 1, 0) 的人每次可以往右上、右、右下移动一格

每个小朋友只能移动 n - 1 步且终点必须为 (n - 1, n - 1) ，求三个小朋友总共可收集的最大水果数。

思路

咋一看是挺难的，但是每个小朋友都只能移动 n - 1 步且必须到达 (n - 1, n - 1) 那也就是说左上的小朋友有且仅有沿对角线一种走法，右上和左下的小朋友的可行动区域也仅是一个小三角形，且三个小朋友的行动路径不可能相交。

那么问题就转变成了两个简单的dp（求右上和左下的小朋友行动最优方案）。

实现

class Solution {
public:
    int maxCollectedFruits(vector<vector<int>>& fruits) {
        const int n = fruits.size();
        int ans = 0;

        vector f(n + 1, vector<int> (n + 1));
        f[0][n - 1] = fruits[0][n - 1];
        for (int i = 1; i < n; i++) {
            for (int j = max(i + 1, n - 1 - i); j < n; j++) {
                f[i][j] = max({f[i - 1][j + 1], f[i - 1][j], f[i - 1][j - 1]}) + fruits[i][j];
            }
        }
        ans += f[n - 2][n - 1];

        f[n - 1][0] = fruits[n - 1][0];
        for (int j = 1; j < n; j++) {
            for (int i = max(j + 1, n - 1 - j); i < n; i++) {
                f[i][j] = max({f[i + 1][j - 1], f[i][j - 1], f[i - 1][j - 1]}) + fruits[i][j];
            }
        }
        ans += f[n - 1][n - 2];

        for (int i = 0; i < n; i++) ans += fruits[i][i];
        return ans;
    }
};
class Solution:
    def maxCollectedFruits(self, fruits: List[List[int]]) -> int:
        n = len(fruits)
        f = [0] * ((n + 1) * (n + 1))
        def cal(x, y):
            return x * (n + 1) + y
        
        ans = 0
        f[cal(0, n - 1)] = fruits[0][n - 1]
        for i in range(1, n):
            for j in range(max(i + 1, n - 1 - i), n):
                f[cal(i, j)] = max(f[cal(i - 1, j - 1)], f[cal(i - 1, j)], f[cal(i - 1, j + 1)]) + fruits[i][j]
        ans += f[cal(n - 2, n - 1)]

        f[cal(n - 1, 0)] = fruits[n - 1][0]
        for j in range(1, n):
            for i in range(max(j + 1, n - 1 - j), n):
                f[cal(i, j)] = max(f[cal(i + 1, j - 1)], f[cal(i, j - 1)], f[cal(i - 1, j - 1)]) + fruits[i][j]
        ans += f[cal(n - 1, n - 2)]

        ans += sum(x[i] for i, x in enumerate(fruits))
        return ans

力扣每日一题808-分汤

日期：2025-08-08

题意

给定初始有 n 毫升的汤A和汤B，每轮操作等概率地发生以下四种事件：

  • A减少 100 毫升，B减少 0 毫升
  • A减少 75 毫升，B减少 25 毫升
  • A减少 50 毫升，B减少 50 毫升
  • A减少 25 毫升，B减少 75 毫升

求(A在B之前取完的概率)加上(AB同时取完概率的一半)

思路

先看数据范围，n <= 1e9 非常的大，当 n 很大时什么做法都不可能实现的，那么肯定是个思维数学题。

仔细观察每次操作的影响，A减少的期望量显然是大于B的，那么当 n 很大时一定是A先取完的。

再考虑以下小范围时应该怎么做。求概率，比较自然可以想到使用概率dp，同时注意到每次操作的减少量的最大公因数为 25 ，故可以将毫升数统统除以 25 表示操作次数与操作减少量。

再用获得的dp算法大概跑一下范围，可以发现操作次数超过 200 后概率在可接受误差内可认为 1

实现

class Solution {
using ld = long double;
static constexpr ld eps = 1e-5;
static constexpr int N = 25;
static constexpr ld p = 0.25;
public:
    double soupServings(int n) {
        const int t = (n + N - 1) / N;
        if (t >= 200) return 1.0;

        auto cal = [](const int& x) -> int {
            return max(x, 0);
        };

        vector f(t + 1, vector<ld> (t + 1));
        fill(f[0].begin(), f[0].end(), 1.0);
        f[0][0] = 0.5;
        for (int i = 1; i <= t; i++) {
            for (int j = 1; j <= t; j++) {
                f[i][j] = (f[cal(i - 4)][j] + f[cal(i - 3)][cal(j - 1)] + f[cal(i - 2)][cal(j - 2)] + f[cal(i - 1)][cal(j - 3)]) * p;
            }
        }
        return f[t][t];
    }
};
class Solution:
    def soupServings(self, n: int) -> float:
        t = (n + 24) // 25
        if t >= 200:
            return 1.0
        
        p = 0.25
        @cache
        def dfs(x, y) -> float:
            if x <= 0 and y <= 0:
                return 0.5
            elif x <= 0:
                return 1.0
            elif y <= 0:
                return 0.0
            res = 0.0
            for i in range(1, 5):
                res += dfs(x - i, y - 4 + i) * p
            return res
        
        return dfs(t, t)

力扣每日一题231-2 的幂

日期：2025-08-09

题意

给定数 n ，判断 n 是否为 2 的幂次。

思路

那有很多种写法的，最简单也最快的我认为就是利用位运算求 lowbit 也就是 n 二进制下的最低位，显然当 lowbit(n) == n 时 n 为 2 的幂次，不过要注意二的幂次应该是正整数的，题目给的范围为 int 范围。

lowbit(x) == x & -x

实现

class Solution {
public:
    bool isPowerOfTwo(int n) {
        return n > 0 && (n & -n) == n;
    }
};
class Solution:
    def isPowerOfTwo(self, n: int) -> bool:
        return n > 0 and (n & -n) == n

力扣每日一题869-重新排序得到 2 的幂

日期：2025-08-10

题意

给定正整数 n , 判断是否可以将其重排为无前导零的二的幂次数。

思路

注意到给定的数据范围是 n <= 1e9 也就是最多有九位数，转为字符串进行全排列枚举排列方案再按昨日每日一题的方法判断是否为二的幂次数即可，计算量大概是 9! 完全是可以接受的。

但确实不太优雅，1e9 内的二的幂次数显然是不超过 31 个的，我们完全可以预处理枚举这些数，将其中各个二次幂数的各数位出现的次数记录下来，然后与询问进行比对即可。只要各数位出现次数相同显然是可以重排的。

比较简单的做法就是灵神的将二的幂次数转为字符串然后排序加入到uset/ump/set/map 中，也可以开个大小为10的数组记录然后哈希。

但是我们可以注意到 1e9 意味着最多有九个数位，且相同数位出现次数不超过 9 ，我们完全可以转换为一个 long long 的数进行哈希，当然使用 python 的话就不用管这里的数据范围了。这样做常数会相对小些，但说实话这种题好像不用那么在意这个的，简单题简单做就好。

实现

cpp 与 枚举

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        auto check = [](int x) -> bool {
            return (x & -x) == x;
        };

        string s = to_string(n);
        string t = s;
        const int len = s.size();
        do {
            int x = stoi(s);
            if (to_string(x).size() == len && check(x)) return true;
            next_permutation(s.begin(), s.end());
        } while (s != t);
        return false;
    }
};

cpp 与 哈希

using ll = long long;
static constexpr int inf = 1e9;
static constexpr int N = 10;
static ll a[N];
unordered_set<ll> f;
auto init = []() -> int {
    a[0] = 1;
    for (int i = 1; i < N; i++) a[i] = a[i - 1] * 10;
    int x = 1;
    while (x <= inf) {
        ll cur = 0;
        for (int t = x; t; t /= 10) {
            cur += a[t % 10];
        }
        f.insert(cur);
        x <<= 1;
    }
    return 0;
} ();

class Solution {
public:
    bool reorderedPowerOf2(int n) {
        ll x = 0;
        for ( ; n; n /= 10) x += a[n % 10];
        return f.count(x);
    }
};

python 与 哈希

mx = 10**9
a = [1] * 10
for i in range(1, 10):
    a[i] = a[i - 1] * 10
f = set()
for i in range(0, 31):
    x = 1 << i
    cur = 0
    while x:
        cur += a[x % 10]
        x //= 10
    f.add(cur)

class Solution:
    def reorderedPowerOf2(self, n: int) -> bool:
        cur = 0
        while n:
            cur += a[n % 10]
            n //= 10
        return cur in f

力扣每日一题2438-二的幂数组中查询范围内的乘积

日期：2025-08-11

题意

给定数 n 找到对应的 powers 数组：

  • powers 非递减
  • powers 仅含 2 的幂次
  • powers 含数最少

给定一组询问 queries_i = [l_i, r_i] ，求 powers 中区间 [l_i, r_i] 的区间积，对 1e9 + 7 取模

思路

显然 powers 是唯一的，就是将 n 转为二进制的 1 的位

然后区间积第一反应我是求前缀积，这里由于模数是质数，除法等价于乘逆元即可。

但写python做法时看了下灵神写法，转为幂次的前缀和然后预处理就好，复杂度会更低。

实现

cpp 与 前缀积

using ll = long long;
static constexpr int mod = 1e9 + 7;
ll powMod(ll a, ll b) {
    ll res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}
class Solution {
public:
    vector<int> productQueries(int n, vector<vector<int>>& queries) {
        vector<int> f;
        for (int i = 0; i < 31; i++) {
            if (n >> i & 1) f.push_back(1 << i);
        }
        const int len = f.size();
        vector<int> pre(len + 1, 1);
        for (int i = 0; i < len; i++) {
            pre[i + 1] = 1ll * pre[i] * f[i] % mod;
        }

        vector<int> ans;
        for (const auto& q : queries) {
            int l = q[0], r = q[1] + 1;
            ans.push_back(1ll * pre[r] * powMod(pre[l], mod - 2) % mod);
        }
        return ans;
    }
};

python 与 前缀和

mod = 1000000007
def powMod(a, b):
    res = 1
    while b > 0:
        if (b & 1):
            res = res * a % mod
        a = a * a % mod
        b >>= 1
    return res
class Solution:
    def productQueries(self, n: int, queries: List[List[int]]) -> List[int]:
        pre = [0]
        for i in range(0, 31):
            if n >> i & 1:
                pre.append(pre[-1] + i)
        return [powMod(2, pre[r + 1] - pre[l]) for l, r in queries]

力扣每日一题2787-将一个数字表示成幂的和的方案数

日期：2025-08-12

题意

给定正整数 n 和 x， 返回将 n 表示成一些互不相同的的正整数的 x 次幂之和的方案数，对 1e9 + 7 取模。

思路

那就是一个比较经典的 0-1背包问题，显然只需枚举 x 次幂小于等于 n 的数即可，必然是不会有特别多的数的，然后进行背包就好。

实现

using ll = long long;
constexpr int mod = 1e9 + 7;
int pow_(int a, int b) {
    int res = 1;
    for ( ; b; b >>= 1, a *= a) {
        if (b & 1) res *= a;
    }
    return res;
}
class Solution {
public:
    int numberOfWays(int n, int x) {
        vector<int> f;
        for (int i = 1; true; i++) {
            int p = pow_(i, x);
            if (p > n) break;
            f.push_back(p);
        }
        vector<int> dp(n + 1);
        dp[0] = 1;
        for (const auto& num : f) {
            for (int i = n - num; i >= 0; i--) {
                dp[i + num] += dp[i];
                if (dp[i + num] >= mod) dp[i + num] -= mod;
            }
        }
        return dp.back();
    }
};
mod = 1_000_000_007
class Solution:
    def numberOfWays(self, n: int, x: int) -> int:
        f = [0] * (n + 1)
        f[0] = 1
        for i in range(1, n + 1):
            p = pow(i, x)
            if p > n:
                break
            for j in range(n - p, -1, -1):
                f[j + p] += f[j]
                if f[j + p] >= mod:
                    f[j + p] -= mod
        return f[-1]

力扣每日一题326-3的幂

日期：2025-08-13

题意

给定整数 n 判断其是否为 3 的幂次。

思路

简单问题简单做，这题数据范围是 int 那最多不会超过 20 次运算，直接暴力就好。

当然也有更加快的方法，首先可以预处理然后判断一下是否在集合中。

最快的做法则是使用数据范围内最大的 3 的幂次，若 n 可以整除该数则 n 为 3 的幂次。

实现

class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n < 1) return false;
        while (n > 1) {
            if (n % 3) return false;
            n /= 3;
        }
        return true;
    }
};
class Solution:
    def isPowerOfThree(self, n: int) -> bool:
        if n < 1:
            return False
        while n > 1:
            if n % 3 != 0:
                return False
            n /= 3
        return True

力扣每日一题1780-判断一个数字是否可以表示成三的幂的和

日期：2025-08-14

题意

给定正整数 n ，判断 n 是否可以表示成若干不同的三的幂次和。

思路

三的幂次和，那和二的幂次和没什么本质区别的，表示方式都是唯一的，可以从数据范围内最大的三次幂开始，若 n 大于等于该数则减去该数，判断 n 最终是否为 0 即可.

也可以将 n 转换为 3 进制，判断每一位是否均为 0 或 1

实现

class Solution {
public:
    bool checkPowersOfThree(int n) {
        for (int i = 4782969; i; i /= 3) {
            if (n >= i) n -= i;
        }
        return n == 0;
    }
};
class Solution:
    def checkPowersOfThree(self, n: int) -> bool:
        while n > 1:
          if n % 3 == 2:
            return False
          n //= 3
        return True

力扣每日一题342-4的幂

日期：2025-08-15

题意

给定整数 n 判断其是否为 4 的幂次

思路

简单问题简单做就好。

当然也有更加快的，首先 4 的幂次，肯定也是 2 的幂次 嘛；那前几天我们就有做过判断是否为 2 的幂次的题。

但显然还是不够判断的，我们转成二进制视角，还可以发现 4 的幂次是在第 0 2 4 6... 等位上有 1 的（4 == 1 << 2），将其提取出来使用位掩码 0x55555555 即可。

实现

class Solution {
public:
    bool isPowerOfFour(int n) {
        return n > 0 && (n & -n) == n && (n & 0x55555555);
    }
};
class Solution:
    def isPowerOfFour(self, n: int) -> bool:
        return n > 0 and (n & -n) == n and (n & 0x55555555) > 0

力扣每日一题1323-6 和 9 组成的最大数字

日期：2025-08-16

题意

给定仅由 6 和 9 组成的正整数 num。可以将 num 中一个 6 变成 9 ，或将一个 9 变成 6 或不进行操作。求可以得到的最大数字。

思路

由于题目给定了是正整数，那可以直接贪心地找到第一个 6 将其变为 9 即可，若无 6 直接不操作。

实现

class Solution {
public:
    int maximum69Number (int num) {
        string n = to_string(num);
        for (int i = 0; i < n.size(); i++) {
            if (n[i] == '6') {
                n[i] = '9';
                break;
            }
        }
        return stoi(n);
    }
};
class Solution:
    def maximum69Number (self, num: int) -> int:
        s = str(num)
        for i in range(len(s)):
            if s[i] == '6':
                return int(s[ : i] + '9' + s[i + 1 : ])
        return num

力扣每日一题837-新21点

日期：2025-08-17

题意

给定正整数 n k maxPts。当爱丽丝分数小于 k 时就会不停抽卡，每次抽卡等概率得分 [1, maxPts] ，求爱丽丝最总分数不超过 n 的概率。

思路

求不超过 n 的概率，又分数小于 k 时会不停抽卡，那也就是求得分为 [k, n] 的概率。那就是一个比较经典的概率dp了，进行一个递推求概率即可。

实现

class Solution {
public:
    double new21Game(int n, int k, int maxPts) {
        if (maxPts <= n - k + 1 || k == 0) return 1.0;

        vector<double> f(n + 1);
        f[0] = 1.0;
        double pre = 1.0;
        for (int i = 1; i <= n; i++) {
            if (i > maxPts) pre -= f[i - maxPts - 1];
            f[i] = pre / maxPts;
            if (i < k) pre += f[i];
        }

        return accumulate(f.begin() + k, f.end(), 0.0);
    }
};
class Solution:
    def new21Game(self, n: int, k: int, maxPts: int) -> float:
        if n - k + 1 >= maxPts or k == 0:
            return 1
        
        f = [1] + [0] * n
        pre = 1
        for i in range(1, n + 1):
            if i > maxPts:
                pre -= f[i - maxPts - 1]
            f[i] = pre / maxPts
            if (i < k):
                pre += f[i]

        return sum(f[k :])

力扣每日一题679-24 点游戏

日期：2025-08-18

题意

给定长度为 4 的数组 cards, 可以将其上数字按任意顺序排列并在任意合法位置加上符号 + - * / ( ) ，判断是否可以通过得到的式子算出结果 24

思路

注意到数据量并不大，直接进行枚举模拟即可。

实在有点麻烦，这里我就不用python再写一遍了。

实现

class Solution {
static constexpr long double eps = 1e-9;
using ld = long double;
public:
    bool judgePoint24(vector<int>& cards) {
        auto dfs = [&](this auto&& self, vector<ld>& nums) -> bool {
            if (nums.size() == 1) return fabsl(nums[0] - 24.0) <= eps;
            for (int i = 0; i < nums.size(); i++) {
                for (int j = 0; j < nums.size(); j++) {
                    if (i == j) continue;
                    vector<ld> nxt;
                    for (int k = 0; k < nums.size(); k++) if (k != i && k != j) nxt.push_back(nums[k]);
                    for (char op : {'+', '-', '*', '/'}) {
                        if ((op == '+' || op == '*') && i > j) continue;
                        if (op == '+') nxt.push_back(nums[i] + nums[j]);
                        if (op == '-') nxt.push_back(nums[i] - nums[j]);
                        if (op == '*') nxt.push_back(nums[i] * nums[j]);
                        if (op == '/' && fabsl(nums[j]) > eps) nxt.push_back(nums[i] / nums[j]);
                        if (nxt.size() == nums.size() - 1 && self(nxt)) return true;
                        if (!nxt.empty()) nxt.pop_back();
                    }
                }
            }
            return false;
        };
        vector<ld> a(cards.begin(), cards.end());
        return dfs(a);
    }
};

力扣每日一题2348-全 0 子数组的数目

日期：2025-08-19

题意

给定数组 nums ，返回全部为 0 的子数组数目。

思路

比较简单的思路就是找到每个全为零的块，然后单个全零块可以分割为多少个子数组呢，若长度为 n 显然是有 n 个长度为 1 的子数组， n - 1 个长度为 2 的子数组.... 那显然应该是一个等差数列求和 个。

虽然都是 O(n) 的，但乘除的常数是比较大，这里还有一个比较经典的思路：对于一个全零的数组，在其末尾再添加一个 0 ，新添加的零可以贡献多少全零子数组呢，显然是原数组长度加一，根据此思路进行计算即可。

实现

cpp 与 等差

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

cpp

class Solution {
using ll = long long;
public:
    long long zeroFilledSubarray(vector<int>& nums) {
        ll ans = 0;
        int cur = 0;
        for (const auto& x : nums) {
            if (x) cur = 0;
            else ans += ++cur;
        }
        return ans;
    }
};

python

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        ans = 0
        cur = 0
        for x in nums:
            if x == 0:
                cur += 1
                ans += cur
            else:
                cur = 0
        return ans

力扣每日一题1277-统计全为1的正方形子矩阵

日期：2025-08-20

题意

给定 m * n 的 0/1 数组，返回其中由全 1 构成的正方形个数。

思路

那与昨天的思路其实是非常类似的，只是昨天是求全 0 的子数组个数，今天是求全 1 的正方形个数，也就是从 1 维变 2 维了而已。使用同样的思想：往已有全 1 正方形的右/下/右下再添加一个 1 可以贡献多少个新正方形呢，由于这里需要考虑三个方向的情况，故而不再简单的使用一个变量维护，而是新开一个二维数组做递推，或者直接在 matrix 上做。

实现

class Solution {
public:
    int countSquares(vector<vector<int>>& matrix) {
        const int n = matrix.size(), m = matrix.front().size();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (i && j && matrix[i][j]) {
                    matrix[i][j] += min({matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1]});
                }
                ans += matrix[i][j];
            }
        }
        return ans;
    }
};
class Solution:
    def countSquares(self, matrix: List[List[int]]) -> int:
        n = len(matrix)
        m = len(matrix[0])
        ans = 0
        for i in range(n):
            for j in range(m):
                if i and j and matrix[i][j]:
                    matrix[i][j] += min(matrix[i - 1][j - 1], matrix[i - 1][j], matrix[i][j - 1])
                ans += matrix[i][j]

        return ans

力扣每日一题1504-统计全1子矩形

日期：2025-08-21

题意

给定 m * n 的 0/1 矩阵，求其中全为 1 的子矩阵个数。

思路

好像很不好做啊，但是我们观察数据范围 1 <= m, n <= 150 那可以随便乱搞了。

仔细一想，是不是可以转换为我们曾经做过的题：有 n 个任意高度宽为 1 的柱子并排，求矩阵面积和。这里我们可以枚举柱子的底部，高度则为纵向上连续的 1 的个数，那就很好做了。

实现

class Solution {
public:
    int numSubmat(vector<vector<int>>& mat) {
        const int n = mat.size(), m = mat.front().size();
        vector<int> h(m);
        int ans = 0;
        for (int i = 0; i < n; i++) {
            vector<array<int, 3>> stk;
            for (int j = 0, left = -1; j < m; j++) {
                if (mat[i][j]) {
                    h[j]++;
                    while (!stk.empty() && stk.back()[0] >= h[j]) stk.pop_back();
                    if (stk.empty()) {
                        int t = (j - left) * h[j];
                        ans += t;
                        stk.push_back({h[j], j, t});
                    } else {
                        auto [high, l, t] = stk.back();
                        t += (j - l) * h[j];
                        ans += t;
                        stk.push_back({h[j], j, t});
                    }
                } else {
                    h[j] = 0;
                    stk.clear();
                    left = j;
                }
            }
        }
        return ans;
    }
};

力扣每日一题3195-包含所有1的最小矩形面积I

日期：2025-08-22

题意

给定 0/1 矩阵，求包含所有 1 的最小矩阵面积。

思路

需要包含所有的 1 那找到最上、最下、最左最右的 1 的位置并以其为答案的边即可。

实现

class Solution {
public:
    int minimumArea(vector<vector<int>>& grid) {
        const int n = grid.size(), m = grid.front().size();
        int hi, lo = -1, le = m, ri = -1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j]) {
                    hi = i;
                    if (lo == -1) lo = i;
                    le = min(le, j);
                    ri = max(ri, j);
                }
            }
        }
        return (hi - lo + 1) * (ri - le + 1);
    }
};
class Solution:
    def minimumArea(self, grid: List[List[int]]) -> int:
        lo = inf
        hi = -1
        le = inf
        ri = -1
        for i, row in enumerate(grid):
            for j, x in enumerate(row):
                if x:
                    lo = min(lo, i)
                    le = min(le, j)
                    hi = max(hi, i)
                    ri = max(ri, j)
        return (hi - lo + 1) * (ri - le + 1)

力扣每日一题3197-包含所有1的最小矩形面积II

日期：2025-08-23

题意

给定 0/1 矩阵，需找到 3 个不重叠且面积非零的矩形，将矩阵中所有 1 都包含在这三矩形中。求最小三矩形面积和。

思路

这里的数据范围是不大的 1 <= n, m <= 30 那直接进行枚举三个矩阵的边界然后使用昨天的贪心计算方法即可。这里可以注意到共有 6 种划分方法，但是其中 3 种可以通过旋转矩阵等价得来，因此可以稍稍偷懒一些。

实现

class Solution {
public:
    int minimumSum(vector<vector<int>>& grid) {
        auto cal = [&](int a, int b, int c, int d) -> int {
            int le = 100, lo = 100;
            int hi = 0, ri = 0;
            for (int i = a; i < b; i++)
                for (int j = c; j < d; j++)
                    if (grid[i][j]) {
                        le = min(le, j);
                        lo = min(lo, i);
                        hi = max(hi, i);
                        ri = max(ri, j);
                    }
                    
            return (hi - lo + 1) * (ri - le + 1);
        };
        auto rotate = [&]() -> void {
            const int n = grid.size(), m = grid.front().size();
            vector tmp(m, vector<int> (n));
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    tmp[j][n - i - 1] = grid[i][j];
                }
            }
            swap(tmp, grid);
        };

        int ans = 1e9;
        auto work = [&]() -> void {
            const int n = grid.size(), m = grid.front().size();
            if (n >= 3) {
                for (int i = 1; i < n; i++)
                    for (int j = i + 1; j < n; j++) {
                        int tmp = cal(0, i, 0, m);
                        tmp += cal(i, j, 0, m);
                        tmp += cal(j, n, 0, m);
                        ans = min(ans, tmp);
                    }
            }
            if (n >= 2 && m >= 2) {
                for (int i = 1; i < n; i++)
                    for (int j = 1; j < m; j++) {
                        int tmp = cal(0, i, 0, m);
                        tmp += cal(i, n, 0, j);
                        tmp += cal(i, n, j, m);
                        ans = min(ans, tmp);

                        tmp = cal(i, n, 0, m);
                        tmp += cal(0, i, 0, j);
                        tmp += cal(0, i, j, m);
                        ans = min(ans, tmp);
                    }
            }
        };

        work();
        rotate();
        work();
        return ans;
    }
};

力扣每日一题1493-删掉一个元素以后全为1的最长子数组

日期：2025-08-24

题意

给定 0/1 数组，需从中删除任意一个元素，求剩余元素中最长仅含 1 的子数组长度。

思路

可以考虑枚举删哪一个数，使用前后缀处理该数前后连续的 1 的个数即可（见cpp实现）。

也可以考虑使用滑动窗口，我们必须删除一个数，那显然窗口内最多同时可以有一个 0 ，维护一下窗口的左右范围以及区间内 0 的个数即可（见 python实现）。

实现

class Solution:
    def longestSubarray(self, nums: List[int]) -> int:
        l = cnt = ans = 0
        for r, x in enumerate(nums):
            if x == 0:
                cnt += 1
            while cnt > 1:
                if nums[l] == 0:
                    cnt -= 1
                l += 1
            ans = max(r - l, ans)
        return ans
class Solution {
public:
    int longestSubarray(vector<int>& nums) {
        const int n = nums.size();
        vector<int> pre(n + 1);
        for (int i = 0; i < n; i++) {
            if (nums[i]) pre[i + 1] = pre[i] + 1;
        }
        int ans = 0;
        for (int i = n - 1, suf = 0; i >= 0; i--) {
            ans = max(ans, pre[i] + suf);
            if (nums[i]) {
                suf++;
            } else {
                suf = 0;
            }
        }
        return ans;
    }
};

力扣每日一题498-对角线遍历

日期：2025-08-25

题意

给定矩阵，返回将矩阵按对角线遍历展开的结果。

思路

就是简单的模拟题，注意处理好边界即可。

实现

class Solution:
    def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
        n = len(mat)
        m = len(mat[0])
        ans = [0] * (m * n)
        tot = 0
        for i in range(0, n + m - 1):
            mn = max(i - m + 1, 0)
            mx = min(i, n - 1)
            if i & 1:
                for j in range(mn, mx + 1):
                    ans[tot] = mat[j][i - j]
                    tot += 1
            else:
                for j in range(mx, mn - 1, -1):
                    ans[tot] = mat[j][i - j]
                    tot += 1
        return ans
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
        const int n = mat.size(), m = mat.front().size();
        vector<int> ans(n * m);
        for (int i = 0, tot = 0; i < n + m - 1; i++) {
            int mn = max(i - m + 1, 0);
            int mx = min(i, n - 1);
            if (i & 1) {
                for (int j = mn; j <= mx; j++) ans[tot++] = mat[j][i - j];
            } else {
                for (int j = mx; j >= mn; j--) ans[tot++] = mat[j][i - j];
            }
        }
        return ans;
    }
};

力扣每日一题3000-对角线最长的矩形的面积

日期：2025-08-26

题意

给定一些矩形的长宽，求对角线最长的矩形的面积，若存在多个矩形对角线同长，返回对角线最长且面积最大的矩形面积。

思路

直接遍历矩阵进行计算比较即可，避免开方的耗时与精度问题直接使用对角线的平方进行比较就好。

实现

class Solution {
public:
    int areaOfMaxDiagonal(vector<vector<int>>& dimensions) {
        int mx = 0, mxspace = 0;
        for (const auto& vec : dimensions) {
            int x = vec[0], y = vec[1];
            int t = x * x + y * y;
            if (t > mx) {
                mx = t;
                mxspace = x * y;
            } else if (t == mx) {
                mxspace = max(mxspace, x * y);
            }
        }
        return mxspace;
    }
};
class Solution:
    def areaOfMaxDiagonal(self, dimensions: List[List[int]]) -> int:
        return max((x * x + y * y, x * y) for x, y in dimensions)[1]

力扣每日一题3459-最长V形对角线段的长度

日期：2025-08-27

题意

给定二维矩阵，对 V形对角线段 定义如下：

  • 线段必须从 1 开始，线段上数形如 1, 2, 0, 2, 0 ...
  • 沿某一对角线方向扩展，最多允许顺时针 90° 转变一次方向

求矩阵内最长 V行对角线段 长度。

思路

那没有什么特别的性质，数据范围也比较合适 1 <= n, m <= 500 ，那就直接 dfs 搜索即可。

实现

class Solution {
static constexpr array<int, 2> nxt[] = {
    {1, 1}, {1, -1}, {-1, -1}, {-1, 1}
};
public:
    int lenOfVDiagonal(vector<vector<int>>& grid) {
        const int n = grid.size(), m = grid.front().size();
        int ans = 0;
        vector mem(2, vector (4, vector (n, vector<int> (m))));
        auto dfs = [&](this auto&& self, int x, int y, int to, int k, bool turn) -> int {
            auto [tx, ty] = nxt[to];
            x += tx; y += ty;
            if (x < 0 || x >= n || y < 0 || y >= m || grid[x][y] != k) return 0;
            int& tmp = mem[turn][to][x][y];
            if (tmp) return tmp;
            tmp = self(x, y, to, k ^ 2, turn) + 1;
            if (turn) {
                tmp = max(tmp, self(x, y, (to + 1) % 4, k ^ 2, false) + 1);
            }
            return tmp;
        };
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 1) {
                    for (int k = 0; k < 4; k++) {
                        ans = max(ans, dfs(i, j, k, 2, true) + 1);
                    }
                }
            }
        }

        return ans;
    }
};

力扣每日一题3446-按对角线进行矩阵排序

日期：2025-08-28

题意

给定方形矩阵，将其左下部分的对角线按非增排序（含中线），将其右上部分的对角线按非减排序。

思路

好像也没什么特别的做法与性质，就是列出每条对角线的数字按照对应规则排序后再放回即可。

实现

class Solution {
public:
    vector<vector<int>> sortMatrix(vector<vector<int>>& grid) {
        const int n = grid.size();
        for (int i = 0; i < n; i++) {
            vector<int> tmp;
            for (int j = 0; i + j < n; j++) tmp.push_back(grid[i + j][j]);
            ranges::sort(tmp, greater());
            for (int j = 0; i + j < n; j++) grid[i + j][j] = tmp[j];
        }
        for (int i = 1; i < n; i++) {
            vector<int> tmp;
            for (int j = 0; i + j < n; j++) tmp.push_back(grid[j][i + j]);
            ranges::sort(tmp);
            for (int j = 0; i + j < n; j++) grid[j][i + j] = tmp[j];
        }
        return grid;
    }
};
class Solution:
    def sortMatrix(self, grid: List[List[int]]) -> List[List[int]]:
        n = len(grid)
        for i in range(n):
            tmp = [grid[i + j][j] for j in range(n - i)]
            tmp.sort(reverse=True)
            for j in range(n - i):
                grid[i + j][j] = tmp[j]
        for i in range(1, n):
            tmp = [grid[j][i + j] for j in range(n - i)]
            tmp.sort()
            for j in range(n - i):
                grid[j][i + j] = tmp[j]

        return grid

力扣每日一题3021-Alice和Bob玩鲜花游戏

日期：2025-08-29

题意

Alice 和 Bob 站在环形花环上回合游戏。Alice 和 Bob 之间顺时针有 x 朵花 逆时针有 y 朵花，每回合可任选一侧摘下一朵花，若某次行动后两者间一侧无花则该行动者胜利，Alice 先手。对于给定的数 n 和 m 有 1 <= x <= n 与 1 <= y <= m ，求有多少对 (x, y) 满足 Alice 必胜

思路

转换一下就是两堆牌轮流取一张，谁先取到某堆最后一张则胜利。那就是很经典的博弈问题了，我们先手玩一下：

  • 任意一堆为 0 ，那显然是该回合玩家失败（上一回合的玩家将某堆摸为0）
  • 两堆均为偶数，不论先手摸哪一堆，只要后手同样摸同一堆，局面就仍可保持为两堆偶直到某一堆为0，故而有先手必败
  • 一堆奇数一堆偶数，先手玩家只要选择偶数堆进行取牌，局面就会变为两堆偶即上一种情况也即为下一个玩家必败，故先手必胜
  • 两堆奇数，不论先手摸哪一堆，后手只要摸另一堆就会造成双偶数局面，故而有先手必败

综上，合法开局 (x, y) 中有且仅有 x 与 y 一奇一偶时满足 Alice 必胜，进行计算对应数量即可。

实现

class Solution {
using ll = long long;
public:
    long long flowerGame(int n, int m) {
        return 1ll * (n + 1 >> 1) * (m >> 1) + 1ll * (n >> 1) * (m + 1 >> 1);
    }
};
class Solution:
    def flowerGame(self, n: int, m: int) -> int:
        return (n + 1) // 2 * (m // 2) + n // 2 * ((m + 1) // 2)

力扣每日一题36-有效的数独

日期：2025-08-30

题意

给定一个已经填了部分的数独，判断所填部分是否合法。

思路

就是简单模拟一下判断是否每行每列每九宫格无重即可。

实现

class Solution {
static constexpr int N = 9;
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        array<int, 10> vis;
        for (int i = 0; i < N; i++) {
            vis.fill(0);
            for (int j = 0; j < N; j++) {
                if (board[i][j] == '.') continue;
                int& t = vis[board[i][j] - '0'];
                if (t) return false;
                t++;
            }
            vis.fill(0);
            for (int j = 0; j < N; j++) {
                if (board[j][i] == '.') continue;
                int& t = vis[board[j][i] - '0'];
                if (t) return false;
                t++;
            }
        }
        for (int i = 0; i < N; i += 3) {
            for (int j = 0; j < N; j += 3) {
                vis.fill(0);
                for (int x = 0; x < 3; x++)
                for (int y = 0; y < 3; y++)
                if (isdigit(board[i + x][j + y])) {
                    int& t = vis[board[i + x][j + y] - '0'];
                    if (t) return false;
                    t++;
                }
            }
        }
        return true;
    }
};

力扣每日一题37-解数独

日期：2025-08-31

题意

给定保证仅有单个解的数独，找到其的解。

思路

这确实没什么好的做法，直接 dfs 开搜即可。

实现

class Solution {
static constexpr int N = 9;
public:
    void solveSudoku(vector<vector<char>>& board) {
        bool row[N][N]= {};
        bool col[N][N]= {};
        bool t[3][3][N]= {};
        vector<array<int, 2>> spaces;

        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (board[i][j] == '.') spaces.push_back({i, j});
                else {
                    int x = board[i][j] - '1';
                    row[i][x] = col[j][x] = t[i / 3][j / 3][x] = true;
                }
            }
        }
        const int n = spaces.size();
        auto dfs = [&](this auto&& self, int loc) -> bool {
            if (loc == n) return true;
            auto [i, j] = spaces[loc];
            for (int x = 0; x < N; x++) {
                if (row[i][x] || col[j][x] || t[i / 3][j / 3][x]) continue;
                row[i][x] = col[j][x] = t[i / 3][j / 3][x] = true;
                board[i][j] = char('0' + x + 1);
                if (self(loc + 1)) return true;
                row[i][x] = col[j][x] = t[i / 3][j / 3][x] = false;
            }
            return false;
        };
        dfs(0);
    }
};
class Solution:
    def solveSudoku(self, board: List[List[str]]) -> None:
        N = 9
        row = [0] * (N * N)
        col = [0] * (N * N)
        t = [0] * (3 * 3 * N)
        spaces = []

        for i, tmp in enumerate(board):
            for j, x in enumerate(tmp):
                if x == '.':
                    spaces.append((i, j))
                else:
                    tmp = int(x) - 1
                    row[i * N + tmp] = 1
                    col[j * N + tmp] = 1
                    t[i // 3 * 3 * N + j // 3 * N + tmp] = 1

        n = len(spaces)
        def dfs(loc):
            if loc == n:
                return True

            i, j = spaces[loc]
            for x in range(N):
                if row[i * N + x] or col[j * N + x] or t[i // 3 * N * 3 + j // 3 * N + x]:
                    continue
                row[i * N + x] = col[j * N + x] = t[i // 3 * N * 3 + j // 3 * N + x] = 1
                board[i][j] = str(x + 1)
                if dfs(loc + 1):
                    return True
                row[i * N + x] = col[j * N + x] = t[i // 3 * N * 3 + j // 3 * N + x] = 0
            return False

        dfs(0)