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

🍕前面的话🥞

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

👩‍💻博客主页：京与旧铺的博客主页

✨欢迎关注🖱点赞🎀收藏⭐留言✒

🔮本文由京与旧铺原创，csdn首发！

😘系列专栏：java学习

💻首发时间：🎞2022年5月9日🎠

🎨你做三四月的事，八九月就会有答案，一起加油吧

🔏参考在线编程网站：🎧力扣

🀄如果觉得博主的文章还不错的话，请三连支持一下博主哦

🎧最后的话，作者是一个新人，在很多方面还做的不好，欢迎大佬指正，一起学习哦，冲冲冲

🏓导航小助手📻

图片

🥧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;
     }
 }

🌌总结

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

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