0%

20210303学习记录

2021-03-03 学习记录

今天学习的内容:

  1. 数据结构:栈
  2. Leetcode刷题:(1)#1124 表现良好的最长时间段;(2)#1003 检查替换后的词是否有效;(3)#145 二叉树的后序遍历
  3. 学习微服务架构(完善user-srv这个demo服务)

1. 数据结构:栈

今天复习的是数据结构中的栈。使用Go语言实现了一下栈的基本操作,自行实现没有使用内置数据结构。代码在github上,这里记录一下遇到的问题。

0x01 栈操作的并发性问题

我们知道出栈和入栈操作并不是原子操作(stack.top在入栈和出栈时都会被操作),在不考虑实现无锁数据结构的情况下,我们考虑加一个读写锁来保证线程安全。

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
// Push push a new node into the stack(on the top)
func (stack *Stack) Push(val interface{}) error {
stack.lock.Lock()
defer stack.lock.Unlock()
pNode := new(node)
pNode.val = val
pNode.prev = stack.top
stack.top = pNode
stack.length++
return nil
}

// Pop pop the top node of the stack
func (stack *Stack) Pop() (ok bool, err error) {
stack.lock.Lock()
defer stack.lock.Unlock()
if stack.top == nil {
err = fmt.Errorf("pop a empty stack")
return
}
stack.top = stack.top.prev
stack.length--
ok = true
return
}

2.Leetcode刷题

#1124 表现良好的最长时间段

这个题终究是没有看懂时间复杂度最低的单调栈的做法,最后还是使用暴力解法做了出来。

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
func longestWPI(hours []int) int {
var arr []int = make([]int, len(hours))
var prefixSum []int = make([]int, len(hours)+1)
tmp := 0
for i, val := range hours {
if val > 8 {
arr[i] = 1
} else {
arr[i] = -1
}
}
prefixSum[0] = 0
for i := 0; i < len(arr); i++ {
tmp += arr[i]
prefixSum[i+1] = tmp
}

res := 0
for i := 0; i < len(prefixSum); i++{ // 实在没有理解最后的优化思路,太复杂了
for j := i+1; j < len(prefixSum); j++{
if prefixSum[j] > prefixSum[i] {
if j - i > res {
res = j - i
}
}
}
}
return res
}
#1003 检查替换后的词是否有效

这个题没有看题解自己调试了两次做出来了。不过一开始我并没有考虑使用栈,而是使用了类似消消乐的思想,题目要求给定字符串是否是由”abc”这个子字串组成,其中”abc”可以任意穿插。直观操作类似消消乐,遍历字符串,只要遇到”abc”就将它”消去”,然后重新遍历消去后剩余的字符串。

1
2
3
4
5
6
7
8
9
10
11
12
13
func isValid(s string) bool {
for i := 0; i < len(s)-2; i++ {
if s[i] == 97 && s[i+1] == 98 && s[i+2] == 99 {
s = s[:i] + s[i+3:]
i = -1
}
}
if len(s) == 0 {
return true
} else {
return false
}
}

不过这样操作时间复杂度达到了O(n²),看了题解之后发现可以使用栈来优化,依次让字符串的每个字符入栈,遇到”abc”后就直接将这三个字符全部出栈,最后检查栈是否是空的即可,这样时间复杂度只有O(n).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func isValid(s string) bool {
var str []byte
str = append(str, s[0])
str = append(str, s[1])
for i := 2; i < len(s); i++{
str = append(str, s[i])
if len(str) >= 3 && str[len(str)-1] == 99 && str[len(str)-2] == 98 && str[len(str)-3] == 97 {
str = str[:len(str)-3]
}
}
if len(str) == 0 {
return true
} else {
return false
}
}

重点来了。上面的这个代码其实无法通过,原因是,如果s="a",即s的长度不足3的话,程序会直接panic。所以这里需要进行边界检查!连续两个题全部忘记了边界检查,导致提交的时候出错。

最终正确代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func isValid(s string) bool {
if len(s) < 3 {
return false
}
var str []byte
str = append(str, s[0])
str = append(str, s[1])
for i := 2; i < len(s); i++{
str = append(str, s[i])
if len(str) >= 3 && str[len(str)-1] == 99 && str[len(str)-2] == 98 && str[len(str)-3] == 97 {
str = str[:len(str)-3]
}
}
if len(str) == 0 {
return true
} else {
return false
}
}
#145 二叉树的后序遍历

这个题拿到之后由于原来知道二叉树的迭代遍历可以通过栈完成,于是直接写了个栈的遍历方法。投机取巧了一下写了个前序遍历然后把结果反了过来。

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
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func postorderTraversal(root *TreeNode) []int {
var stack []*TreeNode
var res []int
var left *TreeNode
var right *TreeNode
var top *TreeNode
if root == nil { // 注意边界情况检查!!!!
return res
}
stack = append(stack, root)
for len(stack) > 0 {
top = stack[len(stack)-1]
res = append(res, top.Val)
left = top.Left
right = top.Right
stack = stack[:len(stack)-1]
if left != nil {
stack = append(stack, left)
}
if right != nil {
stack = append(stack, right)
}
}
for i, j := 0, len(res)-1; i < j; i, j = i+1, j-1 {
res[i], res[j] = res[j], res[i]
}
return res

}

学习微服务架构

今天成功实现了一个简单的登录接口,前端请求后端的handler,handler调用user-srv的login服务,该服务执行login操作,查询数据库并返回结果给后端handler,后端handler通过判断结果给前端返回信息和状态码。