Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (10) 最长回文子串 合并K个排序链表 合并区间 二叉树的最大高度 平衡二叉树

发表于 更新于 分类于

最长回文子串

最长回文子串

解题思路

  1. 中心扩展算法，从每个位置出发，向两边扩展，若遇到的是回文子串，就继续扩展；若不是回文子串就结束，到下一个位置去。扩展方法：

    • 向左扩展，向左寻找与当前位置相同的字符，直到遇到不等的字符为止
    • 向右扩展，向右扩展，向右寻找与当前位置相同的字符，直到遇到不等的字符为止
    • 左右双向扩展，同时向左右扩展，直到遇到左右字符不等为止

  2. 动态规划法，用dp[i][j]表示字符串s从第i个字符到第j个字符是否未回文子串（true表示是回文子串，false表示不是回文子串）。

    • 则状态转移方程为dp[i][j] = dp[i+1][j-1] ^ (s[i] == s[j])
    • 边界条件
      • 只有一个字符时，肯定是回文子串dp[i][i] = true
      • 只有两个字符时，只要两个字符相等就一定是回文子串dp[i][i+1] = (s[i] == s[i+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
func longestPalindrome(s string) string {
    len := len(s)   // 字符串长度
    var left, right int // 扩展的左右边界
    var maxStart, maxLen int    // 最长回文子串的起始位置，最长回文子串的长度

    for i := 0; i < len; i++ {
        curLen := 1    // 当前回文子串长度
        for left = i-1; left >= 0 && s[left] == s[i]; left-- {
            // 向左扩展，直到遇到与当前字符不等的字符为止
            curLen++
        }
        for right = i+1; right < len && s[right] == s[i]; right++ {
            // 向右扩展，直到遇到与当前字符不等的字符为止
            curLen++
        }
        for left >= 0 && right < len {
            // 左右扩展，直到遇到左右字符不相等为止
            if s[left] != s[right] {
                break
            }
            left--
            right++
            curLen+=2
        }
        if curLen > maxLen {
            maxLen = curLen
            maxStart = left+1
        }
    }

    return s[maxStart:maxStart + maxLen]
}
  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
func longestPalindrome(s string) string {
    len := len(s)   // 字符串长度
    if len < 2 {
        // 长度为0 或 1，直接返回
        return s
    }
    var maxStart int    // 最长回文子串的起始位置
    maxLen := 1     //最长回文子串的长度
    // 声明dp数组
    dp := make([][]bool, len)
    for i := 0; i < len; i++ {
        dp[i] = make([]bool, len)
        //dp[i][i] = true // 1个字符必为回文子串
    }

    for j := 1; j < len; j++ {
        for i := 0; i < j; i++ {
            if s[i] == s[j] && (j-i <= 2 || dp[i+1][j-1] == true) {
                // 当j = i+1时，dp[i][j] = (s[i] == s[i+1])
                // 当j > i+1时，dp[i][j] = dp[i+1][j-1] && (s[i] == s[j])
                dp[i][j] = true
                if j-i+1 > maxLen {
                    maxStart = i
                    maxLen = j-i+1
                }
            }
        }
    }
    return s[maxStart:maxStart+maxLen]
}

合并K个排序链表

合并K个排序链表

解题思路

  1. 暴力法，根据归并的思想，每次选取排序链表组中值最小的节点加入到结果链表中

  2. 顺序合并，对于两个有序链表的合并是简单的，那么可以逐一合并各个链表，第i次合并第i个链表

  3. 分治合并，对方法2进行优化，不对其进行顺序合并，而是两两合并。

    • 若有k个链表，第一轮合并k/2组链表，每一组时间代价是O(2n)
    • 第二轮合并k/4组链表，每一组时间代价O(4n)
    • 以此类推，最后剩下一个链表即为结果

解题代码

  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
43
44
45
46
47
48
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    newHead := &ListNode{}  // 新的有序链表的头节点
    rear := newHead // 指向新的有序链表的尾部
    p := make([]*ListNode, len(lists))  // p[i]指向lists中第i个链表
    for i := 0; i < len(lists); i++ {
        p[i] = lists[i]
    }
    var overNum int // 已完成合并的链表个数
    for overNum <= len(lists)-1 { // 合并len(lists)-1个链表
        // 找到值最小的节点
        min := p[0]
        minIndex := 0   // 值最小节点指针下标
        for i := 0; i < len(lists); i++ {
            if min == nil || (p[i] != nil && p[i].Val < min.Val) {
                min = p[i]
                minIndex = i
            }
        }
        if min == nil {
            break
        }
        p[minIndex] = p[minIndex].Next    // p[minIndex]后移
            if p[minIndex] == nil {
            // 已完成一个链表的合并
            overNum++
        }
        rear.Next = min    // rear后插入最小节点min
        rear = rear.Next    // rear后移
        rear.Next = nil     // rear的后继设置为nil
    }
    
    // 将剩余的一个未合并完成的直接加入到结果链表的后面
    for i := 0; i < len(p); i++ {
        if p[i] != nil {
            rear.Next = p[i]
            break
        }
    }

    return newHead.Next
}
  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
43
44
45
46
47
48
49
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    if len(lists) == 0 {
        return nil
    }
    res := lists[0]
    for i := 1; i < len(lists); i++ {
        res = mergeList(res, lists[i])
    }

    return res
}

