第438场周赛：判断利用后字符串中的数字是否相等、提取至多 K 个元素的最大 ...

天津储鑫盛钢材现货供应商 · 3 天前

Q1、判断利用后字符串中的数字是否相等

1、题目描述

给你一个由数字构成的字符串 s 。重复实行以下利用，直到字符串恰恰包含两个数字：

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

假如 s 最后剩下的两个数字相同，返回 true 。否则，返回 false。
2、解题思路

计算利用：对于字符串中的每一对连续数字，计算它们的和模 10。这个利用会将字符串长度从 n 缩短为 n-1，直到字符串长度减少到 2。
终止条件：每次利用之后，字符串的长度减少 1。当字符串长度达到 2 时，我们检查这两个数字是否相同。假如相同，返回 true，否则返回 false。
循环处理惩罚：我们可以使用一个循环来反复进行这些利用，直到字符串长度为 2。每次利用都将原来的字符串转换成新的字符串。
代码实现：接纳一个循环来不停实行利用，直到字符串的长度变成 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，直到长度为 2。假设字符串的初始长度是 n，那么我们最多进行 n - 2 次利用。每次利用需要遍历字符串的每一对连续数字，所以每次利用的时间复杂度为 O(n)。因此，总的时间复杂度为 O(n^2)。
空间复杂度：
每次利用都需要使用一个新的字符串 newS 来生存结果，因此空间复杂度为 O(n)。

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

1、题目描述

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

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

返回最大总和。
2、解题思路

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

构建候选数组：我们可以从每一行中选择前 limits 个最大元素，如许就得到一个候选元素数组 candidates。

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

步骤：

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

将这些元素放入候选数组 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、复杂度分析

时间复杂度：

对于每一行，我们需要对 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))。

空间复杂度：

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

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

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

1、题目描述

给你一个由数字构成的字符串 s 。重复实行以下利用，直到字符串恰恰包含两个数字：

从第一个数字开始，对于 s 中的每一对连续数字，计算这两个数字的和模 10。

用计算得到的新数字依次更换 s 的每一个字符，并保持原本的顺序。

假如 s 最后剩下的两个数字相同，则返回 true 。否则，返回 false。
2、解题思路

直观明白

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

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

深入分析
这个问题的关键在于怎样高效地进行利用，特别是在处理惩罚大规模字符串时，逐步计算每对连续数字的和模 10 大概会导致时间复杂度过高。为此，我们可以通过一种数学方法来办理这个问题。

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

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

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

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

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、复杂度分析

时间复杂度：

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

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

空间复杂度：

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

Q4、正方形上的点之间的最大隔断

1、题目描述

给你一个整数 side，表示一个正方形的边长，正方形的四个角分别位于笛卡尔平面的 (0, 0) ，(0, side) ，(side, 0) 和 (side, side) 处。
同时给你一个 正整数 k 和一个二维整数数组 points，此中 points = [xi, yi] 表示一个点在正方形边界上的坐标。
你需要从 points 中选择 k 个元素，使得任意两个点之间的最小曼哈顿隔断 最大化 。
返回选定的 k 个点之间的最小曼哈顿隔断的最大大概值。
两个点 (xi, yi) 和 (xj, yj) 之间的曼哈顿隔断为 |xi - xj| + |yi - yj|。
2、解题思路

问题转化：

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

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

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

一维化点的坐标：

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

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

左边界（x = 0）：坐标 y 映射为 y。

上边界（y = side）：坐标 x 映射为 side + x。

右边界（x = side）：坐标 y 映射为 side * 3 - y。

下边界（y = 0）：坐标 x 映射为 side * 4 - x。

排序：

通过对全部点进行一维化并排序，问题变得更容易处理惩罚。

二分搜索与倍增优化：

我们使用二分搜索来确定最小隔断的最大值。

对于每个候选的最小隔断，使用倍增技术（雷同于跳表的思想）来判断是否可以大概从已排序的点会合选择出 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) 空间来存储映射后的点以及倍增数组。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

第438场周赛：判断利用后字符串中的数字是否相等、提取至多 K 个元素的最大 ...

本帖子中包含更多资源

0 个回复

快速回复

楼主热帖

标签云