化妆品营销型网站,北京医疗网站建设公司排名,义乌 外贸网站 开发,店面设计报价Q1、跳过交替单元格的之字形遍历
1、题目描述
给你一个 m x n 的二维数组 grid#xff0c;数组由 正整数 组成。
你的任务是以 之字形 遍历 grid#xff0c;同时跳过每个 交替 的单元格。
之字形遍历的定义如下#xff1a;
从左上角的单元格 (0, 0) 开始。在当前行中向…Q1、跳过交替单元格的之字形遍历
1、题目描述
给你一个 m x n 的二维数组 grid数组由 正整数 组成。
你的任务是以 之字形 遍历 grid同时跳过每个 交替 的单元格。
之字形遍历的定义如下
从左上角的单元格 (0, 0) 开始。在当前行中向 右 移动直到到达该行的末尾。下移到下一行然后在该行中向 左 移动直到到达该行的开头。继续在行间交替向右和向左移动直到所有行都被遍历完。
**注意**在遍历过程中必须跳过每个 交替 的单元格。
返回一个整数数组 result其中包含按 顺序 记录的、且跳过交替单元格后的之字形遍历中访问到的单元格值。
2、解题思路 方向交替 遍历过程中偶数行从左到右奇数行从右到左。可以使用 reverse 方法在遍历奇数行时反转数组。 跳过单元格 通过布尔变量 flag 来控制是否访问当前单元格。 每访问一个单元格后将 flag 取反跳过下一个单元格。 结果记录 将每次访问到的单元格值存入结果数组 ret 中。
3、代码实现
class Solution {
public:vectorint zigzagTraversal(vectorvectorint grid) {vectorint ret; // 存储最终结果数组bool flag true; // 标记是否访问当前单元格, 初始为访问// 遍历每一行for (int i 0; i grid.size(); i) {// 当前行的引用, 便于操作auto row grid[i];// 奇数行需要反转以实现从右到左的遍历if (i % 2 1) {ranges::reverse(row); // 使用 C20 的 ranges::reverse 反转行}// 遍历当前行的所有元素for (int x : row) {// 如果标记为 true, 则访问当前单元格if (flag) {// 将当前单元格值加入结果数组ret.push_back(x);}// 取反标记, 跳过下一个单元格flag !flag;}}return ret; // 返回最终结果}
};4、复杂度分析
时间复杂度分析
行遍历 外层 for 循环遍历所有 m 行。 行内遍历 每行遍历 n 个元素共访问 m × n m\times n m×n 个单元格。奇数行反转操作的复杂度为 O(n)。
总时间复杂度 O ( m × n ) O(m \times n) O(m×n)
空间复杂度分析
额外空间 结果数组 ret 存储跳过单元格后的值大小最多为 ⌈ m × n / 2 ⌉ \lceil m \times n / 2 \rceil ⌈m×n/2⌉。反转操作在原地完成不需要额外空间。
总空间复杂度 O ( m × n ) O(m \times n) O(m×n)存储结果数组的空间 Q2、机器人可以获得的最大金币数
1、题目描述
给你一个 m x n 的网格。一个机器人从网格的左上角 (0, 0) 出发目标是到达网格的右下角 (m - 1, n - 1)。在任意时刻机器人只能向右或向下移动。
网格中的每个单元格包含一个值 coins[i][j]
如果 coins[i][j] 0机器人可以获得该单元格的金币。如果 coins[i][j] 0机器人会遇到一个强盗强盗会抢走该单元格数值的 绝对值 的金币。
机器人有一项特殊能力可以在行程中 最多感化 2个单元格的强盗从而防止这些单元格的金币被抢走。
**注意**机器人的总金币数可以是负数。
返回机器人在路径上可以获得的 最大金币数 。
2、解题思路
我们可以使用动态规划 (Dynamic Programming, DP) 来解决问题。采用一个三维 dp 数组其中 dp[i][j][k] 表示机器人到达网格单元 (i, j) 时感化了 k 个强盗后能够获得的最大金币数。
动态规划转移方程 定义状态 dp[i][j][k]到达单元 (i, j)感化了 k 个强盗后的最大金币数。k 的范围为 [0, 2]表示机器人最多能感化 2 个强盗。 状态转移 假设当前单元格的金币值为 coins[i][j] 如果从 上方 (i-1, j) 转移到 (i, j) 如果不感化强盗dp[i][j][k] max(dp[i][j][k], dp[i-1][j][k] coins[i][j])。如果感化强盗即 coins[i][j] 0 且剩余感化次数 k 0dp[i][j][k] max(dp[i][j][k], dp[i-1][j][k-1])。 如果从 左侧 (i, j-1) 转移到 (i, j) 与从上方的情况类似。 初始条件 对于起点 (0, 0) 如果 coins[0][0] 0金币数为 coins[0][0]。如果 coins[0][0] 0 且感化强盗次数 k 0金币数为 0感化该强盗。 最终结果 机器人到达右下角 (m-1, n-1) 时可能感化了 0、1 或 2 个强盗。最终答案为 max(dp[m-1][n-1][0], dp[m-1][n-1][1], dp[m-1][n-1][2])3、代码实现
class Solution {
public:int maximumAmount(vectorvectorint coins) {int m coins.size(); // 网格的行数int n coins[0].size(); // 网格的列数// 定义 DP 数组: dp[i][j][k] 表示到达 (i, j) 感化了 k 个强盗后的最大金币数vectorvectorvectorint dp(m, vectorvectorint(n, vectorint(3, INT_MIN)));// 初始化起点for (int k 0; k 2; k) {dp[0][0][k] (coins[0][0] 0 k 0) ? 0 : coins[0][0];}// 动态规划填表for (int i 0; i m; i) {for (int j 0; j n; j) {// 遍历感化强盗的次数 kfor (int k 0; k 2; k) {// 跳过起点if (i 0 j 0) {continue;}int coinValue coins[i][j]; // 当前单元格的金币值// 从上方到达当前单元格 (i, j)if (i 0) {if (coinValue 0) {// 当前单元格是正值, 直接加金币dp[i][j][k] max(dp[i][j][k], dp[i - 1][j][k] coinValue);} else {// 当前单元格是负值, 分两种情况讨论dp[i][j][k] max(dp[i][j][k], dp[i - 1][j][k] coinValue); // 不感化强盗if (k 0) {dp[i][j][k] max(dp[i][j][k], dp[i - 1][j][k - 1]); // 感化强盗}}}// 从左侧到达当前单元格 (i, j)if (j 0) {if (coinValue 0) {dp[i][j][k] max(dp[i][j][k], dp[i][j - 1][k] coinValue);} else {dp[i][j][k] max(dp[i][j][k], dp[i][j - 1][k] coinValue);if (k 0) {dp[i][j][k] max(dp[i][j][k], dp[i][j - 1][k - 1]);}}}}}}// 返回到达右下角时感化最多 2 个强盗的最大金币数return max({dp[m - 1][n - 1][0], dp[m - 1][n - 1][1], dp[m - 1][n - 1][2]});}
};4、复杂度分析
时间复杂度
三重循环外层遍历网格的每个单元格两层内循环遍历感化次数 k总复杂度为 O ( m × n × 3 ) O ( m × n ) O(m \times n \times 3) O(m \times n) O(m×n×3)O(m×n)。
空间复杂度
使用了一个三维数组 dp大小为 O ( m × n × 3 ) O(m \times n \times 3) O(m×n×3)。 Q3、图的最大边权的最小值
1、题目描述
给你两个整数 n 和 threshold 同时给你一个 n 个节点的 有向 带权图节点编号为 0 到 n - 1 。这个图用 二维 整数数组 edges 表示其中 edges[i] [Ai, Bi, Wi] 表示节点 Ai 到节点 Bi 之间有一条边权为 Wi的有向边。
你需要从这个图中删除一些边也可能 不 删除任何边使得这个图满足以下条件
所有其他节点都可以到达节点 0 。图中剩余边的 最大 边权值尽可能小。每个节点都 至多 有 threshold 条出去的边。
请你返回删除必要的边后最大 边权的 最小值 为多少。如果无法满足所有的条件请你返回 -1
2、解题思路
本题本质上是一个 图的最短路径问题但有多个限制条件。我们可以通过以下步骤来思考并解决问题 反向图构建 我们需要从每个节点到达节点 0所以我们构建图的 反向图。反向图中原本从 Ai 到 Bi 的边变为从 Bi 到 Ai 的边。这样我们只需要考虑从节点 0 到其他节点的路径即可。 最大边权最小化 为了确保所有的节点都能到达节点 0且最大边权最小我们需要使用 最短路径算法。这里的最短路径的定义是我们要求路径中的 最大边权最小这和普通的最短路径问题有些不同。 我们可以使用 Dijkstra 算法 来解决这个问题。Dijkstra 算法通常用于找到从起点到所有其他节点的最短路径而在这个问题中我们可以将路径的 “最短” 定义为 “最大边权最小”。 满足 threshold 条件 限制每个节点至多有 threshold 条出去的边意味着我们需要在考虑边的同时保持每个节点的出度不超过 threshold。这个限制可以通过构建图时进行检查。 最终返回 经过 Dijkstra 算法我们能够找到从节点 0 到其他所有节点的最大边权。如果所有节点都能到达节点 0则返回最大边权中的最小值如果有节点无法到达节点 0则返回 -1。
3、代码实现
class Solution {
public:int minMaxWeight(int n, vectorvectorint edges, int threshold) {// 如果边小于 n-1, 直接返回 -1 (无法构成连通图)if (edges.size() n - 1) {return -1;}// 构建反向图vectorvectorpairint, int g(n);// g[y] 包含 (x, w), 表示 x - y 的边权为 wfor (const auto edge : edges) {int x edge[0], y edge[1], w edge[2];g[y].emplace_back(x, w);}// 初始化距离数组, 初始时所有节点的距离为正无穷const int INF numeric_limitsint::max();vectorint dis(n, INF);dis[0] 0; // 起点到自身的最大边权为 0// 最小堆, 存储 (最大边权, 节点编号)priority_queuepairint, int, vectorpairint, int, greater pq;pq.emplace(0, 0); // 起点while (!pq.empty()) {auto [d, x] pq.top();pq.pop();// 如果当前距离大于记录的最小距离, 跳过if (d dis[x]) {continue;}// 遍历当前节点的所有入边for (const auto [y, w] : g[x]) {int new_d max(d, w); // 更新最大边权// 如果找到更优的路径if (new_d dis[y]) {dis[y] new_d;pq.emplace(new_d, y);}}}// 找到所有节点到达 0 的最大边权值int ret *max_element(dis.begin(), dis.end());return ret INF ? -1 : ret; // 如果节点无法到达, 返回 -1, 否则返回答案}
};4、复杂度分析
时间复杂度
图的构建O(E)其中 E 是边的数量。Dijkstra 算法O((E V) log V)其中 E 是边数V 是节点数。使用优先队列实现 Dijkstra时间复杂度为 O((E V) log V)。
因此整体时间复杂度为 O((E V) log V)。
空间复杂度
使用了 O(V E) 的空间来存储图和优先队列。 Q4、统计 K 次操作以内得到非递减子数组的数目
1、题目描述
给你一个长度为 n 的数组 nums 和一个整数 k 。
对于 nums 中的每一个子数组你可以对它进行 至多 k 次操作。每次操作中你可以将子数组中的任意一个元素增加 1 。
注意 每个子数组都是独立的也就是说你对一个子数组的修改不会保留到另一个子数组中。
请你返回最多 k 次操作以内有多少个子数组可以变成 非递减 的。
如果一个数组中的每一个元素都大于等于前一个元素如果前一个元素存在那么我们称这个数组是 非递减 的。
2、解题思路
我们需要通过合理的算法找到最多 k 次操作可以使得多少个子数组变为非递减的。对于每一个子数组考虑以下步骤
单调队列 我们可以通过滑动窗口和单调队列来优化子数组的判断过程。在滑动窗口中每次考虑将窗口的某一段变成非递减的子数组。 修正次数计算 对于每个子数组我们计算需要多少次操作使得它变为非递减。具体来说如果 nums[i] nums[i1]我们需要进行 nums[i] - nums[i1] 次操作才能使得 nums[i] 小于或等于 nums[i1]。 左边界和右边界的维护 对于每个子数组我们维护左右边界确保在窗口内的操作次数不超过 k。如果窗口内的操作次数超过 k则我们调整窗口的左边界。 栈和单调队列的配合 使用栈来维护每个元素的左边界和右边界栈的作用是帮助我们快速找到某个元素的最近的一个较小元素。单调队列用于保持当前窗口内的元素的单调性从而帮助我们高效地计算每个子数组的操作次数。
3、代码实现
class Solution {
public:long long countNonDecreasingSubarrays(vectorint nums, int k) {int n nums.size();vectorint left(n), right(n);vectorint s {-1}; // 栈, 初始化为 -1// 构造 left 和 right 数组for (int i 0; i n; i) {while (s.size() 1 nums[i] nums[s.back()]) {right[s.back()] i; // 更新右边界s.pop_back();}left[i] s.back(); // 栈顶是左侧 nums[i] 的最近元素s.push_back(i);}for (int i : s) {if (i ! -1) {// 栈中剩余元素的右边界为 nright[i] n;}}// 记录每个 i 右侧有哪些位置的 left 是 ivectorvectorint g(n);for (int w 0; w n; w) {if (left[w] 0) {g[left[w]].push_back(w);}}// 滑动窗口 单调队列long long ret 0;// 当前窗口内的修正次数int cnt 0;// 窗口的左边界int l 0;// 单调队列, 维护窗口最大值的下标dequeint q;for (int r 0; r n; r) {int x nums[r];// 计算窗口内最大值与当前值的差距if (!q.empty()) {cnt max(nums[q.front()] - x, 0);}// 单调队列入队, 维持单调性while (!q.empty() nums[q.back()] x) {q.pop_back();}q.push_back(r);// 调整窗口右边界, 直到满足修正次数的限制while (cnt k) {int out nums[l];for (int w : g[l]) {if (w r) {break;}cnt - (out - nums[w]) * (min(right[w] - 1, r) - w 1);}l;// 单调队列出队if (!q.empty() q.front() l) {q.pop_front();}}// 计算窗口内的子数组个数ret r - l 1;}return ret;}
};4、复杂度分析
栈的处理栈的操作复杂度是 O(n)。
滑动窗口和单调队列每次右边界 r 只会被访问一次因此整体时间复杂度为 O(n)。
总时间复杂度由于主要的操作是 O(n)因此整体时间复杂度为 O(n)。
