力扣每日一练之二维数组下篇 Day5

2022 年 6 月 17 日
本文字数：2370 字
阅读完需：约 8 分钟

力扣每日一练之二维数组下篇 Day5

🍕前面的话🥞

大家好！本篇文章将介绍 2 周搞定数据结构的题，来自力扣的 36.有效的数独和 73.矩阵置零，本文将以这两道题作为背景，介绍经典的数独以及矩阵模拟，展示语言为 java（博主学习语言为 java)。今天呢，是博主开始刷力扣的第五天，如果有想要开始准备自己的算法面试的同学，可以跟着我的脚步一起，共同进步。大家都是并肩作战的伙伴，一起努力奋力前行，路漫漫其修远兮，吾将上下而求索，相信我们一定都可以拿到自己期望的 offer，冲冲冲！

👩‍💻博客主页：京与旧铺的博客主页
✨欢迎关注🖱点赞🎀收藏⭐留言✒
🔮本文由京与旧铺原创，csdn 首发！
😘系列专栏：java 学习
💻首发时间：🎞2022 年 5 月 9 日🎠
🎨你做三四月的事，八九月就会有答案，一起加油吧
🔏参考在线编程网站：🎧力扣
🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦
🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

🏓导航小助手📻

[TOC]

图片

🥧LeetCode 73.矩阵置零

给定一个 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]]

复制代码

🍭解题思路

我们可以用两个标记数组分别记录每一行和每一列是否有零出现。

具体地，我们首先遍历该数组一次，如果某个元素为 00，那么就将该元素所在的行和列所对应标记数组的位置置为 \text{true}true。最后我们再次遍历该数组，用标记数组更新原数组即可。

🍦源代码

class Solution {    public void setZeroes(int[][] matrix) {        int m = matrix.length, n = matrix[0].length;        boolean[] row = new boolean[m];        boolean[] col = new boolean[n];        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (matrix[i][j] == 0) {                    row[i] = col[j] = true;                }            }        }        for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (row[i] || col[j]) {                    matrix[i][j] = 0;                }            }        }    }}

复制代码

🧀LeetCode 36.有效的数独

请你判断一个 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 存在, 因此这个数独是无效的。

复制代码

🥡解题思路+源代码

class Solution {    public boolean isValidSudoku(char[][] board) {        //定义数字行内出现的次数        int[][] row = new int[9][9];        //定义数字列内出现的次数        int[][] column = new int[9][9];        //定义数字九宫格内出现的次数最大为9次        int[][][] jiugongge = new int[3][3][9];        //遍历数组        for (int i =0;i <9;i++){            for(int j = 0;j<9;j++){                char c = board[i][j];                //只要存在数字                if (c !='.'){                    //把数字-1化成索引下标,c是字符串要减去字符串，-1会报错。                    int index = c-'1';                    //这个时候++意思是第i行这个c值次数+1，默认row第二位就是{1-9}-1；每一行都有可能是1-9                    //例如现在是第一行第一列是9，就在row[1][8]号位置+1                    row[i][index]++;                    //列同理                    column[j][index]++;                    //并且九宫格内次数也要+1,例如也是第1行第一列，i/3 j/3会自动定位到所在的小宫格                    jiugongge[i/3][j/3][index]++;                    //次数大于1就不成立一个数独                    if (row[i][index]>1||column[j][index]>1||jiugongge[i/3][j/3][index]>1) return false;                }            }        }        return true;    }}

复制代码

🌌总结

通过这两道题，我们学习了数独的特性和矩阵模拟，复习了数组和循环的知识，那么呢，期待一下下一篇文章吧，和我一起进步，每天努力多一些，迈出更大的一步

觉得文章写的不错的亲亲，点赞评论关注走一波，爱你们哦🛴

发布于: 刚刚阅读数: 4

Geek_b91541

关注

还未添加个人签名 2022.06.02 加入

还未添加个人简介

发布

暂无评论

创作场景

力扣每日一练之二维数组下篇 Day5

力扣每日一练之二维数组下篇 Day5

🥧LeetCode 73.矩阵置零

🍭解题思路

🍦源代码

🧀LeetCode 36.有效的数独

🥡解题思路+源代码

🌌总结

觉得文章写的不错的亲亲，点赞评论关注走一波，爱你们哦🛴

Geek_b91541

评论