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

题目链接: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;
        }
    }
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏小樱的经验随笔

约瑟夫问题方法总结

n个人围成一个圈,每个人分别标注为1、2、...、n,要求从1号从1开始报数,报到k的人出圈,接着下一个人又从1开始报数,如此循环,直到只剩最后一个人时,该人即...

37680
来自专栏格子的个人博客

Java源码阅读之红黑树在HashMap中的应用 - JDK1.8

JDK1.8之前,HashMap并没有采用红黑树,所以哈希桶上的链表过长时,就会有效率问题。

12940
来自专栏菩提树下的杨过

数据结构C#版笔记--啥夫曼树(Huffman Tree)与啥夫曼编码(Huffman Encoding)

哈夫曼树Huffman tree 又称最优完全二叉树,切入正题之前,先看几个定义 1、路径 Path 简单点讲,路径就是从一个指定节点走到另一个指定节点所经过的...

28390
来自专栏包子铺里聊IT

[Google最新面试题] continental divider

给一个矩阵,其中0代表海洋,其他数字代表高度, 秉着水往低处流的原则,求出能够 流向任意海洋的点。 比如说 0 0 0 1 2 3 0 0 1 2 2 4 3 ...

28840
来自专栏云霄雨霁

查找----基于红黑平衡树

14800
来自专栏腾讯数据库技术

如何利用红黑树实现排名?

25430
来自专栏和蔼的张星的图像处理专栏

2. 尾部的零

设计一个算法,计算出n阶乘中尾部零的个数 样例 11! = 39916800,因此应该返回 2. 这其实是一个数学题,思路倒是很简单,主要就是找每个数有多...

14030
来自专栏小樱的经验随笔

洛谷 P1876 开灯(思维,枚举,规律题)

P1876 开灯 题目背景 该题的题目是不是感到很眼熟呢? 事实上,如果你懂的方法,该题的代码简直不能再短。 但是如果你不懂得呢?那。。。(自己去想) 题目描述...

30660
来自专栏数据结构与算法

洛谷P4093 [HEOI2016/TJOI2016]序列

题目描述 佳媛姐姐过生日的时候,她的小伙伴从某宝上买了一个有趣的玩具送给他。玩具上有一个数列,数列中某些项的值可能会变化,但同一个时刻最多只有一个值发生变化。现...

32070
来自专栏函数式编程语言及工具

泛函编程(17)-泛函状态-State In Action

    对OOP编程人员来说,泛函状态State是一种全新的数据类型。我们在上节做了些介绍,在这节我们讨论一下State类型的应用:用一个具体的例子来示范如何使...

21180

扫码关注云+社区

领取腾讯云代金券