C++算法题 - 矩阵

目录

  • 36. 有效的数独
  • 54. 螺旋矩阵
  • 48. 旋转图像
  • 73. 矩阵置零
  • 289. 生命游戏

36. 有效的数独

LeetCode_link

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：
一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 '.' 表示。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]

输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

思路：统计数字的出现次数，一旦出现超过一次，就失败。注意这个题不需要判断题是否有解。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int rows[9][9] = {0};
        int cols[9][9] = {0};
        int inside[9][9] = {0};
        for(int i = 0; i < 9; i ++){
            for(int j = 0; j < 9; j++){
                if(board[i][j] < '0' || board[i][j] > '9')  continue;
                int num = board[i][j] - '0';
                //行
                if(rows[i][num - 1] > 0){
                    return false;
                }else{
                    rows[i][num - 1] ++;
                }

                //列
                if(cols[j][num - 1] > 0){
                    return false;
                }else{
                    cols[j][num - 1] ++;
                }

                //内
                if(inside[(i/3)*3 + j/3][num - 1] > 0){
                    return false;
                }else{
                    inside[(i/3)*3 + j/3][num - 1] ++;
                }
            }
        }
        return true;
    }
};

54. 螺旋矩阵

LeetCode_link

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

示例 1：
在这里插入图片描述
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：
在这里插入图片描述
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]

提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

思路：一圈圈来

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        int row = matrix.size(), col = matrix[0].size();
        int circle = min((row + 1) / 2, (col + 1) / 2);
        vector<int> temp, rec;
        for(int i = 0; i < circle; i++){
            temp = one_circle(matrix ,row, col, i);
            rec.insert(rec.end(), temp.begin(), temp.end());
        }
        return rec;

    }
    vector<int> one_circle(vector<vector<int>>& matrix, int row, int col, int circle){
        int i = circle, j = circle;
        vector<int> rec;
        rec.push_back(matrix[i][j]);
        while(j < col - circle - 1){ //向右
            j ++;
            rec.push_back(matrix[i][j]);
        }
        while(i < row - circle - 1){ //向下
            i ++;
            rec.push_back(matrix[i][j]);
        }
        while(row - circle * 2 >= 2 && j > circle){ //向左（如果行是1，就不走了）
            j --;
            rec.push_back(matrix[i][j]);
        }
        while(col - circle * 2 >= 2 && i > circle + 1){ //向上（如果列是1，就不走了）
            i --;
            rec.push_back(matrix[i][j]);
        }
        return rec;
    }
};

48. 旋转图像

LeetCode_link

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：
在这里插入图片描述
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：
在这里插入图片描述
输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：
n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

思路：四角旋转

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int row = matrix.size();
        int circle = ceil((row + 1) / 2);
        for(int i = 0; i < circle; i ++){
            turn_one_circle(matrix, row, i);
        }
    }
    void turn_one_circle(vector<vector<int>>& matrix, int row, int circle){
        int temp;
        row -= 1;
        for(int i = 0; i < row - circle * 2; i++){
            temp = matrix[circle][circle + i];
            matrix[circle][circle + i] = matrix[row - circle - i][circle];
            matrix[row - circle - i][circle] = matrix[row - circle][row - circle - i];
            matrix[row - circle][row - circle - i] = matrix[circle + i][row - circle];
            matrix[circle + i][row - circle] = temp;
        }
    }
};

也可以先水平旋转，再主对角线旋转

73. 矩阵置零

LeetCode_link

给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。

示例 1：
在这里插入图片描述
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]

示例 2：
在这里插入图片描述
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]

提示：
m == matrix.length
n == matrix[0].length
1 <= m, n <= 200
-231 <= matrix[i][j] <= 231 - 1

思路：使用标记数组，一个记录行，一个记录列

class Solution {
public:
    void setZeroes(vector<vector<int>>& matrix) {
        int m = matrix.size(), n = matrix[0].size();
        vector<int> row(m);
        vector<int> col(n);
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(matrix[i][j] == 0){
                    row[i] = 1;
                    col[j] = 1;
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(row[i] == 1 || col[j] == 1){
                    matrix[i][j] = 0;
                }
            }
        }

    }
};

289. 生命游戏

LeetCode_link

根据 百度百科 ， 生命游戏 ，简称为 生命 ，是英国数学家约翰·何顿·康威在 1970 年发明的细胞自动机。

