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 5
146. 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 2
215. 数组中的第 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 5
25. 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 1
15. 三数之和
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 5
21. 合并两个有序链表
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 4
1. 两数之和
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 1
5. 最长回文子串
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"))
}
// bb
102. 二叉树的层序遍历
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))
}
// 4
200. 岛屿数量
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))
}
// 2
121. 买卖股票的最佳时机
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}))
}
// 5
20. 有效的括号
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 false
141. 环形链表
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))
}
// true
88. 合并两个有序数组
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 6
236. 二叉树的最近公共祖先
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)
}
// 1
46. 全排列
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 1
54. 螺旋矩阵
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