Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (24) 复制带随机指针的链表 基本计算器II 最大数 移掉K位数字

发表于 更新于 分类于

复制带随机指针的链表

复制带随机指针的链表

解题思路

我们用哈希表记录每一个节点对应新节点的创建情况。

解题代码

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
/**
 * Definition for a Node.
 * type Node struct {
 *     Val int
 *     Next *Node
 *     Random *Node
 * }
 */

func copyRandomList(head *Node) *Node {
    cachedNode := map[*Node]*Node{}
    var deepCopy func(head *Node) *Node
    deepCopy = func(head *Node) *Node {
        if head == nil {
            return nil
        }

        if node, ok := cachedNode[head]; ok {
            // 已经创建了这个节点
            return node
        }

        // 创建新的节点
        newNode := &Node{ Val: head.Val }
        // 记录在哈希表中
        cachedNode[head] = newNode
        newNode.Next = deepCopy(head.Next)
        newNode.Random = deepCopy(head.Random)

        return newNode
    }

    return deepCopy(head)
}

基本计算器 II

基本计算器 II

解题思路

利用两个栈，opStack存放运算符，numStack存放操作数。遍历字符串表达式：

  • 若遇到空格，则跳过
  • 若遇到数字，则直接压入numStack
  • 若遇到运算符，依次弹出opStack栈顶并从numStack中弹出两个操作数进行运算，直到栈顶运算符的优先级低于当前运算符的优先级

遍历完成后，依次弹出opStack栈顶元素进行运算。最终结果就是numStack中的最后一个元素。

解题代码

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
func calculate(s string) int {
    numStack := make([]int, 0)  // 存储数字的栈
    opStack := make([]byte, 0)  // 存储运算符的栈
    
    for i := 0; i < len(s); {
        if s[i] == ' ' {
            // 空格直接跳过
            i++
            continue
        } else if '0' <= s[i] && s[i] <= '9' {     // 遇到数字
            num := int(s[i]-'0')
            j := i+1
            for ; j < len(s) && '0' <= s[j] && s[j] <= '9'; j++ {
                num = 10*num + int(s[j]-'0')
            }
            // 数字压入栈中
            numStack = append(numStack, num)
            // 更新指针i
            i = j
        } else {    // 是操作符 + - * /
            for shouldPop(opStack, s[i]) {
                // 运算符弹出栈顶
                op := opStack[len(opStack)-1]
                opStack = opStack[:len(opStack)-1]
                // 弹出两个操作数
                n2 := numStack[len(numStack)-1]
                n1 := numStack[len(numStack)-2]
                numStack = numStack[:len(numStack)-2]
                // 做运算，压入numStack
                numStack = append(numStack, operation(op, n1, n2))
            }
            // 当前运算符压入栈中
            opStack = append(opStack, s[i])
            i++
        }
    }
    // opStack不为空时，弹出所有运算符并做运算
    for len(opStack) > 0 {
        // 运算符弹出栈顶
        op := opStack[len(opStack)-1]
         opStack = opStack[:len(opStack)-1]
        // 弹出两个操作数
        n2 := numStack[len(numStack)-1]
        n1 := numStack[len(numStack)-2]
        numStack = numStack[:len(numStack)-2]
        // 做运算，压入numStack
        numStack = append(numStack, operation(op, n1, n2))
    }

    return numStack[0]
}

// 当前运算符是op，判断是否需要弹出栈顶运算符
func shouldPop(opStack []byte, op byte) bool {
    if len(opStack) == 0 {
        // 运算符栈为空
        return false
    }
    if op == '*' || op == '/' {
        // 当前运算符是 * 或者 / 时，栈顶也是 * 或者 / 可以弹出栈顶元素进行运算
        if opStack[len(opStack)-1] == '*' || opStack[len(opStack)-1] == '/' {
            return true
        } else {
            return false
        }
    } else {
        return true
    }
}

// 做运算 n1 <op> n2 = ?
func operation(op byte, n1, n2 int) int {
    switch op {
        case '+':
            return n1 + n2
        case '-':
            return n1 - n2
        case '*':
            return n1 * n2
        case '/':
            return n1 / n2
    }
    return 0
}

最大数

最大数

解题思路

可以利用sort.Sort函数对数组进行排序：

  • 如果拼接结果ab比ba好，那么认为a应该放在b前面

解题代码

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
type intSlice []int

func largestNumber(nums []int) string {
    // 排序
    slice := intSlice(nums)
    sort.Sort(slice)

    // 转化为字符串
    var res string
    begin := 0
    // 去除最前面的 0
    for i := 0; i < len(nums)-1 && slice[i] == 0; i++ {
        begin++
    }
    // 将剩余数字拼接成字符串
    for i := begin; i < len(nums); i++ {
        res += strconv.FormatInt(int64(slice[i]), 10)
    }

    return res
}

// 实现接口进行排序
func (this intSlice) Len() int {
    return len(this)
}

func (this intSlice) Less(i, j int) bool {
    if compare(concat(this[i], this[j]), concat(this[j], this[i])) == 1 {
        return true
    } else {
        return false
    }
}

func (this intSlice) Swap(i, j int) {
    this[i], this[j] = this[j], this[i]
}

// 讲n1和n2转换为字符串并连接在一起
func concat(n1, n2 int) string {
    return strconv.FormatInt(int64(n1), 10) + strconv.FormatInt(int64(n2), 10)
}

// 比较两个字符串的大小
func compare(s1, s2 string) int {
    for i := 0; i < len(s1); i++ {
        if s1[i] > s2[i] {
            return 1
        } else if s1[i] < s2[i] {
            return -1
        }
    }

    return 0
}

移掉K位数字

移掉K位数字

解题思路

利用单调栈，从左至右扫描num：

  • 如果当前遍历的数比栈顶大，符合递增，入栈
    • 为了防止前导0入栈，需要有入栈条件：当前字符不为0或者栈不为空
  • 如果当前遍历的数比栈顶小，栈顶立刻出栈。因为栈顶的数属于高位，删掉它，小的顶上，高位变小，效果好于低位变小。

遍历结束时，有可能还没删够k个字符，此时依次弹出栈顶，删除低位。

解题代码

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 removeKdigits(num string, k int) string {
    if k == len(num) {
        // 移除所有的数字，直接返回0
        return "0"
    }
    stack := make([]byte, 0)    // 单调栈
    // 遍历num
    for i := 0; i < len(num); i++ {
        // 只要k>0并且栈顶元素大于当前字符num[i]，栈顶元素出栈
        for k > 0 && len(stack) > 0 && stack[len(stack)-1] > num[i] {
            stack = stack[:len(stack)-1]
            k--
        }
        // 当当前字符不为0或者栈不空时，当前字符入栈（防止前导0入栈）
        if num[i] != '0' || len(stack) > 0 {
            stack = append(stack, num[i])
        }
    }
    // 移除的字符数量不足k个，依次出栈
    for k > 0 && len(stack) > 0{
        stack = stack[:len(stack)-1]
        k--
    }
    if len(stack) == 0 {
        return "0"
    }
    return string(stack)
}