二维数组的花式遍历技巧 :: labuladong的算法小抄

[labuladong]

文章链接点这里：二维数组的花式遍历技巧

评论礼仪 见这里，违者直接拉黑。

[FredGoo]

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

[labuladong]

可以优化

[PengHongfu]

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--;
        }
    }

[wangnan0916]

个人常用的螺旋矩阵的遍历方式，感觉比较易懂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;
    }
};

[NCUCyy]

厉害捏👍

[AfternoonDreamer]

太强了！感谢分享！！

[taoziganbei]

for(int i=0;i<n-1;i++)
{
for(int j=i+1;j<n;j++){}
}

因为最后一行的最右一个元素就是对角线上，不需要翻转，然后每一行是要从对角线往右一个元素开始计数

[PeachLuis]

螺旋数组，还是用模拟比较容易理解上手

 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;
    }

[walleve-z]

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
}

[YifangDONG]

补充一下原地反转单词顺序的代码

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;
    }
}

[shiboys]

用快慢指针的话，目测比你的简单些

String reverseWords(String s) {
        char[] charArr = s.toCharArray();
        // 先将所有字符都反转
        swapChars(charArr, 0, charArr.length - 1);
        // 再将相关单词反转
        int slow = 0, fast = 1;
        int n = charArr.length;
        while (fast <= n) {
            if (fast == n || (charArr[fast] == ' ')) {
                swapChars(charArr, slow, fast - 1);
                slow = fast+1;
            }
            fast++;
        }
        return new String(charArr);
    }

void swapChars(char[] arr, int start, int end) {
        if (start == end) {
            return;
        }
        char tmp;
        while (start < end) {
            tmp = arr[start];
            arr[start] = arr[end];
            arr[end] = tmp;
            start++;
            end--;
        }
    }

[wymann01]

补充 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()
        }
    }

[shiboys]

你丫调用系统的 api reverse 函数，折算啥事？Java 也有 reverse 函数，要求是尽量自己写

[ichengzi]

[labuladong]

@ichengzi 👍👍

[Burkhardttt]

关于矩阵旋转，我是否可以这样操作呢：顺时针旋转90°就是先沿主对角线镜像翻转，然后reverse；逆时针旋转90°就是先reverse，然后在沿主对角线镜像翻转。（主要是我想规避我理不清逆时针旋转里数组角标的问题哈哈哈哈）

[pikapikaaa]

48题为什么用swap就不行呢，我手写交换函数，发现无法让数组实现交换，直接在for里写交换就行，不明白（就是注释掉地的那一行）

[fly-han]

你得传4个下标才行，否则只是传递两个值的话，无法完成。

[ybubuzi]

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

[Ref-Rain07]

打卡 2022.4.18

[musiczh]

妙啊

[didiniubi]

杀了我吧 用84厘米大砍刀

[wqZhi]

分享一下我 54题【Spiral Matrix】的解法

public List<Integer> spiralOrder(int[][] matrix) {
    List<Integer> res = new LinkedList<>();
    int row = matrix.length, col = matrix[0].length;
    int x = 0, y = -1;

    while(true){
        for(int i = 0; i < col; i++){//left to right
            res.add(matrix[x][++y]);
        }
        row--;
        if (row == 0){break;}

        for(int i = 0; i < row; i++){//up to bottom
            res.add(matrix[++x][y]);
        }
        col--;
        if (col == 0){break;}

        for(int i = 0; i < col; i++){//right to left
            res.add(matrix[x][--y]);
        }
        row--;
        if (row == 0){break;}

        for(int i = 0; i < row; i++){//bottom to up
            res.add(matrix[--x][y]);
        }
        col--;
        if (col == 0){break;}
    }  
    return res;
}

[leftstrong]

建立二维坐标系

• rotate90 ：(x, y)-->(y, -x)
• rotate180 ：(x, y)-->(-x, -y)
• rotate270 ：(x, y)-->(-y, x)

int[][] matrix为N*N矩阵

• N为奇数

取值 matrix[N/2][N/2] 为x,y直角坐标系原点，构建Cell(x, y, val)

• N为偶数

补上一行+一列，N++ 后参考奇数情况操作，最后旋转后需要剥去一层皮肤

