LeetCode 36. 有效的數獨

来源:https://www.cnblogs.com/izhoujie/archive/2020/04/03/12629853.html
-Advertisement-
Play Games

我的LeetCode：https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii LeetCode 36. 有效的數獨 題目 判斷一個 9x9 的數獨是否有效。只 ...


我的LeetCode：https://leetcode-cn.com/u/ituring/

我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii

LeetCode 36. 有效的數獨

題目

判斷一個 9x9 的數獨是否有效。只需要__根據以下規則__，驗證已經填入的數字是否有效即可。

  1. 數字 1-9 在每一行只能出現一次。
  2. 數字 1-9 在每一列只能出現一次。
  3. 數字 1-9 在每一個以粗實線分隔的 3x3 宮內只能出現一次。

上圖是一個部分填充的有效的數獨。

數獨部分空格內已填入了數字，空白格用 '.' 表示。

示例 1:

輸入:
[
  ["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:

輸入:
[
  ["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 存在, 因此這個數獨是無效的。

說明:

  • 一個有效的數獨（部分已被填充）不一定是可解的。
  • 只需要根據以上規則，驗證已經填入的數字是否有效即可。
  • 給定數獨序列只包含數字 1-9 和字元 '.' 。
  • 給定數獨永遠是 9x9 形式的。

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/valid-sudoku
著作權歸領扣網路所有。商業轉載請聯繫官方授權，非商業轉載請註明出處。

解題思路

這道題做出來是比較簡單的，暴力來每行每豎每小宮格分別校驗就可以了，這樣看至少需要三次全掃描；
如何做到只掃描一遍就能完成呢？分析後可能發現比較難解決是小宮格的索引問題，其次如果要保存原始數據，應該需要
橫豎小宮格共三個二維數組（或者set集合），但是我們只需要知道1-9這幾個數字有還是沒有以及只能有一個，對應到編碼就是0和1，因此可以進一步壓縮二維數組為一位數組，
每個數組的int的前9個bit位用來存儲1-9是否出現過且僅出現過一次，綜上，從需要三次掃描三個二維數組到一次掃描三個二維數組再到最後一次掃描三個一維數組，演算法的效率提升是非常明顯的；

思路1-三遍掃描，橫豎小宮格各自作校驗

步驟：

  1. 新建三個set對應橫豎小宮格；
  2. 三次掃描分別校驗橫豎小宮格；

思路2-只掃描一次

只掃描一次的關鍵是定位小宮格的索引：
關鍵點小宮格的索引公式：（i/3）*3 + j/3;

可以這麼理解：
- i/3表示第幾行的小宮格，取值為0、1、2對應實際的第一、二、三行；
- （i/3）3表示第i/3的小宮格下標的的起始數字，比如第一行是從0開始，第二行是從3開始，第三行是從6開始；
- j/3表示所在行的第j/3個宮格，取值為0、1、2對應實際的第一、二、三個小宮格；
- （i/3）3 + j/3 組合起來就是：前半段表示小宮格的所在行及起始下標，後半段表示當前行的第幾個小宮格，組合的所有可能值0、1、2、3、、4、5、6、7、8就對應九個小宮格；

思路3-只掃描一次，進一步壓縮輔助空間，使用bit位記錄數據

實際做法和代碼與思路2無太大區別，唯一的區別是數組換位一維的，校驗時使用位記錄和對比校驗；

演算法源碼示例

package leetcode;

import java.util.HashSet;

/**
 * @author ZhouJie
 * @date 2020年2月1日 下午4:30:05 
 * @Description: 36. 有效的數獨
 *
 */
public class LeetCode_0036 {

}

class Solution_0036 {
	/**
	 * @author ZhouJie
	 * @date 2020年2月1日 下午8:27:14 
	 * @Description: TODO(方法簡述) 
	 * @return boolean 
	 * @UpdateUser-UpdateDate:[ZhouJie]-[2020年2月1日 下午8:27:14]  
	 * @UpdateRemark:1-行列小宮格分別遍歷校驗，使用一個set
	 *
	 */
	public boolean isValidSudoku_1(char[][] board) {
		if (board == null) {
			return false;
		}
		HashSet<Character> set = new HashSet<Character>();
		// 行列判斷
		for (int x = 0; x < 9; x++) {
			set.clear();
			// 行判斷
			for (int y = 0; y < 9; y++) {
				if (!check(set, board[x][y])) {
					return false;
				}
			}
			set.clear();
			// 列判斷
			for (int y = 0; y < 9; y++) {
				if (!check(set, board[y][x])) {
					return false;
				}
			}
		}
		// 小宮格判斷，先定位單個小宮格位置，再遍歷小宮格的數字
		for (int i = 0; i < 9; i += 3) {
			for (int j = 0; j < 9; j += 3) {
				set.clear();
				for (int x = 0; x < 3; x++) {
					for (int y = 0; y < 3; y++) {
						if (!check(set, board[x + i][y + j])) {
							return false;
						}
					}
				}
			}
		}
		return true;
	}

	private boolean check(HashSet<Character> set, char c) {
		if (c == '.') {
			return true;
		} else if (set.contains(c)) {
			return false;
		} else {
			set.add(c);
			return true;
		}
	}

	/**
	 * @author ZhouJie
	 * @date 2020年2月1日 下午8:27:38 
	 * @Description: TODO(方法簡述) 
	 * @return boolean 
	 * @UpdateUser-UpdateDate:[ZhouJie]-[2020年2月1日 下午8:27:38]  
	 * @UpdateRemark:2-行列小宮格各自使用自己的校驗空間同時校驗，一次遍歷 
	 *
	 */
	public boolean isValidSudoku_2(char[][] board) {
		// 行列小宮格的編號
		int[][] rows = new int[9][9];
		int[][] columns = new int[9][9];
		int[][] boxes = new int[9][9];

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				char c = board[i][j];
				if (c != '.') {
					int num = c - '1';
					// 關註點，計算小宮格索引公式
					int boxIndex = (i / 3) * 3 + j / 3;
					// 行判斷
					if (rows[i][num] == 1) {
						return false;
					} else {
						rows[i][num] = 1;
					}
					// 列判斷
					if (columns[j][num] == 1) {
						return false;
					} else {
						columns[j][num] = 1;
					}
					// 小宮格判斷
					if (boxes[boxIndex][num] == 1) {
						return false;
					} else {
						boxes[boxIndex][num] = 1;
					}
				}
			}
		}
		return true;
	}

	/**
	 * @author: ZhouJie
	 * @date: 2020年4月3日 下午9:30:03 
	 * @param: @param board
	 * @param: @return
	 * @return: boolean
	 * @Description: 3-進一步壓縮空間，使bit位來計算數據
	 *
	 */
	public boolean isValidSudoku_3(char[][] board) {
		// 行列小宮格的編號
		int[] rows = new int[9];
		int[] columns = new int[9];
		int[] boxes = new int[9];

		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				char c = board[i][j];
				if (c != '.') {
					int num = c - '1';
					// 關註點，計算小宮格索引公式
					int boxIndex = (i / 3) * 3 + j / 3;
					// 行判斷
					if (((rows[i] >> num) & 1) == 1) {
						return false;
					} else {
						rows[i] |= 1 << num;
					}
					// 列判斷
					if (((columns[j] >> num) & 1) == 1) {
						return false;
					} else {
						columns[j] |= 1 << num;
					}
					// 小宮格判斷
					if (((boxes[boxIndex] >> num) & 1) == 1) {
						return false;
					} else {
						boxes[boxIndex] |= 1 << num;
					}
				}
			}
		}
		return true;
	}
}

