力扣每日一练之二维数组下篇Day5
🍕前面的话🥞
大家好！本篇文章将介绍2周搞定数据结构的题，来自力扣的36.有效的数独和73.矩阵置零，本文将以这两道题作为背景，介绍经典的数独以及矩阵模拟，展示语言为java（博主学习语言为java)。今天呢，是博主开始刷力扣的第五天，如果有想要开始准备自己的算法面试的同学，可以跟着我的脚步一起，共同进步。大家都是并肩作战的伙伴，一起努力奋力前行，路漫漫其修远兮，吾将上下而求索，相信我们一定都可以拿到自己期望的offer，冲冲冲！
👩💻博客主页：京与旧铺的博客主页
✨欢迎关注🖱点赞🎀收藏⭐留言✒
🔮本文由京与旧铺原创
😘系列专栏：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;
}
}