参考代码

  /**
     * 顺时针旋转90度 (i,j)-->(j,-i)
     */
    Cell[][] rotate90(){
        Cell[][] cellMatrix = buildCell(matrix);
        Cell[][] result = new Cell[N][N];
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                result[i][j] = cellMatrix[i][j].rotate90();
            }
        }
        return result;
    }
/**
     * 根据原始矩阵构建，坐标系矩阵
     * @param matrix
     * @return
     */
    private Cell[][] buildCell(int[][] matrix){
        Cell[][] res = new Cell[N][N];
        int half = N/2;
        int ci,cj;
        for (int i = 0; i < N; i++) {
            ci = -half;
            cj = half - i;
            for (int j = 0; j < N; j++) {
                res[i][j] = new Cell(ci++,cj,matrix[i][j]);
            }
        }
        return res;
    }

class Cell{
        int x;
        int y;
        int val;
        Cell(int x,int y, int val){
            this.x = x;
            this.y = y;
            this.val = val;
        }

        /**
         * 顺时针旋转90度 (x,y)-->(y,-x)
         */
        public Cell rotate90(){
            return new Cell(y,-x,val);
        }

        public Cell rotate180(){
            return new Cell(-x,-y,val);
        }

        public Cell rotate270(){
            return new Cell(-y,x,val);
        }

        protected Cell clone(){
            return new Cell(x,y,val);
        }
    }

[leftstrong]

顶一下，java操作数组下标不能为负数，旋转操作不便，有别的语言支持的，有请嘉宾show出来重新以上旋转矩阵真的思路

[zenyanggongmian1995]

public class LeetCode151 {

  public static String reverseWords(String s) {

    // 切除s的首尾空格
    String trimS = s.trim();

    // 翻转一整个字符串。
    StringBuilder reversedString = new StringBuilder();
    for (int i = trimS.length() - 1; i >= 0; i--) {
      reversedString.append(trimS.charAt(i));
    }
    String tmp1 = reversedString.toString();

    // 将翻转后的字符串按空格切割。
    String[] s1 = tmp1.split(" ");

    // 翻转切割后的每个单字符串
    StringBuilder reverse = new StringBuilder();

    for (int i = 0; i < s1.length; i++) {
      if (!s1[i].equals("")) { // 因为字符串中间可能有多个空格，只关注非空格的部分。
        for (int j = s1[i].length() - 1; j >= 0; j--) {
          reverse.append(s1[i].charAt(j));
        }
        reverse.append(" ");
      }
    }
    //  最后一个字符串也会导致多增加一个尾部空格，去除尾部空格。
    String res = reverse.toString().trim();
    return res;
  }


  public static void main(String[] args) {
    String s = "a good   example";

    System.out.println(reverseWords(s));
  }

}

[EyeDroplyq]

打卡

[CAILeiz]

const arr = [
  [1, 2, 3, 4],
  [5, 6, 7, 8],
  [7, 6, 5, 4],
  [4, 1, 2, 3],
];
const n = arr.length;
// 1. 按照左上角到右上角翻转
for (let i = 0; i < n; i++) {
  for (let j = 0; j < n; j++) {
    if (i < j) {
      [arr[i][j], arr[j][i]] = [arr[j][i], arr[i][j]];
    }
  }
}
for (let i = 0; i < n; i++) {
  for (let j = 0; j <= Math.floor(n / 2); j++) {
    [arr[i][j], arr[i][n - 1 - j]] = [arr[i][n - 1 - j], arr[i][j]];
  }
}

[EchooWww]

感觉螺旋数组while-loop的执行条件可以优化为while (top <= bottom || left <= right) 内存使用会降低一些

[ninja119347]

C++ 螺旋矩阵DP版本

   
 void dp(vector<vector<int>>& matrix, int start, int upper, int low,int left, int right){
        if(upper>low||left>right) return;
        for(int i=left;i<=right;i++){
            matrix[upper][i] = start++;
        }
        for(int i = upper+1;i<=low;i++){
            matrix[i][right] = start++;
        }
        for(int i = right-1;i>=left;i--){
            if(upper!= low) matrix[low][i]=start++;
        }
        for(int i =low-1;i>upper;i--){
            if(left!=right) matrix[i][left]=start++;
        }
        dp(matrix,start,upper+1,low-1,left+1,right-1);
    }
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n,vector<int>(n));
        dp(res,1,0,n-1,0,n-1);
        return res;
    }

