找回密码
 立即注册

QQ登录

只需一步,快速开始

扫一扫,访问微社区

查看: 1627|回复: 2
收起左侧

[米群网刷题小分队] 【LeetCode小分队】【spiral matrix】-【刷题第一弹】

[复制链接]

21

主题

8

精华

415

积分

高级会员

Rank: 3Rank: 3

积分
415
发表于 10-11-2014 04:01 PM | 显示全部楼层 |阅读模式

亲!马上注册或者登录会查看更多内容!

您需要 登录 才可以下载或查看,没有帐号?立即注册

x
本帖最后由 TeamEditor 于 11-5-2014 05:42 PM 编辑

快速通道:
https://oj.leetcode.com/problems/spiral-matrix/

题目:

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].

思路:(必填)
代码:(必填)
复杂度分析:(必填)
细节和陷阱:(选填)
相似题目:(选填)

===============
点此查看汇总贴
===============


本帖被以下淘专辑推荐:

21

主题

8

精华

415

积分

高级会员

Rank: 3Rank: 3

积分
415
 楼主| 发表于 10-11-2014 04:07 PM | 显示全部楼层
这道题 个人认为,没有太多实战性,没有考到经典算法,不太可能考到。

思路:如果是4*5的棋盘
1 1 1 1 2
4 5 5 6 2
4 8 7 7 2
4 3 3 3 3

可以按照这个顺序去记录,然后1111 和55的差别是长度减2,因此,很容易推得
  1. public class Solution {
  2.     public List<Integer> spiralOrder(int[][] matrix) {
  3.         
  4.         List<Integer> arr = new ArrayList<Integer> ();
  5.         if(matrix == null|| matrix.length ==0 || matrix[0].length == 0 ) return arr;
  6.         int row = matrix.length;
  7.         int col = matrix[0].length;
  8.         int i=0, j=0, num = 0, hor = col-1, ver = row-1;
  9.         while(num < row*col){
  10.             
  11.             if(hor == 0 && ver == 0){
  12.                 arr.add(matrix[i][j]); return arr;
  13.             }
  14.             if(num == row*col) return arr;

  15.             int k=0;
  16.             while(k++ < hor && num < row*col){
  17.                 arr.add(matrix[i][j++]); num++;
  18.             }
  19.             k = 0;
  20.             while(k++ < ver&& num < row*col){
  21.                 arr.add(matrix[i++][j]); num++;
  22.             }
  23.             k = 0;
  24.             while(k++ < hor&& num < row*col){
  25.                 arr.add(matrix[i][j--]); num++;
  26.             }
  27.             k = 0;
  28.             while(k++ < ver&& num < row*col){
  29.                 arr.add(matrix[i--][j]); num++;
  30.             }
  31.             i++;j++;
  32.             hor -= 2; ver -= 2;
  33.         }
  34.         
  35.         return arr;
  36.     }
  37. }
复制代码


如果误区有的时候最后一轮不是 像之前的走4次,可能2次,也可能1次,所以要小心这两种情况。
回复 支持 反对

使用道具 举报

8

主题

5

精华

1243

积分

顶级会员

Rank: 6Rank: 6

积分
1243

热心会员推广达人

发表于 11-5-2014 12:42 PM | 显示全部楼层
  1.     public ArrayList<Integer> spiralOrder(int[][] matrix) {
  2.         ArrayList<Integer> res = new ArrayList<Integer>();
  3.         if(matrix==null || matrix.length == 0 || matrix[0].length == 0) return res;
  4.         int row = matrix.length;
  5.         int col = matrix[0].length;
  6.         int rowS = 0;
  7.         int colS = 0;
  8.         while(rowS<row/2 && colS<col/2){
  9.             int i = rowS;
  10.             int j = colS;
  11.             while(j<col-colS-1) res.add(matrix[i][j++]);
  12.             while(i<row-rowS-1) res.add(matrix[i++][j]);
  13.             while(j>colS) res.add(matrix[i][j--]);
  14.             while(i>rowS) res.add(matrix[i--][j]);
  15.             rowS++;
  16.             colS++;
  17.         }
  18.         if(rowS==row/2 && row%2==1 && colS<col/2){
  19.             for(int j = colS; j<col-colS; j++)
  20.                 res.add(matrix[rowS][j]);
  21.         }
  22.         else if(colS==col/2 && col%2==1 && rowS<row/2){
  23.             for(int i = rowS; i<row-rowS; i++)
  24.                 res.add(matrix[i][colS]);
  25.         }
  26.         else if(row==col && row%2==1)
  27.             res.add(matrix[rowS][colS]);
  28.         else
  29.             return res;
  30.         return res;
  31.     }
  32. spiral 走法要牢记,每次都按存在一个回路的来走,就是中间的四个while循环,当不存在一个回路时,有几种情况,第一就是row多了一行且这行没走过的col值大于1,第二就是col多了一列,这列没走过的row大于1,第三就是row和col只剩一个没走,就是比如3*3中间的那个点,第四就是row和col都没有剩下的,这种情况只有当row==col且row值为偶数的情况。将这些分析清楚后码代码就不会有漏的了
复制代码
回复 支持 反对

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表