早起刷题（Day 12）
洪笳淏 Lv4
 2022-04-14 10:00:00      

今日未早起，淦！

LeetCode1151. 最少交换次数来组合所有的 1

#滑动窗口

题目描述

给出一个二进制数组 data，你需要通过交换位置，将数组中 任何位置 上的 1 组合到一起，并返回所有可能中所需 最少的交换次数。

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
示例 1:
输入: data = [1,0,1,0,1]
输出: 1
解释: 
有三种可能的方法可以把所有的 1 组合在一起：
[1,1,1,0,0]，交换 1 次；
[0,1,1,1,0]，交换 2 次；
[0,0,1,1,1]，交换 1 次。
所以最少的交换次数为 1。

示例  2:
输入：data = [0,0,0,1,0]
输出：0
解释： 
由于数组中只有一个 1，所以不需要交换。

示例 3:
输入：data = [1,0,1,0,1,0,0,1,1,0,1]
输出：3
解释：
交换 3 次，一种可行的只用 3 次交换的解决方案是 [0,0,0,0,0,1,1,1,1,1,1]。

示例 4:
输入: data = [1,0,1,0,1,0,1,1,1,0,1,0,0,1,1,1,0,0,1,1,1,0,1,0,1,1,0,0,0,1,1,1,1,0,0,1]
输出: 8
 

提示:
1 <= data.length <= 105
data[i] == 0 or 1.

解题思路

(1). 我们需要得到的输出的最终效果是数组中所有的 $1$ 都被聚集于一个子数组中，这个子数组的长度就是数组中所有 $1$ 的数量 totalOnes；
(2). 那么我们只需要判断所有长度等于 totalOnes 的子数组中含有 $1$ 最多的个数是多少就可以了，因为 $0$ 的个数就是需要交换的最少次数；
(3). 怎么快速的统计所有该长度的子数组的含 $1$ 数量呢？这里就可以使用滑动窗口；
(4). 首先统计第一个窗口内 $1$ 的个数，之后只需要移动滑动窗口，再分别加上移入窗口和移出窗口的元素即可，避免了对每个窗口遍历统计。

时间复杂度

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
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
func minSwaps(data []int) int {

	totalOnes := 0
	for i:=0; i<len(data); i++ {
		if data[i] == 1 {
			totalOnes++
		}
	}
	
	l, r := 0, totalOnes
	countOnes := 0
	for i:=l; i<r; i++ {
		if data[i] == 1 {
			countOnes++
		}
	}

	maxWindowOnes := countOnes

	for r < len(data) {
		x := data[r]
		r++

		countOnes += x-data[l]
		maxWindowOnes = max(maxWindowOnes, countOnes)

		l++
	}

	return totalOnes-maxWindowOnes
}

func max(a, b int) int {
	if a > b {
		return a
	}

	return b
}

249. 移位字符串分组

#map #字符串

题目描述

给定一个字符串，对该字符串可以进行 “移位” 的操作，也就是将字符串中每个字母都变为其在字母表中后续的字母，比如：”abc” -> “bcd”。这样，我们可以持续进行 “移位” 操作，从而生成如下移位序列：
"abc" -> "bcd" -> ... -> "xyz"
给定一个包含仅小写字母字符串的列表，将该列表中所有满足 “移位” 操作规律的组合进行分组并返回。

1
2
3
4
5
6
7
8
9
10
11
示例：

输入：["abc", "bcd", "acef", "xyz", "az", "ba", "a", "z"]
输出：
[
  ["abc","bcd","xyz"],
  ["az","ba"],
  ["acef"],
  ["a","z"]
]
解释：可以认为字母表首尾相接，所以 'z' 的后续为 'a'，所以 ["az","ba"] 也满足 “移位” 操作规律。

解题思路

(1). 对于初始字符串数组中给定的所有元素，我们都要找到其对应的所有变换后的字符串，然后再在初始字符串数组中查找是否有这些变换后的字符串；
(2). 对于查找操作，用 map 是时间代价最小的方式，所以我们要先遍历整个字符串数组，将所有字符串存入 map 中；
(4). 在对某一个序列中应该出现的所有字符串的形态都进行查找后，再次遍历到属于该序列的某一个字符串时，就不用重新查找整个序列。所以要再使用一个 map 来记录已经遍历过且在初始字符串数组中的元素，因为存在重复元素，所以 map 的 value 要使用 int 类型记录出现的次数，并且在生成序列的时候要生成对应次数的该字符串；
(5). 因为最终的序列要按照字典序排列，那么对于遍历到的某一个元素，要在其序列的头部插入字典序在其前面的字符串，在其后面插入字典序在其后面的字符串。

