Dawn's Blogs

分享技术 记录成长

0%

算法刷题笔记 (22) 零钱兑换II 打家劫舍 奇偶链表 Pow(x,n) 二叉搜索树中第K小的元素

发表于 更新于 分类于

零钱兑换 II

零钱兑换 II

解题思路

利用动态规划，dp[i]表示金额为i的硬币组合数，边界条件是dp[0] = 1，表示组成金额0有一种组合数。

  • 初始化：dp[0] = 1
  • 遍历coins，对于其中的每个元素coin：
    • 遍历i从coin到amount，dp[i] += dp[i-coin]
  • dp[amount]为最终答案

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
func change(amount int, coins []int) int {
    dp := make([]int, amount+1)     // dp[i]表示组成金额i的组合数
    dp[0] = 1

    for _, coin := range coins {
        for i := coin; i <= amount; i++ {
            dp[i] += dp[i-coin]
        }
    }

    return dp[amount]
}

打家劫舍

打家劫舍

解题思路

  1. 利用动态规划的思路，定义二维dp数组表示所能获取到的最大金额。其中dp[i][0]代表不偷取i号房屋所获得的最大金额，而dp[i][1]代码偷取i号房屋所获得的最大金额。

    • 初始化：dp[0][0] = 0、dp[0][1] = nums[0]、dp[1][0] = dp[0][1]、dp[1][1] = nums[1]

    • 状态转移方程：

      • `dp[i][0] = max(dp[i-1][0], dp[i-1][1])``
      • ``dp[i][1] = max(dp[i-2][1], dp[i-1][0]) + nums[i]`

    • 返回结果：max(dp[len(nums)-1][0], dp[len(nums)-1][1])

  2. 依然是动态规划的思路，只不过定义一维dp数组，dp[i]表示偷i间房子的最大金额。

    • 初始化：没有房子dp[0] = 0；只有一个房子，偷这个房子即可dp[i] = nums[0]
    • 状态转移方程：dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])，dp[i]有两种选择，不偷第i-1间房子（dp[i-1]）或者偷第i-1间房子（dp[i-2]+nums[i-1]）。

解题代码

  1. dp[i][0]代表不偷取i号房屋所获得的最大金额，而dp[i][1]代码偷取i号房屋所获得的最大金额
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 rob(nums []int) int {
    if len(nums) == 1 {
        // 只有一间房屋，直接窃取即可
        return nums[0]
    }
    // dp数组定义及其初始化
    // dp[i][0]表示不偷取i号房屋的最大金额
    // dp[i][1]表示偷取i号房屋获取的最大金额
    dp := make([][2]int, len(nums))
    dp[0][0] = 0
    dp[0][1] = nums[0]
    dp[1][0] = dp[0][1]
    dp[1][1] = nums[1]

    for i := 2; i < len(nums); i++ {
        dp[i][0] = max(dp[i-1][0], dp[i-1][1])
        dp[i][1] = max(dp[i-2][1], dp[i-1][0]) + nums[i]
    }

    return max(dp[len(nums)-1][0], dp[len(nums)-1][1])
}

func max(n1, n2 int) int {
    if n1 > n2 {
        return n1
    } else {
        return n2
    }
}
  1. 一维dp数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func rob(nums []int) int {
    dp := make([]int, len(nums)+1)
    dp[0] = 0
    dp[1] = nums[0]

    // 计算dp数组
    for i := 2; i <= len(nums); i++ {
        dp[i] = max(dp[i-1], dp[i-2]+nums[i-1])
    }

    return dp[len(nums)]
}

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

奇偶链表

奇偶链表

解题思路

将索引为偶数的节点全部从原链表中取下来，并组成一个新的偶数链表，那么原链表就是奇数链表。最后，将偶数链表挂到奇数链表之后即可。

