力扣每日一練之二維數組下篇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;
    }
}

力扣每日一練之二維數組下篇Day5