候诊室中的最少椅子数
【简单】3168. 候诊室中的最少椅子数
本题较为简单，可以不用练习。
分析
遇到E，将count++，否则将count--，使用一个变量minTarget记录遍历过程中的最大count值。
1
2
3
4
5
6
7
8
9
10
11
12
|
func minimumChairs(s string) int {
count, minTarget := 0, 0
for i := 0; i < len(s); i++ {
if s[i] == 'E' {
count++
} else {
count--
}
minTarget = max(minTarget, count)
}
return minTarget
}
|
无需开会的工作日
【中等】3169. 无需开会的工作日
分析
本题和 56. 合并区间 差不多，都需要将重叠的区间合并。
然后更新重叠区间的右侧位置，然后计算不重叠区间中间的差值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
func countDays(days int, meetings [][]int) int {
sort.Slice(meetings, func(i, j int) bool { // 先按照左侧位置升序，若相同则按照右侧位置升序。
if meetings[i][0] != meetings[j][0] {
return meetings[i][0] < meetings[j][0]
}
return meetings[i][1] < meetings[j][1]
})
count := meetings[0][0] - 1
for i := 1; i < len(meetings); i++ {
if meetings[i][0] > meetings[i-1][1] { // 区间不重叠
count += meetings[i][0] - meetings[i-1][1] - 1
} else { // 重叠区间，更新区间右侧位置
meetings[i][1] = max(meetings[i][1], meetings[i-1][1])
}
}
count += days - meetings[len(meetings)-1][1]
return count
}
|
删除星号以后字典序最小的字符串
【中等】3170. 删除星号以后字典序最小的字符串
本题可以多加练习。
分析
参考：三种写法：26 个栈+位运算优化（Python/Java/C++/Go）
去掉左侧最小的字符，应该尽量去掉靠右的最小字符。
使用26个栈存放每个字符出现的位置，然后遍历所有的栈，第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
|
func clearStars(s string) string {
stack := make([][]int, 26) // 存每个元素出现的位置
sByte := []byte(s)
for i := 0; i < len(sByte); i++ {
if s[i] != '*' {
stack[s[i]-'a'] = append(stack[s[i]-'a'], i)
} else {
for j, strStack := range stack {
if len(strStack) != 0 { // 找到左侧最小的元素
sByte[strStack[len(strStack)-1]] = '*' // 将要删除的位置设置为*
// strStack = strStack[:len(strStack)-1]
// 注意：删除最后一个元素不能这样写，因为strStack是stack中一维数组的副本，
// 这样只是缩短了strStack的索引范围，对stack数组没有任何的影响，
// 要删除内部一维数组中的最后一个元素，应该直接修改stack数组，如下：
stack[j] = strStack[:len(strStack)-1] // 删除最后的元素
break
}
}
}
}
t := sByte[:0] // 一种技巧，复用底层数组
for i := 0; i < len(sByte); i++ {
if sByte[i] != '*' {
t = append(t, sByte[i])
}
}
return string(t)
}
|
本题还需要注意的一点是：删除二维数组中的最后一个元素，不能修改使用迭代变量的方式，要根据stack数组的下标修改stack数组的值。
找到按位与最接近 K 的子数组
【困难】3171. 找到按位与最接近 K 的子数组
分析
参考：利用 AND 的性质（Python/Java/C++/Go）
and操作可以看做是取两个集合的交集
如果 a&b=a，说明a是b的子集
从左到右遍历nums，然后从x-1开始倒着遍历nums[j]：
- 如果nums[j]&x!=nums[j]，说明nums[j]可以变小，更新nums[j]=nums[j]&x
- 否则nums[j]&x=nums[j]，x不仅是nums[j]的超集，同时也是nums[k](k<j)的超集
所以后续的循环都不会改变nums[j]的值，退出内层循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
func minimumDifference(nums []int, k int) int {
ans := math.MaxInt
for i, x := range nums {
ans = min(ans, abs(x-k)) // 单个元素
for j := i - 1; j >= 0 && nums[j]&x != nums[j]; j-- {
nums[j] &= x
ans = min(ans, abs(nums[j]-k))
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}
|
