目录
332. 重新安排行程 Reconstruct Itinerary 🌟🌟🌟
334. 递增的三元子序列 Increasing Triplet Subsequence 🌟🌟
🌟 每日一练刷题专栏 🌟
Rust每日一练 专栏
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
332. 重新安排行程 Reconstruct Itinerary
给你一份航线列表 tickets ，其中 tickets[i] = [fromi, toi] 表示飞机出发和降落的机场地点。请你对该行程进行重新规划排序。
所有这些机票都属于一个从 JFK（肯尼迪国际机场）出发的先生，所以该行程必须从 JFK 开始。如果存在多种有效的行程，请你按字典排序返回最小的行程组合。
- 例如，行程
["JFK", "LGA"]与["JFK", "LGB"]相比就更小，排序更靠前。
假定所有机票至少存在一种合理的行程。且所有的机票 必须都用一次 且 只能用一次。
示例 1：
输入：tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] 输出：["JFK","MUC","LHR","SFO","SJC"]
示例 2：
输入：tickets = [["JFK","SFO"],["JFK","ATL"],["SFO","ATL"],["ATL","JFK"],["ATL","SFO"]] 输出：["JFK","ATL","JFK","SFO","ATL","SFO"] 解释：另一种有效的行程是 ["JFK","SFO","ATL","JFK","ATL","SFO"] ，但是它字典排序更大更靠后。
提示：
1 <= tickets.length <= 300tickets[i].length == 2fromi.length == 3toi.length == 3fromi和toi由大写英文字母组成fromi != toi
代码：
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))
}
输出：
[JFK MUC LHR SFO SJC]
[JFK ATL JFK SFO ATL SFO]
334. 递增的三元子序列 Increasing Triplet Subsequence
给你一个整数数组 nums ，判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ，使得 nums[i] < nums[j] < nums[k] ，返回 true ；否则，返回 false 。
示例 1：
输入：nums = [1,2,3,4,5] 输出：true 解释：任何 i < j < k 的三元组都满足题意
示例 2：
输入：nums = [5,4,3,2,1] 输出：false 解释：不存在满足题意的三元组
示例 3：
输入：nums = [2,1,5,0,4,6] 输出：true 解释：三元组 (3, 4, 5) 满足题意，因为 nums[3] == 0 < nums[4] == 4 < nums[5] == 6
提示：
1 <= nums.length <= 5 * 10^5-2^31 <= nums[i] <= 2^31 - 1
进阶：你能实现时间复杂度为 O(n) ，空间复杂度为 O(1) 的解决方案吗？
代码1：动态规划
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)
}
代码2：二分查找
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)
}
输出：
true
false
true
三重循环暴力枚举：
```golang
func increasingTriplet(nums []int) bool {
for i := 0; i < len(nums); i++ {
for j := i+1; j < len(nums); j++ {
if nums[j] > nums[i] {
for k := j+1; k < len(nums); k++ {
if nums[k] > nums[j] {
return true
}
}
}
}
}
return false
}
```
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
|
| Rust每日一练 专栏（2023.5.16~）更新中... |
|
| Golang每日一练 专栏（2023.3.11~）更新中... |
|
| Python每日一练 专栏（2023.2.18~2023.5.18）暂停更 |
|
| C/C++每日一练 专栏（2023.2.18~2023.5.18）暂停更 |
|
| Java每日一练 专栏（2023.3.11~2023.5.18）暂停更 |
