12 - 算法 II

[Linjiayu6]

参考地址

• [x] 1. 时间复杂度等 执行效率可评估
• [x] 2. 数组
• [x] 3. 从浏览器缓存淘汰策略和Vue的keep-alive学习LRU算法
• [ ] 4. 链表
• [ ] 5. 栈
• [x] 6. 哈希表
• [ ] 7. 🌲
• [ ] 8. 堆
• [ ] 9. topk

[Linjiayu6]

一. 数组

- [栈] push / pop
- [队列] unshift(增加) / shift(从头推出)
- [截取] (返回操作后的值, 原值不改变) arr.slice(start, end) eg:slice(1, 3) 只是 1, 2
- [增加] splice arr.splice(index, 0, va;1, val2, ....) 会改变原数组
- [删除] splice arr.splice(index, delnum) 从哪儿开始 删除几个
- [过滤] [19, 2, 5].filter(d => d > 10) 最后是[19]
- [过滤+是否包含]  [19, 2, 5].filter(d => [2, 3].includes(d))  最后是[2]

• [ ] leetcode88: 合并两个有序数组🔥🔥🔥🔥🔥 Lin.JY 题解 错在 num1的 界限判断

• [x] 字节&leetcode1：两数之和 字典(map/obj)

• [x] 腾讯&leetcode15：三数之和 🔥🔥🔥🔥🔥

• [x] 腾讯：数组扁平化、去重、排序 1 - flat(Infinity) 2 - toString()

• [x] 146：LRU 缓存机制 LRU 缓存机制 1 - map🔥 / obj map.has(key) / map.get(key) / map.set(key, value) / map.delete(key) / map.size map.keys() / map.values() => Array.from(map.keys()) keys和values是有顺序的

交集的一定都要用 filter + includes + splice + indexOf

• [x] 349. 两个数组的交集 需要去重

• [x] 350. 两个数组的交集 II 不能去重 1 - indexOf 2 - 去重 + filter + 'abc'.includes('a') => true 🔥 3 - 去重 + map🔥

• [x] 阿里: 编写一个函数计算多个数组的交集 1 - 去重 + reduce🔥 +filter + includes 2 - 去重 + for + filter + includes

[Linjiayu6]

2 - 链表

• [ ] 21. 合并两个有序链表 🔥🔥🔥🔥🔥 第 4 次 做出来 Lin.JY 题解 1 - 递归 🔥 2 - 迭代

• [x] 141. 环形链表 Lin.JY 题解 1 - map 2 - 快慢指针

• [x] 206. 反转链表 Lin.JY 题解 1 - 递归 2 - 迭代

• [x] 876. 链表的中间结点 🔥🔥🔥🔥🔥 Lin.JY 题解 1 - 快慢指针 总错 + 1 2 - 计算

• [x] 19. 删除链表的倒数第N个节点 🔥🔥🔥🔥🔥 多练 Lin.JY 题解 1 - 快慢指针 + 新增个头结点

• [x] 160. 相交链表 Lin.JY 题解 1 - map 2 - 标记方法 🔥🔥🔥🔥🔥

[Linjiayu6]

3 - 字符串

• [x] 151. 翻转字符串里的单词 1 - split / trim / join / filter 2 - 正则 s.trim().split(/\s+/).reverse().join(' ') 🔥🔥🔥🔥🔥

• [x] 14. 最长公共前缀 Lin.JY 题解 1 - 先把两两比较写出来, 再多次比较 只需要比较前缀即可

• [x] 判断字符串是不是回文 - 📚 07.06 快手考题 1 - 使用api 2 - 不使用api

• [x] 3. 无重复字符的最长子串 - 📚 07.25 作业帮考题 🔥🔥🔥🔥🔥

• [x] 415. 字符串相加 🔥🔥🔥🔥🔥 Lin.JY 题解 1 - 进位思考🤔 需要多练 不熟悉

[Linjiayu6]

4 - 栈

• [x] 155. 最小栈 Math.min(...this.stack) 数组里最小值

• [x] 20. 有效的括号 🔥🔥🔥🔥🔥 Lin.JY 题解 1- 栈匹配 多做 不熟练

• [x] 1047. 删除字符串中的所有相邻重复项 🔥🔥🔥🔥🔥 Lin.JY 题解 1- 利用栈 多做 不熟练 2- 硬计算 硬匹配

• [ ] 1209. 删除字符串中的所有相邻重复项 II

• [ ] 删除字符串中出现次数 >= 2 次的相邻字符

[Linjiayu6]

5 - 队列

• [x] 剑指 Offer 09. 用两个栈实现队列 🔥🔥🔥🔥🔥 stack1 只进 push, stack2 只负责pop, 但是需要将stack1 进来的值 移到stack2

• [ ] 239. 滑动窗口最大值

[Linjiayu6]

6 - 哈希表

• [x] 380. 常数时间插入、删除和获取随机元素 Lin.JY 题解 1 - set 集合处理 set.add(val) / set.has(val) / set.size / set.delete(val)

• [x] 剑指 Offer 50. 第一个只出现一次的字符 Lin.JY 题解 1 - map / for( [key, value] of map)

