1. 二叉树展开为链表(114)

给你二叉树的根结点 root ,请你将它展开为一个单链表:
展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。
你可以使用原地算法(O(1) 额外空间)展开这棵树吗?

示例 1:
输入:root = [1,2,5,3,4,null,6]
输出:[1,null,2,null,3,null,4,null,5,null,6]

示例 2:
输入:root = []
输出:[]

示例 3:
输入:root = [0]
输出:[0]
type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
前序遍历+递归实现
时间复杂度:O(n)
空间复杂度:O(n)
*/
func flatten1(root *TreeNode) {
	var preorderTraversal func(root *TreeNode) []*TreeNode
	preorderTraversal = func(root *TreeNode) []*TreeNode {
		var list []*TreeNode
		if root != nil {
			list = append(list, root)
			list = append(list, preorderTraversal(root.Left)...)
			list = append(list, preorderTraversal(root.Right)...)
		}
		return list
	}

	list := preorderTraversal(root)
	for i := 1; i < len(list); i++ {
		prev, cur := list[i-1], list[i]
		prev.Left, prev.Right = nil, cur
	}
}

/*
前序遍历+迭代实现
时间复杂度:O(n)
空间复杂度:O(n)
*/
func flatten2(root *TreeNode) {
	var list []*TreeNode
	var stack []*TreeNode
	node := root
	for node != nil || len(stack) > 0 {
		for node != nil {
			list = append(list, node)
			stack = append(stack, node)
			node = node.Left
		}
		node = stack[len(stack)-1]
		node = node.Right
		stack = stack[0 : len(stack)-1]
	}

	for i := 1; i < len(list); i++ {
		prev, cur := list[i-1], list[i]
		prev.Left, prev.Right = nil, cur
	}
}

func main() {

}

2. 最长连续序列(128)

给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。
请你设计并实现时间复杂度为O(n) 的算法解决此问题。

示例 1:
输入:nums = [100,4,200,1,3,2]
输出:4
解释:最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。

示例 2:
输入:nums = [0,3,7,2,5,8,4,6,0,1]
输出:9
由示例2可知重复的算同一个
/*
哈希表
时间复杂度:O(n)
空间复杂度:O(n)
*/
func longestConsecutive(nums []int) int {
	mp := make(map[int]bool)
	for _, v := range nums {
		mp[v] = true
	}
	var result int
	for k, _ := range mp {
		//最坏情况时间复杂度为O(n²),在这里进行优化,
		//即:只有当一个数是连续序列的第一个数的情况下才会进入内层循环
		//如果一个k数前一个存在,则k的前一个数和k会组成连续的数,
		//则会进入if的内循环for,则会多出很多不必要的枚举
		//最终导致最坏情况时间复杂度为O(n²)
		if !mp[k-1] {
			curV := k
			curLen := 1
			for mp[curV+1] {
				curV++
				curLen++
			}
			if curLen > result {
				result = curLen
			}
		}
	}

	return result
}

func main() {
	nums := []int{0, 3, 7, 2, 5, 8, 4, 6, 0, 1}
	fmt.Println(longestConsecutive(nums))
}

3. 单词拆分(139)

给你一个字符串 s 和一个字符串列表 wordDict 作为字典。请你判断是否可以利用字典中出现的单词拼接出 s
注意:不要求字典中出现的单词全部都使用,并且字典中的单词可以重复使用。
wordDict 中的所有字符串互不相同
s 和 wordDict[i] 仅有小写英文字母组成

示例 1:
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以由 "leet" 和 "code" 拼接成。

示例 2:
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以由 "apple" "pen" "apple" 拼接成。
注意,你可以重复使用字典中的单词。

示例 3:
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false
/*
动态规划
时间复杂度:O(n²)
空间复杂度:O(n)
转移方程:dp[i]=dp[j] && check(s[j..i−1])
https://leetcode.cn/problems/word-break/solution/dan-ci-chai-fen-by-leetcode-solution/
*/
func wordBreak(s string, wordDict []string) bool {
	wordDictSet := make(map[string]bool)
	for _, v := range wordDict {
		wordDictSet[v] = true
	}
	dp := make([]bool, len(s)+1)
	dp[0] = true
	for i := 1; i <= len(s); i++ {
		for j := 0; j < i; j++ {
			if dp[j] && wordDictSet[s[j:i]] {
				dp[i] = true
				break
			}
		}
	}
	return dp[len(s)]
}

