LeetCode热题Top100 | 中等 | 下

给你二叉树的根结点 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() {

}

给定一个未排序的整数数组 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))
}

给你一个字符串 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))
}

给定一个链表的头节点 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)
}

给你一个整数数组 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))
}

给你一个由'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))
}

给定一个包含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))
}

给定一个整数数组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))
}

给你一个字符串 s ，请你统计并返回这个字符串中 回文子串 的数目。
回文字符串 是正着读和倒过来读一样的字符串。
子字符串 是字符串中的由连续字符组成的一个序列。
具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。
s 由小写英文字母组成

示例 1：
输入：s = "abc"
输出：3
解释：三个回文子串: "a", "b", "c"

示例 2：
输入：s = "aaa"
输出：6
解释：6个回文子串: "a", "a", "a", "aa", "aa", "aaa"

/*
中心拓展
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
func countSubstrings(s string) int {
	n := len(s)
	ans := 0
	for i := 0; i < 2*n-1; i++ {
		l, r := i/2, i/2+i%2
		for l >= 0 && r < n && s[l] == s[r] {
			l--
			r++
			ans++
		}
	}
	return ans
}

/*
动态规划法
时间复杂度：O(n^2)
空间复杂度：O(n^2)
*/
func countSubstrings2(s string) int {
	n := len(s)
	ans := 0
	check := make([][]bool, n)
	for i := range check {
		check[i] = make([]bool, n)
	}
	for i := 0; i < n; i++ {
		for j := 0; j <= i; j++ {
			if s[i] == s[j] && (j-i < 2 || check[i+1][j-1]) {
				ans++
				check[i][j] = true
			}
		}
	}
	return ans
}

func main() {
	s := "aaa"
	fmt.Println(countSubstrings(s))
	fmt.Println(countSubstrings2(s))
}

给定一个二叉树的根节点 root，和一个整数 targetSum ，求该二叉树里节点值之和等于 targetSum 的 路径 的数目。
路径 不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。

示例 1：
输入：root = [10,5,-3,3,2,null,11,3,-2,null,1], targetSum = 8
输出：3
解释：和等于 8 的路径有 3 条，如图所示。

示例 2：
输入：root = [5,4,8,11,null,13,4,7,2,null,null,5,1], targetSum = 22
输出：3

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

/*
深度优先搜索
时间复杂度：O(n^2)
空间复杂度：O(n)
*/
func pathSum(root *TreeNode, targetSum int) int {
	if root == nil {
		return 0
	}
	res := rootSum(root, targetSum)
	res += pathSum(root.Left, targetSum)
	res += pathSum(root.Right, targetSum)
	return res
}

func rootSum(root *TreeNode, targetSum int) (res int) {
	if root == nil {
		return
	}
	val := root.Val
	if val == targetSum {
		res++
	}
	res += rootSum(root.Left, targetSum-val)
	res += rootSum(root.Right, targetSum-val)
	return
}

/*
前缀和
时间复杂度：O(n)
空间复杂度：O(n)
*/
func pathSum2(root *TreeNode, targetSum int) (ans int) {
	preSum := map[int64]int{0: 1} // 0:1 表示如果 curr-target 结果为0，则算一个结果
	var dfs func(*TreeNode, int64)
	dfs = func(node *TreeNode, curr int64) {
		if node == nil {
			return
		}
		curr += int64(node.Val)
		ans += preSum[curr-int64(targetSum)] //如果 curr-target 结果为0，则算一个结果
		preSum[curr]++                       //往hash表加入当前前缀和
		dfs(node.Left, curr)                 //开始向下深度优先遍历
		dfs(node.Right, curr)
		preSum[curr]-- //回溯，往hash表删除当前前缀和
		return
	}
	dfs(root, 0)
	return
}

func main() {

}

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。
完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。
例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例1：
输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：
输入：n = 13
输出：2
解释：13 = 4 + 9

/*
动态规划
时间复杂度：O(n*√n)
空间复杂度：O(n)
*/
func numSquares(n int) int {
	f := make([]int, n+1)
	for i := 1; i <= n; i++ {
		minn := math.MaxInt32
		for j := 1; j*j <= i; j++ {
			minn = min(minn, f[i-j*j])
		}
		f[i] = minn + 1
	}
	return f[n]
}

func min(i, j int) int {
	if i < j {
		return i
	}
	return j
}

func main() {
	fmt.Println(numSquares(13))
}

给你一个整数数组 nums 和一个整数k ，请你统计并返回 该数组中和为k的子数组的个数。

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

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

解法：https://leetcode.cn/problems/subarray-sum-equals-k/solution/he-wei-kde-zi-shu-zu-by-leetcode-solution/

/*
暴力法
时间复杂度：O(n^2)
空间复杂度：O(1)
*/
func subarraySum(nums []int, k int) int {
	var ans int
	for i := 0; i < len(nums); i++ {
		sum := 0
		j := i
		for j < len(nums) {
			sum += nums[j]
			j++
			if sum == k {
				ans++
			}
		}
	}
	return ans
}

/*
前缀和 + 哈希表优化
时间复杂度：O(n)
空间复杂度：O(n)
*/
func subarraySum2(nums []int, k int) int {
	count, pre := 0, 0
	m := map[int]int{0: 1}
	for i := 0; i < len(nums); i++ {
		pre += nums[i]
		if _, ok := m[pre-k]; ok {
			count += m[pre-k]
		}
		m[pre]++
	}
	return count
}

func main() {
	nums := []int{1, 1, 1}
	fmt.Println(subarraySum(nums, 2))
	fmt.Println(subarraySum2(nums, 2))
}