首页 > 其他 > 详细

LeetCode 885. Spiral Matrix III

时间:2019-12-17 13:33:41      阅读:78      评论:0      收藏:0      [点我收藏+]

原题链接在这里:https://leetcode.com/problems/spiral-matrix-iii/

题目:

On a 2 dimensional grid with R rows and C columns, we start at (r0, c0) facing east.

Here, the north-west corner of the grid is at the first row and column, and the south-east corner of the grid is at the last row and column.

Now, we walk in a clockwise spiral shape to visit every position in this grid. 

Whenever we would move outside the boundary of the grid, we continue our walk outside the grid (but may return to the grid boundary later.) 

Eventually, we reach all R * C spaces of the grid.

Return a list of coordinates representing the positions of the grid in the order they were visited.

Example 1:

Input: R = 1, C = 4, r0 = 0, c0 = 0
Output: [[0,0],[0,1],[0,2],[0,3]]

技术分享图片

Example 2:

Input: R = 5, C = 6, r0 = 1, c0 = 4
Output: [[1,4],[1,5],[2,5],[2,4],[2,3],[1,3],[0,3],[0,4],[0,5],[3,5],[3,4],[3,3],[3,2],[2,2],[1,2],[0,2],[4,5],[4,4],[4,3],[4,2],[4,1],[3,1],[2,1],[1,1],[0,1],[4,0],[3,0],[2,0],[1,0],[0,0]]

技术分享图片

Note:

  1. 1 <= R <= 100
  2. 1 <= C <= 100
  3. 0 <= r0 < R
  4. 0 <= c0 < C

题解:

At the beginning, turn at 1 and 1, then 2 and 2, then 3 and 3, and goes on.

Thus, we need to figure out the loop relationship.

Every 2 times, we goes into the repeated steps. When finishing repeated steps, turn.

After 2 times, increase repeated steps.

With this, we know 2 times loop is outside repeated steps loop.

Time Complexity: O(R * C).

Space: O(1). regardless res.

AC Java:

 1 class Solution {
 2     int [][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
 3     
 4     public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
 5         int [][] res = new int[R * C][2];
 6         if(R == 0 || C == 0){
 7             return res;
 8         }
 9         
10         res[0] = new int[]{r0, c0};
11         
12         int count = 1;
13         int index = 0;
14         int k = 1;
15         while(count < R * C){
16             for(int j = 0; j<2; j++){
17                 int [] dir = dirs[index % 4];
18                 for(int i = 0; i<k; i++){
19                     r0 += dir[0];
20                     c0 += dir[1];
21                     if(r0 >= 0 && r0 < R && c0 >=0 && c0 < C){
22                         res[count++] = new int[]{r0, c0};
23                     }
24                 }
25                 
26                 index++;
27             }
28             
29             k++;
30         }
31         
32         return res;
33      }
34 }

类似Spiral MatrixSpiral Matrix II.

LeetCode 885. Spiral Matrix III

原文:https://www.cnblogs.com/Dylan-Java-NYC/p/12053827.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!