螺旋矩阵遍历
给定一个包含 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]
模拟顺时针旋转
绘制螺旋轨迹路径，我们发现当路径超出界限或者进入之前访问过的单元格时，会顺时针旋转方向。
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控制方向转变
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){ // 防止重复
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 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
说明：你不能倾斜容器，且 n 的值至少为 2。
示例：
输入：[1,8,6,2,5,4,8,3,7]
输出：49
双指针
由于容纳的水量是由两个指针指向的数字中较小值 * 指针之间的距离决定的。所以每次我们移动两个数字中数字较小的那个，才有可能使得容纳水量变多。
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/)
给定一个正整数 n，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。
示例:
输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]
模拟旋转法
关键：使用{0, 1, 0, -1}，{1, 0, -1, 0}，ind % 4的组合模拟方向的旋转
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;
}
设定边界法
关键：
1）定义当前左右上下边界 l,r,t,b，初始值 num = 1，迭代终止值 tar = n * n；
2）当 num <= tar 时，始终按照 从左到右、 从上到下、 从右到左 、从下到上 填入顺序循环，每次填入后：
执行 num += 1：得到下一个需要填入的数字；
更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩 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 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 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)指针。然后，直到找到目标并返回 true（或者指针指向矩阵维度之外的 (row，col) 为止，我们执行以下操作：如果当前指向的值大于目标值，则可以 “向上” 移动一行。 否则，如果当前指向的值小于目标值，则可以移动一列。不难理解为什么这样做永远不会删减正确的答案；因为行是从左到右排序的，所以我们知道当前值右侧的每个值都较大。 因此，如果当前值已经大于目标值，我们知道它右边的每个值会比较大。也可以对列进行非常类似的论证，因此这种搜索方式将始终在矩阵中找到目标（如果存在）。
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;
}
旋转图像
按层旋转
1）先按层划分，比如示例2，可分为两层，外圈和内圈。
2）每层再按照位置旋转，比如示例2，15-5-11-16旋转，13-1-10-12旋转，2-9-7-14旋转即可。
技巧：每一层先确定四个角的坐标，然后通过offset就可以比较清晰地得到旋转的四个数的对应坐标。
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;
}
}
}
先转置，再翻转每行
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;
}
}
}
