133. 克隆图 Clone Graph

给你无向连通图中一个节点的引用，请你返回该图的深拷贝（克隆）。

图中的每个节点都包含它的值 val（int）和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

测试用例格式：

简单起见，每个节点的值都和它的索引相同。例如，第一个节点值为 1（val = 1），第二个节点值为 2（val = 2），以此类推。该图在测试用例中使用邻接列表表示。

邻接列表是用于表示有限图的无序列表的集合。每个列表都描述了图中节点的邻居集。

给定节点将始终是图中的第一个节点（值为 1）。你必须将给定节点的拷贝作为对克隆图的引用返回。

示例 1：

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]

输出：[[2,4],[1,3],[2,4],[1,3]]

解释：

图中有 4 个节点。

节点 1 的值是 1，它有两个邻居：节点 2 和 4 。

节点 2 的值是 2，它有两个邻居：节点 1 和 3 。

节点 3 的值是 3，它有两个邻居：节点 2 和 4 。

节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

示例 2：

输入：adjList = [[]]

输出：[[]]

解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

示例 3：

输入：adjList = []

输出：[]

解释：这个图是空的，它不含任何节点。

示例 4：

输入：adjList = [[2],[1]]

输出：[[2],[1]]

提示：

节点数不超过 100 。

每个节点值 Node.val 都是唯一的，1 <= Node.val <= 100。

无向图是一个简单图，这意味着图中没有重复的边，也没有自环。

由于图是无向的，如果节点 p 是节点 q 的邻居，那么节点 q 也必须是节点 p 的邻居。

图是连通图，你可以从给定节点访问到所有节点。

代码：

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)
}

输出：

1: [2 4] 2: [1 3] 3: [2 4] 4: [1 3]

1: [2 3 4] 2: [1 3] 3: [1 2 4] 4: [1 3]

1: [2 3 4] 2: [1 3 4] 3: [1 2 4] 4: [1 2 3]

1: [2] 2: [1]

134. 加油站 Gas Station

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的。

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]

输出: 3

解释:

从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油

开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油

开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油

开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油

开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油

开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。

因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]

输出: -1

解释:

你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。

我们从 2 号加油站出发，可以获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油

开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油

开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油

你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。

因此，无论怎样，你都不可能绕环路行驶一周。

提示:

gas.length == n

cost.length == n

1 <= n <= 10^5

0 <= gas[i], cost[i] <= 10^4

代码1：暴力枚举

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))
}

代码2： 贪心算法

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))
}

输出：

-1

135. 分发糖果 Candy

n 个孩子站成一排。给你一个整数数组 ratings 表示每个孩子的评分。

你需要按照以下要求，给这些孩子分发糖果：

每个孩子至少分配到 1 个糖果。

相邻两个孩子评分更高的孩子会获得更多的糖果。

请你给每个孩子分发糖果，计算并返回需要准备的最少糖果数目。

示例 1：

输入：ratings = [1,0,2]

输出：5

解释：你可以分别给第一个、第二个、第三个孩子分发 2、1、2 颗糖果。

示例 2：

输入：ratings = [1,2,2]

输出：4

解释：你可以分别给第一个、第二个、第三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果，这满足题面中的两个条件。

提示：

n == ratings.length

1 <= n <= 2 * 10^4

0 <= ratings[i] <= 2 * 10^4

代码1：

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))
}

代码2：

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))
}