您现在的位置是:首页 > 正文

每日算法:矩阵篇(在行列都排好序的矩阵中找数、“之”字形打印矩阵、旋转正方形矩阵、转圈打印矩阵)

2024-04-01 03:17:22阅读 1

1、转圈打印矩阵

【题目】 给定一个整型矩阵matrix,请按照转圈的方式打印它。

例如: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

打印结果为:1,2,3,4,8,12,16,15,14,13,9,5,6,7,11, 10,

【要求】 额外空间复杂度为O(1)

思路:我们定义两个点,一个是左上角a[a][b],一个是右下角a[c][d]。坐标就是(a,b)、(c,d)。我们可以打印最外层的数,依次然后a、b都加1,c、d减一,进入内圈。

1    2     3    4

5                 8

9                12

13  14  15  16

然后是内圈:

5    6

10  11

public class Matrix {


    public static void spiralOrderPrint(int[][] matrix){
        int a = 0;
        int b = 0;
        int c = matrix.length - 1;
        int d = matrix[0].length - 1;
        while(a <= c && b <= d){
            printEdge(matrix,a++,b++,c--,d--);
        }
    }

    /**
     * 从左上角arr[a][b]到右下角arr[c][d]
     */
    public static void printEdge(int[][] arr,int a,int b,int c,int d){
        if(a == c){
            for(int i = b;i < d;i++){
                System.out.print(arr[a][i] + " ");
            }
        }else if(b == d){
            for(int i = a;i < c;i++){
                System.out.print(arr[i][b] + " ");
            }
        }else{
            int curR = a;
            int curC = b;
            while(curC != d){
                System.out.print(arr[a][curC] + " ");
                curC++;
            }
            while(curR != c){
                System.out.print(arr[curR][d] + " ");
                curR++;
            }
            while(curC != b){
                System.out.print(arr[c][curC] + " ");
                curC--;
            }
            while(curR != a ){
                System.out.print(arr[curR][b] + " ");
                curR--;
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = { { 1, 2, 3, 4 },
                           { 5, 6, 7, 8 },
                           { 9, 10, 11, 12 },
                           { 13, 14, 15, 16 } };
        spiralOrderPrint(matrix);

    }
}

2、旋转正方形矩阵

【题目】 给定一个整型正方形矩阵matrix,请把该矩阵调整成

顺时针旋转90度的样子。

【要求】 额外空间复杂度为O(1)

思路:依然是有a、b、c、d的坐标

交换对应的节点。

外圈遍历完,就可以进入内圈。

public class RotateMatrix {

    public static void rotateEdge(int[][] arr,int a,int b,int c,int d){
        int times = c - a;
        int temp = 0;
        for(int i = 0; i != times;i++){
            temp = arr[a][b + i];
            arr[a][b + i] = arr[c - i][b];
            arr[c - i][b] = arr[c][d - i];
            arr[c][d - i] = arr[a + i][d];
            arr[a + i][d] = temp;
        }
    }

    public static void rotate(int[][] matrix){
        int a = 0;
        int b = 0;
        int c = matrix.length - 1;
        int d = matrix[0].length - 1;
        while(a < c){
            rotateEdge(matrix,a++,b++,c--,d--);
        }
    }

    public static void printMatrix(int[][] matrix) {
        for (int i = 0; i != matrix.length; i++) {
            for (int j = 0; j != matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
    }
    public static void main(String[] args) {
        int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 },
                { 13, 14, 15, 16 } };
        printMatrix(matrix);
        rotate(matrix);
        System.out.println("=========");
        printMatrix(matrix);

    }
}

3、“之”字形打印矩阵

【题目】 给定一个矩阵matrix,按照“之”字形的方式打印这

个矩阵,例如: 1 2 3 4 5 6 7 8 9 10 11 12

“之”字形打印的结果为:1,2,5,9,6,3,4,7,10,11,8,12

【要求】 额外空间复杂度为O(1)。

这个就有点像以对角线打印输出数据,打印的方向我们可以用一个boolean类型来控制,我们先设置两个点x(a,b),y(c,d)。起初都是指向1。然后我们有一个规则。

x点向右移动,如果到边界了,就向下移动。

y点向下移动,如果到边界了,就向右移动。

public class zhiziprint {

    public static void printMatrixZigZag(int[][] matrix) {
        int a = 0;
        int b = 0;
        int c = 0;
        int d = 0;
        int endR = matrix.length - 1;
        int endC = matrix[0].length - 1;
        boolean flag = false;
        while (a != endR + 1) {
            printLevel(matrix, a, b, c, d, flag);
            //arr[a][b],移动,这个点只向右移动,如果到头了,向下。
            a = b == endC ? a + 1 : a;
            b = b == endC ? b : b + 1;
            //arr[c][d],移动,这个点只向下移动,如果到头了,向右。
            d = c == endR ? d + 1 : d;
            c = c == endR ? c : c + 1;
            flag = !flag;
        }
        System.out.println();
    }

    public static void printLevel(int[][] arr, int a, int b, int c, int d, boolean flag) {
        if (flag) {
            while (a != c + 1) {
                System.out.print(arr[a++][b--] + " ");
            }
        } else {
            while(c != a - 1){
                System.out.print(arr[c--][d++] + " ");
            }
        }
    }

    public static void main(String[] args) {
        int[][] matrix = { { 1, 2, 3, 4 }, { 5, 6, 7, 8 }, { 9, 10, 11, 12 } };
        printMatrixZigZag(matrix);

    }

}

4、在行列都排好序的矩阵中找数

【题目】 给定一个有N*M的整型矩阵matrix和一个整数K,matrix的每一行和每一 列都是排好序的。实现一个函数,判断K

是否在matrix中。 例如: 0 1 2 5 2 3 4 7 44 4 8 5 7 7 9 如果K为7,返回true;如果K为6,返回false。

【要求】 时间复杂度为O(N+M),额外空间复杂度为O(1)。

思路:我们采用从右上角开始查找。

1    3     5      6

2    5     7      9

4    6     8     10

我们指针指向6开始查找如果指向的数比要查找的数大,那么指向的数下面的一列就都不存在满足条件的了。那么指针向左移动。

如果指向的数比要查找的数小那么所在行就都可以抛弃了,然后向下移动。最后就能找到要查找的数,或者没找到。

public class FindMatrix {

    public static boolean findNum(int[][] arr,int num){
        //a、b是右上角两个数
        int a = 0;
        int b = arr[0].length - 1;
        int len = arr.length;

        while( a <= len - 1 && b >= 0){
            if(arr[a][b] > num){
                b--;
            }else if(arr[a][b] < num){
                a++;
            }else{
                return true;
            }
        }
        return false;

    }

    public static void main(String[] args) {
        int[][] matrix = { { 1, 3, 5,6 }, { 2,5,7,9}, {4,6,8,10 }};
        System.out.println(findNum(matrix,6));
    }
}	 

 

网站文章

  • R语言泊松回归

    泊松回归涉及回归模型,其响应变量是计数形式而不是分数数字。 例如,计算出生人数或一个足球比赛系列中的胜率数。响应变量的值也遵循泊松分布。泊松回归的一般数学方程为 -log(y) = a + b1x1 + b2x2 + bnxn.....以下是使用的参数的描述 -y - 是响应变量。 a 和 b 是数字系数。 x - 是预测变量。用于创建泊松回归模型的函数是glm()函数。...

    2024-04-01 03:17:16
  • Zabbix配置邮件告警

    Zabbix配置邮件告警

    告警发送是监控系统的重要功能之一 , 在配置好触发器(Trigger),将告警表达式定义好后,我们需要设置规则,比如设置当告警发生后,是否需要发送告警,以及将什么样内容的告警发送给谁等。

    2024-04-01 03:17:09
  • Dart Map对象Interface接口的实现

    Dart Map对象Interface接口的实现, 指定Map对象里的键值对

    2024-04-01 03:16:24
  • 数据库——视图

    数据库——视图

    视图一、视图概念二、 为什么要使用视图三、 性能问题四、 定义视图五、 查看视图六、 删除视图一、视图概念视图(View)是一种虚拟存在的表,对于使用视图的用户来说基本上是透明的。视图并不在数据库中实...

    2024-04-01 03:16:16
  • ZYNQ 安装ubuntu文件系统

    ZYNQ 安装ubuntu文件系统

    ZYNQ 7020 Ubuntu16.04文件系统安装 在关于zynq openamp的章节我们已经完成了zynq 的u-boot,内核,设备树的制作,通过XSDK完成了启动文件的创建。 同样道理制作...

    2024-04-01 03:16:09
  • 正则表达式

    正则表达式

    正则表达式可以更简单的进行数据合法性判断,介绍正则表达式的书写,匹配方法,案例实现,数据筛选

    2024-04-01 03:15:30
  • 【Python】多线程

    import threadingimport time class myThread (threading.Thread): #继承父类threading.Thread def __init__(self, threadID, name): threading.Thread.__init__(self) self.name = na...

    2024-04-01 03:15:23
  • eureka使用总结

    eureka使用总结

    目录Eureka常用配置Eureka 单节点搭建eureka多节点服务注册的配置选项Eureka单独使用Rest服务调用/eureka/status 服务状态注册到eureka的服务信息查看注册到eu...

    2024-04-01 03:15:15
  • NFT细分赛道分类及代表项目汇总

    NFT细分赛道分类及代表项目汇总

    NFT是Non-Fungible Token的缩写,中文称为「非同质化代币」,通常是指开发者在以太坊平台上根据ERC721标准/协议所发行的代币,它的特性为不可分割、不可替代、独一无二的,简单来说,采...

    2024-04-01 03:14:36
  • JSP JAVA javaweb仓库库存管理系统(仓库进销存管理系统库存管理系统仓库管理系统)

    JSP JAVA javaweb仓库库存管理系统(仓库进销存管理系统库存管理系统仓库管理系统)

    JSP仓库库存管理系统(仓库进销存管理系统库存管理系统仓库管理系统)

    2024-04-01 03:14:29