设计师网站建设,广州网站建设的公司,asp.net 网站 结构,用python做网站的多吗小哆啦开始刷力扣的第二十八天 54. 螺旋矩阵 - 力扣#xff08;LeetCode#xff09; #x1f32a;️ 一场螺旋风暴的较量
在一个阳光明媚的午后#xff0c;小哆啦悠闲地坐在窗边啃着曲奇#xff0c;突然#xff0c;一道神秘的光芒闪过#xff0c;小智从代码的虚空中出现… 小哆啦开始刷力扣的第二十八天 54. 螺旋矩阵 - 力扣LeetCode ️ 一场螺旋风暴的较量
在一个阳光明媚的午后小哆啦悠闲地坐在窗边啃着曲奇突然一道神秘的光芒闪过小智从代码的虚空中出现。
“哆啦我今天带来了一个特别有意思的题目”小智眨着眼睛说。
“哦是什么”小哆啦眯起眼睛嘴角还沾着饼干屑。
“螺旋矩阵 ”小智一挥手白板上赫然出现了一道经典题目 给你一个 m 行 n 列的矩阵 matrix要求你按照顺时针螺旋顺序返回矩阵中的所有元素。 示例
输入matrix [[1,2,3],[4,5,6],[7,8,9]]
输出[1,2,3,6,9,8,7,4,5]“这也太简单了吧”小哆啦信心满满地说“让我来个暴力解法沿着顺时针走一圈不就好了嘛” 第一回合暴力解法上线
小哆啦撸起袖子啪啪敲起键盘写下了第一个版本
function spiralOrder(matrix: number[][]): number[] {if (matrix.length 0 || matrix[0].length 0) return [];const m matrix.length;const n matrix[0].length;const result: number[] [];const visited: boolean[][] Array.from({ length: m }, () Array(n).fill(false));let direction 0; // 0: 右, 1: 下, 2: 左, 3: 上let row 0, col 0;const directions [[0, 1], [1, 0], [0, -1], [-1, 0]];for (let i 0; i m * n; i) {result.push(matrix[row][col]);visited[row][col] true;const nextRow row directions[direction][0];const nextCol col directions[direction][1];if (nextRow 0 nextRow m nextCol 0 nextCol n !visited[nextRow][nextCol]) {row nextRow;col nextCol;} else {direction (direction 1) % 4;row directions[direction][0];col directions[direction][1];}}return result;
}小哆啦按下运行键屏幕上果然输出了**[1,2,3,6,9,8,7,4,5]**结果完全正确
时间复杂度 O(m * n) 空间复杂度 O(m * n)额外的 visited 数组
“哈哈哈我是不是很厉害”小哆啦得意地转头看向小智。 小智的灵魂拷问
小智推了推眼镜嘴角勾起一抹淡淡的微笑“哆啦你确定这就是最优解吗”
小哆啦一愣“怎么不是每个元素都访问了一遍没多走一步啊”
小智轻敲白板“可是……你额外用了一个 visited 数组空间复杂度已经飙到 O(m * n) 了这不等于背着一大堆行李去爬山吗”
小哆啦嘴角抽了抽“那……那怎么改”
⚡ 第二回合边界收缩法登场
“我们可以巧妙利用边界收缩法”小智耐心地解释道“动态调整上下左右的边界来控制遍历路径而不是额外用空间去标记访问过的格子。”
小哆啦听完恍然大悟“等于说我们把访问过的路径‘挤压’成边界把矩阵变成一个收缩的战场”
于是在小智的引导下小哆啦写出了第二版代码
function spiralOrderOptimized(matrix: number[][]): number[] {if (matrix.length 0 || matrix[0].length 0) return [];let top 0, bottom matrix.length - 1;let left 0, right matrix[0].length - 1;const result: number[] [];while (top bottom left right) {for (let i left; i right; i) result.push(matrix[top][i]); // 从左到右top;for (let i top; i bottom; i) result.push(matrix[i][right]); // 从上到下right--;if (top bottom) { // 防止重复遍历for (let i right; i left; i--) result.push(matrix[bottom][i]); // 从右到左bottom--;}if (left right) { // 防止重复遍历for (let i bottom; i top; i--) result.push(matrix[i][left]); // 从下到上left;}}return result;
}时间复杂度 O(m * n) 空间复杂度 O(1) 解法对比
解法时间复杂度空间复杂度思路暴力解法O(m * n)O(m * n)模拟遍历记录访问过的路径边界收缩法O(m * n)O(1)动态调整边界避免额外空间 最终总结
小哆啦从初出茅庐的暴力解法到小智提点后的边界收缩法这不仅是一次代码的升级更是一场算法思维的蜕变。螺旋矩阵看似只是绕圈圈但真正高效的解法藏在对边界和路径的精准把控之中。
“下次再有这种题目我一定一眼就用边界收缩法”小哆啦挥着拳头说道。
“算法的成长就是不断突破自己思维边界的过程。”小智微微一笑。
如果你也有更妙的思路欢迎在评论区和我们一起探讨✨
