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

🍕前面的话🥞

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

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

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

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

😘系列专栏：java学习

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

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

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

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

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

🏓导航小助手📻

文章目录

• 力扣每日一练之二维数组下篇Day5
• • @[toc]
• 🥧LeetCode 73.矩阵置零
• 🍭解题思路
• 🍦源代码
• 🧀LeetCode 36.有效的数独
• 🥡解题思路+源代码
• 🌌总结
• • 觉得文章写的不错的亲亲，点赞评论关注走一波，爱你们哦🛴

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

🌌总结

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

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