您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 記錄一個不同的流媒體網站實現方法，和用Python爬蟲爬它的坑
    今天找到一片電影，想把它下載下來。 先開Networks工具分析一下： 初步分析發現，視頻載入時會拉取TS格式的文件，推測這是一個m3u8的索引，記錄著幾百段TS文件，這樣方便快進時載入。 但是實際分析m3u8文件時，發現這並不是一個有效的索引文件，應該只是載入一個形式，實際的handler在其他地 ...
  • 實際開發中 dao、entity的代碼怎樣自動生成？一款工具送給你
    01 關註"一猿小講"朋友，都知道以往的文章一直倡導拒絕 CRUD，那到底什麼是 CRUD？今天咱們就聊聊 Java 妹子小猿與資料庫老頭交互的事兒。 產品小汪鏗鏘有力的說：小猿同學，咱們近期要推一爆款產品，你先實現用戶基本的登錄的功能。 啥玩意？小猿內心嘀咕嘀咕：爆款產品，還基本的登錄，那不就是實 ...
  • 徒手打造一款為業務賦能的小工具，另附實戰經驗。
    線上應用程式升級，需要把缺失的數據關聯補充一下，你寫個程式處理一下？ 客戶信息同步，由於是線上敏感欄位都是加密處理，所以需要你再寫個程式解密處理一下？ 曾記得 N 年前，我經常幹這種事情，碼這種代碼。今天回過頭來，對此類事情簡單做一個分享，以防你們也遇到此類問題，不妨拿去實踐一下，說不定會提高效率呢 ...
  • LeetCode 42. 接雨水
    我的LeetCode：https://leetcode cn.com/u/ituring/ 我的LeetCode刷題源碼[GitHub]：https://github.com/izhoujie/Algorithmcii LeetCode 42. 接雨水 題目 給定 n 個非負整數表示每個寬度為 1 ...
  • Java概述(B1)
    Java概述 Java是什麼？ Java is a general purpose programming language that is class based, object oriented, and designed to have as few implementation depend ...
  • python基礎學習-字元串常見操作
    字元串常見操作 索引 切片 字元串的常見操作 應用 判斷是否是小數 ...
  • 吐槽，Java 設計的槽點
    今天不灌水，直接上乾貨！希望下麵的講解，能與你產生一些共鳴。 1. 求長度各有千秋 你是否曾經在面試的時候，經常被問到：數組有沒有 length() 方法？字元串有沒有 length() 方法？ 集合有沒有 length() 方法？ 面對這個問題，那麼不得不吐槽一下，Java 中獲取長度的方式，設計 ...
  • java 基本數據類型對象包裝類
    byte Byte short Short int Integer long Long boolean Boolean char Character float Float double Double 基本數據類型對象包裝類最常見作用：用於基本數據類型和字元串類型之間做轉換。 基本數據類型轉成字元串 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類