[Linjiayu6]

7 - 树🌲

DFS

https://github.com/Linjiayu6/LeetCode/issues/2 解题思路

• [x] 144. 二叉树的前序遍历

• [x] 94. 二叉树的中序遍历

• [x] 145. 二叉树的后序遍历

BFS

• [x] 102. 二叉树的层序遍历

• [x] 107. 二叉树的层次遍历 II Lin.JY 题解

进阶

• [x] 104. 二叉树的最大深度

• [x] 105. 从前序与中序遍历序列构造二叉树 需要多练

• [x] 106. 从中序与后序遍历序列构造二叉树 需要多练 写的磨叽

• [ ] 236. 二叉树的最近公共祖先

• [x] 110. 平衡二叉树 🔥🔥🔥🔥🔥 多练 先写个当前树的高度 再 左右子树对比 和 继续递归

• [x] 112. 路径总和 👧👧👧👧👧👧头条 慧林常问

• [x] 101. 对称二叉树 🔥🔥🔥🔥🔥 需要多练 两个结点的比较

• [ ] 字节一面：给定一个二叉树, 找到该树中两个指定节点间的最短距离

[Linjiayu6]

8 - 堆 🔥🔥🔥🔥🔥

• [x] 剑指 Offer 40. 最小的k个数 腾讯&字节 快排 + slice(0, k)

• [x] 347. 前 K 个高频元素 🔥🔥🔥🔥🔥 👧👧👧👧👧👧头条 慧林常问 Lin.JY 题解 多做

• [x] 215. 数组中的第K个最大元素 🔥🔥🔥🔥🔥 快排 堆排序

• [ ] 295. 数据流的中位数

[Linjiayu6]

9 - 图

• [ ] leetcode997：找到小镇的法官
• [ ] leetcode207：课程表问题
• [ ] 剑指Offer&Bigo：旋转矩阵

[Linjiayu6]

10 - 排序算法

• [x] 快速排序 🔥🔥🔥🔥🔥

• [ ] 384. 打乱数组 多做

• [ ] 希尔排序

• [ ] 排序链表 Lin.JY 题解 1 - 普通方法 2 - 归并 🔥🔥🔥🔥🔥

• [x] 扑克牌问题 1 - 多练 🔥🔥🔥🔥🔥 字节

• [x] 排序 Lin.JY 题解 归并排序

1. 快速: 中间位置的值 pivot, left 小于 pivot, right 大于 pivot (时间复杂度 最好 nlogn 最差 n^2 平均nlogn)
2. 归并: 大问题拆分 局部有序排序 最后 结合在一起 (时间复杂度 最好 nlogn 最差 nlogn 平均nlogn)
3. 冒泡: 从下往上 冒泡， 每次找的都是未排序的最大值 (时间复杂度 最好 n 最差 n^2 平均n^2)
4. 插入: 后面往前面插入 前面有序 (时间复杂度 最好 n 最差 n^2 平均n^2)
5. 桶: 先分组, 再排序 (先求数组的最大值和最小值，得知了分组的范围，需要确认分多少个桶，再针对桶内部进行排序)
6. 选择: 从第一个i 位置开始, j = i + 1, 往后面去找最小的，和i位置交换。每次选择最小的交换。 (时间复杂度 最好 n^2 最差 n^2 平均n^2)
7. shell
8. 堆

[Linjiayu6]

11 - 二分查找

• [ ] 腾讯：简述二分查找算法与时间复杂度，并实现一个二分查找算法

• [ ] 34. 在排序数组中查找元素的第一个和最后一个位置 🔥🔥🔥🔥🔥 Lin.JY 题解 多做

• [ ] 腾讯&leetcode230：二叉搜索树中第K小的元素

[Linjiayu6]

12 - 其他编程题

• [x] 数组 扁平 / 去重 / 排序 1- flat + set 2- toString + split + set + join

• [x] 模板渲染 1- 硬写 2- 正则 + replace 🔥🔥🔥🔥🔥

• [x] 阿里 手写 async/await 的实现 07.28 阿里一面考题 🔥🔥🔥🔥🔥 多练 generator 不能主动执行 co辅助 让其自动执行

• [x] indexOf实现 1- 迭代遍历

• [x] 拆解URL参数中queryString 📚 07.06 快手考题 1- 有hash值的情况 2 - 正则过滤 url.match(/(\w+)=(\w+)/g) => [aaa=123, b=123]
  Lin.JY 题解

• [ ] 输出结果改造 🔥🔥🔥🔥🔥 字节: 输出以下代码运行结果，为什么？如果希望每隔 1s 输出一个结果，应该如何改造？注意不可改动 square 方法 Lin.JY 题解

• [ ] [bind 手写]()

• [ ] [手写promise]()

• [ ] [手写promise.finally]() 📚 07.28 阿里一面考题

• [x] [串行异步 pipeline]() 📚 07.28 阿里一面考题 & 头条一面考题 🔥🔥🔥🔥🔥 Lin.JY 题解

[Linjiayu6]

13 - 动态规划

• [ ] 53. 最大子序和 📚 07.28 头条一面考题 Lin.JY 题解