给定一个包含 m × n 个格子的面板，每一个格子都可以看成是一个细胞。每个细胞都具有一个初始状态： 1 即为 活细胞 （live），或 0 即为 死细胞 （dead）。每个细胞与其八个相邻位置（水平，垂直，对角线）的细胞都遵循以下四条生存定律：

  1. 如果活细胞周围八个位置的活细胞数少于两个，则该位置活细胞死亡；
  2. 如果活细胞周围八个位置有两个或三个活细胞，则该位置活细胞仍然存活；
  3. 如果活细胞周围八个位置有超过三个活细胞，则该位置活细胞死亡；
  4. 如果死细胞周围正好有三个活细胞，则该位置死细胞复活；

下一个状态是通过将上述规则同时应用于当前状态下的每个细胞所形成的，其中细胞的出生和死亡是同时发生的。给你 m x n 网格面板 board 的当前状态，返回下一个状态。

示例 1：
在这里插入图片描述
输入：board = [[0,1,0],[0,0,1],[1,1,1],[0,0,0]]
输出：[[0,0,0],[1,0,1],[0,1,1],[0,1,0]]

示例 2：
在这里插入图片描述
输入：board = [[1,1],[1,0]]
输出：[[1,1],[1,1]]

提示：
m == board.length
n == board[i].length
1 <= m, n <= 25
board[i][j] 为 0 或 1

思路：使用额外的数组

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        int rec[m][n];
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int live = live_cell(board, i, j);
                if(board[i][j] == 1){
                    if(live < 2)    rec[i][j] = 0;
                    if(live == 2 || live == 3)  rec[i][j] = 1;
                    if(live > 3)    rec[i][j] = 0;
                }else{
                    if(live == 3){
                        rec[i][j] = 1;
                    }else{
                        rec[i][j] = 0;
                    }
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                board[i][j] = rec[i][j];
            }
        }
    }
    int live_cell(vector<vector<int>> board, int now_i, int now_j){
        int m = board.size(), n = board[0].size();
        int row[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
        int col[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
        int count = 0;
        for(int k = 0; k < 8; k++){
            if(now_i + row[k] >= 0 && now_i + row[k] < m && now_j + col[k] >= 0 && now_j + col[k] < n){
                if(board[now_i + row[k]][now_j + col[k]] == 1){
                    count ++;
                }
            }
        }
        return count;
    }
};

思路：不使用额外的数组，但是使用额外的标记，-1本死但活，2本活但死

class Solution {
public:
    void gameOfLife(vector<vector<int>>& board) {
        int m = board.size(), n = board[0].size();
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                int live = live_cell(board, i, j);
                if(board[i][j] == 1){
                    if(live < 2)    board[i][j] = 2;
                    if(live == 2 || live == 3)  board[i][j] = 1;
                    if(live > 3)    board[i][j] = 2;
                }else{
                    if(live == 3){
                        board[i][j] = -1;
                    }else{
                        board[i][j] = 0;
                    }
                }
            }
        }
        for(int i = 0; i < m; i++){
            for(int j = 0; j < n; j++){
                if(board[i][j] == -1)   board[i][j] = 1;
                if(board[i][j] == 2)   board[i][j] = 0;
            }
        }
    }
    int live_cell(vector<vector<int>> board, int now_i, int now_j){
        int m = board.size(), n = board[0].size();
        int row[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
        int col[8] = {-1, 0, 1, -1, 1, -1, 0, 1};
        int count = 0;
        for(int k = 0; k < 8; k++){
            if(now_i + row[k] >= 0 && now_i + row[k] < m && now_j + col[k] >= 0 && now_j + col[k] < n){
                if(board[now_i + row[k]][now_j + col[k]] >= 1){
                    count ++;
                }
            }
        }
        return count;
    }
};

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/553321.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

【IoTDB 线上小课 02】开源增益的大厂研发岗面经

【IoTDB 线上小课 02】开源增益的大厂研发岗面经

还有友友不知道我们的【IoTDB 视频小课】系列吗&#xff1f; 关于 IoTDB&#xff0c;关于物联网&#xff0c;关于时序数据库&#xff0c;关于开源...给我们 5 分钟&#xff0c;持续学习&#xff0c;干货满满~ 5分钟学会 大厂研发岗面试 之前的第一期小课&#xff0c;我们听了 I…
阅读更多...
SpringMVC（二）【请求与响应】

SpringMVC（二）【请求与响应】

0、测试环境 我们简化开发&#xff0c;创建一个简单的环境&#xff08;因为没有其它包比如 service、dao&#xff0c;所以这里不用 Spring 容器&#xff0c;只用 SpringMVC 容器&#xff09;&#xff1a; Servelet 容器配置&#xff1a; package com.lyh.config;import org.s…
阅读更多...
jmeter及PTS压测介绍和使用

