问题描述:
Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order.
For example,
Given the following matrix:
[ [ 1, 2, 3 ], [ 4, 5, 6 ], [ 7, 8, 9 ] ]
You should return [1,2,3,6,9,8,7,4,5]
.
原问题链接:https://leetcode.com/problems/spiral-matrix/
问题分析
这个问题其实是对矩阵螺旋访问的实现。这里访问的顺序是首先从最上面的行从左到右,然后从最右边的行从上到下,再从最下面的行从右到左,再从最左边的列从下到上。因为每访问完一行或者一列之后,矩阵的范围就缩小了一部分。而且这些能够访问的最左最右以及最上最下的行列将作为后续访问的界限。所以我们可以定义4个变量,rowBegin, rowEnd, colBegin, colEnd分别表示它们行的起始和结束位置,列的起始和结束位置。然后再按照前面要求的顺序螺旋的去访问。当访问完第一行的时候,rowBegin++, 访问完最后一列则colEnd--, 然后依次的rowEnd--, colBegin++。
在实现的代码里有一个容易出错的细节,就是当遍历完最上面的第一行以及最右边的列之后,当我们要从最下面行的右边向左遍历以及最左边列的下面向上遍历的时候。我们还是需要判断一下rowBegin <= rowEnd以及colBegin <= colEnd。因为在一些情况下我们前面的访问就已经使得它们的行或者列被访问了,需要避免重复的访问。
详细的代码实现如下:
public class Solution { public List<Integer> spiralOrder(int[][] matrix) { List<Integer> result = new ArrayList<>(); if(matrix.length == 0) return result; int rowBegin = 0, rowEnd = matrix.length - 1, colBegin = 0, colEnd = matrix[0].length - 1; while(rowBegin <= rowEnd && colBegin <= colEnd) { for(int i = colBegin; i <= colEnd; i++) result.add(matrix[rowBegin][i]); rowBegin++; for(int i = rowBegin; i <= rowEnd; i++) result.add(matrix[i][colEnd]); colEnd--; if(rowBegin <= rowEnd) { for(int i = colEnd; i >= colBegin; i--) result.add(matrix[rowEnd][i]); } rowEnd--; if(colBegin <= colEnd) { for(int i = rowEnd; i >= rowBegin; i--) result.add(matrix[i][colBegin]); } colBegin++; } return result; } }
相关推荐
leetcode category other hot keywords:Palindrome(mic), Subsequence Array 螺旋矩阵Spiral Matrix 顺时针打印矩阵 Next Permutation Product of Array Except Self 189.rotate-array 283.move-zero Range Sum ...
leetcode 530 力码 全部的: 易(173/237+x) 中(144/437+x) 硬(4/x) 问题 1.Two Sum(dict) 7.(跳过)(数学) 9.(跳过)(串串技巧) 11.盛水最多的容器 12.(跳过)(问题不好) 13.(跳过)(蛮力) 14.(跳过)...
java lru leetcode LeetCode 记录数据结构与算法/LeetCode练习过程,将...Spiral Matrix Mergesort [Algorithm Swap](Mergesort/Algorithm swap.md) Numbers Queue Stack Toposort Trie Tree Two Pointers Union Find
Spiral Matrix com.leetcode.list Linked List Cycle Linked List Cycle II Remove Duplicates from Sorted List com.leetcode.string Single Number com.leetcode.tree Balanced Binary Tree Maximum Depth of ...
leetcode 答案螺旋矩阵 返回二维数组中整数元素的顺时针螺旋列表 [答案击败 100% Java LeetCode 运行时提交] [答案击败 100% Java LeetCode 内存使用提交] 大(O)= O(N)
# [LeetCode](https://leetcode.com/problemset/algorithms/) ![Language](https://img.shields.io/badge/language-Python%20%2F%20C++%2011-orange.svg) [![License]...
多线程 leetcode 前言 ...Spiral Matrix Path Sum II Copy List with Random Pointer Building H2O Fizz Buzz Multithreaded hard Merge k Sorted Lists Reverse Nodes in k-Group Trapping Rain Water
第 338 章leetcode_cpp leetcode 的 C++ 代码 包含的问题 1 两和容易2 加两个数中5 最长回文子串中6 ZigZag 转换介质7 反转整数简单8 ...Spiral Matrix II 培养基61 轮播列表中第62话第63话64 最小路径和中66
leetcode LeetCode Solutions 算法 - Algorithms 排序算法:快速排序、归并排序、计数排序 搜索算法:回溯、递归、剪枝技巧 图论:最短路、最小生成树、网络流建模 动态规划:背包问题、最长子序列、计数问题 基础...
Spiral Matrix medium O 66 Plus One easy O O 118 Pascal's Triangle easy O O 119 Pascal's Triangle II easy O 要满足只用一个array大小空间O(k) k为input大小来完成,须具备backtracking概念 151 Reverse Words ...
def spiralOrder(self, matrix: List[List[int]]) -> List[int]: if not matrix:return [] m,n = len(matrix),len(matrix[0]) x = y = di = 0 dx = [0,1,0,-1] dy = [1,0,-1,0] res = [] visite
对于每一道算法题会总结代码、时间复杂度以及一些好的blog排序(sort)...Spiral Matrix IILeetCode 53 Maximum SubarrayLeetCode 152 Maximum Product SubarrayLintCode 138 Subarray SumLintCode 139 Subarray Sum ...
这是我准备面试时建议的个人问题清单。...https://leetcode.com/problems/spiral-matrix/ https://leetcode.com/problems/search-a-2d-matrix/ https://leetcode.com/problems/set-matrix-zeroes/ 弦乐 ...
Spiral Matrix II ZigZag Conversion Divide Two Integers Text Justification Max Points on a Line Community QQ 群: 237669375 Github: https://www.github.com/soulmachine/algorithm-essentials 微博: @...