func main() {
	s := "applepenapple"
	wordDict := []string{"apple", "pen"}
	//s = "catsandog"
	//wordDict = []string{"cats", "dog", "sand", "and", "cat"}
	fmt.Println(wordBreak(s, wordDict))
}

4.环形链表2(142)

给定一个链表的头节点 head,返回链表开始入环的第一个节点。如果链表无环,则返回null。
如果链表中有某个节点,可以通过连续跟踪 next 指针再次到达,则链表中存在环。
为了表示给定链表中的环,评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置(索引从 0 开始)。
如果 pos 是 -1,则在该链表中没有环。注意:pos 不作为参数进行传递,仅仅是为了标识链表的实际情况。
不允许修改链表。

示例 1:
输入:head = [3,2,0,-4], pos = 1
输出:返回索引为 1 的链表节点
解释:链表中有一个环,其尾部连接到第二个节点。

示例2:
输入:head = [1,2], pos = 0
输出:返回索引为 0 的链表节点
解释:链表中有一个环,其尾部连接到第一个节点。

示例 3:
输入:head = [1], pos = -1
输出:返回 null
解释:链表中没有环。
type ListNode struct {
	Val  int
	Next *ListNode
}

//方法一:哈希表法
//每次到达一个节点,如果该节点已经存在于哈希表中,则说明该链表是环形链表,否则就将该节点加入哈希表中
//时间复杂度:O(n)
//空间复杂度:O(n)
func detectCycle1(head *ListNode) *ListNode {
	tempHead := head
	tempMap := make(map[*ListNode]struct{})
	for tempHead != nil {
		if _, ok := tempMap[tempHead]; ok {
			return tempHead
		}
		tempMap[tempHead] = struct{}{}
		tempHead = tempHead.Next
	}
	return nil
}

func main() {
	node1 := new(ListNode)
	node2 := new(ListNode)
	node3 := new(ListNode)
	node4 := new(ListNode)
	node1.Val = 3
	node1.Next = node2
	node2.Val = 2
	node2.Next = node3
	node3.Val = 0
	node3.Next = node4
	node4.Val = -4
	node4.Next = node2

	result := detectCycle1(node1)
	fmt.Println(result.Val)
}

5. 前k个高频元素(347)

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小

示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]

示例 2:
输入: nums = [1], k = 1
输出: [1]
/*
方法一:大顶堆
时间复杂度:O(nlog(k)), n为数组长度,k为操作堆的时间
空间复杂度:O(N)
*/
func topKFrequent1(nums []int, k int) []int {
	mp := make(map[int]int)
	for _, v := range nums {
		mp[v]++
	}
	h := &IHeap{}
	heap.Init(h)
	for key, value := range mp {
		heap.Push(h, [2]int{key, value})
		if h.Len() > k {
			heap.Pop(h)
		}
	}
	ret := make([]int, k)
	for i := 0; i < k; i++ {
		ret[k-i-1] = heap.Pop(h).([2]int)[0]
	}
	return ret
}

type IHeap [][2]int

func (I IHeap) Len() int           { return len(I) }
func (I IHeap) Less(i, j int) bool { return I[i][1] < I[j][1] } //大顶堆
func (I IHeap) Swap(i, j int)      { I[i], I[j] = I[j], I[i] }
func (I *IHeap) Push(x any)        { *I = append(*I, x.([2]int)) }
func (I *IHeap) Pop() any {
	old := *I
	n := len(old)
	x := old[n-1]
	*I = old[0 : n-1]
	return x
}

/*
方法二:快速排序
时间复杂度:O(n²),平均 nlog(n)
空间复杂度:O(n)
https://leetcode.cn/problems/top-k-frequent-elements/solution/qian-k-ge-gao-pin-yuan-su-by-leetcode-solution/
*/
func topKFrequent2(nums []int, k int) []int {
	mp := make(map[int]int)
	for _, v := range nums {
		mp[v]++
	}
	var values [][]int
	for k, v := range mp {
		values = append(values, []int{k, v})
	}

	quickSort(values, 0, len(values)-1)

	var result []int
	for _, v := range values {
		result = append(result, v[0])
	}

	return result[len(result)-k:]
}