时间复杂度

O(26*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
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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
func groupStrings(strings []string) [][]string {

	m := make(map[string]bool)
	traveled := make(map[string]int)

	for i:=0; i<len(strings); i++ {
		m[strings[i]] = true
		traveled[strings[i]]++
	}

	var judgeUp func(string) string
	judgeUp = func(s string) string {
		var ret string
		for i:=0; i<len(s); i++ {
			x := s[i]
			if x == 'a' {
				ret += "z"
			} else {
				ret += string(x-1)
			}
		}

		return ret
	}



	var judgeDown func(string) string
	judgeDown = func(s string) string {
		var ret string
		for i := 0; i<len(s); i++ {
			x := s[i]
			if x == 'z' {
				ret += "a"
			} else {
				ret += string(x+1)
			}
		}

		return ret
	}



	ret := [][]string{}
	for i:=0; i<len(strings); i++ {
		if traveled[strings[i]] == 0 {
			continue
		}

		t := []string{}
		x := strings[i]

		for x[0] != 'a' {
			if m[x] {
				for traveled[x] > 0 {
					t = append([]string{x}, t...)
					traveled[x]--
				}
			}
			x = judgeUp(x)
		}



		for m[x] && traveled[x] > 0 {
			t = append([]string{x}, t...)
			traveled[x]--
		}

		x = judgeDown(strings[i])

		for x[0] != 'z' {
			if m[x] {
				for traveled[x] > 0 {
					t = append(t, x)
					traveled[x]--
				}
			}
			x = judgeDown(x)
		}

		for x[0] == 'z' && m[x] && traveled[x] > 0 {
			t = append(t, x)
			traveled[x]--
		}

		ret = append(ret, t)
	}
	
	return ret
}

54. 螺旋矩阵

#模拟题

题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。

1
示例 1：

avatar

1
2
3
4
输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[1,2,3,6,9,8,7,4,5]

示例 2：

avatar

1
2
3
4
5
6
7
8
9
输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
输出：[1,2,3,4,8,12,11,10,9,5,6,7]
 

提示：
m == matrix.length
n == matrix[i].length
1 <= m, n <= 10
-100 <= matrix[i][j] <= 100

解题思路

(1). 本题主要注意两点：如何确保外层矩阵不重复遍历；如果保证遍历的方向；
(2). 对于外层矩阵，可以采用四个变量 left、right、top、bottom 限制矩阵的收缩范围；
(3). 对于最终行/列的遍历方向问题，设置两个 bool 变量 down 和 turnRight，在向下\右遍历过后，将这两个变量置为 false，否则置为 true，就能保证下次是和上次相反的遍历方向。

时间复杂度

O(M*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
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
func spiralOrder(matrix [][]int) []int {

	var (
		high = 0
		low = len(matrix)-1
		left = 0
		right = len(matrix[0])-1
	)

	ret := make([]int,0)
	down := true
	turnRight := true

	for low >= high && right >= left {
		if low == high {
			var x, y int
			if turnRight {
				x, y = left, right
			} else {
				x, y = right, left
			}

			for i := x; i <= y; i++ {
				ret = append(ret, matrix[low][i])
			}
			break
		}
		
		if left == right {

			var x, y int
			if down {
				x, y = high, low
			} else {
				x, y = low, high
			}
			
			for i:=x; i<=y; i++ {
				ret = append(ret, matrix[i][left])
			}
			break
		}

		for i := left; i<right; i++ {
			ret = append(ret, matrix[high][i])
			turnRight = false
		}

		for i:=high; i<low; i++ {
			ret = append(ret, matrix[i][right])
			down = false
		}

		for i:=right; i>left; i-- {
			ret = append(ret, matrix[low][i])
			turnRight = true
		}

		for i:=low; i>high; i-- {
			ret = append(ret, matrix[i][left])
			down = true
		}

		high++
		left++
		low--
		right--
	}

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