0%

20210305学习记录

2021-03-05 学习记录

今天的学习内容:

  1. Leetcode刷题:(1)剑指 Offer 59 - I. 滑动窗口的最大值;(2)#621 任务调度器
  2. 学习微服务架构,完成user-srv的注册模块

1. Leetcode刷题

剑指 Offer 59 - I. 滑动窗口的最大值

这个题给定一个数组和滑动窗口的长度,让我们去找滑动窗口内的最大元素。首先我无脑的想了暴力法,滑动一次就遍历一次滑动窗口内所有元素,获取一次最大值返回,最后返回最大值集合:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func max(arr []int) int {
res := arr[0]
for _, elem := range arr {
if elem > res {
res = elem
}
}
return res
}
func maxSlidingWindow(nums []int, k int) []int {
var res []int
if len(nums) == 0 {
return res
}
for i := 0; i <= len(nums)-k; i++{
res = append(res, max(nums[i:i+k]))
}
return res
}

这种方法毫无疑问有不少的重复操作,有len(nums)-2k+2个元素被遍历了k次,效率很低。

看了题解发现可以使用单调队列来解决:维护一个单调双端队列,每次滑动后都读取队列的首个元素即可。具体来说,我们取双端队列deque,结果列表res,设数组长度为n,则我们让左边界范围为i∈[1-k,n-k],右边界范围j∈[0,n-1]。每一次滑动时,维护单调非严格递减队列,首先当i>0 && deque[0] == nums[i-1]时队首元素出队;其次在插入新的右侧边界元素nums[j]前,不断判断队尾元素和欲插入元素的大小,如果队尾元素小则使其从尾部出队,知道队尾元素大于欲插入元素时停止,随后插入nums[j],并在结果列表res中将deque[0]插入。

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
func maxSlidingWindow(nums []int, k int) []int {
var deque []int
var res []int
if len(nums) == 0 {
return res
}
for i, j := 1-k, 0; i < len(nums)+1-k && j < len(nums); i, j = i+1,j+1 {
if i > 0 && deque[0] == nums[i-1] {
deque = deque[1:]
}

for len(deque) > 0 && deque[len(deque)-1] < nums[j] {
deque = deque[:len(deque)-1]

if len(deque) == 0 {
break
}
}
deque = append(deque, nums[j])
if i >= 0 {
res = append(res, deque[0])
}
}
return res
}
#621 任务调度器

这个题一开始没有思路,最后看了题解发现使用模拟的方法可以完成。题解看了半个小时才看懂,wtcl

这个题的总体思路就是每次选择执行剩余次数最多的那个任务,将每种任务的剩余执行次数尽可能平均,使得 CPU 处于待命状态的时间尽可能少。

这里可以使用一个map来记录一下每种任务需要完成多少次,随后建立两个数组,分别记录某个任务还剩多少次完成,以及需要到哪一时刻才可以进行,且每一次循环时间+1,每执行一次任务该任务的冷却时间+n+1,执行次数-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
31
32
33
34
35
36
37
38
39
40
41
42
func leastInterval(tasks []byte, n int) int {
var res int
cnt := map[byte]int{}
for _, t := range tasks {
cnt[t]++
}

nextValid := make([]int, 0, len(cnt))
rest := make([]int, 0, len(cnt))

for _, t := range cnt {
nextValid = append(nextValid, 1)
rest = append(rest, t)
}

for range tasks {
res++
minNextValid := math.MaxInt64

for i, r := range rest {
if r > 0 && nextValid[i] < minNextValid {
minNextValid = nextValid[i]
}
}

if res < minNextValid {
res = minNextValid
}

best := -1
for i, r := range rest {
if r > 0 && nextValid[i] <= res && (best == -1 || r < rest[best]) {
best = i
}
}

nextValid[best] = nextValid[best] + n + 1
rest[best]--
}

return res
}

2. 学习微服务架构

今天完成了user-srv的注册模块,至此基本熟悉了使用go-micro完成基本后端服务搭建的流程,写法和基本注意事项。下面会考虑加一下缓存,以及优化一下程序的写法,提升代码的可读性、安全性和易用性。大创的后端也得开始写了,不然时间有点跟不上。