-
Notifications
You must be signed in to change notification settings - Fork 85
/
矩阵.md
225 lines (164 loc) · 7.08 KB
/
矩阵.md
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
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
# 矩阵
----
![矩阵](https://img-blog.csdnimg.cn/20191021201809145.png)
<br>
<br>
## 螺旋矩阵
----
给定一个包含 `m x n` 个要素的矩阵,(`m` 行, `n` 列),按照螺旋顺序,返回该矩阵中的所有要素。
示例 :
```css
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
```
#### 解题思路
我们定义矩阵的第 k 层是到最近边界距离为 k 的所有顶点。例如,下图矩阵最外层元素都是`第 1 层`,次外层元素都是`第 2 层`,然后是`第 3 层`的。
```css
[[1, 1, 1, 1, 1, 1, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 2, 3, 3, 3, 2, 1],
[1, 2, 2, 2, 2, 2, 1],
[1, 1, 1, 1, 1, 1, 1]]
```
对于每层,我们从左上方开始以顺时针的顺序遍历所有元素,假设当前层左上角坐标是 $\text{(r1, c1)}$,右下角坐标是 $\text{(r2, c2)}$。
首先,遍历上方的所有元素 `(r1, c)`,按照 `c = c1,...,c2` 的顺序。然后遍历右侧的所有元素 `(r, c2)`,按照 `r = r1+1,...,r2` 的顺序。如果这一层有四条边(也就是 `r1 < r2` 并且 `c1 < c2` ),我们以下图所示的方式遍历下方的元素和左侧的元素。
![螺旋矩阵](https://img-blog.csdnimg.cn/20191021150901496.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzc3NzQ5,size_16,color_FFFFFF,t_70)
```java
public List<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> rst = new ArrayList<Integer>();
if(matrix == null || matrix.length == 0) {
return rst;
}
int rows = matrix.length;
int cols = matrix[0].length;
int count = 0;
while(count * 2 < rows && count * 2 < cols){
for (int i = count; i < cols - count; i++) {
rst.add(matrix[count][i]);
}
for (int i = count + 1; i < rows - count; i++) {
rst.add(matrix[i][cols - count - 1]);
}
if (rows - 2 * count == 1 || cols - 2 * count == 1) { // 如果只剩1行或1列
break;
}
for (int i = cols - count - 2; i >= count; i--) {
rst.add(matrix[rows - count - 1][i]);
}
for (int i = rows - count - 2; i >= count + 1; i--) {
rst.add(matrix[i][count]);
}
count++;
}
return rst;
}
```
<br>
<br>
## 判断数独是否合法
----
请判定一个`数独`是否有效。该数独可能只填充了部分数字,其中缺少的数字用 . 表示。
维护一个`HashSet`用来记同一`行`、同一`列`、同一`九宫格`是否存在相同数字
![判断数独是否合法](https://imgconvert.csdnimg.cn/aHR0cHM6Ly91cGxvYWQud2lraW1lZGlhLm9yZy93aWtpcGVkaWEvY29tbW9ucy90aHVtYi9mL2ZmL1N1ZG9rdS1ieS1MMkctMjAwNTA3MTQuc3ZnLzI1MHB4LVN1ZG9rdS1ieS1MMkctMjAwNTA3MTQuc3ZnLnBuZw?x-oss-process=image/format,png)
示例 :
```css
输入:
[
["8","3",".",".","7",".",".",".","."],
["6",".",".","1","9","5",".",".","."],
[".","9","8",".",".",".",".","6","."],
["8",".",".",".","6",".",".",".","3"],
["4",".",".","8",".","3",".",".","1"],
["7",".",".",".","2",".",".",".","6"],
[".","6",".",".",".",".","2","8","."],
[".",".",".","4","1","9",".",".","5"],
[".",".",".",".","8",".",".","7","9"]
]
输出: false
解释: 除了第一行的第一个数字从 5 改为 8 以外,空格内其他数字均与 示例1 相同。
但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。
```
说明:
一个有效的数独(部分已被填充)`不一定`是可解的。
只需要根据以上规则,验证已经填入的数字是否`有效即可`。
给定数独序列只包含数字 `1-9` 和字符 `'.'` 。
给定数独永远是 `9x9` 形式的。`
#### 解题思路
一次迭代
首先,让我们来讨论下面两个问题:
如何枚举子数独?
可以使用 `box_index = (row / 3) * 3 + columns / 3`,其中 / 是整数除法。
![一次迭代](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzJiMTQxMzkyZTJhMTgxMWQwZThkZmRmNjI3OWIxMzUyZTU5ZmFkMGIzOTYxOTA4YzZmZjk0MTJiNmE3ZTdjY2YtaW1hZ2UucG5n?x-oss-process=image/format,png)
如何确保行 / 列 / 子数独中没有重复项?
可以利用 `value -> count` 哈希映射来跟踪所有已经遇到的值。
现在,我们完成了这个算法的所有准备工作:
遍历数独。
检查看到每个单元格值是否已经在当前的行 / 列 / 子数独中出现过:
如果出现重复,返回 `false`。
如果没有,则保留此值以进行进一步跟踪。
返回 `true`。
![确保行 / 列 / 子数独中没有重复项](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tL0ZpZ3VyZXMvMzYvMzZfc2xpZGVfMi5wbmc?x-oss-process=image/format,png)
```java
public boolean isValidSudoku(char[][] board) {
Set seen = new HashSet();
for (int i=0; i<9; ++i) {
for (int j=0; j<9; ++j) {
char number = board[i][j];
if (number != '.')
if (!seen.add(number + " in row " + i) ||
!seen.add(number + " in column " + j) ||
!seen.add(number + " in block " + i / 3 + "-" + j / 3))
return false;
}
}
return true;
}
```
<br>
<br>
## 旋转图像
----
给定一个`N×N`的二维矩阵表示图像,`90度`顺时针旋转图像。
示例 :
```css
输入: [[1,1,0,0],[1,0,0,1],[0,1,1,1],[1,0,1,0]]
输出: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
解释: 首先翻转每一行: [[0,0,1,1],[1,0,0,1],[1,1,1,0],[0,1,0,1]];
然后反转图片: [[1,1,0,0],[0,1,1,0],[0,0,0,1],[1,0,1,0]]
```
说明:
```css
1 <= A.length = A[0].length <= 20
0 <= A[i][j] <= 1
```
#### 解题思路
我们先来看看每个元素在旋转的过程中是如何移动的:
![如何移动](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzEyNjA1ZWZiNjBkMmVmYzY0ZTZlY2ZjZjY1NjJhOThhNDlhY2IzY2U2OTZiMGMxYWQzZGE0NmFiODk3N2ZhMTYtNDhfYW5nbGVzLnBuZw?x-oss-process=image/format,png)
这提供给我们了一个思路,将给定的矩阵分成四个矩形并且将原问题划归为`旋转这些矩形`的问题。
![旋转这些矩形](https://imgconvert.csdnimg.cn/aHR0cHM6Ly9waWMubGVldGNvZGUtY24uY29tLzdhNjg0YjIwN2E5NTE4OGZmNjQ1MGU0NzI0ZDZlZThiZGY0MjVmYzQ4Mzc3NWE4ZTMwMDgyZWQyNTA2MGRhYzEtNDhfcmVjdGFuZ2xlcy5wbmc?x-oss-process=image/format,png)
现在的解法很直接 -- 可以在第一个矩形中移动元素并且在 长度为 4 个元素的临时列表中`移动`它们。
![变化过程](https://img-blog.csdnimg.cn/20191021173207924.gif)
```java
public void rotate(int[][] matrix) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return;
}
int length = matrix.length;
for (int i = 0; i < length / 2; i++) {
for (int j = 0; j < (length + 1) / 2; j++){
int tmp = matrix[i][j];
matrix[i][j] = matrix[length - j - 1][i];
matrix[length -j - 1][i] = matrix[length - i - 1][length - j - 1];
matrix[length - i - 1][length - j - 1] = matrix[j][length - i - 1];
matrix[j][length - i - 1] = tmp;
}
}
}
```
<br>
<br>