第438场周赛：判断利用后字符串中的数字是否相等、提取至多 K 个元素的最大
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 - '0') + (s - '0')) % 10 + '0');
}
// 用新字符串替换原字符串
s = newS;
}
// 判断最后剩下的两个数字是否相同
return s.size() == 2 && s == s;
}
};
https://i-blog.csdnimg.cn/direct/788aa4073e8540359ff85d5c679407bc.png
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.rbegin(), grid.rend());
// 从该行中选择前 limits 个最大的元素
for (int j = 0; j < limits && j < grid.size(); ++j) {
candidates.push_back(grid);
}
}
// 将所有候选元素按从大到小排序
sort(candidates.rbegin(), candidates.rend());
long long sum = 0; // 记录最大总和
// 选择前 k 个最大的元素
for (int i = 0; i < k && i < candidates.size(); ++i) {
sum += candidates;
}
return sum; // 返回最大总和
}
};
https://i-blog.csdnimg.cn/direct/3f4de492be2b48e1b1edbb2bfede0ce8.png
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 = 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 = f * x % MOD;
p2 = p2 + e2;
p5 = p5 + e5;
}
// 欧拉定理求逆元
inv_f = qpow(f, 3);
for (int i = MX; i > 0; i--) {
int x = i;
x >>= countr_zero((unsigned)x);
while (x % 5 == 0) {
x /= 5;
}
inv_f = inv_f * x % MOD;
}
}
// 组合数计算函数
int comb(int n, int k) {
// 由于每项都 < 10，所以无需中途取模
return f * inv_f * inv_f * qpow(2, p2 - p2 - p2) * qpow(5, p5 - p5 - p5) % 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 - s);
}
// 如果差值为 0, 则最终两个数字相同
return diff % MOD == 0;
}
};
https://i-blog.csdnimg.cn/direct/466ad07adfc84e41b4e9b3ec1f767a09.png
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 = 表示一个点在正方形边界上的坐标。
你需要从 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 = (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, p));
}
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); // 哨兵, 表示越界
// 检查函数, 判断是否可以在边界上放置 k 个点, 且最小距离不小于 low
auto check = [&](int low) -> bool {
// 预处理倍增数组 nxt
int j = n;
// 转移来源在右边, 要倒序计算
for (int i = n - 1; i >= 0; i--) {
while (j && a >= a + low) {
j--;
}
nxt = j;
for (int k = 1; k <= high_bit; k++) {
nxt = nxt];
}
}
// 枚举起点
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;
}
}
// 出界
if (cur == n) {
break;
}
if (a - a <= 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;
}
};
https://i-blog.csdnimg.cn/direct/c37328c3b45c4e97b95ab94973154ba2.png
4、复杂度分析
时间复杂度：
[*]排序：对 n 个点进行排序的时间复杂度是 O(n log n)。
[*]二分搜索：在二分搜索过程中，每次检查需要 O(n) 的时间，最多进行 log(side) 次二分查找。因此，总的时间复杂度为 O(n log n + n log side)。
空间复杂度：
[*]需要额外的 O(n) 空间来存储映射后的点以及倍增数组。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]