未分類

Valid Sudoku

Go, HashTable, LeetCode

Valid Sudoku

The Sudoku board could be partially filled, where empty cells are filled with the character ‘.’.

Note:

A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

提示 解題應用
Hash Table Hash Map

Default:

1
2
3
func isValidSudoku(board [][]byte) bool {
}

解答思路:

參數範例:

1
["..4...63.",".........","5......9.","...56....","4.3.....1","...7.....","...5.....",".........","........."]

數讀有玩過的話規則應該都能理解，水平線與垂直線及九宮格間的數字填入1~9皆不可重覆，不過因為給的參數是二元陣列，所以就算是行與列兩者的處理方式也不太一樣，以水平列來說算是最為單純，以上述範例來說，水平的話就跟處理一維陣列資料差不多，只要遍歷每個元素是否重覆即可，不過垂直就沒那麼簡單了，因為以第一個垂直線來說，它需要獲得每個陣列中的第一個，這意味著你需要將全數二元陣列遍歷完才有辦法判斷，而九宮格則是要每爬完三條水平線才能處理，至於要怎麼知道這些數字重覆，你可以產生一個陣列如果不在陣列裡頭就儲存直到發現重覆，不過這邊我們用Hash Map的方式來做似乎比較明智些，如此一來就不用在去寫一個回圈來遍歷陣列的值是否重覆。

程式碼解說:

這邊我拆成了三個部分來說水平、垂直與九宮格的處理方式，水平相對單純許多，只要記錄一水平線中的每個值是否存在，不存在的話就塞入，這邊與接下來另外垂直與九宮格所儲存的方式一樣，主要是檢查map的key值，而不用在乎真正存入的值是什麼，這邊我姑且先和key的值一樣都是放該數字的值，而再每一水平線檢查完後就將水平的hash map清空，事實上只是重新指派新的空間，釋放記憶體的動作就交給golang的garbage collection

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
var str string
hori := make(map[string]string)
for i, v := range board {
	for j, vv := range v {
		str = string(vv)
		if str != "." {
			_, okj := hori[str]
			if okj {
				return false
			} else {
				hori[str] = str
			}
		}
	}
	hori = make(map[string]string)
}

垂直的部分就稍嫌麻煩許多，因為要記錄全部二元陣列的值才有辦法判斷，所以這邊hash map的key與value的值就是該垂直線的第n列+數字以此來區隔各列的數字，不過可能有人會問index的值是直接由j轉成字串，不就會變成ascii的轉換了嗎?確實是如此，因為golang要賦予key值一定要同型別所以就直接這樣轉，不過值是ascii這倒無所謂，因為主要是來區別各列不同就可以了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var str string
var index string
vert := make(map[string]string)
for i, v := range board {
	for j, vv := range v {
		index = string(j)
		str = string(vv)
		if str != "." {
			_, oki := vert[index+str]
			if oki {
				return false
			} else {
				vert[index+str] = index + str
			}
		}
	}
}

九宮格的操作與水平、垂直線不同，要區分的是要存在哪一格的九宮格，因為總共分成上、中、下各三個共計九個，所以這邊我們就把i與j的值除以3即可，0,1,2除以3為0 3,4,5除以3為1 6,7,8除以3為2 並以此為座標來區分，如此以來便能很容易的將數字分配到這九個九宮格做判斷並儲存

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
var str string
var x string
var y string
nine := make(map[string]string)
for i, v := range board {
	for j, vv := range v {
		str = string(vv)
		if str != "." {
			x = string(i / 3)
			y = string(j / 3)
			_, okk := nine[x+y+str]
			if okk {
				return false
			} else {
				nine[x+y+str] = x + y + str
			}
		}
	}
}

完整程式碼:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
func isValidSudoku(board [][]byte) bool {
	var str string
	var index string
	var x string
	var y string
	hori := make(map[string]string)
	vert := make(map[string]string)
	nine := make(map[string]string)
	for i, v := range board {
		for j, vv := range v {
			index = string(j)
			str = string(vv)
			if str != "." {
				_, oki := vert[index+str]
				_, okj := hori[str]
				x = string(i / 3)
				y = string(j / 3)
				_, okk := nine[x+y+str]
				if oki || okj || okk {
					return false
				} else {
					vert[index+str] = index + str
					hori[str] = str
					nine[x+y+str] = x + y + str
				}
			}
		}
		hori = make(map[string]string)
	}
	return true
}

總結:

數讀的檢查分為水平、垂直與九宮格，因需判斷該數字是否重覆再加上垂直與九宮格皆需分類為第n列的數字與哪一格的九宮格，故hash map儲存為最佳儲存方式。

  • 水平線: 最為單純，和處理一維陣列資料差不多
  • 垂直線: 需增加第n列為條件來做儲存與判斷
  • 九宮格: 將水平線的第x行與垂直線的第y列分別除以3為判別九宮格座標來儲存
分享到