func quickSort(a [][]int, left, right int) {
	if left >= right {
		return
	}
	l, r := left, right
	pivot := a[left]
	for left < right {
		for left < right && a[right][1] >= pivot[1] {
			right--
		}
		a[left] = a[right]
		for left < right && a[left][1] <= pivot[1] {
			left++
		}
		a[right] = a[left]
	}
	a[left] = pivot
	middle := left
	quickSort(a, l, middle-1)
	quickSort(a, middle+1, r)
}

func main() {
	nums := []int{1, 1, 1, 2, 2, 3, 4, 5}
	k := 2
	fmt.Println(topKFrequent1(nums, k))
	fmt.Println(topKFrequent2(nums, k))
}

6. 岛屿数量(200)

给你一个由'1'(陆地)和 '0'(水)组成的的二维网格,请你计算网格中岛屿的数量。
岛屿总是被水包围,并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外,你可以假设该网格的四条边均被水包围。

示例 1:
输入:grid = [
  ['1','1','1','1','0'],
  ['1','1','0','1','0'],
  ['1','1','0','0','0'],
  ['0','0','0','0','0']
]
输出:1

示例 2:
输入:grid = [
  ['1','1','0','0','0'],
  ['1','1','0','0','0'],
  ['0','0','1','0','0'],
  ['0','0','0','1','1']
]
输出:3
/*
深度优先搜索
时间复杂度:O(m*n)
时间复杂度:O(m*n)
*/
func numIslands1(grid [][]byte) int {
	length := len(grid)
	if length == 0 {
		return 0
	}
	result := 0
	for i := 0; i < len(grid); i++ {
		for j := 0; j < len(grid[0]); j++ {
			if grid[i][j] == '1' {
				result++
				dfs(grid, i, j)
			}
		}
	}

	return result
}

func dfs(grid [][]byte, i, j int) {
	row, column := len(grid), len(grid[0])

	grid[i][j] = '0'
	if i-1 >= 0 && grid[i-1][j] == '1' {
		dfs(grid, i-1, j)
	}
	if i+1 < row && grid[i+1][j] == '1' {
		dfs(grid, i+1, j)
	}
	if j-1 >= 0 && grid[i][j-1] == '1' {
		dfs(grid, i, j-1)
	}
	if j+1 < column && grid[i][j+1] == '1' {
		dfs(grid, i, j+1)
	}
}

/*
广度优先搜索
时间复杂度:O(m*n)
时间复杂度:O(min(m,n))
*/
func numIslands2(grid [][]byte) int {
	length := len(grid)
	if length == 0 {
		return 0
	}
	row, column := len(grid), len(grid[0])
	result := 0
	type pair struct{ i, j int }
	for r := 0; r < row; r++ {
		for c := 0; c < column; c++ {
			if grid[r][c] == '1' {
				result++
				grid[r][c] = '0'
				var queue []pair
				queue = append(queue, pair{i: r, j: c})
				for len(queue) > 0 {
					rc := queue[len(queue)-1:]
					queue = queue[0 : len(queue)-1]
					i, j := rc[0].i, rc[0].j
					if i-1 >= 0 && grid[i-1][j] == '1' {
						queue = append(queue, pair{i: i - 1, j: j})
						grid[i-1][j] = '0'
					}
					if i+1 < row && grid[i+1][j] == '1' {
						queue = append(queue, pair{i: i + 1, j: j})
						grid[i+1][j] = '0'
					}
					if j-1 >= 0 && grid[i][j-1] == '1' {
						queue = append(queue, pair{i: i, j: j - 1})
						grid[i][j-1] = '0'
					}
					if j+1 < column && grid[i][j+1] == '1' {
						queue = append(queue, pair{i: i, j: j + 1})
						grid[i][j+1] = '0'
					}
				}
			}
		}
	}

	return result
}

