12 - 算法 II

[Linjiayu6]

参考地址

• 1. 时间复杂度等 执行效率可评估
• 2. 数组
• 3. 从浏览器缓存淘汰策略和Vue的keep-alive学习LRU算法
• 4. 链表
• 5. 栈
• 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的 界限判断

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

• 腾讯&leetcode15：三数之和 🔥🔥🔥🔥🔥

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

• 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

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

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

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

[Linjiayu6]

2 - 链表

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

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

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

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

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

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

[Linjiayu6]

3 - 字符串

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

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

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

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

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

[Linjiayu6]

4 - 栈

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

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

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

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

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

[Linjiayu6]

5 - 队列

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

• 239. 滑动窗口最大值

[Linjiayu6]

6 - 哈希表

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

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

[Linjiayu6]

7 - 树🌲

DFS

Linjiayu6/LeetCode#2
解题思路

• 144. 二叉树的前序遍历

• 94. 二叉树的中序遍历

• 145. 二叉树的后序遍历

BFS

• 102. 二叉树的层序遍历

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

进阶

• 104. 二叉树的最大深度

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

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

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

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

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

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

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

[Linjiayu6]

8 - 堆 🔥🔥🔥🔥🔥

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

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

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

• 295. 数据流的中位数

[Linjiayu6]

9 - 图

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

[Linjiayu6]

10 - 排序算法

• 快速排序 🔥🔥🔥🔥🔥

• 384. 打乱数组
  多做

• 希尔排序

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

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

• 排序
  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 - 其他编程题

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

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

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

• indexOf实现
  1- 迭代遍历

• 拆解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 阿里一面考题

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

[Linjiayu6]

13 - 动态规划

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