Go CodeTop 题解
3. 无重复字符的最长子串
使用滑动窗口的思想，用一个 Map 来存储目前遇到的字符。
package main
import (
"fmt"
"math"
)
func lengthOfLongestSubstring(s string) int {
if len(s) <= 0 {
return 0
}
h := make(map[byte]int, 0)
r, l, res := 0, 0, math.MinInt64
for r < len(s) {
c := s[r]
r++
h[c]++
for h[c] > 1 {
d := s[l]
l++
h[d]--
}
res = max(res, r-l)
}
if res == math.MinInt64 {
return 0
}
return res
}
func main() {
var s string
fmt.Scanln(&s)
fmt.Println(lengthOfLongestSubstring(s))
}206. 反转链表
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func reverseList(head *ListNode) *ListNode {
if head == nil {
return head
}
a, b := head, head.Next
for b != nil {
t := b.Next
b.Next = a
a = b
b = t
}
head.Next = nil
return a
}
func main() {
head := &ListNode{
Val: 5,
Next: &ListNode{
Val: 4,
Next: &ListNode{
Val: 3,
Next: &ListNode{
Val: 2,
Next: &ListNode{
Val: 1,
Next: nil,
},
},
},
},
}
head = reverseList(head)
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
}
// 1 2 3 4 5146. LRU 缓存
package main
import (
"container/list"
"fmt"
)
type entry struct {
key int
val int
}
type LRUCache struct {
capacity int
list *list.List
k2N map[int]*list.Element
}
func (c *LRUCache) Get(key int) int {
node := c.k2N[key]
if node == nil {
return -1
}
c.list.MoveToFront(node)
return node.Value.(entry).val
}
func (c *LRUCache) Put(key int, value int) {
if node := c.k2N[key]; node != nil {
node.Value = entry{key, value}
c.list.MoveToFront(node)
return
}
c.k2N[key] = c.list.PushFront(entry{key, value})
if len(c.k2N) > c.capacity {
delete(c.k2N, c.list.Remove(c.list.Back()).(entry).key)
}
}
func main() {
lru := LRUCache{3, list.New(), map[int]*list.Element{}}
lru.Put(1, 1)
lru.Put(2, 1)
lru.Put(3, 1)
lru.Put(1, 2)
lru.Put(4, 1)
fmt.Println(lru.Get(4), lru.Get(1))
}
// 1 2215. 数组中的第 K 个最大元素
215. 数组中的第K个最大元素 - 力扣（LeetCode）
用快速排序完成
package main
import "fmt"
func quick_sort(nums []int, l, r int) {
if l >= r {
return
}
i, j, x := l, r, nums[(l+r)/2]
for i <= j {
for i <= r && nums[i] < x {
i++
}
for j >= l && nums[j] > x {
j--
}
if i <= j {
nums[i], nums[j] = nums[j], nums[i]
i++
j--
}
}
quick_sort(nums, l, j)
quick_sort(nums, i, r)
}
func main() {
nums := []int{3, 1, 2, 4, 5}
quick_sort(nums, 0, len(nums)-1)
fmt.Println(nums)
}
// 1 2 3 4 525. K 个一组翻转链表
每次调用翻转链表翻转 K 个节点，接着递归下去即可。
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func reverseKGroup(head *ListNode, k int) *ListNode {
if head == nil {
return head
}
a, b := head, head
for i := 0; i < k; i++ {
if b == nil {
return head
}
b = b.Next
}
newHead := reverseList(a, b)
a.Next = reverseKGroup(b, k)
return newHead
}
func reverseList(h1, h2 *ListNode) *ListNode {
a, b := h1, h1.Next
for b != h2 {
t := b.Next
b.Next = a
a = b
b = t
}
h1.Next = h2
return a
}
func main() {
head := &ListNode{
Val: 5,
Next: &ListNode{
Val: 4,
Next: &ListNode{
Val: 3,
Next: &ListNode{
Val: 2,
Next: &ListNode{
Val: 1,
Next: nil,
},
},
},
},
}
head = reverseKGroup(head, 2)
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
}
// 4 5 2 3 115. 三数之和
package main
import (
"fmt"
"sort"
)
func threeSum(nums []int) [][]int {
sort.Ints(nums)
var res [][]int
for i := 0; i < len(nums); i++ {
if i > 0 && nums[i] == nums[i-1] {
continue
}
for j, k := i+1, len(nums)-1; j < k; j++ {
if j > i+1 && nums[j] == nums[j-1] {
continue
}
for j < k-1 && nums[i]+nums[j]+nums[k-1] >= 0 {
k--
}
if nums[i]+nums[j]+nums[k] == 0 {
res = append(res, []int{nums[i], nums[j], nums[k]})
}
}
}
return res
}
func main() {
res := threeSum([]int{-1, 0, 1, 2, -1, -4})
fmt.Println(res)
}
// [[-1 -1 2] [-1 0 1]]53. 最大子数组和
用滑动窗口的思想来做，需要在第二个 for 循环之前将 res 赋值。
package main
import (
"fmt"
"math"
)
func maxSubArray(nums []int) int {
r, l, sum := 0, 0, 0
res := math.MinInt
for r < len(nums) {
sum += nums[r]
r++
res = max(res, sum)
for sum < 0 {
sum -= nums[l]
l++
}
}
return res
}
func main() {
res := maxSubArray([]int{-2, 1, -3, 4, -1, 2, 1, -5, 4})
fmt.Println(res)
}
// 连续子数组 [4,-1,2,1] 的和最大，为 6补充题：手撕快速排序
[912. 排序数组 - 力扣（LeetCode）](https://leetcode.cn/problems/sort-an-array/description/
package main
import "fmt"
func quick_sort(nums []int, l, r int) {
if l >= r {
return
}
i, j, x := l, r, nums[(l+r)/2]
for i <= j {
for i <= r && nums[i] < x {
i++
}
for j >= l && nums[j] > x {
j--
}
if i <= j {
nums[i], nums[j] = nums[j], nums[i]
i++
j--
}
}
quick_sort(nums, l, j)
quick_sort(nums, i, r)
}
func main() {
nums := []int{3, 1, 2, 4, 5}
quick_sort(nums, 0, len(nums)-1)
fmt.Println(nums)
}
// 1 2 3 4 521. 合并两个有序链表
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func mergeTwoLists(list1 *ListNode, list2 *ListNode) *ListNode {
dummy := &ListNode{}
p := dummy
for list1 != nil && list2 != nil {
if list1.Val < list2.Val {
p.Next = list1
p = p.Next
list1 = list1.Next
} else {
p.Next = list2
p = p.Next
list2 = list2.Next
}
}
if list1 != nil {
p.Next = list1
}
if list2 != nil {
p.Next = list2
}
return dummy.Next
}
func main() {
l1 := &ListNode{
Val: 1,
Next: &ListNode{
Val: 3,
Next: nil,
},
}
l2 := &ListNode{
Val: 2,
Next: &ListNode{
Val: 4,
Next: nil,
},
}
newList := mergeTwoLists(l1, l2)
for newList != nil {
fmt.Println(newList.Val)
newList = newList.Next
}
}
// 1 2 3 41. 两数之和
package main
import "fmt"
func twoSum(nums []int, target int) []int {
m := make(map[int]int, 0)
for i := 0; i < len(nums); i++ {
if _, ok := m[target-nums[i]]; ok {
return []int{i, m[target-nums[i]]}
} else {
m[nums[i]] = i
}
}
return []int{}
}
func main() {
fmt.Println(twoSum([]int{2, 7, 11, 15}, 9))
}
// 0 15. 最长回文子串
package main
import "fmt"
func longestPalindrome(s string) string {
res := ""
for i := 0; i < len(s); i++ {
s1 := match(s, i, i)
if len(s1) > len(res) {
res = s1
}
s2 := match(s, i, i+1)
if len(s2) > len(res) {
res = s2
}
}
return res
}
func match(s string, l, r int) string {
for l >= 0 && r < len(s) && s[l] == s[r] {
l--
r++
}
return s[l+1 : r]
}
func main() {
fmt.Println(longestPalindrome("cbbd"))
}
// bb102. 二叉树的层序遍历
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func levelOrder(root *TreeNode) [][]int {
res := [][]int{}
if root == nil {
return res
}
q := []*TreeNode{root}
for len(q) > 0 {
l := len(q)
path := []int{}
for i := 0; i < l; i++ {
node := q[0]
q = q[1:]
path = append(path, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
res = append(res, path)
}
return res
}
func main() {
tree := &TreeNode{
Val: 3,
Left: &TreeNode{
Val: 9,
},
Right: &TreeNode{
Val: 20,
Left: &TreeNode{
Val: 15,
},
Right: &TreeNode{
Val: 7,
},
},
}
fmt.Println(levelOrder(tree))
}
// [[3] [9 20] [15 7]]33. 搜索旋转排序数组
package main
import "fmt"
func search(nums []int, target int) int {
l, r := 0, len(nums)-1
for l < r {
mid := (l + r + 1) / 2
if nums[mid] >= nums[0] {
l = mid
} else {
r = mid - 1
}
}
if target >= nums[0] {
l = 0
} else {
l = r + 1
r = len(nums) - 1
}
for l < r {
mid := (l + r) / 2
if nums[mid] >= target {
r = mid
} else {
l = mid + 1
}
}
if nums[r] != target {
return -1
}
return r
}
func main() {
fmt.Println(search([]int{4, 5, 6, 7, 0, 1, 2}, 0))
}
// 4200. 岛屿数量
package main
import "fmt"
type Solution struct {
dx, dy []int
g [][]byte
}
func numIslands(grid [][]byte) int {
sol := Solution{
dx: []int{0, 1, 0, -1},
dy: []int{1, 0, -1, 0},
g: grid,
}
res := 0
m, n := len(sol.g), len(sol.g[0])
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if sol.g[i][j] == '1' {
sol.dfs(i, j)
res++
}
}
}
return res
}
func (sol *Solution) dfs(x, y int) {
sol.g[x][y] = '0'
for i := 0; i < 4; i++ {
a, b := x+sol.dx[i], y+sol.dy[i]
if a >= 0 && b >= 0 && a < len(sol.g) && b < len(sol.g[0]) && sol.g[a][b] == '1' {
sol.dfs(a, b)
}
}
}
func main() {
grid := [][]byte{
{'1', '1', '1', '1', '0'},
{'1', '1', '0', '1', '0'},
{'1', '1', '0', '0', '0'},
{'0', '0', '0', '1', '0'},
}
fmt.Println(numIslands(grid))
}
// 2121. 买卖股票的最佳时机
package main
import "fmt"
func maxProfit(prices []int) int {
dp := make([][]int, len(prices))
for i := range dp {
dp[i] = make([]int, 2)
}
dp[0][0] = 0
dp[0][1] = -prices[0]
for i := 1; i < len(prices); i++ {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1], -prices[i])
}
return dp[len(prices)-1][0]
}
func main() {
fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
}
// 520. 有效的括号
package main
import (
"fmt"
)
func isValid(s string) bool {
stk := []rune{}
for _, v := range s {
if v == '(' || v == '[' || v == '{' {
stk = append(stk, v)
} else if len(stk) > 0 && math.Abs(float64(v) - float64(stk[len(stk) - 1])) < 3 {
stk = stk[:len(stk) - 1]
} else {
return false
}
}
return len(stk) == 0
}
func main() {
fmt.Println(isValid("{}[]()"))
fmt.Println(isValid("([)]"))
}
// ture false141. 环形链表
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func hasCycle(head *ListNode) bool {
slow, fast := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if fast == slow {
return true
}
}
return false
}
func main() {
head := &ListNode{
Val: 3,
Next: &ListNode{
Val: 2,
Next: &ListNode{
Val: 0,
Next: &ListNode{
Val: -4,
},
},
},
}
head.Next.Next.Next.Next = head.Next
fmt.Println(hasCycle(head))
}
// true88. 合并两个有序数组
package main
import "fmt"
func merge(nums1 []int, m int, nums2 []int, n int) {
i, j, k := m-1, n-1, m+n-1
for i >= 0 && j >= 0 {
if nums1[i] < nums2[j] {
nums1[k] = nums2[j]
j--
} else {
nums1[k] = nums1[i]
i--
}
k--
}
for j >= 0 {
nums1[k] = nums2[j]
j--
k--
}
}
func main() {
nums1 := []int{1, 2, 3, 0, 0, 0}
nums2 := []int{2, 5, 6}
merge(nums1, 3, nums2, 3)
fmt.Println(nums1)
}
// 1 2 2 3 5 6236. 二叉树的最近公共祖先
236. 二叉树的最近公共祖先 - 力扣（LeetCode）
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func lowestCommonAncestor(root, p, q *TreeNode) *TreeNode {
if root == p || root == q || root == nil {
return root
}
l := lowestCommonAncestor(root.Left, p, q)
r := lowestCommonAncestor(root.Right, p, q)
if l == nil {
return r
}
if r == nil {
return l
}
return root
}
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 2},
Right: nil,
}
res := lowestCommonAncestor(root, root, root.Left)
fmt.Println(res.Val)
}
// 146. 全排列
package main
import "fmt"
var (
res [][]int
path []int
st []bool
)
func permute(nums []int) [][]int {
res = [][]int{}
path = []int{}
st = make([]bool, len(nums))
dfs(nums, 0)
return res
}
func dfs(nums []int, u int) {
if u == len(nums) {
tmp := make([]int, len(path)) // 构建新的slice，避免后续操作影响已保存结果
copy(tmp, path)
res = append(res, tmp)
return
}
for i := 0; i < len(nums); i++ {
if !st[i] {
st[i] = true
path = append(path, nums[i])
dfs(nums, u+1)
path = path[:len(path)-1]
st[i] = false
}
}
}
func main() {
nums := []int{1, 2, 3}
res := permute(nums)
for _, r := range res {
fmt.Println(r)
}
}
// [1 2 3]
// [1 3 2]
// [2 1 3]
// [2 3 1]
// [3 1 2]
// [3 2 1]103. 二叉树的锯齿形层序遍历
103. 二叉树的锯齿形层序遍历 - 力扣（LeetCode）
package main
import (
"fmt"
"slices"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func zigzagLevelOrder(root *TreeNode) [][]int {
res := [][]int{}
if root == nil {
return res
}
count := 1
q := []*TreeNode{root}
for len(q) > 0 {
l := len(q)
path := []int{}
for i := 0; i < l; i++ {
node := q[0]
q = q[1:]
path = append(path, node.Val)
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
}
if count%2 == 0 {
slices.Reverse(path)
}
count++
res = append(res, path)
}
return res
}
func main() {
tree := &TreeNode{
Val: 3,
Left: &TreeNode{
Val: 9,
},
Right: &TreeNode{
Val: 20,
Left: &TreeNode{
Val: 15,
},
Right: &TreeNode{
Val: 7,
},
},
}
fmt.Println(zigzagLevelOrder(tree))
}
// [[3] [20 9] [15 7]]92. 反转链表 II
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func reverseBetween(head *ListNode, left int, right int) *ListNode {
if head == nil {
return head
}
// 创建 dummy 节点
dummy := &ListNode{Next: head}
p := dummy
// 移动到反转的起点位置
for i := 0; i < left-1; i++ {
p = p.Next
}
a, b := p.Next, p.Next.Next
// 反转链表
for i := 0; i < right-left; i++ {
t := b.Next
b.Next = a
a = b
b = t
}
p.Next.Next = b
p.Next = a
return dummy.Next
}
func main() {
head := &ListNode{
Val: 5,
Next: &ListNode{
Val: 4,
Next: &ListNode{
Val: 3,
Next: &ListNode{
Val: 2,
Next: &ListNode{
Val: 1,
Next: nil,
},
},
},
},
}
head = reverseBetween(head, 2, 4)
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
}
// 5 2 3 4 154. 螺旋矩阵
package main
import "fmt"
type Solution struct {
dx []int
dy []int
}
func spiralOrder(matrix [][]int) []int {
s := Solution{dx: []int{0, 1, 0, -1}, dy: []int{1, 0, -1, 0}}
m, n := len(matrix), len(matrix[0])
st := make([][]bool, m)
for i := 0; i < m; i++ {
st[i] = make([]bool, n)
}
res := make([]int, m*n)
x, y, d := 0, 0, 0 // 初始位置及方向
for i := 0; i < m*n; i++ {
res[i] = matrix[x][y]
st[x][y] = true
a, b := x+s.dx[d], y+s.dy[d]
if a < 0 || a >= m || b < 0 || b >= n || st[a][b] {
d = (d + 1) % 4 // 改变方向
a, b = x+s.dx[d], y+s.dy[d]
}
x, y = a, b
}
return res
}
func main() {
res := spiralOrder([][]int{
{1, 2, 3},
{4, 5, 6},
{7, 8, 9},
})
fmt.Println(res)
}
// [1 2 3 6 9 8 7 4 5]23. 合并 K 个升序链表
package main
import (
"container/heap"
"fmt"
)
type ListNode struct {
Val int
Next *ListNode
}
type hp []*ListNode
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].Val < h[j].Val } // 最小堆
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v any) { *h = append(*h, v.(*ListNode)) }
func (h *hp) Pop() any { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func mergeKLists(lists []*ListNode) *ListNode {
h := hp{}
for _, head := range lists {
if head != nil {
h = append(h, head)
}
}
heap.Init(&h) // 堆化
dummy := &ListNode{} // 哨兵节点，作为合并后链表头节点的前一个节点
cur := dummy
for len(h) > 0 {
node := heap.Pop(&h).(*ListNode)
if node.Next != nil {
heap.Push(&h, node.Next)
}
cur.Next = node
cur = cur.Next
}
return dummy.Next
}
func main() {
lists := []*ListNode{
{Val: 1, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5}}},
{Val: 1, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}},
{Val: 2, Next: &ListNode{Val: 6, Next: nil}},
}
res := mergeKLists(lists)
for res != nil {
fmt.Printf("%d ", res.Val)
res = res.Next
}
}
// 1 1 2 3 4 4 5 6160. 相交链表
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func getIntersectionNode(headA, headB *ListNode) *ListNode {
a, b := headA, headB
for a != b {
if a != nil {
a = a.Next
} else {
a = headB
}
if b != nil {
b = b.Next
} else {
b = headA
}
}
return a
}
func main() {
a := &ListNode{
Val: 4,
Next: &ListNode{
Val: 1,
Next: &ListNode{
Val: 8,
Next: nil,
},
},
}
b := &ListNode{Val: 3}
b.Next = a.Next.Next
fmt.Println(getIntersectionNode(a, b).Val)
}
// 8300. 最长递增子序列
package main
import "fmt"
func lengthOfLIS(nums []int) int {
dp := make([]int, len(nums))
for i := range dp {
dp[i] = 1
}
res := 0
for i := 0; i < len(nums); i++ {
for j := 0; j < i; j++ {
if nums[j] < nums[i] {
dp[i] = max(dp[i], dp[j]+1)
}
}
res = max(res, dp[i])
}
return res
}
func main() {
fmt.Println(lengthOfLIS([]int{0, 1, 0, 3, 2, 3}))
}
// 4415. 字符串相加
package main
import (
"fmt"
"strconv"
)
func addStrings(num1 string, num2 string) string {
var A, B []int
for i := len(num1) - 1; i >= 0; i-- {
A = append(A, int(num1[i]-'0'))
}
for i := len(num2) - 1; i >= 0; i-- {
B = append(B, int(num2[i]-'0'))
}
C := add(A, B)
var res string
for i := len(C) - 1; i >= 0; i-- {
res += strconv.Itoa(C[i])
}
return res
}
func add(A []int, B []int) []int {
var C []int
t := 0
for i := 0; i < len(A) || i < len(B) || t > 0; i++ {
if i < len(A) {
t += A[i]
}
if i < len(B) {
t += B[i]
}
C = append(C, t%10)
t /= 10
}
return C
}
func main() {
fmt.Println(addStrings("123", "456"))
}
// 579143. 重排链表
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func reorderList(head *ListNode) {
if head == nil {
return
}
mid := findMid(head)
l1, l2 := head, mid.Next
mid.Next = nil
l2 = reverseList(l2)
merge(l1, l2)
}
func findMid(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
return slow
}
func reverseList(head *ListNode) *ListNode {
if head == nil {
return head
}
a, b := head, head.Next
for b != nil {
t := b.Next
b.Next = a
a = b
b = t
}
head.Next = nil
return a
}
func merge(l1 *ListNode, l2 *ListNode) {
for l1 != nil && l2 != nil {
t1 := l1.Next
t2 := l2.Next
l1.Next = l2
l1 = t1
l2.Next = l1
l2 = t2
}
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: nil}}}}
reorderList(head)
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
}
// 1 4 2 342. 接雨水
package main
import "fmt"
func trap(height []int) int {
lh, rh, res, l, r := 0, 0, 0, 0, len(height)-1
for l < r {
lh = max(lh, height[l])
rh = max(rh, height[r])
if lh < rh {
res += lh - height[l]
l++
} else {
res += rh - height[r]
r--
}
}
return res
}
func main() {
fmt.Println(trap([]int{4, 2, 0, 3, 2, 5}))
}
// 9142. 环形链表 II
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func detectCycle(head *ListNode) *ListNode {
slow, fast := head, head
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
slow = slow.Next
if slow == fast {
break
}
}
if fast == nil || fast.Next == nil {
return nil
}
slow = head
for slow != fast {
slow = slow.Next
fast = fast.Next
}
return slow
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2}}
head.Next.Next = head
fmt.Println(detectCycle(head).Val)
}
// 156. 合并区间
package main
import (
"fmt"
"sort"
)
func merge(intervals [][]int) (res [][]int) {
sort.Slice(intervals, func(i, j int) bool { return intervals[i][0] < intervals[j][0] })
for i := 0; i < len(intervals); i++ {
if len(res) == 0 || res[len(res)-1][1] < intervals[i][0] {
res = append(res, intervals[i])
} else {
res[len(res)-1][1] = max(res[len(res)-1][1], intervals[i][1])
}
}
return
}
func main() {
fmt.Println(merge([][]int{
{1, 3},
{2, 6},
{8, 10},
{15, 18},
}))
}
// [[1 6] [8 10] [15 18]]124. 二叉树中的最大路径和
124. 二叉树中的最大路径和 - 力扣（LeetCode）
package main
import (
"fmt"
"math"
)
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
var res int
func maxPathSum(root *TreeNode) int {
res = math.MinInt
dfs(root)
return res
}
func dfs(root *TreeNode) int {
if root == nil {
return 0
}
l := max(0, dfs(root.Left))
r := max(0, dfs(root.Right))
res = max(res, l+r+root.Val)
return max(l, r) + root.Val
}
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 3},
}
fmt.Println(maxPathSum(root))
}
// 672. 编辑距离
package main
import "fmt"
func minDistance(word1, word2 string) int {
m, n := len(word1), len(word2)
memo := make([][]int, m+1)
for i := range memo {
memo[i] = make([]int, n+1)
for j := range memo[i] {
memo[i][j] = -1
}
}
return dp(word1, m-1, word2, n-1, memo)
}
func dp(word1 string, m int, word2 string, n int, memo [][]int) int {
if m == -1 {
return n + 1
}
if n == -1 {
return m + 1
}
if memo[m][n] != -1 {
return memo[m][n]
}
if word1[m] == word2[n] {
memo[m][n] = dp(word1, m-1, word2, n-1, memo)
} else {
memo[m][n] = min(dp(word1, m-1, word2, n-1, memo)+1, min(dp(word1, m-1, word2, n, memo)+1, dp(word1, m, word2, n-1, memo)+1))
}
return memo[m][n]
}
func main() {
fmt.Println(minDistance("horse", "ros"))
}
// 319. 删除链表的倒数第 N 个结点
19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func removeNthFromEnd(head *ListNode, n int) *ListNode {
if head == nil {
return nil
}
dummy := &ListNode{Next: head}
p, q := dummy, dummy
for i := 0; i < n+1; i++ {
p = p.Next
}
for p != nil {
p = p.Next
q = q.Next
}
q.Next = q.Next.Next
return dummy.Next
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5, Next: nil}}}}}
removeNthFromEnd(head, 2)
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
}
// 1 2 3 593. 复原 IP 地址
package main
import (
"fmt"
"strconv"
"strings"
)
var res []string
func restoreIpAddresses(s string) []string {
res = []string{}
dfs(s, 0, 0, "")
return res
}
func dfs(s string, u int, k int, path string) {
if u == len(s) {
if k == 4 {
path = strings.TrimSuffix(path, ".")
res = append(res, path)
}
return
}
if k == 4 {
return
}
t := 0
for i := u; i < len(s); i++ {
if i > u && s[u] == '0' {
break
}
t = t*10 + int(s[i]-'0')
if t > 255 {
break
}
dfs(s, i+1, k+1, path+strconv.Itoa(t)+".")
}
return
}
func main() {
fmt.Println(restoreIpAddresses("25525511135"))
}
// [255.255.11.135 255.255.111.35]1143. 最长公共子序列
package main
import (
"fmt"
)
func longestCommonSubsequence(text1 string, text2 string) int {
m, n := len(text1), len(text2)
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
res := 0
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if text1[i-1] == text2[j-1] {
dp[i][j] = dp[i-1][j-1] + 1
} else {
dp[i][j] = max(dp[i-1][j], dp[i][j-1])
}
res = max(res, dp[i][j])
}
}
return res
}
func main() {
fmt.Println(longestCommonSubsequence("abcde", "ace"))
}
// 394. 二叉树的中序遍历
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func inorderTraversal(root *TreeNode) []int {
var res []int
var stack []*TreeNode
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
root = root.Left
}
index := len(stack) - 1 // 栈顶
root = stack[index]
stack = stack[:index] // 出栈
res = append(res, root.Val)
root = root.Right
}
return res
}
func main() {
root := &TreeNode{Val: 1, Left: nil, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}}}
fmt.Println(inorderTraversal(root))
}
// 1 3 282. 删除排序链表中的重复元素 II
82. 删除排序链表中的重复元素 II - 力扣（LeetCode）
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return head
}
dummy := &ListNode{Next: head}
p := dummy
for p.Next != nil {
q := p.Next.Next
for q != nil && q.Val == p.Next.Val {
q = q.Next
}
if q == p.Next.Next {
p = p.Next
}
p.Next = q
}
return dummy.Next
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4, Next: &ListNode{Val: 4, Next: &ListNode{Val: 5, Next: nil}}}}}}}
res := deleteDuplicates(head)
for res != nil {
fmt.Printf("%d ", res.Val)
res = res.Next
}
}
// 1 2 5199. 二叉树的右视图
package main
import "fmt"
type TreeNode struct {
Val int
Left *TreeNode
Right *TreeNode
}
func rightSideView(root *TreeNode) []int {
res := []int{}
if root == nil {
return res
}
q := []*TreeNode{root}
for len(q) > 0 {
l := len(q)
for i := 0; i < l; i++ {
node := q[0]
q = q[1:]
if node.Left != nil {
q = append(q, node.Left)
}
if node.Right != nil {
q = append(q, node.Right)
}
if i == l-1 {
res = append(res, node.Val)
}
}
}
return res
}
func main() {
tree := &TreeNode{
Val: 3,
Left: &TreeNode{
Val: 9,
},
Right: &TreeNode{
Val: 20,
Left: &TreeNode{
Val: 15,
},
Right: &TreeNode{
Val: 7,
},
},
}
fmt.Println(rightSideView(tree))
}
// 3 20 7704. 二分查找
package main
import "fmt"
func search(nums []int, target int) int {
l, r := 0, len(nums)-1
for l < r {
mid := (l + r) / 2
if nums[mid] >= target {
r = mid
} else {
l = mid + 1
}
}
if nums[r] != target {
return -1
}
return r
}
func main() {
fmt.Println(search([]int{-1, 0, 3, 5, 9, 12}, 9))
}
// 4232. 用栈实现队列
package main
import "fmt"
type MyQueue struct {
stk1 []int
stk2 []int
}
func Constructor() MyQueue {
return MyQueue{[]int{}, []int{}}
}
func (this *MyQueue) Push(x int) {
this.stk1 = append(this.stk1, x)
}
func (this *MyQueue) Pop() int {
this.move()
ans := this.stk2[len(this.stk2)-1]
this.stk2 = this.stk2[:len(this.stk2)-1]
return ans
}
func (this *MyQueue) Peek() int {
this.move()
return this.stk2[len(this.stk2)-1]
}
func (this *MyQueue) Empty() bool {
return len(this.stk1) == 0 && len(this.stk2) == 0
}
func (this *MyQueue) move() {
if len(this.stk2) == 0 {
for len(this.stk1) > 0 {
this.stk2 = append(this.stk2, this.stk1[len(this.stk1)-1])
this.stk1 = this.stk1[:len(this.stk1)-1]
}
}
}
func main() {
obj := Constructor()
obj.Push(2)
obj.Push(3)
fmt.Println(obj.Peek())
obj.Pop()
fmt.Println(obj.Peek())
}
// 2 34. 寻找两个正序数组的中位数
4. 寻找两个正序数组的中位数 - 力扣（LeetCode）
package main
import "fmt"
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
i, j, k, pre, cur := 0, 0, 0, 0, 0
n1, n2 := len(nums1), len(nums2)
m := n1 + n2
mid := m / 2
for k <= mid {
pre = cur
if i < n1 && j < n2 {
if nums1[i] < nums2[j] {
cur = nums1[i]
i++
} else {
cur = nums2[j]
j++
}
} else if i < n1 {
cur = nums1[i]
i++
} else {
cur = nums2[j]
j++
}
k++
}
if m%2 == 0 {
return float64(pre+cur) / 2
}
return float64(cur)
}
func main() {
fmt.Println(findMedianSortedArrays([]int{1, 3}, []int{2}))
}
// 2148. 排序链表
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func sortList(head *ListNode) *ListNode {
if head == nil || head.Next == nil {
return head
}
slow, fast := head, head
var preS *ListNode
for fast != nil && fast.Next != nil {
fast = fast.Next.Next
preS = slow
slow = slow.Next
}
preS.Next = nil
l, r := sortList(head), sortList(slow)
return merge(l, r)
}
func merge(l *ListNode, r *ListNode) *ListNode {
dummy := &ListNode{}
p := dummy
for l != nil && r != nil {
if l.Val < r.Val {
p.Next = l
p = p.Next
l = l.Next
} else {
p.Next = r
p = p.Next
r = r.Next
}
}
if l != nil {
p.Next = l
}
if r != nil {
p.Next = r
}
return dummy.Next
}
func main() {
head := &ListNode{Val: 4, Next: &ListNode{Val: 2, Next: &ListNode{Val: 1, Next: &ListNode{Val: 3, Next: nil}}}}
res := sortList(head)
for res != nil {
fmt.Printf("%d ", res.Val)
res = res.Next
}
}
// 1 2 3 469. x 的平方根
package main
import "fmt"
func mySqrt(x int) int {
l, r := 0, x
for l < r {
mid := (l + r + 1) / 2
if x >= mid*mid {
l = mid
} else {
r = mid - 1
}
}
return r
}
func main() {
fmt.Println(mySqrt(4))
}
// 28. 字符串转换整数
8. 字符串转换整数 (atoi) - 力扣（LeetCode）
// 简易版本 未截断i32
func myAtoi(s string) int {
res, flag, i := 0, 1, 0
for s[i] == ' ' {
i ++
}
if s[i] == '-' {
flag = -1
i ++
} else if s[i] == '+' {
i ++
}
for i < len(s) && s[i] >= '0' && s[i] <= '9' {
res = res * 10 + int(s[i] - '0')
i ++
}
return res * flag
}
// AC 版本
func myAtoi(s string) int {
res, flag, i := 0, 1, 0
for i < len(s) && s[i] == ' ' {
i ++
}
if i < len(s) && s[i] == '-' {
flag = -1
i ++
} else if i < len(s) && s[i] == '+' {
i ++
}
for i < len(s) && s[i] >= '0' && s[i] <= '9' {
if res > (1<<31 - 1 - int(s[i]-'0')) / 10 {
if flag == -1 {
return -1 << 31
}
return 1<<31 - 1
}
res = res * 10 + int(s[i] - '0')
i ++
}
return res * flag
}31. 下一个排列
package main
import (
"fmt"
"slices"
)
func nextPermutation(nums []int) {
n := len(nums) - 1
for n > 0 && nums[n] <= nums[n-1] {
n--
}
if n == 0 {
slices.Reverse(nums)
} else {
t := n
for t < len(nums) && nums[t] > nums[n-1] {
t++
}
nums[n-1], nums[t-1] = nums[t-1], nums[n-1]
slices.Reverse(nums[n:])
}
}
func main() {
s := []int{1, 2, 3}
nextPermutation(s)
fmt.Println(s)
}
// 1 3 222. 括号生成
package main
import "fmt"
var (
result []string
path string
)
func generateParenthesis(n int) []string {
result = make([]string, 0)
path = ""
dfs(n, n)
return result
}
func dfs(l, r int) {
if l < 0 || r < 0 || l > r {
return
}
if l == 0 && r == 0 {
result = append(result, path)
return
}
path = path + "("
dfs(l-1, r)
path = path[:len(path)-1]
path = path + ")"
dfs(l, r-1)
path = path[:len(path)-1]
}
func main() {
fmt.Println(generateParenthesis(2))
}
// [(()) ()()]2. 两数相加
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func addTwoNumbers(l1 *ListNode, l2 *ListNode) *ListNode {
dummy := &ListNode{}
p := dummy
t := 0
for t != 0 || l1 != nil || l2 != nil {
if l1 != nil {
t += l1.Val
l1 = l1.Next
}
if l2 != nil {
t += l2.Val
l2 = l2.Next
}
p.Next = &ListNode{Val: t % 10}
p = p.Next
t /= 10
}
return dummy.Next
}
func main() {
l1 := &ListNode{1, &ListNode{3, nil}}
l2 := &ListNode{2, &ListNode{3, nil}}
res := addTwoNumbers(l1, l2)
for res != nil {
fmt.Printf("%d", res.Val)
res = res.Next
}
}
// 3670. 爬楼梯
package main
import "fmt"
var memo []int
func climbStairs(n int) int {
memo = make([]int, n+1)
for i := range memo {
memo[i] = -1
}
return dp(n)
}
func dp(n int) int {
if n == 1 || n == 2 {
return n
}
if memo[n] != -1 {
return memo[n]
}
memo[n] = dp(n-1) + dp(n-2)
return memo[n]
}
func main() {
fmt.Println(climbStairs(3))
}
// 3165. 比较版本号
package main
import (
"fmt"
"strconv"
"strings"
)
func compareVersion(version1 string, version2 string) int {
s1 := strings.Split(version1, ".")
s2 := strings.Split(version2, ".")
for i := 0; i < len(s1) || i < len(s2); i++ {
v1, v2 := 0, 0
if i < len(s1) {
v1, _ = strconv.Atoi(s1[i])
}
if i < len(s2) {
v2, _ = strconv.Atoi(s2[i])
}
if v1 > v2 {
return 1
}
if v1 < v2 {
return -1
}
}
return 0
}
func main() {
fmt.Println(compareVersion("1.1", "0.1"))
}
// 1239. 滑动窗口最大值
package main
import (
"fmt"
)
func maxSlidingWindow(nums []int, k int) []int {
ans := make([]int, 0, len(nums)-k+1) // 预先分配好空间
q := []int{}
for i, x := range nums {
for len(q) > 0 && nums[q[len(q)-1]] <= x {
q = q[:len(q)-1] // 维护 q 的单调性
}
q = append(q, i) // 入队
if i-q[0] >= k { // 队首已经离开窗口了
q = q[1:]
}
if i >= k-1 {
ans = append(ans, nums[q[0]])
}
}
return ans
}
func main() {
fmt.Println(maxSlidingWindow([]int{1, 3, -1, -3, 5, 3, 6, 7}, 3))
}
// 3 3 5 5 6 741. 缺失的第一个正数
package main
import (
"fmt"
)
func firstMissingPositive(nums []int) int {
n := len(nums)
for i := 0; i < n; i++ {
for nums[i] > 0 && nums[i] <= n && nums[nums[i]-1] != nums[i] {
nums[nums[i]-1], nums[i] = nums[i], nums[nums[i]-1]
}
}
for i := 0; i < n; i++ {
if nums[i] != i+1 {
return i + 1
}
}
return n + 1
}
func main() {
fmt.Println(firstMissingPositive([]int{3, 4, -1, 1}))
}
// 2322. 零钱兑换
package main
import (
"fmt"
)
func coinChange(coins []int, amount int) int {
dp := make([]int, amount+1)
for i := range dp {
dp[i] = amount + 1
}
dp[0] = 0
for i := 1; i < len(dp); i++ {
for _, coin := range coins {
if i >= coin {
dp[i] = min(dp[i], dp[i-coin]+1)
}
}
}
if dp[amount] == amount+1 {
return -1
}
return dp[amount]
}
func main() {
fmt.Println(coinChange([]int{1, 2, 5}, 11))
}
// 376. 最小覆盖子串
package main
import (
"fmt"
"math"
)
func minWindow(s string, t string) string {
win, need := map[rune]int{}, map[rune]int{}
for _, c := range t {
need[c]++
}
l, r, st, vl, length := 0, 0, 0, 0, math.MaxInt
for r < len(s) {
c := rune(s[r])
r++
if _, ok := need[c]; ok {
win[c]++
if win[c] == need[c] {
vl++
}
}
for vl == len(need) {
if r-l < length {
st = l
length = r - l
}
d := rune(s[l])
l++
if _, ok := need[d]; ok {
if win[d] == need[d] {
vl--
}
win[d]--
}
}
}
if length == math.MaxInt {
return ""
}
return s[st : st+length]
}
func main() {
fmt.Println(minWindow("ADOBECODEBANC", "ABC"))
}
// BANC78. 子集
package main
import (
"fmt"
)
var (
res [][]int
path []int
)
func subsets(nums []int) [][]int {
res = [][]int{}
dfs(nums, 0)
return res
}
func dfs(nums []int, u int) {
if u == len(nums) {
temp := make([]int, len(path))
copy(temp, path)
res = append(res, temp)
return
}
dfs(nums, u+1)
path = append(path, nums[u])
dfs(nums, u+1)
path = path[:len(path)-1]
}
func main() {
fmt.Println(subsets([]int{1, 2, 3}))
}
// [[] [3] [2] [2 3] [1] [1 3] [1 2] [1 2 3]]105. 从前序与中序遍历序列构造二叉树
105. 从前序与中序遍历序列构造二叉树 - 力扣（LeetCode）
func buildTree(preorder []int, inorder []int) *TreeNode {
return dfs(preorder, 0, len(preorder)-1, inorder, 0, len(inorder)-1)
}
func dfs(preorder []int, pst int, ped int, inorder []int, ist int, ied int) *TreeNode {
if pst > ped {
return nil
}
val := preorder[pst]
var idx int
root := &TreeNode{Val: val}
for i := ist; i <= ied; i++ {
if inorder[i] == val {
idx = i
break
}
}
root.Left = dfs(preorder, pst+1, pst+idx-ist, inorder, ist, idx-1)
root.Right = dfs(preorder, pst+idx-ist+1, ped, inorder, idx+1, ied)
return root
}155. 最小栈
package main
import (
"fmt"
"math"
)
type MinStack struct {
stk, minS []int
}
func Constructor() MinStack {
return MinStack{stk: []int{}, minS: []int{math.MaxInt}}
}
func (s *MinStack) Push(val int) {
s.stk = append(s.stk, val)
s.minS = append(s.minS, min(val, s.minS[len(s.minS)-1]))
}
func (s *MinStack) Pop() {
s.stk = s.stk[:len(s.stk)-1]
s.minS = s.minS[:len(s.minS)-1]
}
func (s *MinStack) Top() int {
return s.stk[len(s.stk)-1]
}
func (s *MinStack) GetMin() int {
return s.minS[len(s.minS)-1]
}
func main() {
obj := Constructor()
obj.Push(11)
obj.Push(2)
fmt.Println(obj.GetMin())
}
// 232. 最长有效括号
package main
import "fmt"
func longestValidParentheses(s string) int {
var stack []int
dp := make([]int, len(s)+1)
max := 0
for i := 0; i < len(s); i++ {
if string(s[i]) == "(" {
stack = append(stack, i)
} else {
if len(stack) == 0 {
continue
} else {
lidx := stack[len(stack)-1]
stack = stack[:len(stack)-1]
dp[i+1] = i + 1 - lidx + dp[lidx]
}
}
if dp[i+1] > max {
max = dp[i+1]
}
}
return max
}
func main() {
fmt.Println(longestValidParentheses(")()())"))
}
// 443. 字符串相乘
package main
import (
"fmt"
"strconv"
)
func multiply(num1 string, num2 string) string {
if num1 == "0" || num2 == "0" {
return "0"
}
m, n := len(num1), len(num2)
res := make([]int, m+n)
for i := m - 1; i >= 0; i-- {
for j := n - 1; j >= 0; j-- {
mul := int(num1[i]-'0') * int(num2[j]-'0')
r1, r2 := i+j, i+j+1
sum := mul + res[r2]
res[r1] += sum / 10
res[r2] = sum % 10
}
}
for i := 0; i < len(res); i++ {
if res[i] != 0 {
res = res[i:]
break
}
}
var result string
for _, v := range res {
result += strconv.Itoa(v)
}
return result
}
func main() {
fmt.Println(multiply("12", "13"))
}
// 156151. 反转字符串中的单词
package main
import (
"fmt"
"strings"
)
func reverseWords(s string) string {
words := strings.Fields(s)
for i := 0; i < len(words)/2; i++ {
words[i], words[len(words)-1-i] = words[len(words)-1-i], words[i]
}
res := strings.Join(words, " ")
return res
}
func main() {
fmt.Println(reverseWords("the sky is blue"))
}
// blue is sky the129. 求根节点到叶节点数字之和
129. 求根节点到叶节点数字之和 - 力扣（LeetCode）
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
var res int
func sumNumbers(root *TreeNode) int {
res = 0
dfs(root, 0)
return res
}
func dfs(root *TreeNode, sum int) {
if root == nil {
return
}
sum = sum*10 + root.Val
if root.Left == nil && root.Right == nil {
res += sum
return
}
dfs(root.Left, sum)
dfs(root.Right, sum)
}
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 3},
}
fmt.Println(sumNumbers(root))
}
// 25104. 二叉树的最大深度
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func maxDepth(root *TreeNode) int {
if root == nil {
return 0
}
l := maxDepth(root.Left)
r := maxDepth(root.Right)
return max(l, r) + 1
}
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 3},
}
fmt.Println(maxDepth(root))
}
// 2101. 对称二叉树
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func isSymmetric(root *TreeNode) bool {
return dfs(root.Left, root.Right)
}
func dfs(left, right *TreeNode) bool {
if left == nil && right == nil {
return true
}
if left == nil || right == nil {
return false
}
if left.Val != right.Val {
return false
}
return dfs(left.Left, right.Right) && dfs(left.Right, right.Left)
}
func main() {
root := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 2},
}
fmt.Println(isSymmetric(root))
}
// true144. 二叉树的前序遍历
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func preorderTraversal(root *TreeNode) []int {
var res []int
var stack []*TreeNode
for root != nil || len(stack) > 0 {
for root != nil {
stack = append(stack, root)
res = append(res, root.Val)
root = root.Left
}
index := len(stack) - 1 // 栈顶
root = stack[index]
stack = stack[:index] // 出栈
root = root.Right
}
return res
}
func main() {
root := &TreeNode{Val: 1, Left: nil, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}}}
fmt.Println(preorderTraversal(root))
}
// 1 2 3543. 二叉树的直径
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
var res int
func diameterOfBinaryTree(root *TreeNode) int {
res = 0
dfs(root)
return res
}
func dfs(root *TreeNode) {
if root == nil {
return
}
l := maxD(root.Left)
r := maxD(root.Right)
res = max(res, l+r)
dfs(root.Left)
dfs(root.Right)
}
func maxD(root *TreeNode) int {
if root == nil {
return 0
}
l := maxD(root.Left)
r := maxD(root.Right)
return max(l, r) + 1
}
func main() {
root := &TreeNode{Val: 1, Left: nil, Right: &TreeNode{Val: 2, Left: &TreeNode{Val: 3}}}
fmt.Println(diameterOfBinaryTree(root))
}
// 298. 验证二叉搜索树
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func isValidBST(root *TreeNode) bool {
return dfs(root, nil, nil)
}
func dfs(root, min, max *TreeNode) bool {
if root == nil {
return true
}
if max != nil && max.Val <= root.Val || min != nil && min.Val >= root.Val {
return false
}
return dfs(root.Left, min, root) && dfs(root.Right, root, max)
}
func main() {
root := &TreeNode{Val: 2, Left: &TreeNode{Val: 1}, Right: &TreeNode{Val: 3}}
fmt.Println(isValidBST(root))
}
// true470. 用 Rand7() 实现 Rand10()
470. 用 Rand7() 实现 Rand10() - 力扣（LeetCode）
func rand10() int {
t := (rand7() - 1) * 7 + rand7()
if t > 40 {
return rand10()
}
return (t - 1) % 10 + 1
}34. 在排序数组中查找元素的第一个和最后一个位置
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
package main
import "fmt"
func searchRange(nums []int, target int) []int {
if len(nums) == 0 {
return []int{-1, -1}
}
l, r := 0, len(nums)-1
for l < r {
mid := (l + r + 1) >> 1
if nums[mid] <= target {
l = mid
} else {
r = mid - 1
}
}
var i, j int
if nums[r] == target {
i = r
} else {
return []int{-1, -1}
}
l, r = 0, len(nums)-1
for l < r {
mid := (l + r) >> 1
if nums[mid] >= target {
r = mid
} else {
l = mid + 1
}
}
if nums[r] == target {
j = r
} else {
return []int{-1, -1}
}
return []int{j, i}
}
func main() {
fmt.Println(searchRange([]int{5, 7, 7, 8, 8, 10}, 8))
}
// 3 464. 最小路径和
34. 在排序数组中查找元素的第一个和最后一个位置 - 力扣（LeetCode）
package main
import (
"fmt"
"math"
)
func minPathSum(grid [][]int) int {
m, n := len(grid), len(grid[0])
memo := make([][]int, m)
for i := range memo {
memo[i] = make([]int, n)
for j := range memo[i] {
memo[i][j] = -1
}
}
return dp(grid, m-1, n-1, memo)
}
func dp(grid [][]int, m, n int, memo [][]int) int {
if m == 0 && n == 0 {
return grid[0][0]
}
if m < 0 || n < 0 {
return math.MaxInt
}
if memo[m][n] != -1 {
return memo[m][n]
}
memo[m][n] = min(dp(grid, m-1, n, memo), dp(grid, m, n-1, memo)) + grid[m][n]
return memo[m][n]
}
func main() {
fmt.Println(minPathSum([][]int{
{1, 3, 1},
{1, 5, 1},
{4, 2, 1},
}))
}
// 748. 旋转图像
package main
import "fmt"
func rotate(matrix [][]int) {
m := len(matrix)
for i, j := 0, m-1; i < j; i, j = i+1, j-1 {
matrix[i], matrix[j] = matrix[j], matrix[i]
}
for i := 0; i < m; i++ {
for j := i + 1; j < m; j++ {
matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
}
}
}
func main() {
m := [][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
rotate(m)
fmt.Println(m)
}
// [[7 4 1] [8 5 2] [9 6 3]]39. 组合总数
package main
import "fmt"
var (
res [][]int
path []int
)
func combinationSum(candidates []int, target int) [][]int {
res = [][]int{}
path = []int{}
dfs(candidates, target, 0)
return res
}
func dfs(candidates []int, target int, u int) {
if target == 0 {
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
return
} else if target < 0 {
return
}
for i := u; i < len(candidates); i++ {
path = append(path, candidates[i])
dfs(candidates, target-candidates[i], i)
path = path[:len(path)-1]
}
}
func main() {
fmt.Println(combinationSum([]int{2, 3, 6, 7}, 7))
}
// [[2 2 3] [7]]113. 路径之和 II
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
var res [][]int
var path []int
func pathSum(root *TreeNode, targetSum int) [][]int {
res = [][]int{}
path = []int{}
dfs(root, targetSum)
return res
}
func dfs(root *TreeNode, targetSum int) {
if root == nil {
return
}
path = append(path, root.Val)
targetSum -= root.Val
if root.Left == nil && root.Right == nil && targetSum == 0 {
tmp := make([]int, len(path))
copy(tmp, path)
res = append(res, tmp)
}
if root.Left != nil {
dfs(root.Left, targetSum)
}
if root.Right != nil {
dfs(root.Right, targetSum)
}
path = path[:len(path)-1]
}
func main() {
root := &TreeNode{
Val: 3,
Left: &TreeNode{Val: 2},
Right: &TreeNode{Val: 1},
}
fmt.Println(pathSum(root, 5))
}
// [3 2]394. 字符串解码
package main
import (
"fmt"
"strings"
)
func decodeString(s string) string {
numStack, strStack, num, result := []int{}, []string{}, 0, ""
for _, ch := range s {
if ch >= '0' && ch <= '9' {
num = num*10 + int(ch-'0')
} else if ch == '[' {
numStack, strStack, num, result = append(numStack, num), append(strStack, result), 0, ""
} else if ch == ']' {
result, num = strStack[len(strStack)-1]+strings.Repeat(result, numStack[len(numStack)-1]), 0
strStack, numStack = strStack[:len(strStack)-1], numStack[:len(numStack)-1]
} else {
result += string(ch)
}
}
return result
}
func main() {
fmt.Println(decodeString("3[a]2[bc]"))
}
// aaabcbc240. 搜索二维矩阵
package main
import (
"fmt"
)
func searchMatrix(matrix [][]int, target int) bool {
i, j := 0, len(matrix[0])-1
for i < len(matrix) && j >= 0 {
if matrix[i][j] > target {
j--
} else if matrix[i][j] < target {
i++
} else {
return true
}
}
return false
}
func main() {
fmt.Println(searchMatrix([][]int{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}, 5))
}
// true221. 最大正方形
package main
import (
"fmt"
)
func maximalSquare(matrix [][]byte) int {
m, n, res := len(matrix), len(matrix[0]), 0
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 1; i <= m; i++ {
for j := 1; j <= n; j++ {
if matrix[i-1][j-1] == '1' {
dp[i][j] = min(dp[i-1][j-1], dp[i-1][j], dp[i][j-1]) + 1
res = max(res, dp[i][j])
}
}
}
return res * res
}
func main() {
fmt.Println(maximalSquare([][]byte{{'1', '1', '1'}, {'1', '1', '0'}, {'0', '0', '0'}}))
}
// 4162. 寻找峰值
package main
import (
"fmt"
)
func findPeakElement(nums []int) int {
l, r := 0, len(nums)-1
for l < r {
mid := (l + r) / 2
if nums[mid] >= nums[mid+1] {
r = mid
} else {
l = mid + 1
}
}
return r
}
func main() {
fmt.Println(findPeakElement([]int{1, 2, 3, 1}))
}
// 2234. 回文链表
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func isPalindrome(head *ListNode) bool {
if head == nil {
return true
}
slow, fast := head, head
for fast != nil && fast.Next != nil {
slow = slow.Next
fast = fast.Next.Next
}
if fast != nil {
slow = slow.Next
}
p, q := head, reverseList(slow)
for q != nil {
if q.Val != p.Val {
return false
}
q = q.Next
p = p.Next
}
return true
}
func reverseList(head *ListNode) *ListNode {
if head == nil {
return head
}
a, b := head, head.Next
for b != nil {
t := b.Next
b.Next = a
a = b
b = t
}
head.Next = nil
return a
}
func main() {
head := &ListNode{1, &ListNode{2, &ListNode{2, &ListNode{1, nil}}}}
fmt.Println(isPalindrome(head))
}
// true112. 路径总和
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
var res bool
func hasPathSum(root *TreeNode, targetSum int) bool {
res = false
dfs(root, targetSum)
return res
}
func dfs(root *TreeNode, targetSum int) {
if root == nil {
return
}
targetSum -= root.Val
if root.Left == nil && root.Right == nil && targetSum == 0 {
res = true
return
}
dfs(root.Left, targetSum)
dfs(root.Right, targetSum)
}
func main() {
root := &TreeNode{1, &TreeNode{2, nil, nil}, &TreeNode{4, nil, nil}}
fmt.Println(hasPathSum(root, 3))
}
// true14. 最长公共前缀
package main
import "fmt"
func longestCommonPrefix(strs []string) string {
res := ""
for i := 0; i < len(strs[0]); i++ {
c := strs[0][i]
for _, str := range strs {
if i >= len(str) || str[i] != c {
return res
}
} res += string(c)
} return res
}
func main() {
fmt.Println(longestCommonPrefix([]string{"flower", "flow", "flight"}))
}
// fl128. 最长连续序列
package main
import "fmt"
func longestConsecutive(nums []int) int {
set, res := map[int]bool{}, 0
for _, n := range nums {
set[n] = true
}
for n := range set {
if !set[n-1] {
num := n
sum := 1
for set[num+1] {
num++
sum++
}
res = max(res, sum)
}
}
return res
}
func main() {
fmt.Println(longestConsecutive([]int{100, 4, 200, 1, 3, 2}))
}
// 4718. 最长重复子数组
package main
import "fmt"
func findLength(nums1 []int, nums2 []int) int {
m, n, res := len(nums1), len(nums2), 0
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
}
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if nums1[i] == nums2[j] {
dp[i+1][j+1] = dp[i][j] + 1
}
res = max(res, dp[i+1][j+1])
}
}
return res
}
func main() {
fmt.Println(findLength([]int{1, 2, 3, 2, 1}, []int{3, 2, 1, 4, 7}))
}
// 3169. 多数元素
package main
import "fmt"
func majorityElement(nums []int) int {
cnt, tg := 0, 0
for i := 0; i < len(nums); i++ {
if cnt == 0 {
tg = nums[i]
cnt++
continue
}
if nums[i] != tg {
cnt--
} else {
cnt++
}
}
return tg
}
func main() {
fmt.Println(majorityElement([]int{3, 2, 3}))
}
// 3662. 二叉树最大宽度
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
type Node struct {
Node *TreeNode
Pos int
}
func widthOfBinaryTree(root *TreeNode) int {
res := 0
if root == nil {
return res
}
q := []*Node{{root, 1}}
for len(q) > 0 {
length := len(q)
l, r := q[0].Pos, 0
for i := 0; i < length; i++ {
t := q[0]
q = q[1:]
t1 := t.Node
r = t.Pos
p := r - l + 1
if t1.Left != nil {
q = append(q, &Node{t1.Left, p * 2})
}
if t1.Right != nil {
q = append(q, &Node{t1.Right, p*2 + 1})
}
}
res = max(res, r-l+1)
}
return res
}
func main() {
tree := &TreeNode{
Val: 1,
Left: &TreeNode{Val: 3, Left: &TreeNode{Val: 2}},
Right: &TreeNode{Val: 2},
}
fmt.Println(widthOfBinaryTree(tree))
}
// 2122. 买卖股票的最佳时机 II
122. 买卖股票的最佳时机 II - 力扣（LeetCode）
package main
import "fmt"
func maxProfit(prices []int) int {
dp := make([][]int, len(prices))
for i := range dp {
dp[i] = make([]int, 2)
}
dp[0][0] = 0
dp[0][1] = -prices[0]
for i := 1; i < len(prices); i++ {
dp[i][0] = max(dp[i-1][0], dp[i-1][1]+prices[i])
dp[i][1] = max(dp[i-1][1], dp[i-1][0]-prices[i])
}
return dp[len(prices)-1][0]
}
func main() {
fmt.Println(maxProfit([]int{7, 1, 5, 3, 6, 4}))
}
// 762. 不同路径
package main
import "fmt"
func uniquePaths(m int, n int) int {
dp := make([][]int, m+1)
for i := range dp {
dp[i] = make([]int, n+1)
} if m == 1 || n == 1 {
return 1
}
dp[0][1], dp[1][0] = 1, 1
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if i != 0 {
dp[i][j] += dp[i-1][j]
} if j != 0 {
dp[i][j] += dp[i][j-1]
} } } return dp[m-1][n-1]
}
func main() {
fmt.Println(uniquePaths(3, 7))
}
// 28226. 翻转二叉树
package main
import "fmt"
type TreeNode struct {
Val int
Left, Right *TreeNode
}
func invertTree(root *TreeNode) *TreeNode {
if root == nil {
return root
}
t := root.Left
root.Left = root.Right
root.Right = t
invertTree(root.Left)
invertTree(root.Right)
return root
}
func main() {
root := &TreeNode{
Val: 2,
Left: &TreeNode{Val: 1},
Right: &TreeNode{Val: 3},
}
invertTree(root)
fmt.Printf("%d %d %d", root.Val, root.Left.Val, root.Right.Val)
}
// 2 3 1179. 最大数
package main
import (
"fmt"
"sort"
"strconv"
"strings"
)
func largestNumber(nums []int) string {
sort.Slice(nums, func(i, j int) bool {
a, b := nums[i], nums[j]
strA, strB := strconv.Itoa(a), strconv.Itoa(b)
return strA+strB >= strB+strA
})
var res string
for _, num := range nums {
res += strconv.Itoa(num)
}
if len(res) > 0 && res[0] == '0' {
return "0"
}
return res
}
func main() {
fmt.Println(largestNumber([]int{10, 2}))
}
// 210152. 乘积最大的子数组
package main
import (
"fmt"
)
func maxProduct(nums []int) int {
dp1, dp2 := make([]int, len(nums)), make([]int, len(nums))
dp1[0], dp2[0] = nums[0], nums[0]
res := nums[0]
for i := 1; i < len(nums); i++ {
dp1[i] = max(nums[i], dp1[i-1]*nums[i], dp2[i-1]*nums[i])
dp2[i] = min(nums[i], dp1[i-1]*nums[i], dp2[i-1]*nums[i])
res = max(res, dp1[i])
}
return res
}
func main() {
fmt.Println(maxProduct([]int{2, 3, -2, 4}))
}
// 683. 删除排序链表中重复元素
83. 删除排序链表中的重复元素 - 力扣（LeetCode）
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func deleteDuplicates(head *ListNode) *ListNode {
if head == nil {
return head
}
slow, fast := head, head.Next
for fast != nil {
if slow.Val != fast.Val {
slow.Next = fast
slow = slow.Next
}
fast = fast.Next
}
slow.Next = nil
return head
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 2, Next: nil}}}
deleteDuplicates(head)
for head != nil {
fmt.Printf("%d ", head.Val)
head = head.Next
}
}
// 2695. 岛屿的最大面积
package main
import "fmt"
type Solution struct {
dx, dy []int
g [][]int
}
func maxAreaOfIsland(grid [][]int) int {
sol := Solution{
dx: []int{0, 1, 0, -1},
dy: []int{1, 0, -1, 0},
g: grid,
}
m, n, res := len(sol.g), len(sol.g[0]), 0
for i := 0; i < m; i++ {
for j := 0; j < n; j++ {
if sol.g[i][j] == 1 {
res = max(res, sol.dfs(i, j))
}
}
}
return res
}
func (sol *Solution) dfs(x, y int) int {
sol.g[x][y] = 0
res := 1
for i := 0; i < 4; i++ {
a, b := x+sol.dx[i], y+sol.dy[i]
for a >= 0 && b >= 0 && a < len(sol.g) && b < len(sol.g[0]) && sol.g[a][b] == 1 {
res += sol.dfs(a, b)
}
}
return res
}
func main() {
g := [][]int{{1, 1, 0}, {1, 1, 0}, {0, 0, 0}}
fmt.Println(maxAreaOfIsland(g))
}
// 4227. 基本计算器 II
package main
import "fmt"
func calculate(s string) int {
s += "+"
nums, curNum, prevOp, sum := []int{}, 0, '+', 0
for _, ch := range s {
if ch >= '0' && ch <= '9' {
curNum = curNum*10 + int(ch-'0')
} else if ch != ' ' {
switch prevOp {
case '+':
nums = append(nums, curNum)
case '-':
nums = append(nums, -curNum)
case '*':
nums[len(nums)-1] *= curNum
case '/':
nums[len(nums)-1] /= curNum
}
curNum, prevOp = 0, rune(ch)
}
}
for _, n := range nums {
sum += n
}
return sum
}
func main() {
fmt.Println(calculate("3+2*2"))
}
// 7198. 打家劫舍
package main
import "fmt"
func rob(nums []int) int {
dp := make([]int, len(nums)+2)
for i := len(nums) - 1; i >= 0; i-- {
dp[i] = max(dp[i+1], dp[i+2]+nums[i])
}
return dp[0]
}
func main() {
fmt.Println(rob([]int{1, 2, 3, 1}))
}
// 4139. 单词拆分
package main
import "fmt"
func wordBreak(s string, dict []string) bool {
dp := make([]bool, len(s)+1)
dp[0] = true
for i := 0; i < len(s); i++ {
for _, w := range dict {
if !dp[i] || len(w) > len(s)-i || s[i:i+len(w)] != w {
continue
}
dp[i+len(w)] = true
}
}
return dp[len(s)]
}
func main() {
fmt.Println(wordBreak("leetcode", []string{"leet", "code"}))
}
// true补充题：手撕堆排序
package main
import "fmt"
func heapSort(nums []int) {
n := len(nums)
for i := n / 2; i >= 0; i-- {
sink(nums, i, n-1)
}
for end := n - 1; end >= 0; end-- {
nums[0], nums[end] = nums[end], nums[0]
sink(nums, 0, end-1)
}
}
func sink(heap []int, root, end int) {
// 循环直到节点没有子节点（child直到超出数组的范围）
for child := 2*root + 1; child <= end; child = 2*root + 1 {
// 如果有右子节点，并且右子节点的值大于左子节点，则选取右子节点与父节点进行比较
if child < end && heap[child] < heap[child + 1] {
child++
}
// 如果父节点的值大于子节点，则满足最大堆的性质，无须交换，直接返回
if heap[root] >= heap[child] {
break
}
// 否则，交换父节点与子节点的值，继续下沉调整
heap[root], heap[child] = heap[child], heap[root]
root = child
}
}
func main() {
nums := []int{3, 2, 1, 4, 5}
heapSort(nums)
fmt.Println(nums)
}
// 1 2 3 4 524. 两两交换链表中的节点
package main
import "fmt"
type ListNode struct {
Val int
Next *ListNode
}
func swapPairs(head *ListNode) *ListNode {
if head == nil {
return head
}
dummy := &ListNode{Next: head}
p := dummy
for p.Next != nil && p.Next.Next != nil {
n1, n2 := p.Next, p.Next.Next
n1.Next = n2.Next
n2.Next = n1
p.Next = n2
p = n1
}
return dummy.Next
}
func main() {
head := &ListNode{Val: 1, Next: &ListNode{Val: 2, Next: &ListNode{Val: 3, Next: &ListNode{Val: 4}}}}
res := swapPairs(head)
for res != nil {
fmt.Printf("%d ", res.Val)
res = res.Next
}
}
// 2 1 4 3297. 二叉树的序列化与反序列化
297. 二叉树的序列化与反序列化 - 力扣（LeetCode）
type TreeNode struct {
Val int
Left, Right *TreeNode
}
type Codec struct{}
func Constructor() Codec {
return Codec{}
}
// Serializes a tree to a single string.
func (this *Codec) serialize(root *TreeNode) string {
if root == nil {
return "X"
}
return strconv.Itoa(root.Val) + "," + this.serialize(root.Left) + "," + this.serialize(root.Right)
}
// Deserializes your encoded data to tree.
func buildTree(list *[]string) *TreeNode {
rootVal := (*list)[0]
*list = (*list)[1:]
if rootVal == "X" {
return nil
}
Val, _ := strconv.Atoi(rootVal)
root := &TreeNode{Val: Val}
root.Left = buildTree(list)
root.Right = buildTree(list)
return root
}
func (this *Codec) deserialize(data string) *TreeNode {
list := strings.Split(data, ",")
return buildTree(&list)
}560. 和为 K 的子数组
package main
import "fmt"
func subarraySum(nums []int, k int) int {
hash := make(map[int]int)
hash[0] = 1
pre, res := 0, 0
for _, n := range nums {
pre += n
if _, ok := hash[pre-k]; ok {
res += hash[pre-k]
}
hash[pre]++
}
return res
}
func main() {
fmt.Println(subarraySum([]int{1, 1, 1}, 2))
}
// 2209. 长度最小的子数组
package main
import (
"fmt"
"math"
)
func minSubArrayLen(target int, nums []int) int {
r, l, length := 0, 0, math.MaxInt
for r < len(nums) {
target -= nums[r]
r++
for target <= 0 {
length = min(length, r-l)
target += nums[l]
l++
}
}
if length == math.MaxInt {
return 0
}
return length
}
func main() {
fmt.Println(minSubArrayLen(7, []int{2, 3, 1, 2, 4, 3}))
}
// 2Last updated