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))
}
9. 回文子串(647)#
给你一个字符串 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))
}
10. 路径总和Ⅲ(437)#
给定一个二叉树的根节点 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() {
}
11. 完全平方数(279)#
给你一个整数 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))
}
12. 和为k的子数组(560)#
给你一个整数数组 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))
}
...