第1周 数组、链表、跳表
2021-11-20
3分钟阅读时长
题目数量：16
第三课|数组、链表、跳表
1. 数组、链表、跳表的基本实现和特性
参考链接
[Linked List 示例代码](http://www.cs.cmu.edu/~adamchik/15-121/lectures/Linked Lists/code/LinkedList.java)
LRU Cache - Linked list： LRU 缓存机制
Redis - Skip List：跳跃表 、为啥 Redis 使用跳表（Skip List）而不是使用 Red-Black？
2. 实战题目解析：移动零
3. 实战题目解析：盛水最多的容器、爬楼梯
Array 实战题目
// 双指针
// 双指针
- 15. 三数之和 (高频老题）
// 排序 + 双指针
4. 实战题目解析：3数之和、环形链表
两数之和题目： https://leetcode-cn.com/problems/two-sum/
Linked List 实战题目
使用递归函数，一直递归到链表的最后一个结点，该结点就是反转后的头结点，记作 ret .
此后，每次函数在返回的过程中，让当前结点的下一个结点的 next 指针指向当前节点。
同时让当前结点的 next 指针指向 NULL ，从而实现从链表尾部开始的局部反转
当递归函数全部出栈后，链表反转完成。
// 原地反转
// 头插法
// 递归
// 快慢指针
// 快慢指针
- 25. K 个一组翻转链表 困难 重点
课后作业
func removeDuplicates(nums []int) int {
n := len(nums)
if n == 0 {
return 0
}
slow := 1
for fast := 1; fast < n; fast++ {
if nums[fast] != nums[fast-1] {
nums[slow] = nums[fast]
slow++
}
}
return slow
}
- 189. 旋转数组 中等 重点
// 方法一：使用新数组直接放到对应位置
func rotate(nums []int, k int) {
n := len(nums)
newNums := make([]int, n)
for i := 0; i < n; i++ {
newNums[(i + k) % n] = nums[i]
}
copy(nums, newNums)
}
// 方法二：1 环状替换
func rotate(nums []int, k int) {
n := len(nums)
k %= n
for start, count := 0, gcd(k, n); start < count; start++ {
pre, cur := nums[start], start
for ok := true; ok; ok = cur != start {
next := (cur + k) % n
nums[next], pre, cur = pre, nums[next], next
}
}
}
func gcd(a, b int) int {
for a != 0 {
a, b = b%a, a
}
return b
}
// 方法二：2 环状替换
func rotate(nums []int, k int) {
n := len(nums)
k %= n
for start, count := 0, 0; count < n; start++ {
pre, cur := nums[start], start
for ok := true; ok; ok = start != cur {
next := (cur + k) % n
pre, cur, nums[next] = nums[next], next, pre
count++
}
}
}
// 方法三：数组翻转
func reverse(a []int) {
for i, n := 0, len(a); i < n/2; i++ {
a[i], a[n-1-i] = a[n-1-i], a[i]
}
}
func rotate(nums []int, k int) {
k %= len(nums)
reverse(nums)
reverse(nums[:k])
reverse(nums[k:])
}
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
*/
func mergeTwoLists(l1 *ListNode, l2 *ListNode) *ListNode {
}
//方法一：直接合并后排序
func merge(nums1 []int, m int, nums2 []int, _ int) {
copy(nums1[m:], nums2)
sort.Ints(nums1)
}
// 双指针
func merge(nums1 []int, m int, nums2 []int, n int) {
last := m + n - 1
m, n = m - 1, n - 1
for m >= 0 && n >=0 {
if nums1[m] < nums2[n] {
nums1[last], n, last = nums2[n], n - 1, last - 1
} else {
nums1[last], m, last = nums1[m], m - 1, last - 1
}
}
for n >= 0 {
nums1[last], last, n = nums2[n], last - 1, n - 1
}
}
// 暴力两层循环
// 哈希表
func twoSum(nums []int, target int) []int {
ht := map[int]int{}
for i, n := range nums {
m := target - n
if j, ok := ht[m]; ok {
return []int{j, i}
}
ht[n] = i
}
return nil
}
func moveZeroes(nums []int) {
for left,right := 0, 0; right < len(nums); right++ {
if nums[right] != 0 {
nums[left], nums[right] = nums[right], nums[left]
left++
}
}
}
func plusOne(digits []int) []int {
for i := len(digits) -1 ; i >= 0; i-- {
digits[i] = (digits[i] + 1) % 10
if digits[i] != 0 {
return digits
}
}
digits = make([]int, len(digits) + 1)
digits[0] = 1
return digits
}
本周作业及下周预习
本周作业同上课后作业相同
下周预习
预习知识点
- 栈：如何实现浏览器的前进和后退功能？
- 队列：队列在线程池等有限资源池中的应用
- 散列表（上）：Word 文档中的单词拼写检查功能是如何实现的？
- 散列表（中）：如何打造一个工业级水平的散列表？
- 散列表（下）：为什么散列表和链表经常会一起使用？
- 哈希算法（上）：如何防止数据库中的用户信息被脱库？
- 哈希算法（下）：哈希算法在分布式系统中有哪些应用？