大型网站 php,网站建设与管理考试题,wordpress显示icp备案号,三水网站建设公司Q1、判断操作后字符串中的数字是否相等
1、题目描述
给你一个由数字组成的字符串 s 。重复执行以下操作#xff0c;直到字符串恰好包含 两个 数字#xff1a;
从第一个数字开始#xff0c;对于 s 中的每一对连续数字#xff0c;计算这两个数字的和 模 10。用计算得到的新…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[i] 。
返回最大总和。
2、解题思路 元素选择 每一行的元素都有一个提取数量的限制limits[i] 表示从第 i 行最多可以选择的元素个数。所以我们需要从每一行中选择最有价值的元素即每一行的前 limits[i] 个最大元素。 构建候选数组 我们可以从每一行中选择前 limits[i] 个最大元素这样就得到一个候选元素数组 candidates。 最大化总和 在获取了所有候选元素之后我们将它们排序并从中选择前 k 个最大元素计算这些元素的总和。 步骤 对每一行按降序排序选取前 limits[i] 个元素。 将这些元素放入候选数组 candidates 中。 对候选数组排序选取其中前 k 个元素计算这些元素的总和。
3、代码实现
class Solution {
public:long long maxSum(vectorvectorint grid, vectorint limits, int k) {vectorint 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 100000; // 最大范围
arrayint, 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[i] [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, vectorvectorint 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;};vectorlong 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 的最高有效位vectorarrayint, 5 nxt(n 1); // 倍增数组, 5 可以改为 high_bit1ranges::fill(nxt[n], n); // 哨兵, 表示越界// 检查函数, 判断是否可以在边界上放置 k 个点, 且最小距离不小于 lowauto check [](int low) - bool {// 预处理倍增数组 nxtint 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) 空间来存储映射后的点以及倍增数组。
