fucking-algorithm
fucking-algorithm copied to clipboard
Published
20 hours ago •
labuladong
labuladong
二维数组的花式遍历技巧 :: labuladong的算法小抄
48题的
// 将二维矩阵原地顺时针旋转 90 度
public void rotate(int[][] matrix) {
int n = matrix.length;
// 先沿对角线镜像对称二维矩阵
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
// swap(matrix[i][j], matrix[j][i]);
int temp = matrix[i][j];
matrix[i][j] = matrix[j][i];
matrix[j][i] = temp;
}
}
// 然后反转二维矩阵的每一行
for (int[] row : matrix) {
reverse(row);
}
}
镜像对称那里是不是可以优化下 int j = i + 1
48题 旋转图像 按照左上到右下的对角线进行镜像对称，反转二维矩阵这里应该是翻转列
// 然后反转二维矩阵的前后行
for (int[] row : matrix) {
reverse(row);
}
//LC48 逆时针时针90度翻转
public void rotate1(int[][] matrix) {
int n = matrix.length;
//沿45度角对折
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
int temp = matrix[i][j];
matrix[i][j] = matrix[n - j - 1][n - i - 1];
matrix[n - j - 1][n - i - 1] = temp;
}
}
//列交互元素
int left = 0, right = n - 1;
while (left < right) {
for (int i = 0; i < n; i++) {
int temp = matrix[i][left];
matrix[i][left] = matrix[i][right];
matrix[i][right] = temp;
}
left++;
right--;
}
}
个人常用的螺旋矩阵的遍历方式，感觉比较易懂O(∩_∩)O
const constexpr int dirs[4][2]={
{0,1},{1,0},{0,-1},{-1,0}
};
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
int m=matrix.size(),n=matrix[0].size();
int size=m*n;
vector<int>ans;
int i=0,j=0,curdir=0;
while(ans.size()<size){
ans.push_back(matrix[i][j]);
int ii=i+dirs[curdir][0],jj=j+dirs[curdir][1];
//越界或已访问
if(ii<0||jj<0||ii>=m||jj>=n||matrix[ii][jj]==1000){
curdir=(curdir+1)%4;
ii=i+dirs[curdir][0],jj=j+dirs[curdir][1];
}
matrix[i][j]=1000;
i=ii;
j=jj;
}
return ans;
}
};
for(int i=0;i<n-1;i++) { for(int j=i+1;j<n;j++){} }
因为最后一行的最右一个元素就是对角线上，不需要翻转，然后每一行是要从对角线往右一个元素开始计数
螺旋数组，还是用模拟比较容易理解上手
public int[][] generateMatrix(int n) {
//结果数组
int[][] res = new int[n][n];
//用来模拟方向的数组
int[][] dp = {
{0, 1},
{1, 0},
{0, -1},
{-1, 0}
};
//表示用哪一个dp数组
int index = 0;
//放置访问标志
boolean[][] visited = new boolean[n][n];
int i = 0, j = 0;
int value = 1;
for (int m = 0; m < n * n; m++) {
res[i][j] = value++;
visited[i][j] = true;
//通过下一步进行判断是否需要转向
int next_i = i + dp[index][0],
next_j = j + dp[index][1];
if (next_i == n ||
next_j == n ||
next_i < 0 ||
next_j < 0 ||
visited[next_i][next_j]) {
index = (index + 1) % 4;
}
i += dp[index][0];
j += dp[index][1];
}
return res;
}
Golang版本螺旋矩阵II
func generateMatrix(n int) [][]int {
size := n*n
matrix := make([][]int, n)
for i:=0; i<n; i++ {
matrix[i] = make([]int, n)
}
upbound, lobound, lebound, ribound := 0, n-1, 0, n-1
for cnt:=1; cnt<=size; {
if upbound <= lobound {
for i:=lebound; i<=ribound; i++ {
matrix[upbound][i] = cnt
cnt++
}
upbound++
}
if lebound <= ribound {
for i:= upbound; i<=lobound; i++ {
matrix[i][ribound] = cnt
cnt++
}
ribound--
}
if upbound <= lobound {
for i:=ribound; i>=lebound; i-- {
matrix[lobound][i] = cnt
cnt++
}
lobound--
}
if lebound <= ribound {
for i:=lobound; i>=upbound; i-- {
matrix[i][lebound] = cnt
cnt++
}
lebound++
}
}
return matrix
}
补充一下原地反转单词顺序的代码
public class RevertWordsInPlace {
public static String reverse(String phrase) {
return new String(reverseWords(phrase.toCharArray()));
}
private static char[] reverseWords(char[] arrays) {
// revert individual words
int start = 0;
for (int end = 0; end < arrays.length; end++) {
if (arrays[end] == ' ') {
reverse(arrays, start, end - 1);
start = end + 1;
}
}
reverse(arrays, start, arrays.length - 1);
// revert the whole phrase
reverse(arrays, 0, arrays.length - 1);
return arrays;
}
private static void reverse(char[] arrays, int start, int end) {
while (start <= end) {
swap(arrays, start, end);
start++;
end--;
}
}
private static void swap(char[] arrays, int start, int end) {
char temp = arrays[start];
arrays[start] = arrays[end];
arrays[end] = temp;
}
}
补充 swift 超易懂版本
func rotate(_ matrix: inout [[Int]]) {
var n = matrix.count
// 对角线镜像数组
for i in 0..<n {
for j in i..<n {
let tmp = matrix[i][j]
matrix[i][j] = matrix[j][i]
matrix[j][i] = tmp
}
}
// 反转数组每一行
for i in 0..<n {
matrix[i].reverse()
}
}
关于矩阵旋转，我是否可以这样操作呢：顺时针旋转90°就是先沿主对角线镜像翻转，然后reverse；逆时针旋转90°就是先reverse，然后在沿主对角线镜像翻转。（主要是我想规避我理不清逆时针旋转里数组角标的问题哈哈哈哈）
Python的：
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix)
for i in range(n):
for j in range(i,n):
matrix[i][j],matrix[j][i] = matrix[j][i],matrix[i][j]
for i in range(n):
_L = 0
_R = n - 1
while _L<_R:
matrix[i][_L],matrix[i][_R] = matrix[i][_R],matrix[i][_L]
_L = _L + 1
_R = _R - 1
第303题C++代码：
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
// KEY WORD : 原地
// 先转置，再逆序
// 步骤1 ： 沿对角线对原矩阵镜像
for(int i = 0;i<matrix.size();i++){
for(int j = i;j<matrix.size();j++)
swap(matrix[i][j],matrix[j][i]);
}
// 步骤2：反转二维矩阵的每一行
for(int i = 0;i<matrix.size();i++){
reverse(matrix[i].begin(),matrix[i].end());
}
}
};
我最开始参照东哥的java代码写了之后，用例测试出来我只进行了转置而没有进行逆序，然后才意识到……C++提供一个reverse()函数可以直接逆序。
如果各位在Rotate Matrix这道题上“以对角线镜像翻转”这个步骤的i和j的设置不清楚的话，建议画个图，看在每一行需要调换的两个值跟len(matrix)有什么关系，之后就很明显啦！
48题 顺时针旋转90度：先水平翻转，然后主对角线翻转。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix[0])
if n == 1:
return
"""solution2"""
"""水平翻转"""
for i in range(n//2):
matrix[i], matrix[n-i-1] = matrix[n-i-1], matrix[i]
"""主对角翻转"""
for i in range(n):
for j in range(i,n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
return
48题 顺时针旋转90度：先水平翻转，然后主对角线翻转。
class Solution:
def rotate(self, matrix: List[List[int]]) -> None:
n = len(matrix[0])
if n == 1:
return
"""solution2"""
"""水平翻转"""
for i in range(n//2):
matrix[i], matrix[n-i-1] = matrix[n-i-1], matrix[i]
"""主对角翻转"""
for i in range(n):
for j in range(i,n):
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
return
// 另一种解法，使用图的遍历方式，右下左上的遍历方法
public List<Integer> spiralOrder(int[][] matrix) {
int m = matrix.length, n = matrix[0].length;
int upper_bound = 0, lower_bound = m - 1;
int left_bound = 0, right_bound = n - 1;
boolean[][] visit = new boolean[m][n];
List<Integer> res = new LinkedList<>();
// 遍历方式 右下左上
int[][] methods = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
// 起始坐标
int[] start = new int[]{0, 0};
res.add(matrix[start[0]][start[1]]);
while(res.size() < m * n) {
// 循环4种遍历方式
for (int[] method : methods) {
int i = start[0] + method[0];
int j = start[1] + method[1];
// 上下左右界限判断
while (i >= upper_bound &&
i <= lower_bound &&
j >= left_bound &&
j <= right_bound && !visit[i][j]){
visit[start[0]][start[1]] = true;
start[0] = i;
start[1] = j;
res.add(matrix[i][j]);
i = start[0] + method[0];
j = start[1] + method[1];
}
}
}
return res;
}
抄的题解的，看着比较简洁易懂，分享给大家 主要思路同dong哥，动态调整上下左右边界
class Solution {
public List<Integer> spiralOrder(int[][] matrix) {
int u = 0, d = matrix.length-1;
int l = 0, r = matrix[0].length-1;
List<Integer> list = new ArrayList<>();
while (true){
for (int i = l; i <= r; i ++) list.add(matrix[u][i]);
if (++u > d) break;
for (int i = u; i <= d; i ++) list.add(matrix[i][r]);
if (--r < l) break;
for (int i = r; i >= l; i --) list.add(matrix[d][i]);
if (--d < u) break;
for (int i = d; i >= u; i --) list.add(matrix[i][l]);
if (++l > r) break;
}
return list;
}
}
48题
// 然后反转二维矩阵的每一行
for (int[] row : matrix) {
reverse(row);
}
这里其实对数组每一列以Y轴为对称轴进行交换即可，时间复杂度可降低到O(n)
