文章目录力扣 2946. 循环移位后的矩阵相似检查题目描述思路简述代码实现复杂度分析力扣 155. 最小栈题目描述思路简述代码实现复杂度分析踩坑记录力扣 2946. 循环移位后的矩阵相似检查题目描述力扣 2946. 循环移位后的矩阵相似检查示例 1输入mat [[1,2,1,2],[5,5,5,5],[6,3,6,3]], k 2输出true解释初始矩阵如图一所示。图二表示对奇数行右移一次且对偶数行左移一次后的矩阵状态。图三是经过两次循环移位后的最终矩阵状态与初始矩阵相同。因此返回 true 。示例 2输入mat [[2,2],[2,2]], k 3输出true解释由于矩阵中的所有值都相等即使进行循环移位矩阵仍然保持不变。因此返回 true 。示例 3输入mat [[1,2]], k 1输出false解释循环移位一次后mat [[2,1]]与初始矩阵不相等。因此返回 false 。提示1 mat.length 251 mat[i].length 251 mat[i][j] 251 k 50思路简述核心思路其实很简单无论对一行进行左移 k 次还是右移 k 次判断移位后矩阵能否复原的底层逻辑是完全一致的。这就像我们玩三阶魔方时把红色面正对自己无论向左还是向右旋转某一层都需要旋转 4 次才能让红色面完全回到正对自己的初始状态 —— 循环移位的核心就是周期性。对于矩阵中任意一个元素 mat[i][j]经过题目要求的循环移位后它的目标位置可以直接通过公式推导得出最终只需验证 mat[i][j] 是否与 mat[i][(j k) % n] 相等即可。这里对 n 取模是为了处理 k 大于行长度 n 的情况避免重复循环移位带来的索引越界问题同时也能直接抵消掉完整周期的无效移位。基于这个规律我们完全不需要实际模拟每一次移位操作只需遍历矩阵做一次等式校验就能得出最终结果。代码实现classSolution{public:boolareSimilar(vectorvectorintmat,intk){intmmat.size(),nmat[0].size();for(inti0;im;i){for(intj0;jn;j){if(mat[i][j]!mat[i][(jk)%n])returnfalse;}}returntrue;}};复杂度分析时间复杂度O(mn)需遍历矩阵中所有元素。空间复杂度O(1)仅使用常数额外空间。力扣 155. 最小栈题目描述力扣 155. 最小栈示例 1:输入[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”][[],[-2],[0],[-3],[],[],[],[]]输出[null,null,null,null,-3,null,0,-2]解释MinStack minStack new MinStack();minStack.push(-2);minStack.push(0);minStack.push(-3);minStack.getMin(); -- 返回 -3.minStack.pop();minStack.top(); -- 返回 0.minStack.getMin(); -- 返回 -2.提示-231 val 231- 1pop、top 和 getMin 操作总是在 非空栈 上调用push, pop, top, and getMin最多被调用 3 * 104次思路简述最小栈的核心需求是在常数时间内获取最小值。我们可以用双栈实现用数组实现底层逻辑同理核心思路完全一致主栈st1作为标准栈完整存储所有入栈的元素支持常规的 push、pop、top 操作辅助栈st2专门同步记录每一次入栈后当前栈内的最小值。具体操作逻辑push将元素压入st1若当前元素小于st2的栈顶元素则将其压入st2否则将st2的栈顶元素再次压入st2“占位”操作目的是简化pop逻辑。pop同时弹出st1和st2的栈顶元素。getMinst2的栈顶元素即为当前最小值。代码实现classMinStack{public:MinStack(){st2.push(INT_MAX);}voidpush(intx){st1.push(x);if(st2.top()x)st2.push(x);elsest2.push(st2.top());}voidpop(){st1.pop();st2.pop();}inttop(){returnst1.top();}intgetMin(){returnst2.top();}stackintst1;stackintst2;};/** * Your MinStack object will be instantiated and called as such: * MinStack* obj new MinStack(); * obj-push(x); * obj-pop(); * int param_3 obj-top(); * int param_4 obj-getMin(); */复杂度分析时间复杂度所有操作push、pop、top、getMin均为 O(1)。空间复杂度O(n)需额外使用一个栈存储最小值。踩坑记录刚拿到「循环移位后的矩阵相似检查」这道题时看到是简单题第一反应是想硬凹纯数学规律的O(1)解法结果越想越复杂特殊情况层出不穷最后才发现完全没必要。这里也引出一个纠结的问题做算法题时到底该直接模拟还是该深挖数学规律最小栈这道题里有个很容易忽略的细节必须在构造函数中给辅助栈st2先压入一个INT_MAX完成初始化。如果不做这个操作第一次调用push时访问st2.top()会直接触发空栈访问的报错这个小细节很容易在写代码时漏掉。这里给总结一个超好用的判断口诀希望能够帮助大家刷题时扫一眼就能快速做决策小数据直接模拟。大数据必找规律。步骤清模拟稳。结果能算数学冲。就像今天这道矩阵题矩阵行列数最大才25k最大也只有50这种小数据范围直接模拟或者用简化后的规律遍历远比死磕O(1)数学解法划算得多不仅写得快还不容易出错。今天的两道题都是校招、社招面试里的高频基础题一道是数组矩阵的核心操作题一道是栈结构的经典设计题吃透了对打牢算法基础非常有帮助。如果这篇题解对你有帮助麻烦点个点赞收藏也可以关注我后续会持续更新力扣每日一题的详细题解还有高频面试算法的保姆级讲解陪你一起刷穿力扣