【CodeTop】TOP 100 刷题 1-10

文章目录

1. 无重复字符的最长子串
- 题目描述
- 代码与思路
2. 反转链表
- 题目描述
- 代码与解题思路
3. LRU 缓存
- 题目描述
- 代码与解题思路
4. 数组中的第K个最大元素
- 题目描述
- 代码与解题思路
5. K 个一组翻转链表
- 题目描述
- 代码与解题思路
6. 三数之和
- 题目描述
- 代码与解题思路
7. 最大子数组和
- 题目描述
- 代码与解题思路
8. 手撕快排
- 题目描述
- 代码与解题思路
9. 两数之和
- 题目描述
- 代码与解题思路
10. 最长回文子串
- 题目描述
- 代码与解题思路

1. 无重复字符的最长子串

题目链接：3. 无重复字符的最长子串

题目描述

代码与思路

func lengthOfLongestSubstring(s string) int {
    win := map[byte]int{}
    slow, fast, ans := 0, 0, 0
    for fast < len(s) {
        for win[s[fast]] == 1 { // 字符不能重复，如果重复就得将重复的字符出窗口
            win[s[slow]]--
            slow++
        }
        ans = max(ans, fast-slow+1)
        win[s[fast]]++
        fast++
    }
    return ans 
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

我这里使用的是传统的滑动窗口的解题思路，根据题目条件设置出窗口，每轮遍历将一个新的值入窗口，朴素，但是思路简单好用。足够了。

2. 反转链表

题目链接：206. 反转链表

题目描述

代码与解题思路

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseList(head *ListNode) *ListNode {
    var pre *ListNode = nil // 这里注意一下, 不能用 pre := nil, 语法不支持
    var cur *ListNode = head
    for cur != nil {
        tmp := cur.Next
        cur.Next = pre
        pre = cur
        cur = tmp
    }
    return pre
}

这里要注意一下，反转链表开始遍历的时候是 pre，cur 一前一后，而 go 语言不支持 pre := nil 这个操作，所以得用 var pre *ListNode，别搞错了

3. LRU 缓存

题目链接：146. LRU 缓存

题目描述

代码与解题思路

type entry struct {
    key, value int
}


type LRUCache struct {
    capacity  int
    list      *list.List
    keyToNode map[int]*list.Element
}


func Constructor(capacity int) LRUCache {
    return LRUCache {
        capacity,
        list.New(),
        map[int]*list.Element{},
    }
}


func (c *LRUCache) Get(key int) int {
    node := c.keyToNode[key]
    if node == nil { // 没找到这本书
        return -1
    }
    c.list.MoveToFront(node)
    return node.Value.(entry).value
}


func (c *LRUCache) Put(key int, value int)  {
    if node := c.keyToNode[key]; node != nil { // 有这本书
        node.Value = entry {key, value}
        c.list.MoveToFront(node)
        return
    }
    c.keyToNode[key] = c.list.PushFront(entry{key, value}) // 新书，放在最上面
    if len(c.keyToNode) > c.capacity { // 书数量超过 capacity
        delete(c.keyToNode, c.list.Remove(c.list.Back()).(entry).key) // 去掉最后一本书
    }
}


/**
 * Your LRUCache object will be instantiated and called as such:
 * obj := Constructor(capacity);
 * param_1 := obj.Get(key);
 * obj.Put(key,value);
 */

用的是双向链表 + 哈希的方法：

get 把缓存取出，放在链表表头
put 放入新缓存，如果已经存在 key，就取出放在表头，并更新 value；如果不存在 key，就放在表头（如果超过 capacity 就把链表尾移除）

双向链表能让我们操作头尾的时候是 O(1) 的复杂度，而哈希能让我们在 get 查找的时候是 O(1) 的复杂度。

代码中需要注意的点是：

将节点移到表头可以用 go 语言 list 中自带的 MoveToFront 方法，list 相关可以去学习这一篇文章：Go 基础：list 的介绍与使用
在删除元素的时候，我们使用的两个数据结构：map 和 list 中的元素都要记得删除，所以代码最后一段，我们 delete 和 Remove 同时在使用

4. 数组中的第K个最大元素

题目链接：215. 数组中的第K个最大元素

题目描述

代码与解题思路

var num []int

func findKthLargest(nums []int, k int) int {
    num = nums
    return qselect(0, len(nums)-1, len(num)-k)
}

func qselect(left, right, k int) int { // 双指针快排模板
    mid := getmid(left, right) // 三数取中(也可以随机选数)
    swap(&num[left], &num[mid]) // 选出来的数换 key(基准值)
    key, prev, cur := left, left, left+1
    for cur <= right { // 这里的 right 其实就是数组最右边的下标
        if num[cur] < num[key] {
            prev++
            swap(&num[cur], &num[prev])
        }
        cur++
    }
    swap(&num[key], &num[prev])
    key = prev // key 的左区间比 key 小, 右区间比 key 大, 再分两路递归
    if key < k {
        qselect(key+1, right, k)
    } else if key > k {
        qselect(left, key-1, k)
    }
    return num[k] // 如果 key 的位置正好是 k, 那就找到要取的数了
}

func getmid(left, right int) int { // 三数取中
    mid := (left+right)/2
    if num[mid] > num[left] {
        if num[right] > num[mid] {
            return mid
        } else if num[right] < num[left] {
            return left
        } else {
            return right
        }
    } else {
        if num[right] > num[left] {
            return left
        } else if num[right] < num[mid] {
            return mid
        } else {
            return right
        }
    }
    return -1
}

func swap(a, b *int) {
    *a, *b = *b, *a
}

这道题有两个思路，一个是用快排来解，通过快排的基准值 key 来锁定倒数第 k 个数，但是 LeetCode 最近新添加了一个全是 1 的样例，如果说快排遇到有序数组可以用随机选数或者三数取中来优化，那么，遇到全是同一个数的场景，快排当场退化成 N 方复杂度，算是快排的缺陷了。

我上面的使用的就是快排，所以现在 LeetCode 最后一个全是 1 的样例过不去（别尬黑，LeetCode 官方自己的题解都过不去）

我使用的是快排的双指针法，代码还是比较好理解的，直接读代码就行。

那这个时候就只能用堆排来做了，虽然复杂度是 O(N*logk) 但是 logk 几乎可以忽略不计，所以也能当做是 O(N) 的复杂度，下面是用堆排的算法：

func findKthLargest(nums []int, k int) int {
    n := len(nums)
    buildMaxHeap(nums, n) // 建堆操作, 我们需要一大堆来执行堆排
    for end := n-1; end > 0; end-- { // 排序成升序数组(堆排)
        swap(&nums[end], &nums[0]); // 头尾交换
        AdjustDown(nums, end, 0) // 向下调整(向下调整的左右子树必须是大堆)
    }
    return nums[n-k] // 返回倒数第 k 位置的数
}

func buildMaxHeap(nums []int, n int) { // 建一个大堆
    for i := (n-2)/2; i >= 0; i-- { // 不需要遍历叶子节点(如果不明白就画个图)
        AdjustDown(nums, n, i)
    }
}

func AdjustDown(nums []int, n, parent int) { // 向下调整操作
    child := parent*2+1 // (左孩子)子节点 = 父节点 * 2 + 1, 右孩子是 * 2 + 2
    for child < n { // 子节点需要在堆(数组)的范围内
        if (child+1) < n && nums[child+1] > nums[child] { // 比较左右孩子大小
            child++ // 右孩子大, 那就往右孩子那边调整
        }
        if nums[child] > nums[parent] { // 如果子节点大于父节点, 就交换
            swap(&nums[child], &nums[parent]);
            parent = child // child 作为新的父节点
            child = parent*2+1 // 找下一个孩子
        } else {
            break // 这部分已经是大堆了
        }
    }
}

func swap(a, b *int) {
    *a, *b = *b, *a
}

之前因为一直没有总结，所以堆排我总是忘记怎么做，今天我就要把堆排拿下。

首先是建堆操作，比如说：[3,1,2,5,6,4] 这个数组建堆：

func buildMaxHeap(nums []int, n int) { // 建一个大堆
    for i := (n-2)/2; i >= 0; i-- { // 不需要遍历叶子节点(如果不明白就画个图)
        AdjustDown(nums, n, i)
    }
}

建堆操作的代码，i 不需要从叶子节点开始，为什么 -2，就是为了让 i 能从 2 这个节点，也就是父节点开始遍历，不需要从叶子节点开始，(n-2)/2 无论是什么情况，都能从最右边的第一个父节点开始。

然后通过向下调整操作，也就这段代码：

func AdjustDown(nums []int, n, parent int) { // 向下调整操作
    child := parent*2+1 // (左孩子)子节点 = 父节点 * 2 + 1, 右孩子是 * 2 + 2
    for child < n { // 子节点需要在堆(数组)的范围内
        if (child+1) < n && nums[child+1] > nums[child] { // 比较左右孩子大小
            child++ // 右孩子大, 那就往右孩子那边调整
        }
        if nums[child] > nums[parent] { // 如果子节点大于父节点, 就交换
            swap(&nums[child], &nums[parent]);
            parent = child // child 作为新的父节点
            child = parent*2+1 // 找下一个孩子
        } else {
            break // 这部分已经是大堆了
        }
    }
}

就能建出一个大堆：

最后再用堆排序操作，把数组排成一个升序：

func findKthLargest(nums []int, k int) int {
    n := len(nums)
    buildMaxHeap(nums, n) // 建堆操作, 我们需要一大堆来执行堆排
    for end := n-1; end > 0; end-- { // 排序成升序数组(堆排)
        swap(&nums[end], &nums[0]); // 头尾交换
        AdjustDown(nums, end, 0) // 向下调整(向下调整的左右子树必须是大堆)
    }
    return nums[n-k] // 返回倒数第 k 位置的数
}

因为是一个大堆，所以进行向下调整操作的时候就能够将堆中最大的数调整到堆顶，然后将堆顶(也就是最大的数放到数组尾，让 end–，也就是让堆的 size–，这样向下调整的时候就调整不到放在数组尾的数了)，以此类推，就能将数组排序成升序数组。

5. K 个一组翻转链表

题目链接：25. K 个一组翻转链表

题目描述

代码与解题思路

/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
func reverseKGroup(head *ListNode, k int) *ListNode {
    phead := &ListNode{Next: head}
    pre, end := phead, phead
    for end.Next != nil {
        for i := 0; i < k && end != nil; i++ { // 一段反转区间的尾部
            end = end.Next
        }
        if end == nil { // 最后这段区间不完整, 不用再遍历了
            break
        }
        start, next := pre.Next, end.Next
        end.Next = nil
        pre.Next = reverse(start) // 前面让 end.Next = nil, 再用反转就能反转这段区间
        start.Next = next // next 保存了下一段区间的第一个节点
        pre = start
        end = pre // pre 和 end 再次回到类似哨兵位的位置
    }
    return phead.Next
}

func reverse(head *ListNode) *ListNode { // 反转链表(一模一样的代码)
    var pre *ListNode = nil
    var cur *ListNode = head
    for cur != nil {
        next := cur.Next
        cur.Next = pre
        pre = cur
        cur = next
    }
    return pre
}

代码的注释非常的详细，具体的思路就是通过 end 找到需要反转的区间尾，用 next 记录下一个区间，然后反转当前锁定的区间，然后接通反转后的区间和未处理的区间，以此类推。

这道题主要就是考察对操作链表代码的掌控能力。

6. 三数之和

题目链接：15. 三数之和

题目描述

代码与解题思路

func threeSum(nums []int) (ans [][]int) {
    n := len(nums)
    sort.Ints(nums)
    for i, v := range nums[:n-2] {
        if i != 0 && nums[i-1] == v { // 去重操作
            continue
        }
        if v+nums[i+1]+nums[i+2] > 0 { // 两个优化操作
            break
        }
        if v+nums[n-1]+nums[n-2] < 0 {
            continue
        }
        left, right := i+1, n-1
        for left < right { // 双指针匹配
            s := v+nums[left]+nums[right]
            if s < 0 {
                left++
            } else if s > 0 {
                right--
            } else {
                ans = append(ans, []int{v, nums[left], nums[right]})
                for left < right && nums[left] == nums[left+1] { // 两段去重操作
                    left++
                }
                for left < right && nums[right] == nums[right-1] {
                    right--
                }
                left++
                right--
            }
        }
    }
    return ans
}

需要注意的点：

三段去重的逻辑
两段优化的逻辑

下次写三数之和的时候，先把主体代码写完，能跑过了再去把两段可以优化的点给做优化。

7. 最大子数组和

题目链接：53. 最大子数组和

题目描述

代码与解题思路

func maxSubArray(nums []int) (ans int) {
    ans = -10000
    dp := make([]int, len(nums)+1)
    for i := 1; i <= len(nums); i++ {
        dp[i] = max(nums[i-1], dp[i-1]+nums[i-1])
        ans = max(ans, dp[i])
    }
    return ans
}

这道题我一开始还想着是滑动窗口，其实不是啊，别给搞蒙了，这个是动态规划的题目，具体思路是这样的：

dp 数组存的是这样的：i 位置存的数是 i 位置以及前面位置的最大和，这样我们就能通过 dp[i] = max(nums[i-1], dp[i-1]+nums[i-1]) 也就是通过上一位置取得的最大和来计算当前位置的最大和，利用之前位置算出的值，这就是动态规划的思想

8. 手撕快排

题目链接：912. 排序数组

这道题是个补充题，就是来考手撕快排的。

题目描述

代码与解题思路

func sortArray(nums []int) []int {
    quickSort(0, len(nums)-1, nums)
    return nums
}

func quickSort(left, right int, nums []int) {
    if left > right {
        return
    }
    v := getmid(left, right, nums)
    swap(&nums[v], &nums[left])
    key, pre, cur := left, left, left+1
    for cur <= right { // 这里注意一下, 用的是 right 做边界
        if nums[cur] < nums[key] {
            pre++
            swap(&nums[pre], &nums[cur])
        }
        cur++
    }
    swap(&nums[pre], &nums[key])
    key = pre
    quickSort(left, key-1, nums)
    quickSort(key+1, right, nums)
}

func getmid(left, right int, num []int) int { // 三数取中
    mid := (left+right)/2
    if num[mid] > num[left] {
        if num[right] > num[mid] {
            return mid
        } else if num[right] < num[left] {
            return left
        } else {
            return right
        }
    } else {
        if num[right] > num[left] {
            return left
        } else if num[right] < num[mid] {
            return mid
        } else {
            return right
        }
    }
    return -1
}

func swap(a, b *int) {
    *a, *b = *b, *a
}

没什么可说的，多练习便是，多手撕几次，自然就记住了（还记得我当年的爱好就是没事手撕个快排呢）

9. 两数之和

题目链接：1. 两数之和

题目描述

代码与解题思路

func twoSum(nums []int, target int) []int {
    mp := map[int]int{}
    for i, v := range nums {
        if j, ok := mp[target-v]; ok { // 哈希表中有值 = target-v
            return []int{i, j}
        }
        mp[v] = i
    }
    return nil
}

两种解法，暴力 N 方，哈希 O(N)，把哈希的解法记住就行。

10. 最长回文子串

题目链接：5. 最长回文子串

题目描述

代码与解题思路

func longestPalindrome(s string) string {
    if s == "" {
        return ""
    }
    start, end := 0, 0 // 最长的回文串区间
    for i, _ := range s {
        l1, r1 := extend(i, i, s)   // "aba"
        l2, r2 := extend(i, i+1, s) // "bb"
        if r1-l1 > end-start {
            start, end = l1, r1
        }
        if r2-l2 > end-start {
            start, end = l2, r2
        }
    }
    return s[start:end+1]
}

func extend(l, r int, s string) (int, int) { // 中心扩散
    for l >= 0 && r < len(s) && s[l] == s[r] {
        l--
        r++
    }
    return l+1, r-1
}