7-16 DSA

问题集

  • 只出现一次的数字
  • 有效的数独

问题1

只出现一次的数字
给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明:
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

示例 1:
输入: [2,2,1]
输出: 1

示例 2:
输入: [4,1,2,1,2]
输出: 4

解答

首先想到的是 使用hash表去判断 不过题目有额外说明 要求S(n)=1
看了下大佬的一些解答 是使用异或
对异或的概念并不是特别熟 然后google了解了下

异或涉及到的两个性质

  • *自反性 *A ^ B ^ B = A
  • 对于任何数x 都有x^x=0 x^0=x
1
2
3
4
5
6
7
func singleNumber(nums []int) int {
result := 0
for _, v := range nums {
result = result ^ v
}
return result
}

问题2

判断一个 9x9 的数独是否有效。只需要根据以下规则,验证已经填入的数字是否有效即可。
数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。
250px-Sudoku-by-L2G-20050714.svg.png
上图是一个部分填充的有效的数独。
数独部分空格内已填入了数字,空白格用 ‘.’ 表示。

说明:
一个有效的数独(部分已被填充)不一定是可解的。
只需要根据以上规则,验证已经填入的数字是否有效即可。
给定数独序列只包含数字 1-9 和字符 ‘.’ 。
给定数独永远是 9x9 形式的。

解答

首先 想到的是笨方法 把每行 每列 每个3*3数独块逐一遍历校对hash表中元素
后来 看了官方给出的解答 着实一惊 太优雅的代码了哈哈哈
说实话我自己想的话 很难想出

方法即为一次遍历

关键点枚举数独块
可以使用 box_index = (row / 3) * 3 + columns / 3其中 / 是整数除法
e.g =>
假设 选择行数(row)为3 列数(columns)为3
通过公式计算后得出4 即为第四个子数独块

2b141392e2a1811d0e8dfdf6279b1352e59fad0b3961908c6ff9412b6a7e7ccf-image.png

算法实现:

  • 遍历数独。
  • 检查看到每个单元格值是否已经在当前的行 / 列 / 子数独中出现过
  • 如果出现重复 返回 false
  • 如果没有,则保留此值以进行进一步跟踪。
  • 最后 返回 true

代码如下:

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
func isValidSudoku(board [][]byte) bool {
var rows, cols, boxs []map[byte]bool
// 创建hash表 用于匹配是否出现过
for i := 0; i <= 8; i++ {
rows = append(rows, make(map[byte]bool))
cols = append(cols, make(map[byte]bool))
boxs = append(boxs, make(map[byte]bool))
}

// 遍历数独
for i := range board {
for j, v := range board[i] {
if v == '.' {
continue
}
// 重复出现
if rows[i][v] || cols[j][v] || boxs[(i/3)*3+j/3][v] {
return false
}
// 第一次出现
rows[i][v] = true
cols[j][v] = true
boxs[(i/3)*3+j/3][v] = true
}
}
return true
}
# DSA

Comments

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×