Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (5) 相交链表 合并两个有序数组 买卖股票的最佳时机 有效的括号 二叉树的锯齿形层次遍历

发表于 更新于 分类于

相交链表

相交链表

解题思路

首先计算两个链表的长度len1和len2，对于较长的链表，其指针先向后移动|len1-len2|步，接着两个链表的指针同步向后移动，当两个指针相等时，说明到达了相交链表的第一个节点。

解题代码

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func getIntersectionNode(headA, headB *ListNode) *ListNode {
    if headA == nil || headB == nil {
        return nil
    }
    len1, len2 := Length(headA), Length(headB)  // 求两个链表的长度
    p, q := headA, headB // p, q分别指向两个链表头部

    // 长度较长的先走|len1-len2|步
    if len1 > len2 {
        k := len1 - len2
        p = MoveKStep(p, k)
    } else {
        k := len2 - len1
        q = MoveKStep(q, k)
    }

    // 二者同步向后走
    for p != nil {
        if p == q { // 找到相交的起始节点
            return p
        }
        // 同步向后移动
        p = p.Next
        q = q.Next
    }

    return nil
}

func Length(head *ListNode) int {   // 链表长度
    var length int
    p := head
    for p != nil {
        p = p.Next
        length++
    }

    return length
}

func MoveKStep(p *ListNode, k int) *ListNode { // 链表指针向后移动k步
    for k > 0 {
        p = p.Next
        k--
    }
    return p
}

合并两个有序数组

合并两个有序数组

解题思路

因为需要合并nums2到nums1，所以设立一个辅助数组aux，拷贝nums1的所有值到aux之中。接着利用归并的思想，合并两个有序数组。

解题代码

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
func merge(nums1 []int, m int, nums2 []int, n int)  {


    aux := make([]int, m)   // 辅助数组
    copy(aux, nums1)    // 将nums1的前m个值拷贝给辅助数组

    var i, j, k int // i,j,k分别指向aux的下标，nums2的下标，nums1的下标

    for i < m && j < n {
        // 选取aux[i] 与 nums2[j] 之中的较小者
        if aux[i] <= nums2[j] {
            nums1[k] = aux[i]
            i++
            k++
        } else {
            nums1[k] = nums2[j]
            j++
            k++
        }
    }

    for i < m { // 剩余元素直接复制
        nums1[k] = aux[i]
        i++
        k++
    }

    for j < n { // 剩余元素直接复制
        nums1[k] = nums2[j]
        j++
        k++
    }
}

买卖股票的最佳时机

买卖股票的最佳时机

解题思路

  1. 暴力法，遍历出所有的可能性，时间复杂度为O(n^2)

  2. 动态规划，以minPrice表示当前最小价格，dp[i]表示前i天的最大利润，因为追求利润最大化，故dp[i] = max{ dp[i-1], prices-minPrice }，时间复杂度降为O(n)，空间复杂度为O(n)。因为求dp[i]只用到了dp[i-1]，所以可以利用int型变量记录，空间复杂度降为O(1)

解题代码

  1. 暴力法
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func maxProfit(prices []int) int {
    n := len(prices)
    if n == 1 {
        return 0
    }

    var profit int  // 利润
    for i := 0; i < n-1; i++ {    // 假设第i天买入
        for j := i+1; j < n; j++ {  // 第j天卖出
            if prices[j] - prices[i] > profit {
                profit = prices[j] - prices[i]
            }
        }
    }

    return profit
}
  1. 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func maxProfit(prices []int) int {
    n := len(prices)
    var dp int  // 相当于dp[0] = 0
    minPrice := prices[0]   // 当前最小价格

    for i := 1; i < n; i++ {
        if prices[i] < minPrice {
            minPrice = prices[i]    // 更新当前最小价格
        }
        if dp < prices[i] - minPrice {  //dp[i] = max{ dp[i-1], prices-minPrice }
            dp = prices[i] - minPrice
        }   
    }

    return dp
}

有效的括号

括号匹配

解题思路

利用栈来记录待匹配的左括号，从前向后遍历字符串，若遇到左括号则入栈，若遇到右括号，则栈顶元素出栈匹配右括号，若栈为空或者括号类型不匹配直接返回false。当遍历完字符串后，若栈不为空，说明多出了左括号，返回false；栈为空返回true

解题代码

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
func isValid(s string) bool {
    n := len(s) // 字符串长度
    stack := make([]rune, n)    // 栈
    top := -1 // 栈顶指针

    for _, val := range s {
        if val == '(' || val == '[' || val == '{' {
            // 左括号入栈
            top++
            stack[top] = val
        } else {    // 右括号
            if top == -1 {
                return false
            } else if (val == ')' && stack[top] == '(') ||
            (val == ']' && stack[top] == '[') ||
            (val == '}' && stack[top] == '{') {
                // 左右括号匹配，直接栈顶出栈，读取下一个字符
                top--
            } else {
                // 括号不匹配
                return false
            }
        }
    }

    if top != -1 {   // 栈不为空，说明多出了左括号
        return false
    } else {
        return true
    }
}

二叉树的锯齿形层次遍历

二叉树的锯齿形层次遍历

解题思路

以二叉树的层序遍历为基础，将队列改为栈，来进行层序遍历。

  • 当遍历第偶数层（以根节点为第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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func zigzagLevelOrder(root *TreeNode) [][]int {
    ret := [][]int{}
    
    if root == nil {    // 树为空直接返回
        return ret
    }

    q := []*TreeNode{root}

    for i := 0; len(q) > 0; i++ {   // 遍历第i层(i从0开始)
        p := []*TreeNode{}  // 记录下一层节点
        ret = append(ret, []int{})
        for j := 0; j < len(q); j++ {
            cur := q[len(q)-j-1]    // 栈顶元素出栈
            ret[i] = append(ret[i], cur.Val)
            if i % 2 == 0 { // 从左向右入栈
                if cur.Left != nil {
                    // 左子树不为空，入栈
                    p = append(p, cur.Left)
                }
                if cur.Right != nil {
                    // 右子树不为空，入栈
                    p = append(p, cur.Right)
                }
            } else {    // 从右向左入栈
                if cur.Right != nil {
                    // 右子树不为空，入栈
                    p = append(p, cur.Right)
                }
                if cur.Left != nil {
                    // 左子树不为空，入栈
                    p = append(p, cur.Left)
                }
            }
        }
        q = p
    }

    return ret
}