Golang每日一练(leetDay0115) 重新安排行程、递增的三元子序列

package main
import (
  "fmt"
  "sort"
)
func findItinerary(tickets [][]string) []string {
  // 构建图的邻接表
  graph := make(map[string][]string)
  for _, ticket := range tickets {
    from, to := ticket[0], ticket[1]
    graph[from] = append(graph[from], to)
  }
  // 对邻接表中的目的地进行字典排序
  for _, destinations := range graph {
    sort.Strings(destinations)
  }
  // 深度优先遍历，获取行程
  var itinerary []string
  var dfs func(from string)
  dfs = func(from string) {
    for len(graph[from]) > 0 {
      to := graph[from][0]
      graph[from] = graph[from][1:]
      dfs(to)
    }
    itinerary = append(itinerary, from)
  }
  dfs("JFK")
  // 将行程逆序，得到正确顺序
  for i, j := 0, len(itinerary)-1; i < j; i, j = i+1, j-1 {
    itinerary[i], itinerary[j] = itinerary[j], itinerary[i]
  }
  return itinerary
}
func main() {
  tickets := [][]string{{"MUC", "LHR"}, {"JFK", "MUC"}, {"SFO", "SJC"}, {"LHR", "SFO"}}
  fmt.Println(findItinerary(tickets))
  tickets = [][]string{{"JFK", "SFO"}, {"JFK", "ATL"}, {"SFO", "ATL"}, {"ATL", "JFK"}, {"ATL", "SFO"}}
  fmt.Println(findItinerary(tickets))
}

package main
import "fmt"
func increasingTriplet(nums []int) bool {
  if len(nums) < 3 {
    return false
  }
  first := nums[0]  // 记录当前最小值
  second := 1 << 31 // 初始化为一个较大的值
  for i := 1; i < len(nums); i++ {
    if nums[i] <= first {
      first = nums[i]
    } else if nums[i] <= second {
      second = nums[i]
    } else {
      // 找到了递增的三元子序列
      return true
    }
  }
  return false
}
func main() {
  nums := []int{1, 2, 3, 4, 5}
  result := increasingTriplet(nums)
  fmt.Println(result)
  nums = []int{5, 4, 3, 2, 1}
  result = increasingTriplet(nums)
  fmt.Println(result)
  nums = []int{2, 1, 5, 0, 4, 6}
  result = increasingTriplet(nums)
  fmt.Println(result)
}

package main
import "fmt"
func increasingTriplet(nums []int) bool {
    n := len(nums)
    if n < 3 {
        return false
    }
    subSeq := make([]int, 0, 3) // 存储递增子序列
    for _, num := range nums {
        if len(subSeq) == 0 || num > subSeq[len(subSeq)-1] {
            subSeq = append(subSeq, num)
            if len(subSeq) == 3 {
                return true
            }
        } else {
            left, right := 0, len(subSeq)-1
            for left < right {
                mid := left + (right-left)/2
                if subSeq[mid] >= num {
                    right = mid
                } else {
                    left = mid + 1
                }
            }
            subSeq[right] = num
        }
    }
    return false
}
func main() {
  nums := []int{1, 2, 3, 4, 5}
  result := increasingTriplet(nums)
  fmt.Println(result)
  nums = []int{5, 4, 3, 2, 1}
  result = increasingTriplet(nums)
  fmt.Println(result)
  nums = []int{2, 1, 5, 0, 4, 6}
  result = increasingTriplet(nums)
  fmt.Println(result)
}