Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (9) 二叉树的右视图 重排链表 删除排序链表中的重复元素 x的平方根 爬楼梯

发表于 更新于 分类于

二叉树的右视图

二叉树的右视图

解题思路

利用二叉树的层序遍历，将每一层的最右侧节点加入到结果中

解题代码

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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func rightSideView(root *TreeNode) []int {
    if root == nil {
        // 树为空
        return []int{}
    }
    res := []int{}  // 记录结果
    q := []*TreeNode{root}  // 队列，根节点入队

    for i := 0; len(q) > 0; i++ {
        p := []*TreeNode{}  // p记录下一层节点
        res = append(res, q[len(q)-1].Val) // 将本层最右边的节点加入结果集
        for j := 0; j < len(q); j++ {
            // 将下一层节点加入队列
            cur := q[j]
            if cur.Left != nil {
                // 左子树不为空，入队
                p = append(p, cur.Left)
            }
            if cur.Right != nil {
                // 右子树不为空，入队
                p = append(p, cur.Right)
            }
        }
        q = p   // 已经遍历过本层节点，将q更新为下一层节点
    }

    return 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
46
47
48
49
50
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reorderList(head *ListNode)  {
    mid := midNode(head)    // 得到中间的节点
    l1, l2 := head, mid.Next    // 待合并的两个链表头
    mid.Next = nil
    l2 = reverse(l2)    // 反转后面的链表

    // 下面开始合并l1, l2
    p, q := l1, l2  // p q 分别指向l1 l2
    for q != nil {
        r := q.Next // 记录q的后继
        // 将q指向的节点插入到p后面
        q.Next = p.Next
        p.Next = q
        // p q向后移动
        p = q.Next  // p指向新插入q的后继
        q = r
    }
}

func midNode(head *ListNode) *ListNode { // 返回链表最中间的节点（个数为偶数时，返回靠左侧的节点）
    // 定义快慢指针
    low, fast := head, head
    for fast.Next != nil && fast.Next.Next != nil {
        // 慢指针走一步
        low = low.Next
        // 快指针走两步
        fast = fast.Next.Next
    }

    return low
}

func reverse(head *ListNode) *ListNode {    // 链表逆置，返回链表头
    var pre, cur *ListNode  // cur为当前节点，pre为cur的前驱
    cur = head
    
    for cur != nil {
        // 链表原地逆置
        pre, cur, cur.Next = cur, cur.Next, pre
    }

    return pre  // 返回链表头
}

删除排序链表中的重复元素 II

删除排序链表中的重复元素 II

解题思路

遍历单链表，循环删除所有与当前遍历节点值相同的后继节点，若当前节点是重复的，则同时删除当前节点

解题代码

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func deleteDuplicates(head *ListNode) *ListNode {
    // 新建一个虚拟的头节点，指向原链表头
    newHead := &ListNode{}
    newHead.Next = head
    
    cur, pre := head, newHead   // cur指向当前遍历的节点，pre为cur的前驱
    var flag bool   // 标记当前节点是否为重复节点
    
    for cur != nil {
        flag = false
        for cur.Next != nil && cur.Val == cur.Next.Val {
            // 当cur的下一个节点的Val等于cur的Val时循环，删除与cur的Val相同的下一个节点
            // 删除下一个节点
            cur.Next = cur.Next.Next
            // 标记当前节点重复
            flag = true
        }
        // 此时cur后继的Val与cur不同
        if flag {
            // cur为重复节点，删除cur
            pre.Next = cur.Next
            cur = pre.Next
        } else {
            // cur不是重复节点，pre cur同步后移
            pre = cur
            cur = cur.Next
        }
    }

    return newHead.Next // 返回虚拟头节点的下一个节点
}

x 的平方根

x 的平方根

解题思路

利用二分查找，由于x平方根的整数部分ans是满足k^2 ≤x的最大k值，因此我们可以对k进行二分查找，从而得到答案。

二分查找的下界为0，上界可以粗略地设定为x。在二分查找的每一步中，我们只需要比较中间元素mid的平方与x的大小关系，并通过比较的结果调整上下界的范围。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
func mySqrt(x int) int {
    low, high := 0, x   // 二分查找的上下界
    var ans int

    for low <= high {
        mid := (low + high) / 2
        sqr := mid*mid
        if sqr == x {
            // mid^2刚好等于x
            return mid
        } else if sqr < x {
            // mid太小，进入左区间
            // mid可能是ans
            ans = mid
            low = mid + 1
        } else {
            // sqr > x
            // mid太大，进入右区间
            high = mid - 1
        }
    }
    
    return ans
}

爬楼梯

爬楼梯

解题思路

利用动态规划的思想，设dp[i]为爬上第i层的方法数，那么登上第i层台阶可以从第i-1层爬一层台阶，或者从第i-1层爬两层台阶，故dp[i] = dp[i-1] + dp[i-2]

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
func climbStairs(n int) int {
    // dp数组的声明及其初始化
    dp := make([]int, n+1)
    dp[0] = 1
    dp[1] = 1

    // 计算dp[i]
    for i := 2; i <= n; i++ {
        dp[i] = dp[i-1] + dp[i-2] 
    }

    return dp[n]
}