螺旋矩陣遍歷
給定一個包含 m x n 個元素的矩陣（m 行, n 列），請按照順時針螺旋順序，返回矩陣中的所有元素。
示例 1:
輸入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
輸出: [1,2,3,6,9,8,7,4,5]
示例 2:
輸入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
輸出: [1,2,3,4,8,12,11,10,9,5,6,7]
模擬順時針旋轉(zhuǎn)
繪制螺旋軌跡路徑，我們發(fā)現(xiàn)當(dāng)路徑超出界限或者進(jìn)入之前訪問過的單元格時，會順時針旋轉(zhuǎn)方向。
public static List<Integer> spiralOrder(int[][] matrix) {
List<Integer> ret = new ArrayList<>();
if (matrix.length == 0) {
return ret;
}
int m = matrix.length;
int n = matrix[0].length;
boolean[][] seen = new boolean[m][n];
int row = 0;
int col = 0;
// dRow, dCol代表方向, dInd控制方向轉(zhuǎn)變
int[] dRow = {0, 1, 0, -1};
int[] dCol = {1, 0, -1, 0};
int dInd = 0;
for (int i = 0; i < m * n; i++) {
ret.add(matrix[row][col]);
seen[row][col] = true;
int potNextRow = row + dRow[dInd];
int potNextCol = col + dCol[dInd];
if (potNextRow >= 0 && potNextRow < m && potNextCol >= 0 && potNextCol < n && !seen[potNextRow][potNextCol]) {
row = potNextRow;
col = potNextCol;
} else {
dInd = (dInd + 1) % 4;
row += dRow[dInd];
col += dCol[dInd];
}
}
return ret;
}
逐層模擬
答案是最外層所有元素按照順時針順序輸出，其次是次外層，以此類推。
public static List<Integer> spiralOrder2(int[][] matrix) {
List<Integer> ret = new ArrayList<>();
if (matrix.length == 0) {
return ret;
}
int m = matrix.length;
int n = matrix[0].length;
int r1 = 0;
int r2 = m - 1;
int c1 = 0;
int c2 = n - 1;
while (r1 <= r2 && c1 <= c2) {
for (int c = c1; c <= c2; c++) {
ret.add(matrix[r1][c]);
}
for (int r = r1 + 1; r <= r2; r++) {
ret.add(matrix[r][c2]);
}
if(r1 < r2 && c1 < c2){ // 防止重復(fù)
for (int c = c2 - 1; c >= c1; c--) {
ret.add(matrix[r2][c]);
}
for (int r = r2 - 1; r >= r1 + 1; r--) {
ret.add(matrix[r][c1]);
}
}
r1++;
c1++;
r2--;
c2--;
}
return ret;
}
盛最多水的容器
給你 n 個非負(fù)整數(shù) a1，a2，...，an，每個數(shù)代表坐標(biāo)中的一個點(diǎn) (i, ai) 。在坐標(biāo)內(nèi)畫 n 條垂直線，垂直線 i 的兩個端點(diǎn)分別為 (i, ai) 和 (i, 0)。找出其中的兩條線，使得它們與 x 軸共同構(gòu)成的容器可以容納最多的水。
說明：你不能傾斜容器，且 n 的值至少為 2。
示例：
輸入：[1,8,6,2,5,4,8,3,7]
輸出：49
雙指針
由于容納的水量是由兩個指針指向的數(shù)字中較小值 * 指針之間的距離決定的。所以每次我們移動兩個數(shù)字中數(shù)字較小的那個，才有可能使得容納水量變多。
public static int maxArea(int[] height) {
int L = 0;
int R = height.length - 1;
int maxArea = 0;
while (L <= R){
int area = Math.min(height[L], height[R]) * (R - L);
maxArea = Math.max(maxArea, area);
if(height[L] < height[R]){
L++;
}else {
R--;
}
}
return maxArea;
}
螺旋矩陣 II(https://leetcode-cn.com/problems/spiral-matrix-ii/)
給定一個正整數(shù) n，生成一個包含 1 到 n2 所有元素，且元素按順時針順序螺旋排列的正方形矩陣。
示例:
輸入: 3
輸出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
模擬旋轉(zhuǎn)法
關(guān)鍵：使用{0, 1, 0, -1}，{1, 0, -1, 0}，ind % 4的組合模擬方向的旋轉(zhuǎn)
public static int[][] generateMatrix(int n) {
int[][] res = new int[n][n];
int[] raw_dir = {0, 1, 0, -1};
int[] col_dir = {1, 0, -1, 0};
int dir = 0;
int num = 1;
int max = (int) Math.pow(n, 2);
int i=0;
int j=0;
while (num <= max){
if(i < n && i >= 0 && j < n && j >=0 && res[i][j] == 0){
res[i][j] = num++;
}else {
// 回退到前一步
i -= raw_dir[dir];
j -= col_dir[dir];
// 更改方向
dir = (dir + 1) % 4;
}
i += raw_dir[dir];
j += col_dir[dir];
}
return res;
}
設(shè)定邊界法
關(guān)鍵：
1）定義當(dāng)前左右上下邊界 l,r,t,b，初始值 num = 1，迭代終止值 tar = n * n；
2）當(dāng) num <= tar 時，始終按照 從左到右、 從上到下、 從右到左 、從下到上 填入順序循環(huán)，每次填入后：
執(zhí)行 num += 1：得到下一個需要填入的數(shù)字；
更新邊界：例如從左到右填完后，上邊界 t += 1，相當(dāng)于上邊界向內(nèi)縮 1。
class Solution {
public int[][] generateMatrix(int n) {
int l = 0, r = n - 1, t = 0, b = n - 1;
int[][] mat = new int[n][n];
int num = 1, tar = n * n;
while(num <= tar){
for(int i = l; i <= r; i++) mat[t][i] = num++; // left to right.
t++;
for(int i = t; i <= b; i++) mat[i][r] = num++; // top to bottom.
r--;
for(int i = r; i >= l; i--) mat[b][i] = num++; // right to left.
b--;
for(int i = b; i >= t; i--) mat[i][l] = num++; // bottom to top.
l++;
}
return mat;
}
}
搜索二維矩陣 II(https://leetcode-cn.com/problems/search-a-2d-matrix-ii/)
編寫一個高效的算法來搜索 m x n 矩陣 matrix 中的一個目標(biāo)值 target。該矩陣具有以下特性：
每行的元素從左到右升序排列。
每列的元素從上到下升序排列。
示例:
現(xiàn)有矩陣 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
給定 target = 5，返回 true。
給定 target = 20，返回 false。
左下角遍歷法
但凡此類的問題，都可以從左下角（或者右上角）開始遍歷。
算法：
首先，我們初始化一個指向矩陣左下角的 (row，col)指針。然后，直到找到目標(biāo)并返回 true（或者指針指向矩陣維度之外的 (row，col) 為止，我們執(zhí)行以下操作：如果當(dāng)前指向的值大于目標(biāo)值，則可以 “向上” 移動一行。 否則，如果當(dāng)前指向的值小于目標(biāo)值，則可以移動一列。不難理解為什么這樣做永遠(yuǎn)不會刪減正確的答案；因?yàn)樾惺菑淖蟮接遗判虻?，所以我們知道?dāng)前值右側(cè)的每個值都較大。 因此，如果當(dāng)前值已經(jīng)大于目標(biāo)值，我們知道它右邊的每個值會比較大。也可以對列進(jìn)行非常類似的論證，因此這種搜索方式將始終在矩陣中找到目標(biāo)（如果存在）。
public static boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length;
if(m == 0){
return false;
}
int n = matrix[0].length;
if(n == 0){
return false;
}
int r = m-1;
int c = 0;
while (r >= 0 && c < n){
if (target == matrix[r][c]) {
return true;
}
if (target < matrix[r][c]) {
r--;
}else {
c++;
}
}
return false;
}
旋轉(zhuǎn)圖像
按層旋轉(zhuǎn)
1）先按層劃分，比如示例2，可分為兩層，外圈和內(nèi)圈。
2）每層再按照位置旋轉(zhuǎn)，比如示例2，15-5-11-16旋轉(zhuǎn)，13-1-10-12旋轉(zhuǎn)，2-9-7-14旋轉(zhuǎn)即可。
技巧：每一層先確定四個角的坐標(biāo)，然后通過offset就可以比較清晰地得到旋轉(zhuǎn)的四個數(shù)的對應(yīng)坐標(biāo)。
public static void rotate(int[][] matrix) {
int n = matrix.length;
if (n <= 1) {
return;
}
for (int level = 0; level <= n / 2 - 1; level++) {
int start = level;
int end = n - level - 1;
// (start, start) (start, end)
// (end, start) (end, end)
for (int col = start; col < end; col++) {
int offset = col - start;
int temp = matrix[start][start + offset];
matrix[start][start + offset] = matrix[end - offset][start];
matrix[end - offset][start] = matrix[end][end - offset];
matrix[end][end - offset] = matrix[start + offset][end];
matrix[start + offset][end] = temp;
}
}
}
先轉(zhuǎn)置，再翻轉(zhuǎn)每行
public void rotate(int[][] matrix) {
int n = matrix.length;
// transpose matrix
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
int tmp = matrix[j][i];
matrix[j][i] = matrix[i][j];
matrix[i][j] = tmp;
}
}
// reverse each row
for (int i = 0; i < n; i++) {
for (int j = 0; j < n / 2; j++) {
int tmp = matrix[i][j];
matrix[i][j] = matrix[i][n - j - 1];
matrix[i][n - j - 1] = tmp;
}
}
}
