Golang每日一练(leetDay0105) 最小高度树、戳气球

package main
import "fmt"
func findMinHeightTrees(n int, edges [][]int) []int {
  if n == 1 {
    return []int{0}
  }
  //创建邻接列表
  edgesmap := make([]map[int]bool, n)
  for i := 0; i < n; i++ {
    edgesmap[i] = make(map[int]bool)
  }
  for _, edge := range edges {
    edgesmap[edge[0]][edge[1]] = true
    edgesmap[edge[1]][edge[0]] = true
  }
  // 处理叶节点
  leaves := []int{}
  for i := 0; i < n; i++ {
    if len(edgesmap[i]) == 1 {
      leaves = append(leaves, i)
    }
  }
  // 最小高度的树
  for n > 2 {
    n -= len(leaves)
    newLeaves := []int{}
    for _, i := range leaves {
      var j int
      for j = range edgesmap[i] {
        break
      }
      delete(edgesmap[j], i)
      if len(edgesmap[j]) == 1 {
        newLeaves = append(newLeaves, j)
      }
    }
    leaves = newLeaves
  }
  return leaves
}
func main() {
  n := 4
  edges := [][]int{{1, 0}, {1, 2}, {1, 3}}
  fmt.Println(findMinHeightTrees(n, edges))
  n = 6
  edges = [][]int{{3, 0}, {3, 1}, {3, 2}, {3, 4}, {5, 4}}
  fmt.Println(findMinHeightTrees(n, edges))
}

package main
import "fmt"
func maxCoins(nums []int) int {
    n := len(nums)
    // 添加两个边界
    newNums := make([]int, n+2)
    newNums[0], newNums[n+1] = 1, 1
    for i := 1; i <= n; i++ {
        newNums[i] = nums[i-1]
    }
    // 定义dp数组
    dp := make([][]int, n+2)
    for i := range dp {
        dp[i] = make([]int, n+2)
    }
    // 状态转移
    for l := 3; l <= n+2; l++ { // 区间长度，从3开始
        for i := 0; i+l-1 <= n+1; i++ { // 起始点
            j := i + l - 1 // 结束点
            for k := i+1; k < j; k++ { // 最后被扎破的气球
                dp[i][j] = max(dp[i][j], dp[i][k]+dp[k][j]+newNums[i]*newNums[k]*newNums[j])
            }
        }
    }
    return dp[0][n+1]
}
func max(x, y int) int {
    if x > y {
        return x
    }
    return y
}
func main() {
    nums1 := []int{3,1,5,8}
    fmt.Println(maxCoins(nums1))
    nums2 := []int{1,5}
    fmt.Println(maxCoins(nums2))
}