jmeter及PTS压测介绍和使用

一、常用压测工具&#xff1a; loadrunner apache ab&#xff08;单接口压测最方便&#xff09; jmeter 阿里云PTS&#xff08;原生上传jmeter脚本进行压测&#xff09; 二、jmeter可以压测不同的协议和应用 web http https jdbc for database TCP 三、使用场景及优点 1、功能…
阅读更多...
飞行机器人专栏（十四）-- Kinect DK 人体骨骼点运动提取方法

飞行机器人专栏（十四）-- Kinect DK 人体骨骼点运动提取方法

系列文章目录 Ubuntu 18.04/20.04 CV环境配置&#xff08;下&#xff09;--手势识别TRTposeKinect DK人体骨骼识别_ubuntu kinect骨骼测试-CSDN博客文章浏览阅读1.3k次。trt_pose_ros kinect实现手势识别和人体骨骼识别&#xff0c;用于机器人运动控制参考_ubuntu kinect骨骼测…
阅读更多...
SpringCloud(一)

SpringCloud(一)

微服务框架 一、分布式架构 分布式架构︰根据业务功能对系统进行拆分&#xff0c;每个业务模块作为独立项目开发&#xff0c;称为一个服务。 优点: 降低服务耦合有利于服务升级拓展 微服务是一种经过良好架构设计的分布式架构方案&#xff0c;微服务架构特征: 单一职责:微…
阅读更多...
【函数式接口使用✈️✈️】通过具体的例子实现函数结合策略模式的使用

【函数式接口使用✈️✈️】通过具体的例子实现函数结合策略模式的使用

目录 前言 一、核心函数式接口 1. Consumer 2. Supplier 3. Function,> 二、场景模拟 1.面向对象设计 2. 策略接口实现&#xff08;以 Function 接口作为策略&#xff09; 三、对比 前言 在 Java 8 中引入了Stream API 新特性&#xff0c;这使得函数式编程风格进…
阅读更多...
数据库工具解析之 OceanBase 数据库导出工具

数据库工具解析之 OceanBase 数据库导出工具

背景 大多数的数据库都配备了自己研发的导入导出工具&#xff0c;对于不同的使用者来说&#xff0c;这些工具能够发挥不一样的作用。例如&#xff1a;DBA可以使用导数工具进行逻辑备份恢复&#xff0c;开发者可以使用导数工具完成系统间的数据交换。这篇文章主要是为OceanBase…
阅读更多...
编曲知识20：人声和声处理 分轨导出 总线处理

编曲知识20：人声和声处理 分轨导出 总线处理

和声处理 和声 声像注意不要和主旋律重叠 各个效果器的处理幅度可以更大 呼吸音可直接去掉 尽量不要和主旋律共用一个混响延迟轨 注意音量、注意主次 和声拓展-模拟合唱 录制两轨同八度的主旋律或低八度高八度的主旋律 声像左右分配 音量拉低 将各个合唱轨进行失真处理 …
阅读更多...
【Pytorch】VSCode实用技巧 - 默认终端修改为conda activate pytorch

【Pytorch】VSCode实用技巧 - 默认终端修改为conda activate pytorch

VScode修改配置使得启动终端为conda环境 VScode跑项目&#xff0c;在启动pytorch项目时往往会有千奇百怪的问题&#xff0c;最常见的就是显示“conda activate pytorch”后会要求“conda init”&#xff0c;但输入后实际上也不行&#xff0c;这是因为VSCode默认终端为 Powersh…
阅读更多...
网站模板-慈善捐赠基金会网站模板 Bootstrap4 html

网站模板-慈善捐赠基金会网站模板 Bootstrap4 html

目录 一.前言 二.预览 三.下载链接 一.前言 这是一个慈善网站的页面。页面包含了导航栏、横幅部分、关于、使命、新闻、活动、捐赠和页脚等不同的部分。该网站还包含了一些CSS样式和JavaScript脚本来实现交互和样式效果。 这个网站的具体结构如下&#xff1a; 导航栏部分&a…
阅读更多...
kafka---topic详解

kafka---topic详解

一、分区与高可用 在Kafka中，事件（events 事件即消息）是以topic的形式进行组织的；同时topic是分区（partitioned）的，这意味着一个topic分布在Kafka broker上的多个“存储桶”(buckets)上。这种数据的分布式放置对于可伸缩性非常重要，因为它允许客户端应用程序同时从多个…
阅读更多...
第十三章 使用深度和法线纹理

第十三章 使用深度和法线纹理

