首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >LeetCode54. 螺旋矩阵&LeetCode59.螺旋矩阵 II&LeetCode48. 旋转图像

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

作者头像
mathor
发布2018-08-17 15:51:36
4380
发布2018-08-17 15:51:36
举报
文章被收录于专栏:mathormathor
题目链接: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

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

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;
        }
    }
}
本文参与 腾讯云自媒体分享计划,分享自作者个人站点/博客。
原始发表:2018-08-07,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体分享计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 题目链接:LeetCode54
  • 题目链接:LeetCode59
  • 题目链接:LeetCode48
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档