LeetCode 54. Spiral Matrix
2020-06-26 20:06:00 # leetcode # core problems # hard # array

Problem

LeetCode 54. Spiral Matrix

1. 题目简述

给出一个m * n的矩阵，将其螺旋打印出来。例如：

Example 1:

Input:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
Output: [1,2,3,6,9,8,7,4,5]
Example 2:

Input:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
Output: [1,2,3,4,8,12,11,10,9,5,6,7]

2. 算法思路

相关问题：

  1. LeetCode 59. Spiral Matrix II

极其经典的螺旋打印的问题，这里的暴力做法其实是很麻烦的，用方向数组比较好！

暴力解法——螺旋打印

注意这里的边界情况是只有一行或者一列的情况，要特殊处理，比较麻烦，建议直接去看第二写法或者解法二。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        // 每次打印一圈，直至index越界直接return，写一个子函数。
        List<Integer> res = new ArrayList();

        helper(matrix, 0, 0, res);

        return res;
    }

    private void helper (int[][] matrix, int i, int j, List<Integer> res) {
        if (matrix.length == 0) {
            return;
        }

        int m = matrix.length, n = matrix[0].length;
        int height = m - 2 * i, width = n - 2 * j;

        // 越界的情况
        if (width <= 0 || height <= 0) {
            return;
        }

        // 剩下一行或一列的情况
        if (height == 1) {
            // 一行
            for (int x = 0; x < width; x++) {
                res.add(matrix[i][j + x]);
            }
            return;
        }
        if (width == 1) {
            // 一列
            for (int x = 0; x < height; x++) {
                res.add(matrix[i + x][j]);
            }
            return;
        }

        // 开始按圈添加res
        // 上方一行，例如[1,2]
        for (int x = 0; x < width - 1; x++) {
            res.add(matrix[i][j + x]);
        }
        // 右侧一列，例如[3,6]
        for (int x = 0; x < height - 1; x++) {
            res.add(matrix[i + x][j + width - 1]);
        }
        // 下方一行，例如[9,8]
        for (int x = 0; x < width - 1; x++) {
            res.add(matrix[i + height - 1][j + width - 1 - x]);
        }
        // 左侧一列，例如[7, 4]
        for (int x = 0; x < height - 1; x++) {
            res.add(matrix[i + height - 1 - x][j]);
        }

        helper(matrix, i + 1, j + 1, res);
    }
}

第二种写法和下面的解法二有异曲同工之妙，最好记一下，这样不需要去使用额外的m*n的空间，也就是isVisited数组。题解链接：题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int[] spiralOrder(int[][] matrix) {
        if(matrix.length == 0) return new int[0];
        int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1, x = 0;
        int[] res = new int[(r + 1) * (b + 1)];
        while(true) {
            for(int i = l; i <= r; i++) res[x++] = matrix[t][i]; // left to right.
            if(++t > b) break;
            for(int i = t; i <= b; i++) res[x++] = matrix[i][r]; // top to bottom.
            if(l > --r) break;
            for(int i = r; i >= l; i--) res[x++] = matrix[b][i]; // right to left.
            if(t > --b) break;
            for(int i = b; i >= t; i--) res[x++] = matrix[i][l]; // bottom to top.
            if(++l > r) break;
        }
        return res;
    }
}

方向数组巧妙解法

