【CodeTop】TOP 100 刷题 1

TOP】TOP 100 刷题 1"/>

【CodeTop】TOP 100 刷题 1

文章目录

• 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, 0for 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 = headfor cur != nil {tmp := cur.Nextcur.Next = prepre = curcur = 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  intlist      *list.ListkeyToNode 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 { // 书数量超过 capacitydelete(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);*/

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

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

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

代码中需要注意的点是：

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

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

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

题目描述

代码与解题思路

var num []intfunc findKthLargest(nums []int, k int) int {num = numsreturn 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+1for 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)/2if 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 + 2for 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 + 2for 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, pheadfor end.Next != nil {for i := 0; i < k && end != nil; i++ { // 一段反转区间的尾部end = end.Next}if end == nil { // 最后这段区间不完整, 不用再遍历了break}start, next := pre.Next, end.Nextend.Next = nilpre.Next = reverse(start) // 前面让 end.Next = nil, 再用反转就能反转这段区间start.Next = next // next 保存了下一段区间的第一个节点pre = startend = pre // pre 和 end 再次回到类似哨兵位的位置}return phead.Next
}func reverse(head *ListNode) *ListNode { // 反转链表(一模一样的代码)var pre *ListNode = nilvar cur *ListNode = headfor cur != nil {next := cur.Nextcur.Next = prepre = curcur = 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-1for 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
}

需要注意的点：

1. 三段去重的逻辑
2. 两段优化的逻辑

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

7. 最大子数组和

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

题目描述

代码与解题思路

func maxSubArray(nums []int) (ans int) {ans = -10000dp := 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+1for cur <= right { // 这里注意一下, 用的是 right 做边界if nums[cur] < nums[key] {pre++swap(&nums[pre], &nums[cur])}cur++}swap(&nums[pre], &nums[key])key = prequickSort(left, key-1, nums)quickSort(key+1, right, nums)
}func getmid(left, right int, num []int) int { // 三数取中mid := (left+right)/2if 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-vreturn []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
}

题解有动态规划，但是看不懂，用中心扩散就行了，把中心扩散的 go 版本代码记住，大概就没有什么问题。