早起刷题（Day 1）
洪笳淏 Lv4
 2022-03-30 06:00:00      

LeetCode179. 最大数

#字典序

题目描述

给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。

1
2
3
4
5
6
7
示例 1：
输入：nums = [10,2]
输出："210"

示例 2：
输入：nums = [3,30,34,5,9]
输出："9534330"

解题思路

(1). 本题需要按照字典序排序来生成最终的字符串；
(2). 当给定的数组中元素的最高位都不相等时，情况最简单，直接输出字典序即可；
(3). 当出现 $4$ 和 $42$ 这种类型的子序列时，如果按照字典序来排序只能得到 $424$，但实际上最大值是 $442$，因此可知根据字典序排序只能得到局部最大值 ans，我们要求的是全局最大值 max；
(4). 可以在排序的时候更改一下排序条件，不以字典序为排序条件，而是以两数拼接后的实际大小来排序。

时间复杂度

O(Nlog(N))。因为有排序算法。

解题代码

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 largestNumber(nums []int) string {

	sort.Slice(nums, func(i,j int)bool {
		x, y := nums[i], nums[j]
		sx, sy := 10, 10
		for sx <= x {
			sx *= 10
		}

		for sy <= y {
			sy *= 10
		}

		return sy*x+y > sx*y+x
	})

	if nums[0] == 0 {
		return "0"
	}

	ret := ""
	for i:=0; i<len(nums); i++ {
		ret += strconv.Itoa(nums[i])
	}

	return ret
}

代码细节

  在排序条件中，我们维护了两个变量 sx 和 sy，这两个变量会在拼接操作中为两个数留出对应的位置，方便我们的拼接操作，避免了转换成字符串后再进行拼接。

LeetCode36. 有效的数独

#模拟题

题目描述

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

  1. 数字 1-9 在每一行只能出现一次。
  2. 数字 1-9 在每一列只能出现一次。
  3. 数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）
    注意：
    一个有效的数独（部分已被填充）不一定是可解的。
    只需要根据以上规则，验证已经填入的数字是否有效即可。
    空白格用 '.' 表示。
1
示例 1:

avatar

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
 输入：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 存在, 因此这个数独是无效的。

提示：
board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

解题思路

(1). 先判断行上是否符合标准；
(2). 再判断列上是否符合标准；
(3). 最后传递每个九宫格的左上角坐标来判断每个九宫格是否符合标准。

解题代码

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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
func isValidSudoku(board [][]byte) bool {

	var checkRow func(index int) bool
	checkRow = func(index int) bool {
		check := make([]int, 10)
		row := board[index]
		for i:=0; i<len(row); i++ {
			if row[i] == '.' {
				continue
			} else {
				if check[int(row[i])-'0'] == 1 {
					return false
				} else {
					check[int(row[i])-'0'] = 1
				}
			}
		}
		return true
	}
	
	var checkColumn func(index int) bool
	checkColumn = func(index int) bool {
		check := make([]int, 10)
		for i:=0; i<9; i++ {
			if board[i][index] == '.' {
				continue
			} else {
				if check[int(board[i][index])-'0'] == 1 {
					return false
				} else {
					check[int(board[i][index])-'0'] = 1
				}
			}
		}
		return true
	}
	
	var checkGrid func(r,c int) bool
	checkGrid = func(r,c int) bool {
		check := make([]int, 10)
		for i:=r; i<r+3; i++ {
			for j:=c; j<c+3; j++ {
				if board[i][j] == '.' {
					continue
				} else {
					if check[int(board[i][j])-'0'] == 1 {
						return false
					} else {
						check[int(board[i][j])-'0'] = 1
					}
				}
			}
		}
		return true
	}

	for i:=0; i<9; i++ {
		if !checkRow(i) {
			return false
		}
		if !checkColumn(i) {
			return false
		}
	}
	
	for i:=0; i<=6; i=i+3 {
		for j:=0; j<=6; j=j+3 {
			if !checkGrid(i,j) {
				return false
			}
		}
	}
	return true
}

剑指 Offer 56 - I. 数组中数字出现的次数

#位运算

题目描述

一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。

1
2
3
4
5
6
7
8
9
10
示例 1:
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]

示例 2:
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]

限制：
2 <= nums.length <= 10000

解题思路

(1). 首先我们要明确一点：相同的数字异或等于 0，并且异或操作具备交换性。所以整个数组的异或结果等于两个只出现一次的数的异或；
(2). 两个数的异或结果在某一个二进制位上是 $1$，说明这两个数在该位上不同，那么我们可以利用这一性质，将数组中所有的数字根据该二进制位上是 $1$ 或 $0$ 分类为两组；
(3). 组内的元素再自行进行异或，那么最终两组的结果就是两个只出现过一次的数。

时间复杂度

O(N).

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func singleNumbers(nums []int) []int {

	if len(nums) == 2 {
		return nums
	}
	
	x := nums[0]
	for i:=1; i<len(nums); i++ {
		x ^= nums[i]
	}
	c := x&(-x)
	
	a, b := 0, 0
	for i:=0; i<len(nums); i++ {
		x = nums[i]
		if x&c == c {
			a ^= nums[i]
		} else {
			b ^= nums[i]
		}
	}
	
	return []int{a,b}
}

代码细节

 &emsp在找第一个不同的二进制位的操作中，我们使用了 x&(-x) 的形式。首先明确一下，计算一个正数的相反数等于将其二进制表示全部取反再加 1，例如 $12 = 01100$，那么 $-12 = 10100$，再进行 & 运算可得 $12 & -12 = 00100$，这样就将最低位为 $1$ 的二进制数表示了出来。之后只要将数组中所有的数与该数进行 & 操作就能完成分类。

剑指 Offer 56 - II. 数组中数字出现的次数 II

题目描述

在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。

1
2
3
4
5
6
7
8
9
10
11
示例 1:
输入：nums = [3,4,3,3]
输出：4

示例 2:
输入：nums = [9,1,7,9,7,9,7]
输出：1

限制：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31

解题思路

(1). 因为约定了除了一个数字外，别的数字都会出现 3 次，那么也就意味着每一个数的二进制位会出现 3 的倍数；
(2). 当某一个二进制位上不是 3 的倍数，那么也就意味着是那个只出现了一次的数字肯定占据了一次该二进制位；
(3). 利用 (2) 中找到的二进制位组成这个数。

时间复杂度

O(N).

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
func singleNumber(nums []int) int {

	bitCount := [32]int{}
	for i:=0; i<len(nums); i++ {
		x := nums[i]
		j := 0
		for x != 0 {
			if x ^ (x-1) == 1 {
				bitCount[j]++
			}
			j++
			x >>= 1
		}
	}

	ret := 0
	for i:=0; i<len(bitCount); i++ {
		x := bitCount[i]%3
		ret += x*int(math.Pow(2,float64(i)))
	}
	return ret
}

代码细节

  根据本题的特性，我们很容易就能推广，对于某个数组，除了一个数只出现一次外，其余的数都出现了 $m$ 次，那么利用这种特性，我们也能很轻易地找到这个只出现了一次的数。

  • Post title：早起刷题（Day 1）
  • Post author：洪笳淏
  • Create time：2022-03-30 06:00:00
  • Post link：https://jiahaohong1997.github.io/2022/03/30/早起刷题（Day 1）/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
 Comments