获取深度和法线纹理 背后的原理 深度纹理是一张渲染纹理，它里面存储的像素值不是颜色，而是一个高精度的深度值。深度值范围是[0, 1]，非线性分布的。这些深度值来自于顶点变换后得到的归一化的设备坐标(NDC)。一个模型想要被绘制在屏幕上，需要把它的顶点从模型空间变换到齐…
阅读更多...
OpenCV从入门到精通实战(三)——全景图像拼接

OpenCV从入门到精通实战(三)——全景图像拼接

全景图像拼接实现 定义 Stitcher 的类&#xff0c;用于实现两张图片的拼接。使用的技术是基于 SIFT 特征点检测与匹配&#xff0c;以及利用视角变换矩阵来对齐和拼接图像。 import numpy as np import cv2class Stitcher:#拼接函数def stitch(self, images, ratio0.75, repro…
阅读更多...
云手机助力舆情监测，智慧引领信息时代

云手机助力舆情监测，智慧引领信息时代

随着信息时代的到来&#xff0c;舆情监测已成为政府、企业、高校、金融机构等各行业的必备利器。在这个信息爆炸的时代&#xff0c;如何及时准确地感知民意、把握市场动态&#xff0c;已成为各界迫切需要解决的问题。而云手机作为信息时代的新生力量&#xff0c;在舆情监测方面…
阅读更多...
C++ UML 类图介绍与设计

C++ UML 类图介绍与设计

1 类图概述 UML(Unified Modeling Language)&#xff0c;即统一建模语言&#xff0c;是用来设计软件的可视化建模语言。它的特点是简单、统一、图形化、能表达软件设计中的动态与静态信息。UML从目标系统的不同角度出发&#xff0c;定义了用例图、类图、对象图、状态图、活动图…
阅读更多...
PostgreSQL的学习心得和知识总结（一百三十八）|深入理解PostgreSQL数据库之Protocol message构造和解析逻辑

PostgreSQL的学习心得和知识总结（一百三十八）|深入理解PostgreSQL数据库之Protocol message构造和解析逻辑

目录结构 注&#xff1a;提前言明 本文借鉴了以下博主、书籍或网站的内容&#xff0c;其列表如下&#xff1a; 1、参考书籍&#xff1a;《PostgreSQL数据库内核分析》 2、参考书籍&#xff1a;《数据库事务处理的艺术&#xff1a;事务管理与并发控制》 3、PostgreSQL数据库仓库…
阅读更多...
牛客 NC205 跳跃游戏(三)【中等 贪心 Java,Go，PHP】

牛客 NC205 跳跃游戏(三)【中等 贪心 Java,Go，PHP】

题目 题目链接&#xff1a; https://www.nowcoder.com/practice/14abdfaf0ec4419cbc722decc709938b 思路 参考答案Java import java.util.*;public class Solution {/*** 代码中的类名、方法名、参数名已经指定&#xff0c;请勿修改&#xff0c;直接返回方法规定的值即可*** …
阅读更多...
带缓存的输入输出流（I/O）

带缓存的输入输出流（I/O）

文章目录 前言一、带缓冲的输入输出流是什么&#xff1f;二、使用方法 1.BufferedInputStream与BufferedOutputStream类2.BufferedReader与BufferedWriter类总结 前言 输入输出流可以视为&#xff0c;从A点把货物搬运至B点。那么带缓冲的意思可以视为用货车把A点的货物搬运至B点…
阅读更多...
代码随想录算法训练营DAY28(记录)|C++回溯算法Part.5|491.递增子序列、46.全排列、47.全排列II

代码随想录算法训练营DAY28(记录)|C++回溯算法Part.5|491.递增子序列、46.全排列、47.全排列II

文章目录 491.递增子序列思路伪代码CPP代码优化代码 46.全排列思路伪代码CPP代码 47.全排列IICPP代码 491.递增子序列 力扣题目链接 文章链接&#xff1a;491.递增子序列 视频连接&#xff1a;回溯算法精讲&#xff0c;树层去重与树枝去重 | LeetCode&#xff1a;491.递增子序列…
阅读更多...
安装GPT 学术优化 (GPT Academic)@FreeBSD

安装GPT 学术优化 (GPT Academic)@FreeBSD

GPT 学术优化 (GPT Academic)是一个非常棒的项目 可以帮助我们完成中科院的一些日常工作。 官网&#xff1a;GitHub - binary-husky/gpt_academic: 为GPT/GLM等LLM大语言模型提供实用化交互接口&#xff0c;特别优化论文阅读/润色/写作体验&#xff0c;模块化设计&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023