Golang每日一练(leetDay0045) 克隆图、加油站、分发糖果

package main
import "fmt"
type Node struct {
  Val       int
  Neighbors []*Node
}
func cloneGraph(nodes []*Node) []*Node {
  n := len(nodes)
  clone := make([]*Node, n)
  for i := 0; i < n; i++ {
    visited := make(map[*Node]*Node)
    clone[i] = dfs(nodes[i], visited)
  }
  return clone
}
func dfs(node *Node, visited map[*Node]*Node) *Node {
  if node == nil {
    return nil
  }
  // 如果已经访问过，直接返回
  if n, ok := visited[node]; ok {
    return n
  }
  // 深拷贝节点
  copy := &Node{Val: node.Val}
  visited[node] = copy
  // 深拷贝邻居节点
  for _, neighbor := range node.Neighbors {
    copy.Neighbors = append(copy.Neighbors, dfs(neighbor, visited))
  }
  return copy
}
func createGraph(arr [][]int) []*Node {
  n := len(arr)
  nodes := make([]*Node, n)
  for i := 1; i <= n; i++ {
    nodes[i-1] = &Node{Val: i}
  }
  for i := 1; i <= n; i++ {
    for _, j := range arr[i-1] {
      nodes[i-1].Neighbors = append(nodes[i-1].Neighbors, nodes[j-1])
    }
  }
  return nodes
}
func printGraph(nodes []*Node) {
  for _, node := range nodes {
    neighbors := make([]int, len(node.Neighbors))
    for i, neighbor := range node.Neighbors {
      neighbors[i] = neighbor.Val
    }
    fmt.Printf("%d: %v ", node.Val, neighbors)
  }
  fmt.Println()
}
func main() {
  adjList := [][]int{{2, 4}, {1, 3}, {2, 4}, {1, 3}}
  nodes := createGraph(adjList)
  printGraph(nodes)
  clone := cloneGraph(nodes)
  printGraph(clone)
  adjList = [][]int{{2, 3, 4}, {1, 3}, {1, 2, 4}, {1, 3}}
  nodes = createGraph(adjList)
  printGraph(nodes)
  clone = cloneGraph(nodes)
  printGraph(clone)
  adjList = [][]int{{2, 3, 4}, {1, 3, 4}, {1, 2, 4}, {1, 2, 3}}
  nodes = createGraph(adjList)
  printGraph(nodes)
  clone = cloneGraph(nodes)
  printGraph(clone)
  adjList = [][]int{{2}, {1}}
  nodes = createGraph(adjList)
  printGraph(nodes)
  clone = cloneGraph(nodes)
  printGraph(clone)
}

package main
import (
  "fmt"
)
func canCompleteCircuit(gas []int, cost []int) int {
  n := len(gas)
  for i := 0; i < n; i++ {
    if gas[i] < cost[i] {
      continue
    }
    tank := 0
    for j := 0; j < n; j++ {
      k := (i + j) % n
      tank += gas[k] - cost[k]
      if tank < 0 {
        break
      }
    }
    if tank >= 0 {
      return i
    }
  }
  return -1
}
func main() {
  gas := []int{1, 2, 3, 4, 5}
  cost := []int{3, 4, 5, 1, 2}
  fmt.Println(canCompleteCircuit(gas, cost))
  gas = []int{2, 3, 4}
  cost = []int{3, 4, 3}
  fmt.Println(canCompleteCircuit(gas, cost))
}

package main
import (
  "fmt"
)
func canCompleteCircuit(gas []int, cost []int) int {
  n := len(gas)
  start, total, tank := 0, 0, 0
  for i := 0; i < n; i++ {
    total += gas[i] - cost[i]
    tank += gas[i] - cost[i]
    if tank < 0 {
      start = i + 1
      tank = 0
    }
  }
  if total < 0 {
    return -1
  } else {
    return start
  }
}
func main() {
  gas := []int{1, 2, 3, 4, 5}
  cost := []int{3, 4, 5, 1, 2}
  fmt.Println(canCompleteCircuit(gas, cost))
  gas = []int{2, 3, 4}
  cost = []int{3, 4, 3}
  fmt.Println(canCompleteCircuit(gas, cost))
}

package main
import "fmt"
func candy(ratings []int) int {
  n := len(ratings)
  if n == 0 {
    return 0
  }
  candies := make([]int, n)
  for i := 0; i < n; i++ {
    candies[i] = 1
  }
  for i := 1; i < n; i++ {
    if ratings[i] > ratings[i-1] {
      candies[i] = candies[i-1] + 1
    }
  }
  for i := n - 2; i >= 0; i-- {
    if ratings[i] > ratings[i+1] && candies[i] <= candies[i+1] {
      candies[i] = candies[i+1] + 1
    }
  }
  sum := 0
  for i := 0; i < n; i++ {
    sum += candies[i]
  }
  return sum
}
func main() {
  ratings := []int{1, 0, 2}
  fmt.Println(candy(ratings))
  ratings = []int{1, 2, 2}
  fmt.Println(candy(ratings))
}

package main
import "fmt"
func candy(ratings []int) int {
  n := len(ratings)
  if n == 0 {
    return 0
  }
  left := make([]int, n)
  for i := 0; i < n; i++ {
    left[i] = 1
    if i > 0 && ratings[i] > ratings[i-1] {
      left[i] = left[i-1] + 1
    }
  }
  right := make([]int, n)
  for i := n - 1; i >= 0; i-- {
    right[i] = 1
    if i < n-1 && ratings[i] > ratings[i+1] {
      right[i] = right[i+1] + 1
    }
  }
  sum := 0
  for i := 0; i < n; i++ {
    sum += max(left[i], right[i])
  }
  return sum
}
func max(a, b int) int {
  if a > b {
    return a
  }
  return b
}
func main() {
  ratings := []int{1, 0, 2}
  fmt.Println(candy(ratings))
  ratings = []int{1, 2, 2}
  fmt.Println(candy(ratings))
}