MENU

LeetCode54. 螺旋矩阵&LeetCode59.螺旋矩阵 II&LeetCode48. 旋转图像

August 7, 2018 • Read: 3064 • LeetCode阅读设置

题目链接:LeetCode54

题解

要是去找每次移动下标之间的关系就错了,很难找到,应该从宏观角度去看,首先打印的是最外层一圈,然后打印倒数第二层的一圈,...依次下去,所以应该这么做,找到最左上角的坐标(lx,ly)和最右下角的坐标(rx,ry),让lx加加直到lx=rx,然后让ly加加直到ly=ry,再让rx减减直到rx=lx,最后ry减减直到ry=ly,完了以后将lx,ly加加,rx,ry减减,这样就到了内一层,继续执行旋转,直到rx<lx或ry<ly就停止,注意特殊情况特判即可

代码
class Solution {
    List<Integer> res = new ArrayList<Integer>();
    public List<Integer> spiralOrder(int[][] matrix) {
        res.clear();
        if(matrix.length == 0)
            return res;
        int lx = 0,ly = 0;
        int rx = matrix[0].length - 1,ry = matrix.length - 1;
        while(lx <= rx && ly <= ry) {
            dfs(matrix,lx++,ly++,rx--,ry--);
        }
        return res;
    }
    public void dfs(int[][] arr,int lx,int ly,int rx,int ry) {
        if(ly == ry) 
            while(lx <= rx) 
                res.add(arr[ly][lx++]);
        
        else if(lx == rx) 
            while(ly <= ry) 
                res.add(arr[ly++][lx]);
        
        else {
            int curx = lx,cury = ly;
            while(curx < rx)
                res.add(arr[cury][curx++]);
            while(cury < ry)
                res.add(arr[cury++][rx]);
            while(rx > lx)
                res.add(arr[ry][rx--]);
            while(ry > ly)
                res.add(arr[ry--][lx]);
        }
    }
}

题目链接:LeetCode59

代码
class Solution {
    static int num;
    public int[][] generateMatrix(int n) {
        num = 1;
        int[][] res = new int[n][n];
        if(n == 0)
            return res;
        if(n == 1) {
            res[0][0] = 1;
            return res;
        }
        int lx = 0,ly = 0;
        int rx = n - 1,ry = n - 1;
        while(lx <= rx && ly <= ry) {
            dfs(res,lx++,ly++,rx--,ry--);
        }
        if(n %2 != 0)
            res[n / 2][n / 2] = num;
        return res;
    }
    public void dfs(int[][] res,int lx,int ly,int rx,int ry) {
        int curx = lx,cury = ly;
        while(curx < rx)
            res[cury][curx++] = num++;
        while(cury < ry)
            res[cury++][rx] = num++;
        while(rx > lx)
            res[ry][rx--] = num++;
        while(ry > ly)
            res[ry--][lx] = num++;
    }
}

题目链接:LeetCode48

题解

这三道题几乎都是相同类型的题目,都是跟矩阵旋转有关,说一下这道题的思路,首先获取四个角上的元素,arr[0][0],arr[0][n-1],arr[n-1][n-1],arr[n-1][0],将这四个值进行轮换,对应下图画黑圈的值,然后再换画红圈的值,最后绿圈,最外层完了以后进入内层。

代码
class Solution {
    public void rotate(int[][] matrix) {
        int lx = 0,ly = 0;
        int rx = matrix.length - 1,ry = matrix[0].length - 1;
        while(lx <= rx && ly <= ry) {
            dfs(matrix,lx++,ly++,rx--,ry--);
        }
    }
    public void dfs(int[][] arr,int lx,int ly,int rx,int ry) {
        int times = rx - lx;
        for(int i = 0;i < times;i++) {
            int t = arr[lx][ly + i];
            arr[lx][ly + i] = arr[rx - i][ly];
            arr[rx - i][ly] = arr[rx][ry - i];
            arr[rx][ry - i] = arr[lx + i][ry];
            arr[lx + i][ry] = t;
        }
    }
}
Last Modified: May 12, 2021
Archives Tip
QR Code for this page
Tipping QR Code