FilesExpand file tree

 master

/

SpiralOrder.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

184 lines (148 loc) · 5.01 KB

 master

/

SpiralOrder.java

Copy path

Top

File metadata and controls

• Code
• Blame

184 lines (148 loc) · 5.01 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

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

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

178

179

180

181

182

183

184

package Algorithms.array;

import java.util.ArrayList;

import java.util.List;

public class SpiralOrder {

public static void main(String[] strs) {

int[][] matrix = {

{1, 2},

{3, 4}

};

spiralOrder(matrix);

}

public List<Integer> spiralOrder1(int[][] matrix) {

List<Integer> ret = new ArrayList<Integer>();

if (matrix == null || matrix.length == 0

|| matrix[0].length == 0) {

return ret;

}

rec(matrix, 0, 0, matrix.length, matrix[0].length, ret);

return ret;

}

public static void rec(int[][] matrix, int x, int y, int rows, int cols, List<Integer> ret) {

if (rows <= 0 || cols <= 0) {

return;

}

// first line

for (int i = 0; i < cols; i++) {

ret.add(matrix[x][y + i]);

}

// right column

for (int i = 1; i < rows - 1; i++) {

ret.add(matrix[x + i][y + cols - 1]);

}

// down row

if (rows > 1) {

for (int i = cols - 1; i >= 0; i--) {

ret.add(matrix[x + rows - 1][y + i]);

}

}

// left column. GO UP.

if (cols > 1) {

for (int i = rows - 2; i > 0; i--) {

ret.add(matrix[x + i][y]);

}

}

rec (matrix, x + 1, y + 1, rows - 2, cols - 2, ret);

}

/*

Solution 2:

REF: http://blog.csdn.net/fightforyourdream/article/details/16876107?reload

此算法比较不容易算错

*/

public List<Integer> spiralOrder2(int[][] matrix) {

List<Integer> ret = new ArrayList<Integer>();

if (matrix == null || matrix.length == 0

|| matrix[0].length == 0) {

return ret;

}

int x1 = 0;

int y1 = 0;

int rows = matrix.length;

int cols = matrix[0].length;

while (rows >= 1 && cols >= 1) {

// Record the right down corner of the matrix.

int x2 = x1 + rows - 1;

int y2 = y1 + cols - 1;

// go through the WHOLE first line.

for (int i = y1; i <= y2; i++) {

ret.add(matrix[x1][i]);

}

// go through the right column.

for (int i = x1 + 1; i < x2; i++) {

ret.add(matrix[i][y2]);

}

// go through the WHOLE last row.

if (rows > 1) {

for (int i = y2; i >= y1; i--) {

ret.add(matrix[x2][i]);

}

}

// the left column.

if (cols > 1) {

for (int i = x2 - 1; i > x1; i--) {

ret.add(matrix[i][y1]);

}

}

// in one loop we deal with 2 rows and 2 cols.

rows -= 2;

cols -= 2;

x1++;

y1++;

}

return ret;

}

/*

Solution 3:

使用方向矩阵来求解

*/

public static List<Integer> spiralOrder(int[][] matrix) {

List<Integer> ret = new ArrayList<Integer>();

if (matrix == null || matrix.length == 0

|| matrix[0].length == 0) {

return ret;

}

int rows = matrix.length;

int cols = matrix[0].length;

int visitedRows = 0;

int visitedCols = 0;

// indicate the direction of x

// 1: means we are visiting the row by the right direction.

// -1: means we are visiting the row by the left direction.

int[] x = {1, 0, -1, 0};

// 1: means we are visiting the colum by the down direction.

// -1: means we are visiting the colum by the up direction.

int[] y = {0, 1, 0, -1};

// 0: right, 1: down, 2: left, 3: up.

int direct = 0;

int startx = 0;

int starty = 0;

int candidateNum = 0;

int step = 0;

while (true) {

if (x[direct] == 0) {

// visit Y axis.

candidateNum = rows - visitedRows;

} else {

// visit X axis

candidateNum = cols - visitedCols;

}

if (candidateNum <= 0) {

break;

}

ret.add(matrix[startx][starty]);

step++;

if (step == candidateNum) {

step = 0;

visitedRows += x[direct] == 0 ? 0: 1;

visitedCols += y[direct] == 0 ? 0: 1;

// move forward the direction.

direct ++;

direct = direct%4;

}

// 根据方向来移动横坐标和纵坐标。

startx += y[direct];

starty += x[direct];

}

return ret;

}

}