func mergeList(l1, l2 *ListNode) *ListNode {    // 合并两个顺序链表
    newHead := &ListNode{}  // 虚拟链表头
    rear := newHead // rear指向结果链表的尾部
    p, q := l1, l2  // p q分别指向两个链表

    for p!= nil && q != nil {
        // 将较小值的节点加入到结果链表之后
        if p.Val < q.Val {
            rear.Next = p
            p = p.Next
            rear = rear.Next
            rear.Next = nil
        } else {
            rear.Next = q
            q = q.Next
            rear = rear.Next
            rear.Next = nil
        }
    }

    // 若有链表还未合并完，直接加入到结果链表之后
    if p != nil {
        rear.Next = p
    }
    if q != nil {
        rear.Next = q
    }

    return newHead.Next // 返回结果不需要虚拟头节点
}
  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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func mergeKLists(lists []*ListNode) *ListNode {
    k := len(lists)  // 有k个链表需要合并
    if k == 0 {
        return nil
    }
    for k > 1 { // k>1时循环，最终只剩下1个链表
        newLists := make([]*ListNode, 0)
        k = 0
        for i := 0; i < len(lists); i+=2 {
            if i != len(lists)-1 {
                // 两两合并
                newLists = append(newLists, mergeList(lists[i], lists[i+1]))
                k++
            } else {
                // 剩余一个直接加入
                newLists = append(newLists, lists[i])
                k++
            }
        }
        lists = newLists
    }

    return lists[0]
}

func mergeList(l1, l2 *ListNode) *ListNode {    // 合并两个顺序链表
    newHead := &ListNode{}  // 虚拟链表头
    rear := newHead // rear指向结果链表的尾部
    p, q := l1, l2  // p q分别指向两个链表

    for p!= nil && q != nil {
        // 将较小值的节点加入到结果链表之后
        if p.Val < q.Val {
            rear.Next = p
            p = p.Next
            rear = rear.Next
            rear.Next = nil
        } else {
            rear.Next = q
            q = q.Next
            rear = rear.Next
            rear.Next = nil
        }
    }

    // 若有链表还未合并完，直接加入到结果链表之后
    if p != nil {
        rear.Next = p
    }
    if q != nil {
        rear.Next = q
    }

    return newHead.Next // 返回结果不需要虚拟头节点
}

合并区间

合并区间

解题思路

首先对区间的左端点进行排序，那么在排完序的列表中，可以合并的区间一定是连续的。将第一个区间加入结果res中，并且按顺序考虑每个区间：

  • 若当前区间与结果集的最后一个区间不相交，那么将当前区间加入到结果集中
  • 若当前区间与结果集的最后一个区间相交，那么进一步考虑若当前的右端点在结果集的最后一个区间的右端点的右侧，则更新结果集中最后一个区间的右端点

解题代码

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

func merge(intervals [][]int) [][]int {
    if len(intervals) == 0 {
        return nil
    }
    // 根据左端点对区间的进行排序
    ints := ints(intervals)
    sort.Sort(ints)
    intervals = [][]int(ints)
    // 记录结果
    res := [][]int{intervals[0]}

    for i := 1; i < len(intervals); i++ {
        if intervals[i][0] > res[len(res)-1][1] {
            // 两个区间不相交，将当前区间加入到结果集中
            res = append(res, intervals[i])
        } else {
            // 两个区间相交，合并区间
            if intervals[i][1] > res[len(res)-1][1] {
                // 向右延展区间
                res[len(res)-1][1] = intervals[i][1]
            }
        }
    }
    return res
}


// 以下实现sort.Interface接口
func (this ints) Len() int {
    return len(this)
}

func (this ints) Less(i, j int) bool {
    if this[i][0] < this[j][0] {
        return true
    } else {
        return false
    }
}

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

二叉树的最大高读

二叉树的最大深度

解题思路

基于二叉树的后续遍历，首先得到左子树高度left，右子树高度right，二叉树高度为1 + max(left, right)

解题代码

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func maxDepth(root *TreeNode) int {
    var postorder func(root *TreeNode) int
    postorder = func(root *TreeNode) int {
        if root != nil {
            left := postorder(root.Left) // 左子树高度
            right := postorder(root.Right)   // 右子树高度
            return 1 + max(left, right)
        } else {
            // 空树高度为0
            return 0
        }
    }
    return postorder(root)
}

func max(n1, n2 int) int {
    if n1 > n2 {
        return n1
    } else {
        return n2
    }
}

平衡二叉树

平衡二叉树

解题思路

若left为左子树高度，right为右子树高度，若|left - right| <= 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
43
44
45
46
47
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func isBalanced(root *TreeNode) bool {
    if root != nil {
        left := height(root.Left)   // 左子树高度
        right := height(root.Right) // 右子树高度

        return abs(left-right) <= 1 && isBalanced(root.Left) && isBalanced(root.Right)
    } else {
        // 空树也是平衡二叉树
        return true
    }
    
}

func height(root *TreeNode) int {
    if root != nil {
        left := height(root.Left) // 左子树高度
        right := height(root.Right)   // 右子树高度
        return 1 + max(left, right)
    } else {
        // 空树高度为0
        return 0
    }
}

func max(n1, n2 int) int {
    if n1 > n2 {
        return n1
    } else {
        return n2
    }
}

func abs(n int) int {
    if n >= 0 {
        return n
    } else {
        return -n
    }
}