func main() {
	grid := [][]byte{
		{'1', '1', '0', '0', '0'},
		{'1', '1', '0', '0', '0'},
		{'0', '0', '1', '0', '0'},
		{'0', '0', '0', '1', '1'},
	}
	fmt.Println(numIslands1(grid))
	grid = [][]byte{
		{'1', '1', '0', '0', '0'},
		{'1', '1', '0', '0', '0'},
		{'0', '0', '1', '0', '0'},
		{'0', '0', '0', '1', '1'},
	}
	fmt.Println(numIslands2(grid))
}

7. 寻找重复数(287)

给定一个包含n + 1 个整数的数组nums ,其数字都在[1, n]范围内(包括 1 和 n),可知至少存在一个重复的整数。
假设 nums 只有 一个重复的整数 ,返回这个重复的数 。
你设计的解决方案必须 不修改 数组 nums 且只用常量级 O(1) 的额外空间。

示例 1:
输入:nums = [1,3,4,2,2]
输出:2

示例 2:
输入:nums = [3,1,3,4,2]
输出:3

示例 3:
输入:nums = [2,2,2,2,2]
输出:2

提示:
nums 中 只有一个整数 出现 两次或多次 ,其余整数均只出现 一次

//题解:https://leetcode.cn/problems/find-the-duplicate-number/solution/xun-zhao-zhong-fu-shu-by-leetcode-solution/
//如果不限制空间复杂度,可以用hash的方式查重
/*
快慢指针法
时间复杂度:O(n)
空间复杂度:O(1)
慢指针走一步,快指针走两步;先让快慢指针一起走,最终会相遇,此时快指针和慢指针都在圈里的某个相同位置,
然后重新把慢指针放在开始位置,此时快慢指针每次都走一步,最终相遇的位置就是重复的数,即环的入口位置
*/
func findDuplicate(nums []int) int {
	slow, fast := 0, 0
	slow, fast = nums[slow], nums[nums[fast]]
	for slow != fast {
		slow, fast = nums[slow], nums[nums[fast]]
	}
	slow = 0
	for slow != fast {
		slow = nums[slow]
		fast = nums[fast]
	}
	return slow
}

func main() {
	nums := []int{3, 1, 3, 4, 2}
	fmt.Println(findDuplicate(nums))
}

8. 每日温度(739)

给定一个整数数组temperatures,表示每天的温度,返回一个数组answer,其中answer[i]是指对于第 i 天,下一个更高温度出现在几天后。
如果气温在这之后都不会升高,请在该位置用0 来代替。

30 <= temperatures[i] <= 100

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出:[1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出:[1,1,1,0]

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]
/*
暴力
时间复杂度:O(nm),n是温度列表的长度,m是next的长度,
空间复杂度:O(m)
从后往前遍历,在后面这些走过的数据当中挑一个符合要求且距离最近的数,下标相减就是要求的距离
*/
func dailyTemperatures1(temperatures []int) []int {
	length := len(temperatures)
	ans := make([]int, length)
	next := make([]int, 101)
	for i := 0; i < 101; i++ {
		next[i] = math.MaxInt32
	}
	for i := length - 1; i >= 0; i-- {
		warmerIndex := math.MaxInt32
		for t := temperatures[i] + 1; t <= 100; t++ {
			if next[t] < warmerIndex {
				warmerIndex = next[t]
			}
		}
		if warmerIndex < math.MaxInt32 {
			ans[i] = warmerIndex - i
		}
		next[temperatures[i]] = i
	}
	return ans
}

/*
单调栈
时间复杂度:O(n)
空间复杂度:O(n)
*/
func dailyTemperatures2(temperatures []int) []int {
	length := len(temperatures)
	ans := make([]int, length)
	var stack []int
	for i := 0; i < length; i++ {
		temperature := temperatures[i]
		for len(stack) > 0 && temperature > temperatures[stack[len(stack)-1]] {
			prevIndex := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			ans[prevIndex] = i - prevIndex
		}
		stack = append(stack, i)
	}
	return ans
}

func main() {
	temperatrues := []int{73, 74, 75, 71, 69, 72, 76, 73}
	fmt.Println(dailyTemperatures1(temperatrues))
	fmt.Println(dailyTemperatures2(temperatrues))
}