力扣小记 108、46、322

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* 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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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]枚硬币

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
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
}
文章作者: Twac
文章链接: https://blog.xiaohao233.top/LeetCode/leetcode/2022-11-12/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Twacの自习室