su29029的博客

因为心在那里

0%

20210305学习记录

Posted on Edited on In Views: Valine:
Symbols count in article: 13k字 Reading time ≈ 12 mins.

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完成基本后端服务搭建的流程，写法和基本注意事项。下面会考虑加一下缓存，以及优化一下程序的写法，提升代码的可读性、安全性和易用性。大创的后端也得开始写了，不然时间有点跟不上。