刷题坑
00 杂项
00.01 待刷备份 LintCode LeetCode
[[算法笔记]]
待刷:
①初期，刷入门核心题
这是针对毫无经验的刷题选手的策略。如果已经有一定刷题心得，可以跳过这步。
首先要给自己建立信心，我的策略是先把最基础的入门题刷个30道左右，熟悉coding的过程，找到刷题的感觉。
这些是我筛选过的还不错的入门题，我愿称之为——菜菜子必备的编程20题：
1.整数排序
2.反转一个3位整数
3.三数之中的最大值
4.从不充值的玩家
5.寻找素数
6.寻找最大值
7.链表节点计数
8.矩阵面积
9.打印X
10.分数超过组长的组员
11.硬币翻面
12.张三的故事
13.寻找特定的患者
14.挂科最多的同学
15.查询用户邮箱
16.增长的疫情感染人数
17.公租房信息查询
18.查找重名的同学
19.超过3名球员所得到的分数
20.推荐学理科的同学
②中期，按知识点tag刷题
接下来就要真正的掌握算法和数据结构知识点。
我的策略是逮着一个知识点使劲刷，刷到掌握了为止（不限题数）。
但如果刷了30题以上还是不得其法，可以先放一放，不要给自己造成心理负担。
最让人头疼的动态规划，可以循序渐进的刷这10道题：
1.栅栏染色
2.爬楼梯
3.约翰的后花园
4.单词拆分
5.书籍复印
6.解码方法
7.通配符匹配
8.旅行商问题
9.青蛙跳
10.骰子求和
双指针算法，高频算法之王，变形比较多。想掌握的话，刷这些题：
1.颜色分类
3.排颜色
4.最长子串覆盖
5.有效回文
6.带环链表
7.交错正负数
8.最接近的三数之和
9.四数之和
10.接雨水
宽度优先搜索，考察频率高，但实现不难，刷这7道题：
1.岛屿的个数
2.序列重构
3.拓扑排序
4.课程表
6.安排课程
7.最大子数组差
深度优先搜索，考察频率高，主要是考察递归会不会写。
1.子集
2.图是否是树
3.子数组之和
5.K数和
6.因式分解
分治法，考察频率中等，一般和二叉树一起出现和考察，题一般不难。
1.子集
2.数组划分
3.验证二叉查找树
4.全排列
5.克隆图
6.排颜色
7.子数组之和
哈希表，原理和应用都需要掌握，而且需要掌握代码实现。
1.两数之和
2.最长回文串
3.两数组的交集
堆，经常会用到，原理必须掌握。高频。
1.丑数
2.堆化
3.滑动窗口的中位数
4.大楼轮廓
5.超级丑数
6.食物集合
7.影际网络
贪心，考得不多，但起码要会用。
1.会议室
2.俄罗斯套娃信封
3.最大乘积
4.加油站
5.最大子数组差
链表，中小公司考得多，大公司近年来考得少。题目一般不难，主要考察Reference。
1.合并k个排序链表
3.带环链表
4.旋转链表
5.两个链表的交叉
6.K组翻转链表
线段树，不太考。但当有的题目存在多种解法的时候，线段树可以帮忙降低思考难度。
1.线段树的构造
2.线段树的查询
3.区间求和
4.区间最小数
5.我的日历
6.排序方案
7.构造队列
8.矩形面积
③面试前，按公司ladder刷题
在准备面试前，我建议直接刷目标公司的高频题。熟悉这些公司的常考题、出题风格，会比漫无目的地乱刷效率高很多。
阿里巴巴：
字节跳动：
腾讯：
百度：
美团：
Microsoft
Amazon
领英
Apple
00.02 求中点
-
int mid = left + ((right-left) >> 1); //(L+R)/2 //防止溢出 a>>1 相当于a/2 使用位运算 速度更快
00.03 函数返回新建数组
return new int[] {less+1 ,more-1};
00.04 打印数组
System.out.println(Arrays.toString(nums)); //打印结果为[1,2,3,4,]
00.05 int[]与Integer[]互转
import java.util.stream.IntStream;
import java.util.stream.Stream;
// int[]nums 转化为Integer[] 数组
Integer[] integers = Arrays.stream(nums).boxed().toArray(Integer[]::new);
//转化为int[] 数组
int[] nums = Arrays.stream(integers).mapToInt(Integer::valueOf).toArray();
// 解释
//将int数组转换为Integer数组
int[] nums = {1,2,3};
//先将int数组转换为数值流
IntStream stream = Arrays.stream(nums);
//流中的元素全部装箱，转换为流 ---->int转为Integer
Stream<Integer> integerStream = stream.boxed();
//将流转换为数组
Integer[] integers = integerStream.toArray(Integer[]::new);
00.06 int[] 与 ListNode转换
public class ListNode{
int val;
ListNode next=null;
ListNode(int val) {
this.val=val;
}
}
// 将Integer[] nums转为ListNode
public static ListNode arrayToListNode(Integer[] nums) {
ListNode head= new ListNode(nums[0]);
ListNode oher = head; //暂存头节点 避免丢失
for(int i=1;i<nums.length;i++) {
ListNode temp = new ListNode(nums[i]); //借助中间temp实现
other.next=temp; //将other下一节点指向新生节点temp
other=temp; //将other后移 指向最后一个节点
}
return head; //找回头节点
}
//将ListNode转化为int[] nums
public static int[]
00.07 int[] nums中最小的k数—大根堆/partition
- 复杂度：O(NlogK) + O(K)
- 特别适合处理海量数据
维护一个大小为 K 的最小堆过程如下：使用大顶堆。在添加一个元素之后，如果大顶堆的大小大于 K，那么将大顶堆的堆顶元素去除，也就是将当前堆中值最大的元素去除，从而使得留在堆中的元素都比被去除的元素来得小。
应该使用大顶堆来维护最小堆，而不能直接创建一个小顶堆并设置一个大小，企图让小顶堆中的元素都是最小元素。
Java 的 PriorityQueue 实现了堆的能力，PriorityQueue 默认是小顶堆，可以在在初始化时使用 Lambda 表达式 (o1, o2) -> o2 - o1 来实现大顶堆。
lambda(o1,o2)->o2-o1 Comparator.reverseOrder()
public ArrayList<Integer> getLeastNumbers(int[] nums, int k) {
if(k>nums.length||k<1) {
return new ArrayList<>();
}
// 使用lambda表达式
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((o1,o2)->o2-o1);
// 使用Comparator
priorityQueue<Integer. maxHeap = new PriorityQueue<>(k,Comparator.reverseOrder());
for(int num :nums) {
if(maxHeap.size()<k) {
maxHeap.add(num);
}else{
if(maxHeap.peek()>e) {
maxHeap.poll();
maxHeap.add(num);
}
}
}
return new ArrayList<>(maxHeap);
}
00.08 assert 断言
IDEA中JVM设置自定义参数-ea后即可打开
assert [boolean//表达式]
只有当 表达式为真——>继续执行后续代码否则终止执行并抛出AssertionError
0.09 两链表长度差值
一个变量即可实现
int cnt = 0;
while (cur1!=null) {
cnt++; //遍历第一个链表时++
cur1=cur1.next;
}
while (cur2!=null) {
cnt--; //遍历第二个链表时--
cur2=cur2.next;
}
cnt = Math.abs(cnt); // 二链表长>一链表长时cnt<0
0.10 堆化
O(N)
PriorityQueue<Integer> minheap = new PriorityQueue<>(); // 默认最小堆 PriorityQueue<Integer> maxheap = new PriorityQueue<>(Collections.reverseOrder());// minheap.add();// peek() 查看堆顶元素// poll() 弹出堆顶元素并删除// size() 堆的大小
0.11 ArrayList 与 int[]转换
int[] res = integers.stream().mapToInt(Integer::intValue).toArray();// 使用 stream流 和 方法引用
List<Integer> lists = Arrays.stream(res).boxed().collect(Collectors.toList());// 装箱
0.12 统计出现的频率——>得到频率数组
Map<Integer, Integer> frequents = new HashMap<>();
for (int num:
nums) {
frequents.put(num,frequents.getOrDefault(num,0)+1)
}
// 将 Map 转换为 Set
Set<Map.Entry<Integer,Integer>> entries = frequents.entrySet();
0.13 最短子串
找到 minwindow 的 len 同时记住起始的left 即可
使用 substring(left,left+resLen)
01 排序
-
**排序的稳定性: **
意义: 保留业务数据中的原始信息 不被抹去(两次排序中第二次排序可以保留第一次排序后结果)
- 在原序列中相同值的原始相对次序位置不变
- 冒泡、插入(数据量小60的时候均适用、因为常数项低 )、归并、桶排序、计数排序、基数排序
- 快排不稳定——>partition随机选择分割
- 堆排不稳定——>
-
工程中综合排序:
- 基本数据类型——>快排
- 自定义类——>归并
- 小样本——>插入
-
比较器的使用:
-
利用系统提供的Arrays.sort(nums, new comparator()) 实现排序 相当于c中的sort 的第二个参数实现
-
无comparator的实现默认按照nums的内存地址排序
// 继承Comparator<>接口 重写这个比较的Compare()函数 public static class AgeAscendingComparator implements Comparator<Student> { @Override public int compare(Student o1, Student o2) { return o1.age - o2.age; } } Arrays.sort(students, new IdAscendingComparator()); // 无返回值 -
利用系统的 **优先级队列PriorityQueue<>**实现堆排序 **add() poll()**方法分别实现建堆和弹出堆头
-
利用系统的 **TreeSetp<> **实现红黑树
-
常见基于比较的排序方法性能汇总表
| 排序方法 | 时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|
| 选择 | N2 | 1 | no |
| 冒泡 | N2 | 1 | yes |
| 插入 | N2 | 1 | yes |
| 归并 | N*logN | N | yes |
| 快排 | N*logN | logN | no |
| 堆 | N*logN | 1 | no |
常见注意事项：
- “原定归并排序”会让时间复杂度上升到 N2 不实用；
- 工程上在小数量样本下，使用插入排序进行综合排序利用 NLogN和 N2的优势；
快排的常数项实践下来最快
01.01 快排
思想: 荷兰国旗问题——>在左右区间内再次荷兰国旗划分
public static int[] partition(int[] arr, int l, int r, int p) { int less = l - 1; //小于p的区域的下标最大值边界 int more = r + 1; //大于p的区域下标最小值边界 while (l < more) { if (arr[l] < p) { swap(arr, ++less, l++); } else if (arr[l] > p) { swap(arr, --more, l); } else { l++; } } return new int[] { less + 1, more - 1 }; //返回等于区域的数组下标范围}public static int[] swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr;}
-
经典快排
-
以数组最后一个数作为基准 重复荷兰国旗划分
public static void quickSort(int[] arr) { if (arr == null || arr.length < 2) { return; } quickSort(arr, 0, arr.length - 1);}public static void quickSort(int[] arr, int l, int r) { if (l < r) { swap(arr, l + (int) (Math.random() * (r - l + 1)), r); int[] p = partition(arr, l, r); //经典快排的改进——>对于等于选择基点的区域不参与递归排序 quickSort(arr, l, p[0] - 1); quickSort(arr, p[1] + 1, r); }}public static int[] partition(int[] arr, int l, int r) { int less = l - 1; int more = r; while (l < more) { if (arr[l] < arr[r]) { swap(arr, ++less, l++); } else if (arr[l] > arr[r]) { swap(arr, --more, l); } else { l++; } } swap(arr, more, r); return new int[] { less + 1, more };}public static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp;} -
问题: 大于和小于基准的区域大小不相等(总拿数组最后一个数作为基准 最坏情况下会是O(N^2)) 与数据状态息息相关
-
-
随机快排: 使得概率事件 使用长期期望方式算出时间复杂度 O(N*logN) 随机快排的空间复杂度O(logN)
-
swap(arr, L + (int) (Math.random()*(R - L + 1)), R);// L-R上等概率的随机选择一个数将其与最后一个数交换 使得函数结构上复用 //hash也可以
-
01.02 堆排序
-
完全二叉树: 依次在下一层按照顺序从左到右补齐
-
堆可以用数组来实现 又称为优先级队列
- 数组与完全二叉树之间的转换:
- 数组中位置i的左孩子的下标为
2*i+1右孩子为2*i+2父节点的对应下标为(i-1)/20的父节点为0
-
堆的理解: 完全二叉树
-
大根堆——>完全二叉树中任何一个子树的最大值都是头部
-
建立: 遍历数组, 与其父节点比较直至到根节点, 过程中自己比父节点的值大则swap 若小/等则跳出向上比较的循环 与现有的树高度有关h O(logN)
建立过程中的复杂度：
-
调整: 下沉 heapify() 不断与孩子中的最大值比较
-
public static void heapify(int[] arr, int index, int size) { int left = index * 2 + 1; while (left < size) { //这里是右孩子存在&&右孩子大于左孩子的值情况下选择left+1 否则都是left int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left; // 比较与我待查本身的值 largest = arr[largest] > arr[index] ? largest : index; if (largest == index) { break; } swap(arr, largest, index); // while循环继续的增量条件 index = largest; left = index * 2 + 1; } }
-
-
小根堆——>任何一个子树的最小值都是其头部
-
-
01.03 非基于比较的排序
一种数据状况出现的词频
桶排序
01.04 Bubble+InsertSort+SelectSort
-
BubbleSort-
逐个比较 最值上浮——>则外围循环为从右到左 使得j+1与j比较得到最值上浮
public static void BubbleSort(int[] nums) { if (nums == null || nums.length < 2) { return; } for (int i = nums.length - 1; i > 0; i--) { for (int j = 0; j < i; j++) { if (nums[j] > nums[j + 1]) { swap(nums, j, j + 1); } } }}
-
-
InsertSort-
的
public static void InsertionSort(int[] nums) { if (nums==null||nums.length<2) { return; } for (int i = 1; i < nums.length; i++) { for (int j = i-1; j >0; j--) { if (nums[j]>nums[j+1]) { swap(nums,j,j+1); } } }}
-
-
SelectionSort-
a
public static void SelectionSort(int[] nums) { if (nums == null || nums.length < 2) { return; } for (int i = 0; i < nums.length - 1; i++) { int minIndex = i; for (int j = i + 1; j < nums.length; j++) { minIndex = nums[j] < nums[minIndex] ? j : minIndex; } swap(nums, i, minIndex); }}
-
02 Stack Queue
02.01 队列实现栈结构
public static class TwoQueuesStack {
private Queue<Integer> queue;
private Queue<Integer> help;
public TwoQueuesStack() {
queue = new LinkedList<Integer>();
help = new LinkedList<Integer>();
}
public void push(int pushInt) {
queue.add(pushInt);
}
public int peek() {
if (queue.isEmpty()) {
throw new RuntimeExceptioan("Stack is empty!");
}
while (queue.size() != 1) {
help.add(queue.poll());
}
int res = queue.poll();
help.add(res);
swap();
return res;
}
public int pop() {
if (queue.isEmpty()) {
throw new RuntimeException("Stack is empty!");
}
while (queue.size() > 1) {
help.add(queue.poll());
}
int res = queue.poll();
swap();
return res;
}
private void swap() {
Queue<Integer> tmp = help;
help = queue;
queue = tmp;
}
}
02.02 栈实现队列结构
使用两个栈实现队列,支持队列的基本操作(add poll peek)
- stackPush向stackPop压入数据, 必须一次性将stackPush数据压入;
- stackPop非空, 不可压入数据
import java.util.Stack;
public class TwoStackWithQueue {
public Stack<Integer> stackPush;
public Stack<Integer> stackPop;
public TwoStackWithQueue(){
stackPop=new Stack<Integer>();
stackPush=new Stack<Integer>();
}
//push栈向pop栈倒入数据
private void pushTopop() {
if(stackPop.empty()) {
while (!stackPush.empty()) {
stackPop.push(stackPush.pop());
}
}
}
public void add(int pushInt) {
stackPush.push(pushInt);
pushTopop();
}
public int poll() {
if(stackPop.empty()&&stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushTopop();
return stackPop.pop();
}
public int peek() {
if(stackPop.empty()&&stackPush.empty()) {
throw new RuntimeException("Queue is empty!");
}
pushTopop();
return stackPop.peek();
}
}
03 链表
public class ListNode{
int val;
ListNode next = null;
ListNode(int val) {
this.val = val;
}
}
回文链表
- 快慢指针,当快指针到链尾即慢指针到链中。慢指针继续遍历的下一半链表不断入栈, 入完后弹出与前半比较;
- 不用辅助空间
访问 搜索 插入 删除
private ListNode reverseListNode (ListNode head) {
ListNode cur =head;
ListNode prev =null;
while (cur != null) {
ListNode next = cur.Next;
cur.Next=prev;
prev=cur;
cur=next;
}
return prev;
}
03.01 数组与链表的转化
ListNode listNode = new ListNode(Arrays.asList(arry));
03.02 链表环
-
找环思路
- 快慢分别走 直到两只相遇
- 其中快指针回到头结点 以正常步伐+1 与慢指针同步走 直到两者相遇
- 相遇结点即为头结点
-
**两表首个公共结点思路: **
- 先判断是否有环 Ring 成环必然在环处开始重合
- 无环则 长链表走两表长度差值 gap 步伐 再长短链表指针同步走直到相遇 相遇点为首公共结点
03.03 两表长度差值—一个变量
一个变量即可实现
int cnt = 0;
while (cur1!=null) {
cnt++; //遍历第一个链表时++
cur1=cur1.next;
}
while (cur2!=null) {
cnt--; //遍历第二个链表时--
cur2=cur2.next;
}
cnt = Math.abs(cnt); // 二链表长>一链表长时cnt<0
04 二叉树
public static class TreeNode { public int val; public TreeNode left; public TreeNode right; public TreeNode(int val) { this.val = val; }}
04.01 递归遍历二叉树
三者访问访问二叉树的次序一致, 只是不同时机输出
// 先序递归遍历二叉树public static void preOrderRecur(TreeNode head) { if(head == null) { return; } System.out.print(head.val+" "); preOrderRecur(head.left); preOrderRecur(head.right);}// 中序递归遍历二叉树public static void preOrderRecur(TreeNode head) { if(head == null) { return; } preOrderRecur(head.left); System.out.print(head.val+" "); preOrderRecur(head.right);}// 后序递归遍历二叉树public static void preOrderRecur(TreeNode head) { if(head == null) { return; } preOrderRecur(head.left); preOrderRecur(head.right); System.out.print(head.val+" ");}// 三者访问访问二叉树的次序一致, 只是不同实际输出
04.02 非递归遍历二叉树
递归本质上就是栈 由于二叉树提供节点只能向下访问 无法返回 故而使用栈结构实现返回
public static List<Integer> inOrderTraversalBT(TreeNode root) { List<Integer> res = new ArrayList<>(); //空树则直接返回null的res if (root == null) { return res; } Stack<TreeNode> stack = new Stack<>(); // 保存root TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 向树的最左侧走 并不断压栈 while (cur != null) { stack.push(cur); cur = cur.left; } // 走完最左侧后弹栈顶 TreeNode node = stack.pop(); res.add(node.val); // 往上层的右边去再重复找最左侧 cur = node.right; } return res;}public static List<Integer> preOrderTraversalBT(TreeNode root) { List<Integer> res = new ArrayList<>(); //空树则直接返回null的res if (root == null) { return res; } Stack<TreeNode> stack = new Stack<>(); // 保存root TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 向树的最左侧走 并不断压栈入数组 while (cur != null) { res.add(cur.val); stack.push(cur); cur = cur.left; } // 走完最左侧后弹栈顶 无须入组 cur循环内已经入组 TreeNode node = stack.pop(); // 往上层的右边去 再重复找最左侧 cur = node.right; } return res;}public static List<Integer> postOrderTraversalBT(TreeNode root) { List<Integer> res = new ArrayList<>(); //空树则直接返回null的res if (root == null) { return res; } Stack<TreeNode> stack = new Stack<>(); // 保存root TreeNode cur = root; while (cur != null || !stack.isEmpty()) { // 向树的最右侧走 并不断压栈入数组 while (cur != null) { res.add(cur.val); stack.push(cur); cur = cur.right; // 使得reverse后正常左在前 } // 走完最右侧后弹栈顶 无须入组 cur循环内已经入组 TreeNode node = stack.pop(); // 往上层的左边去 再重复找最右侧 cur=node.left; } Collections.reverse(res); return res;}
后继节点: 二叉树的中序遍历中的下一节点
前驱节点: 二叉树的中序遍历的前一节点
04.03 查找后继节点
- 通过parent找到根节点 再中序遍历
04.04 平衡二叉树
树中的任何一个节点其左右子树高度差在1以内
满二叉树一定是平衡二叉树
空树是平衡树
04.04 搜索二叉树 BST
二叉树中序遍历的结果是依次升序的 一般无重复节点
LC-99-recoverTree
两结点被错误交换 还原
// 非常妙的两个if 使得中序遍历的pre和node在不断比较大小找出错误的位置if (firstNode == null && preNode.val > node.val) { firstNode = preNode;}if (firstNode != null && preNode.val > node.val) { secondNode = node;}
第一个节点，是第一个按照中序遍历时候前一个节点大于后一个节点，我们选取前一个节点，这里指节点 ；
第二个节点，是在第一个节点找到之后，后面出现前一个节点大于后一个节点，我们选择后一个节点，这里指节点 ；
04.05 完全二叉树
判断标准二叉树按层遍历:
该节点有左孩子无右孩子; false
该节点有左孩子没有右孩子/两者都没有: 后面遇到的节点均为叶节点;
求完全二叉树节点个数:
满二叉树: 高度l 则节点个数2^l-1
找出
04.06 重建二叉树
package Tree;import DataStructure.TreeNode;import java.util.Arrays;import static Tree._100_SameTree.isSameTree;public class _105_BuildTree { /* * 从前序和后序遍历结果构造二叉树 * */ public static void main(String[] args) { TreeNode root = new TreeNode(1); root.left = new TreeNode(2); root.right = new TreeNode(3); root.left.left = new TreeNode(4); root.left.right = new TreeNode(5); root.right.right = new TreeNode(7); root.right.left = new TreeNode(6); root.left.left.left = new TreeNode(8); root.left.left.right = new TreeNode(9); int[] preorder = {1, 2, 4, 8, 9, 5, 3, 6, 7}; int[] inorder = {8, 4, 9, 2, 5, 1, 6, 3, 7}; TreeNode root2 = buildTree(preorder, inorder); System.out.println(isSameTree(root2, root)); } public static TreeNode buildTree(int[] preorder, int[] inorder) { if (preorder.length == 0) { return null; } assert (preorder.length == inorder.length); TreeNode root = new TreeNode(preorder[0]); for (int i = 0; i < preorder.length; i++) { // 找到root在中序遍历数组中的位置 if (preorder[0] == inorder[i]) { /*将前 中序遍历数组各分为两半*/ int[] preLeft = Arrays.copyOfRange(preorder, 1, i + 1); int[] preRight = Arrays.copyOfRange(preorder, i + 1, preorder.length); int[] inLeft = Arrays.copyOfRange(inorder, 0, i); int[] inRight = Arrays.copyOfRange(inorder, i + 1, inorder.length); // 递归处理左右两部分 root.left = buildTree(preLeft, inLeft); root.right = buildTree(preRight, inRight); break; } } return root; }}
public static TreeNode buildTree(int[] inorder, int[] postorder) { if (inorder == null || postorder == null) { return null; } return helper(inorder, postorder);}private static TreeNode helper(int[] in, int[] post) { if (in.length == 0) { return null; } //根据后序数组的最后一个元素，创建根节点 TreeNode root = new TreeNode(post[post.length - 1]); //在中序数组中查找值等于【后序数组最后一个元素】的下标 for (int i = 0; i < in.length; ++i) { if (in[i] == post[post.length - 1]) { //确定这个下标i后，将中序数组分成两部分，后序数组分成两部分 int[] inLeft = Arrays.copyOfRange(in, 0, i); int[] inRight = Arrays.copyOfRange(in, i + 1, in.length); int[] postLeft = Arrays.copyOfRange(post, 0, i); int[] postRight = Arrays.copyOfRange(post, i, post.length - 1); //递归处理中序数组左边，后序数组左边 root.left = helper(inLeft, postLeft); //递归处理中序数组右边，后序数组右边 root.right = helper(inRight, postRight); break; } } return root;}
05 LFU & LFU算法
https://mp.weixin.qq.com/s?__biz=MzA4NDE4MzY2MA==&mid=2647524319&idx=1&sn=fdca85b7bb34d46e428a0d240f810811&chksm=87d1bcdcb0a635caecf466761bcd224846f9fa93711c0da35115bb25ea904ddfb4b172389a2f&mpshare=1&scene=1&srcid=0522hQRdOsdk14xOj8EYzGDY&sharer_sharetime=1621651227490&sharer_shareid=116ef760e9b961326f61bb96be400660#rd
概念
LFU 算法即为 Least Frequently Used Algorithm 最不常用算法，发生缺页中断时选择访问次数最少的页面中断
LRU 算法即为 Least Recently Usef Algorithm 最近常用算法，缺页中断时优先最久没有访问的页面
LRU 考察多久未访问，时间越短越好；
LFU 考虑访问频率，访问次数越多越好
Question
请你为 最不经常使用（LFU）缓存算法设计并实现数据结构。
实现 LFUCache 类：
LFUCache(int capacity)- 用 LFU 的容量 capacity 初始化对象int get(int key)- 如果键存在于缓存中，则获取键的值并返回，否则返回 -1。void put(int key, int value)- 如果键已存在，则更新其值；如果键不存在，请插入键值对。当缓存达到其容量时，则应该在插入新页之前，淘汰最不经常使用的页。在此问题中，当存在平局（即两个或更多个键具有相同使用频率）时，应该去除 最近最久未使用 的键。注意「项的使用次数」就是自插入该项以来对其调用 get 和 put 函数的次数之和。使用次数会在对应项被移除后置为 0 。为了确定最不常使用的键，可以为缓存中的每个键维护一个 使用计数器 。使用计数最小的键是最久未使用的键。
当一个键首次插入到缓存中时，它的使用计数器被设置为 1 (由于 put 操作)。对缓存中的键执行 get 或 put 操作，使用计数器的值将会递增。
Solution
哈希算法+双向链表可以实现查找、插入删除均为 O(1)的数据结构
class Cache { private Map<Integer,Node> cache; public int get(int key) {} public void put(int key, int value) {} class DoublelinkedList {}}
06 表
06.01 概念
哈希表：
- 使用可被视为集合结构 不允许重复
- 只有
Key使用 HashSet，有Key & Value使用 HashMap 两者的底层结构实际一致 - 哈希表的增删改查可视为时间复杂度为
O(1)但常数时间较大 put remove put get - 基础类型存放内部按值传递——>占用大小为其本身；其他按引用传递，内存占用为其本身内存地址大小
有序表：
- 集合结构
- TreeSet 和 TreeMap 结构表示，两者底层一致；有序（双向链表）
- 红黑树 AVL树 size-balance-tree 跳表均为有序表
07 堆
07.01 数据流问题
滑动窗口最大值
-
最大堆
-
时间复杂度是 O(N*log K)
-
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder()); int[] res = new int[nums.length - k + 1]; for (int i = 0; i < k; i++) { maxHeap.add(nums[i]); } res[0]= maxHeap.peek(); for (int i = 0,j=i+k;j<nums.length;j++,i++) { maxHeap.remove(nums[i]); maxHeap.add(nums[j]); res[i+1]= maxHeap.peek(); } return res;
-
-
单调队列——>Dqueue 双端队列 队首为最大值 队尾为数据流进入的入口 单向流动的队列
-
-
有效降低复杂度
-
Deque<Integer> queue = new ArrayDeque<>();
int index = 0;
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
// peekLast 从后面看的最后一个元素
while (!queue.isEmpty() && nums[i] > queue.peekLast()) {
// 弹出最后一个元素
queue.pollLast();
}
queue.addLast(nums[i]);
if (i>=k-1) {
res[index++] = queue.peekFirst();
if (i>=k-1&&nums[i-k+1]==queue.peekFirst()) {
queue.removeFirst();
}
}
}
return res;
中位数
大根堆存较小部分 小根堆存较大部分 小根堆长度尽量长
先入大根堆MaxHeap.add(num) 将大根堆的堆顶为较大部分 再讲较大部分入小根堆 MinHeao
minHeap.add(maxHeap.poll())
两堆的 size 相同则取 (minHeap.peek()+maxHeap.peek())/2.0
不等则取 minHeap.peek() (因为保证小根堆较长)
Queue<Integer> minHeap, maxHeap;
public void addNum(int num) {
minHeap = new PriorityQueue<>();
maxHeap = new PriorityQueue<Integer>(Comparator.reverseOrder());
if (minHeap.size() == maxHeap.size()) {
maxHeap.add(num); // 利用大根堆过滤出较大的部分maxHeap.poll() 再入小根堆minHeap
minHeap.add(maxHeap.poll());
} else {
minHeap.add(num);
maxHeap.add(minHeap.poll());
}
}
public double findMedian() {
// 两堆大小相等则取中值 不等为小根堆堆顶
return maxHeap.size() == minHeap.size() ? ((minHeap.peek() + maxHeap.peek()) / 2.0) : minHeap.peek();
}
08 单调栈
Monotonic Stack 栈中元素按照单调顺序排列 ——> 时间复杂度为线性 O(N) 每个元素遍历一次
08.01 模板
- 维持递增栈
- 放入最后结果
- 当前元素入栈
eg:
private static int[] nextGreaterElemenet(int[] nums) {
int[] res = new int[nums.length];
Stack<Integer> stack = new Stack<>();
for (int i = nums.length - 1; i >= 0; i--) {
// 维护单调栈的递增顺序 当要加入的值大于栈顶元素时 抛出栈顶丢弃 保证栈顶最小
while (!stack.isEmpty() && nums[i] >= stack.peek()) {
stack.pop();
}
// add the result to stack
res[i] = stack.isEmpty() ? -1 : stack.peek();
// action to come in stack
stack.push(nums[i]);
}
return res;
}
08.02 tips
-
最近最大的数——>单调栈的特征
-
循环数组——>
-
for (int i = 0; i < 2 * len; i++) { // 遍历值的下标为 i%len int num = nums[i % len]; while (!stack.isEmpty() && nums[stack.peek()] < num) { res[stack.pop()]=num; } if (i<len) { stack.push(i); } }
09 滑动窗口
连续元素 String subarray linkedlistst
min max longest shorte key word
本质上是two points 左边是 left 右边是 iterator(i)
09.01 模板
进——>出——>算
- 将当前遍历值入窗口
- 窗口条件不符合时候 left 持续退出
- 窗口有效 valid 情况下 计算结果
public int lengthofLongestSubstringTwoDistinct(String s, int k) {
HashMap<Character, Integer> map = new HashMap<>();
int left = 0, res = 0;
for (int i = 0; i < s.length(); i++) {
char cur = s.charAt(i);
// 遍历值入窗口
map.put(cur, map.getOrDefault(cur, 0) + 1);
// 窗口不符合条件 left 持续退出
while (map.size() > k) {
char c = s.charAt(left);
map.put(c, map.get(c) - 1);
if (map.get(c) == 0) {
map.remove(c);
}
// size超过窗口大小即left 左移
left++;
}
// 计算子串最值
res = Math.max(res, i - left + 1);
}
return res;
}
Tips
01 位移运算
-
左移 扩大
-
1>>4即1 * 2 * 2 * 2 * 2 = 16 左移 4 位即pow（2,4） -
Java提供的位运算符有：左移(
<<)、右移(>>) 、无符号右移(>>>) 、位与(&) 、位或(|)、位非(~)、位异或(^)，除了位非(~)是一元操作符外，其它的都是二元操作符。1. 左移( << )
a << b 表示将数值 a 的二进制数值从 0 位算起到第 b - 1 位，整体向左方向移动 b 位，符号位不变，低位空出来的位补数值 0。
a << b = a * (2 ^ b)2. 右移( >> )
a >> b 表示将数值 a 的二进制数值从 0 位算起到第 b - 1 位，整体向右方向移动 b 位，符号位不变，高位空出来的位补数值 0。
a >> b = a / ( 2 ^ b )3. 无符号右移( >>> )
无符号右移运算符>>>和右移运算符>>是一样的，只不过右移时左边是补上符号位，而无符号右移运算符是补上0，也就是说，对于正数移位来说等同于：>>，负数通过此移位运算符能移位成正数。
4. 位与( & )
与运算时，进行运算的两个数，从最低位到最高位，一一对应。如果某 bit 的两个数值对应的值都是 1，则结果值相应的 bit 就是 1，否则为 0.
0 & 0 = 0, 0 & 1 = 0, 1 & 1 = 15. 位或( | )
与运算时，进行运算的两个数，从最低位到最高位，一一对应。如果某 bit 的两个数值对应的值只要 1 个为 1，则结果值相应的 bit 就是 1，否则为 0。
0 | 0 = 0,0 | 1 = 1,1 | 1 = 16. 位异或( ^ )
两个操作数进行异或时，对于同一位上，如果数值相同则为 0，数值不同则为 1。
1 ^ 0 = 1,1 ^ 1 = 0,0 ^ 0 = 0;7. 位非( ~ )
对操作数的每一位进行操作，1 变成 0，0 变成 1。
-