解题代码

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
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func oddEvenList(head *ListNode) *ListNode {
    if head == nil {
        return head
    }
    // 首先将所有索引为偶数的节点全部摘下来，组成一个链表
    evenListHead := new(ListNode)   // 所有索引为偶数链表的头节点
    evenListTrail := evenListHead   // 所有索引为偶数链表的尾节点
    p := head
    oddListTrail := p   // 所有索引为奇数链表的尾节点
    for p != nil && p.Next != nil{
        // 将p的后继摘下来
        temp := p.Next
        p.Next = temp.Next
        temp.Next = nil
        // 放到偶数链表的尾部
        evenListTrail.Next = temp
        evenListTrail = evenListTrail.Next
        // p向后移动
        p = p.Next
        if p != nil {
            oddListTrail = p
        }
    }
    // 将偶数链表挂在oddListTrail之后
    oddListTrail.Next = evenListHead.Next
    
    return head
}

Pow(x,n)

Pow(x, n)

解题思路

快速幂，如2^10可以划分为两个2^5相乘，而2^5可以划分为2与两个2^2相乘。如此划分，直到划分为2^0=1

解题代码

  1. 递归
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
func myPow(x float64, n int) float64 {
    if n > 0 {
        return quickMul(x, n)
    } else {
        return 1.0 / quickMul(x, -n)
    }
}

func quickMul(x float64, n int) float64 {
    if n == 0 {
        return 1
    }
    y := quickMul(x, n/2)
    if n % 2 == 1 {
        // n为奇数
        return x*y*y
    } else {
        // n为偶数
        return y*y
    }
}
  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
func myPow(x float64, n int) float64 {
    if n > 0 {
        return quickMul(x, n)
    } else {
        return 1.0 / quickMul(x, -n)
    }
}

func quickMul(x float64, n int) float64 {
    ans := 1.0
    // 贡献的初始值为 x
    x_contribute := x
    for n > 0 {
        if n % 2 == 1 {
            // 如果 N 二进制表示的最低位为 1，那么需要计入贡献
            ans *= x_contribute
        }
        // 将贡献不断地平方
        x_contribute *= x_contribute
        // 舍弃 N 二进制表示的最低位，这样我们每次只要判断最低位即可
        n /= 2
    }

    return ans
}

二叉搜索树中第K小的元素

二叉搜索树中第K小的元素

解题思路

  1. 利用二叉搜索树的特性，二叉搜索树的中序遍历是个递增有序序列，所以可以利用数组记录前k个遍历节点，当第k小的元素遍历完成后跳出循环

  2. 计算左子树的节点总数为left

    • 若left==k-1，则当前根节点恰好是第k小的元素
    • 若left>k-1，则第k小的元素在左子树中，到左子树递归寻找第k小的元素
    • 若left<k-1，则第k小的节点在右子树中，第k小的节点也就是右子树的第k-left-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
33
34
35
36
37
38
39
40
41
42
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) int {
    firstKth := make([]int, k)  // 记录前k小的元素
    visitedNum := 0             // 已经遍历的节点数量
    stack := make([]*TreeNode, 0)     // 栈
    cur := root     // 记录当前节点
    // 二叉树的中序遍历
    for len(stack) > 0 || cur != nil {
        for cur != nil {
            stack = append(stack, cur)
            cur = cur.Left
        }
        if len(stack) > 0 {
            // 栈顶元素出栈
            cur = stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            // 访问
            if visitedNum < k {
                // 还在访问前k个元素
                firstKth[visitedNum] = cur.Val
            } else {
                // 前k个元素访问完成，直接结束中序遍历
                break
            }
            visitedNum++
            if cur.Right != nil {
                cur = cur.Right
            } else {
                cur = nil
            }
        }
    }

    return firstKth[k-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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func kthSmallest(root *TreeNode, k int) int {
    left := countNum(root.Left)     // 左子树的节点个数
    if left == k-1 {
        // 当前根节点恰好是第k小的节点
        return root.Val
    } else if left > k-1 {
        // 第k小的节点在左子树中
        return kthSmallest(root.Left, k)
    } else {
        // 第k小的节点在右子树中
        // 第k小的节点也就是右子树的第k-left-1小的节点
        return kthSmallest(root.Right, k-left-1)
    }
}

func countNum(root *TreeNode) int {     // 计算以root为根节点的二叉树节点总数
    if root != nil {
        left := countNum(root.Left)     // 左子树节点个数
        right := countNum(root.Right)   // 右子树节点个数

        return left+right+1
    }
    return 0
}