对于这种需要四个方向dfs的题目来说，方向数组最适合不过了，对于四个方向，只需要定义dx和dy即可。也就是说dx = [-1, 1, 0, 0]， dy = [0, 0, -1, 1]，分别对应“上下左右”四个方向，每次只需要判断是否越界或者已经填充即可。这么写的好处是节省脑力，不需要判断每次的长度，很省事！！！但是相应的有一丢丢浪费空间，因为需要额外的bool数组来存储每个数字是否已经打印。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix.length == 0) {
            return new ArrayList<Integer>();
        }

        int m = matrix.length, n = matrix[0].length;
        // 这里用一个boolean数组来定义是否已经访问过该数字
        boolean[][] isVisited = new boolean[m][n];
        // 定义四个方向，此题的顺序应该是右下左上，注意顺序
        int[] dx = {0, 1, 0, -1};
        int[] dy = {1, 0, -1, 0};
        // 定义一个返回的结果集
        List<Integer> res = new ArrayList();

        int x = 0, y = 0, direction = 0;

        while (res.size() < m * n) {
            res.add(matrix[x][y]);
            isVisited[x][y] = true;
            if (x + dx[direction] < 0 || x + dx[direction] >= m || y + dy[direction] < 0 || y + dy[direction] >= n || isVisited[x + dx[direction]][y + dy[direction]] == true) {
                // 此时需要变更方向
                direction = (direction + 1) % 4;
            }
            x += dx[direction];
            y += dy[direction];
        }

        return res;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141

package heap;

import java.lang.reflect.Array;

public class MyHeap<T extends Comparable<T>> {
	public static final int INITIAL_SIZE = 16;
	Class<T> type;
	boolean flag = false;
	T[] heap;
	int size = 0; // 堆中元素数量

	// 构造器
	public MyHeap() {

	}

	// 构造器
	public MyHeap(Class<T> type) {
		heap = (T[]) Array.newInstance(type, INITIAL_SIZE);
		this.type = type;
	}

	// 清空堆
	public void clear() {
		heap = (T[]) Array.newInstance(type, INITIAL_SIZE);
		size = 0;
	}

	// 堆中元素数量
	public int size() {
		return size;
	}

	// 检查数组大小
	public void checkSize() {
		if (size > heap.length / 2) {
			T[] heap1 = (T[]) Array.newInstance(type, INITIAL_SIZE * 2);
			System.arraycopy(heap, 0, heap1, 0, heap.length);
			heap = heap1;
		}
	}

	// 求父节点数组下标
	public int getParent(int i) {
		return (i + 1) / 2 - 1;
	}

	// 求左子节点数组下标
	public int getLeftChild(int i) {
		int t = (i + 1) * 2 - 1;
		return t;
	}

	// 求右子节点数组下标
	public int getRightChild(int i) {
		int t = (i + 1) * 2;
		return t;
	}

	// 获取某元素下标
	public int getEle(T t) {
		for (int i = 0; i < size; i++) {
			if (heap[i].equals(t)) {
				flag = true;
				return i;
			}
		}
		return 0;
	}

	// 换位置
	public void swap(int i, int j) {
		T temp;
		temp = heap[i];
		heap[i] = heap[j];
		heap[j] = temp;
	}

	// 维护堆的性质(小顶堆)
	public void buildHeap(int i) {
		if (i > 0) {
			if (heap[i].compareTo(heap[getParent(i)]) < 0) {
				swap(i, getParent(i));
			}
			buildHeap(getParent(i));
		}
	}

	// 插入元素
	public void insert(T t) {
		checkSize();
		heap[size] = t;
		buildHeap(size);
		size++;
	}

	// 获取最小元素（堆顶元素）
	public T minEle() {
		return heap[0];
	}

	// 获取某个元素的父元素
	public T getParentEle(T t) {
		flag = false;
		int i = getEle(t);
		if (!flag) {
			return null;
		} else if (i == 0)
			return heap[0];
		else {
			return heap[getParent(i)];
		}
	}

	// 获取某元素左孩子
	public T getLeftChildEle(T t) {
		flag = false;
		int i = getEle(t);
		if (!flag) {
			return null;
		} else if (getLeftChild(i) >= size) {
			return null;
		} else {
			return heap[getLeftChild(i)];
		}
	}

	// 获取某元素的右孩子
	public T getRightChildEle(T t) {
		flag = false;
		int i = getEle(t);
		if (!flag) {
			return null;
		} else if (getRightChild(i) >= size) {
			return null;
		} else {
			return heap[getRightChild(i)];
		}
	}
}
Prev
2020-06-26 20:06:00 # leetcode # core problems # hard # array
Next