第438场周赛：判断操作后字符串中的数字是否相等、提取至多 K 个元素的最大总和、判断操作后字符串中的数字是否相等 Ⅱ、正方形上的点之间的最大距离

Q1、判断操作后字符串中的数字是否相等

1、题目描述

给你一个由数字组成的字符串 s 。重复执行以下操作，直到字符串恰好包含 两个 数字：

• 从第一个数字开始，对于 s 中的每一对连续数字，计算这两个数字的和 模 10。
• 用计算得到的新数字依次替换 s 的每一个字符，并保持原本的顺序。

如果 s 最后剩下的两个数字 相同 ，返回 true 。否则，返回 false。

2、解题思路

1. 计算操作： 对于字符串中的每一对连续数字，计算它们的和 模 10。这个操作会将字符串长度从 n 缩短为 n-1，直到字符串长度减少到 2。

2. 终止条件： 每次操作之后，字符串的长度减少 1。当字符串长度达到 2 时，我们检查这两个数字是否相同。如果相同，返回 true，否则返回 false。

3. 循环处理： 我们可以使用一个循环来反复进行这些操作，直到字符串长度为 2。每次操作都将原来的字符串转换成新的字符串。

4. 代码实现： 采用一个循环来不断执行操作，直到字符串的长度变成 2。每次操作我们计算出新的字符串并继续进行下去，直到符合终止条件。

3、代码实现

class Solution {
public:
    bool hasSameDigits(string s) {
        // 当字符串的长度大于 2 时, 继续操作
        while (s.size() > 2) {
            string newS; // 用于存储新生成的字符串
            // 遍历字符串中的每一对连续数字
            for (int i = 0; i < s.size() - 1; ++i) {
                // 计算当前数字和下一个数字的和, 并对 10 取模
                newS.push_back(((s[i] - '0') + (s[i + 1] - '0')) % 10 + '0');
            }
            // 用新字符串替换原字符串
            s = newS;
        }
        // 判断最后剩下的两个数字是否相同
        return s.size() == 2 && s[0] == s[1];
    }
};

4、复杂度分析

1. 时间复杂度：
   每次操作将字符串的长度减少 1，直到长度为 2。假设字符串的初始长度是 n，那么我们最多进行 n - 2 次操作。每次操作需要遍历字符串的每一对连续数字，所以每次操作的时间复杂度为 O(n)。因此，总的时间复杂度为 O(n^2)。

2. 空间复杂度：
   每次操作都需要使用一个新的字符串 newS 来保存结果，因此空间复杂度为 O(n)。

Q2、提取至多 K 个元素的最大总和

1、题目描述

给你一个大小为 n x m 的二维矩阵 grid ，以及一个长度为 n 的整数数组 limits ，和一个整数 k 。你的目标是从矩阵 grid 中提取出 至多 k 个元素，并计算这些元素的最大总和，提取时需满足以下限制**：**

• 从 grid 的第 i 行提取的元素数量不超过 limits[i] 。

返回最大总和。

2、解题思路

1. 元素选择： 每一行的元素都有一个提取数量的限制，limits[i] 表示从第 i 行最多可以选择的元素个数。所以，我们需要从每一行中选择最有价值的元素，即每一行的前 limits[i] 个最大元素。

2. 构建候选数组： 我们可以从每一行中选择前 limits[i] 个最大元素，这样就得到一个候选元素数组 candidates。

3. 最大化总和： 在获取了所有候选元素之后，我们将它们排序，并从中选择前 k 个最大元素，计算这些元素的总和。

4. 步骤：

   • 对每一行，按降序排序，选取前 limits[i] 个元素。

   • 将这些元素放入候选数组 candidates 中。

   • 对候选数组排序，选取其中前 k 个元素，计算这些元素的总和。

3、代码实现

class Solution {
public:
    long long maxSum(vector<vector<int>>& grid, vector<int>& limits, int k) {
        vector<int> candidates; // 存储所有候选元素

        // 按行处理
        for (int i = 0; i < grid.size(); ++i) {
            // 将当前行的元素按从大到小排序
            sort(grid[i].rbegin(), grid[i].rend());
            // 从该行中选择前 limits[i] 个最大的元素
            for (int j = 0; j < limits[i] && j < grid[i].size(); ++j) {
                candidates.push_back(grid[i][j]);
            }
        }

        // 将所有候选元素按从大到小排序
        sort(candidates.rbegin(), candidates.rend());
        long long sum = 0; // 记录最大总和
        // 选择前 k 个最大的元素
        for (int i = 0; i < k && i < candidates.size(); ++i) {
            sum += candidates[i];
        }

        return sum; // 返回最大总和
    }
};

4、复杂度分析

