力扣小记 108、46、322

108.将有序数组转换为二叉搜索树

https://leetcode.cn/problems/convert-sorted-array-to-binary-search-tree

思路:
根据题意是构造一棵平衡的BST, 对于BST的每个节点都有着root.left < root < root.right, 先找到root节点在别分构建左子树和右子树

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    return build(nums, 0, len(nums)-1)
}

func build(nums []int, start, end int) *TreeNode {
    if start > end {
        return nil
    }
    mid := start + (end - start) / 2
    root := &TreeNode{
        Val: nums[mid],
        Left: build(nums, start, mid-1),
        Right: build(nums, mid+1, end),
    }
    return root
}

46.全排列

https://leetcode.cn/problems/permutations

思路:
回溯,选出一个数字对剩下的数字排列组合

var res [][]int
func permute(nums []int) [][]int {
    res = [][]int{}
    backtrack(nums, len(nums), []int{})
    return res
}

func backtrack(nums []int, numsLen int, path []int) {
    if len(nums) == 0 {
        p := make([]int, len(path))
        copy(p, path)
        res = append(res, p)
    }
    for i := 0; i < numsLen; i++ {
        cur := nums[i]
        path = append(path, cur)
        nums = append(nums[:i], nums[i+1:]...)
        backtrack(nums, len(nums), path)
        nums = append(nums[:i], append([]int{cur}, nums[i:]...)...)
        path = path[:len(path)-1]
    }
}

322.零钱兑换

https://leetcode.cn/problems/coin-change

思路:
先画出递归树, 用动态规划解,定义dp数组: 第i金额最少需要用dp[i]枚硬币

func coinChange(coins []int, amount int) int {
    dp := make([]int, amount + 1)
    for i := 0; i < len(dp); i++ {
        dp[i] = amount + 1
    }
    dp[0] = 0
    for i := 0; i < len(dp); i++ {
        for _, coin := range coins {
            if i - coin < 0 {
                continue
            }
            dp[i] = min(dp[i], 1+dp[i-coin])
        }
    }
    if dp[amount] == amount + 1 {
        return -1
    }
    return dp[amount]
}

func min(i, j int) int {
    if i < j {
        return i
    }
    return j
}