[shiboys]

二维数组又玩出了花！

[liudi4046]

其实54题中的前面两个if判断是不需要的，如下代码也可以通过：

class Solution {
    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;
    List<Integer> res = new LinkedList<>();
    // res.size() == m * n 则遍历完整个数组
    while (res.size() < m * n) {

            // 在顶部从左向右遍历
            for (int j = left_bound; j <= right_bound; j++) {
                res.add(matrix[upper_bound][j]);
            }
            // 上边界下移
            upper_bound++;

        

            // 在右侧从上向下遍历
            for (int i = upper_bound; i <= lower_bound; i++) {
                res.add(matrix[i][right_bound]);
            }
            // 右边界左移
            right_bound--;

        
        if (upper_bound <= lower_bound) {
            // 在底部从右向左遍历
            for (int j = right_bound; j >= left_bound; j--) {
                res.add(matrix[lower_bound][j]);
            }
            // 下边界上移
            lower_bound--;
        }
        
        if (left_bound <= right_bound) {
            // 在左侧从下向上遍历
            for (int i = lower_bound; i >= upper_bound; i--) {
                res.add(matrix[i][left_bound]);
            }
            // 左边界右移
            left_bound++;
        }
    }
    return res;
}

}

[Infinite-Unexpired-Love]

翻转字符串的C语言版，可以去除多余空格

//实现原地翻转并去除多余空格
//把从end开始倒数length个字符逆序复制到begin位置
void swapChars(char* arr,int begin,int end,int length){
    char ch;
    while(begin<end&&length--){
        ch=arr[begin];
        arr[begin]=arr[end];
        arr[end]=ch;
        ++begin;
        --end;
    }
}

char* reverseWords(char* s) {
    int slow=0,fast=0;
    int length=(int)strlen(s),wordLen=0;
    //先翻转整个字符串
    swapChars(s,0,length-1,length);

    while(fast<length){
        if(s[fast]==' '&&fast!=0&&s[fast-1]!=' '){
            swapChars(s,slow,fast-1,wordLen);
            //slow要走到翻转的这个单词后的第二个位置，因为每个单词间要有一个空格
            slow+=wordLen+1;
            wordLen=0;
        }
        if(s[fast]!=' '){
            ++wordLen;
        }
        ++fast;
    }
    //如果字符串末尾不是空格说明最后一个单词还没有翻转
    if(s[fast-1]!=' '){
        swapChars(s,slow,fast-1,wordLen);
        slow+=wordLen+1;
    }
    //因为slow走到了最后一个单词后的第二个位置，在上一个位置放置字符串结束符，后面的空格不要了
    s[slow-1]='\0';
    return s;
}

[lm-huang]

好像螺旋矩阵的那道题的while循环并不能起到真正控制循环次数的作用，边界控制和元素总和控制二选一就可以了。如果真的想要用res的容量控制，可以int count = 0。每次添加元素的时候count++，并且把count<元素总和写到每个for循环里去。这样就可以把四个类似 if (left_bound <= right_bound) 这样的边界控制语句全删了。

[CZT0]

不是原地反转字符串，但是简单的golang解法（反转字符串再反转单词）

func reverseString(s string) string {
    runes := []rune(s)
    for i, j := 0, len(runes)-1; i < j; i, j = i+1, j-1 {
        runes[i], runes[j] = runes[j], runes[i]
    }
    return string(runes)
}

// 反转单词顺序
func reverseWords(s string) string {
    // 首先反转整个字符串
    reversed := reverseString(s)

    // 分割字符串
    parts := strings.Split(reversed, " ")
    var res []string

    // 反转每个单词
    for _, part := range parts {
        if part != "" {
            res = append(res, reverseString(part))
        }
    }

    // 用空格拼接单词
    return strings.Join(res, " ")
}

[codezs09]

另一种可视化方法，方便理解镜像达到旋转的效果

BTW为甚么没有上传附件按钮。