1. 时间复杂度：

   • 对于每一行，我们需要对 m 个元素进行排序，因此每一行的时间复杂度是 O(m log m)。

   • 在最坏情况下，我们需要对 n 行进行排序，总的时间复杂度是 O(n * m log m)。

   • 排序候选数组 candidates 的时间复杂度是 O((n * m) log (n * m))。

   • 总的时间复杂度是 O(n * m log m + (n * m) log (n * m))。

2. 空间复杂度：

   • 存储候选元素的数组 candidates 的大小为 O(n * m)。

   • 因此，空间复杂度是 O(n * m)。

Q3、判断操作后字符串中的数字是否相等 Ⅱ

1、题目描述

给你一个由数字组成的字符串 s 。重复执行以下操作，直到字符串恰好包含 两个 数字：

• 从第一个数字开始，对于 s 中的每一对连续数字，计算这两个数字的和 模 10。
• 用计算得到的新数字依次替换 s 的每一个字符，并保持原本的顺序。

如果 s 最后剩下的两个数字相同，则返回 true 。否则，返回 false。

2、解题思路

1. 直观理解

   1. 每一步的操作涉及将字符串中的每对连续数字的和模 10，然后替换原有的数字。这种操作显然会让字符串逐步变短，每次都减少一个字符，直到字符串最终只剩下两个数字。

   2. 需要判断的是最终剩下的两个数字是否相同。

2. 深入分析

   这个问题的关键在于如何高效地进行操作，特别是在处理大规模字符串时，逐步计算每对连续数字的和模 10 可能会导致时间复杂度过高。为此，我们可以通过一种数学方法来解决这个问题。

   1. 组合数学： 每次操作其实可以看作是计算当前字符串中的每对数字的影响。为了避免重复计算，我们可以通过数学公式来快速计算每一步的总和，从而推导出最终的结果。

   2. 欧拉定理与预处理： 为了加速计算，我们可以利用组合数和一些数学优化技巧来快速计算。

3. 预处理

   我们通过以下步骤来预处理数据：

   1. 阶乘与逆阶乘：为计算组合数快速求解阶乘和逆阶乘。

   2. 2 和 5 的幂次：由于计算过程中会涉及到取模操作，预处理2和5的幂次有助于我们在计算时直接得到需要的结果。

通过这些预处理操作，我们可以在计算过程中避免重复运算，从而提高效率。

3、代码实现

constexpr int MOD = 10;              // 模数
constexpr int MX = 100'000;          // 最大范围
array<int, MX + 1> f, inv_f, p2, p5; // 预处理的数组

// 快速幂函数, 计算 x 的 n 次方模 MOD
int qpow(int x, int n) {
    int res = 1;
    while (n > 0) {
        if (n % 2 > 0) {
            res = res * x % MOD;
        }
        x = x * x % MOD;
        n /= 2;
    }
    return res;
}

// 预处理函数, 计算阶乘、逆阶乘、2 的幂次和 5 的幂次
void preprocess() {
    f[0] = 1;
    for (int i = 1; i <= MX; i++) {
        int x = i;
        // 计算 2 的幂次
        int e2 = countr_zero((unsigned)x);
        x >>= e2;
        // 计算 5 的幂次
        int e5 = 0;
        while (x % 5 == 0) {
            e5++;
            x /= 5;
        }
        f[i] = f[i - 1] * x % MOD;
        p2[i] = p2[i - 1] + e2;
        p5[i] = p5[i - 1] + e5;
    }

    // 欧拉定理求逆元
    inv_f[MX] = qpow(f[MX], 3);
    for (int i = MX; i > 0; i--) {
        int x = i;
        x >>= countr_zero((unsigned)x);
        while (x % 5 == 0) {
            x /= 5;
        }
        inv_f[i - 1] = inv_f[i] * x % MOD;
    }
}

// 组合数计算函数
int comb(int n, int k) {
    // 由于每项都 < 10，所以无需中途取模
    return f[n] * inv_f[k] * inv_f[n - k] * qpow(2, p2[n] - p2[k] - p2[n - k]) * qpow(5, p5[n] - p5[k] - p5[n - k]) % MOD;
}

class Solution {
public:
    bool hasSameDigits(string s) {
        static int initialized = (preprocess(), 0); // 确保预处理只执行一次
        int diff = 0;
        // 计算最终两个数字的差值
        for (int i = 0; i + 1 < s.size(); i++) {
            diff += comb(s.size() - 2, i) * (s[i] - s[i + 1]);
        }
        // 如果差值为 0, 则最终两个数字相同
        return diff % MOD == 0;
    }
};

4、复杂度分析

1. 时间复杂度：

   • 预处理部分的时间复杂度是 O(MX)，因为我们需要计算阶乘、逆阶乘以及 2 和 5 的幂次。

   • 主逻辑部分遍历字符串 s 中的每一对连续数字，进行组合数计算，因此时间复杂度为 O(n)，其中 n 是字符串的长度。

2. 空间复杂度：

   • 我们使用了大小为 MX + 1 的数组存储阶乘、逆阶乘和幂次，因此空间复杂度为 O(MX)。

Q4、正方形上的点之间的最大距离

1、题目描述

给你一个整数 side，表示一个正方形的边长，正方形的四个角分别位于笛卡尔平面的 (0, 0) ，(0, side) ，(side, 0) 和 (side, side) 处。

同时给你一个 正整数 k 和一个二维整数数组 points，其中 points[i] = [xi, yi] 表示一个点在正方形边界上的坐标。

你需要从 points 中选择 k 个元素，使得任意两个点之间的 最小 曼哈顿距离 最大化 。

返回选定的 k 个点之间的 最小 曼哈顿距离的 最大 可能值。

两个点 (xi, yi) 和 (xj, yj) 之间的曼哈顿距离为 |xi - xj| + |yi - yj|。

2、解题思路

1. 问题转化：

   • 在正方形的边界上，曼哈顿距离是一个较为常见的计算问题。

   • 给定点在边界上，可以通过对点的位置进行 映射，将其转化为一维空间的问题。

   • 通过对这些一维映射后的点进行排序，问题转化为：在一维上选择 k 个点，使得它们之间的最小距离最大化。

2. 一维化点的坐标：

   • 我们将正方形的每个边界映射到一维坐标，按照一定的规则进行编码，确保每个点可以用一个唯一的数字来表示。

   • 对于正方形的每一边，点的位置可以根据其边的特性进行映射：

     • 左边界（x = 0）：坐标 y 映射为 y。
     • 上边界（y = side）：坐标 x 映射为 side + x。
     • 右边界（x = side）：坐标 y 映射为 side * 3 - y。
     • 下边界（y = 0）：坐标 x 映射为 side * 4 - x。

3. 排序：

   • 通过对所有点进行一维化并排序，问题变得更容易处理。

4. 二分搜索与倍增优化：

   • 我们使用二分搜索来确定最小距离的最大值。

   • 对于每个候选的最小距离，使用倍增技术（类似于跳表的思想）来判断是否能够从已排序的点集中选择出 k 个点，保证任意两点之间的距离至少为该最小距离。

3、代码实现

class Solution {
public:
    int maxDistance(int side, vector<vector<int>>& points, int k) {
        // 将边界上的点映射到一维空间
        auto mapPoint = [side](int x, int y) -> long long {
            // 左边界
            if (x == 0) {
                return y;
            }
            // 上边界
            if (y == side) {
                return side + x;
            }
            // 右边界
            if (x == side) {
                return side * 3LL - y;
            }
            // 下边界
            return side * 4LL - x;
        };

        vector<long long> a;
        for (auto& p : points) {
            a.push_back(mapPoint(p[0], p[1]));
        }
        ranges::sort(a); // 将映射后的点排序

        int n = a.size();
        k--; // 往后跳 k-1 步, 这里先减一, 方便计算
        int high_bit = bit_width((unsigned)k) - 1; // 计算 k 的最高有效位
        vector<array<int, 5>> nxt(n + 1); // 倍增数组, 5 可以改为 high_bit+1
        ranges::fill(nxt[n], n);          // 哨兵, 表示越界

        // 检查函数, 判断是否可以在边界上放置 k 个点, 且最小距离不小于 low
        auto check = [&](int low) -> bool {
            // 预处理倍增数组 nxt
            int j = n;
            // 转移来源在右边, 要倒序计算
            for (int i = n - 1; i >= 0; i--) {
                while (j && a[j - 1] >= a[i] + low) {
                    j--;
                }
                nxt[i][0] = j;
                for (int k = 1; k <= high_bit; k++) {
                    nxt[i][k] = nxt[nxt[i][k - 1]][k - 1];
                }
            }

            // 枚举起点
            for (int i = 0; i < n; i++) {
                int cur = i;
                // 往后跳 k-1 步 (注意上面把 k 减一了)
                for (int j = high_bit; j >= 0; j--) {
                    if (k >> j & 1) {
                        cur = nxt[cur][j];
                    }
                }
                // 出界
                if (cur == n) {
                    break;
                }
                if (a[cur] - a[i] <= side * 4LL - low) {
                    return true;
                }
            }
            return false;
        };

        // 二分搜索最大最小距离
        int left = 1, right = side + 1;
        while (left + 1 < right) {
            int mid = left + (right - left) / 2;
            (check(mid) ? left : right) = mid;
        }
        return left;
    }
};

4、复杂度分析

时间复杂度：

• 排序：对 n 个点进行排序的时间复杂度是 O(n log n)。
• 二分搜索：在二分搜索过程中，每次检查需要 O(n) 的时间，最多进行 log(side) 次二分查找。因此，总的时间复杂度为 O(n log n + n log side)。

空间复杂度：

• 需要额外的 O(n) 空间来存储映射后的点以及倍增数组。