一.图相关
1.图本质上可以认为是多叉树的延伸。面试笔试中很少出现图问题,就算有,也是简单的遍历问题,基本上可以完全照搬多叉树的遍历
1 //基本的N叉树节点
2 class TreeNode{
3 int val;
4 TreeNode[] children;
5 }
6 //图节点的逻辑结构
7 class Vertex{
8 int val;
9 Vertex[] neighbors;
10 }
2.图的逻辑结构的具体实现
(1)逻辑结构:由节点和边构成
(2)具体实现:邻接表,邻接矩阵(很少用Vertex类来实现)
邻接表:把每个节点n的邻居都存到一个列表里,然后把n和这个列表关联起来,这样就可以通过一个节点n找到它的所有相邻节点
邻接矩阵:是一个二维布尔数组matrix
3.分类:
有向图,无向图。无权图,加权图。
4.图的遍历
(1)多叉树的遍历(前序遍历,后序遍历)
1 //前序遍历
2 public void traverse(TreeNode root) {
3 if(root==null)
4 return;
5 res.add(root.val);
6 for(TreeNode node : root.children) {
7 traverse(node); //递归遍历每一个子树
8 }
9 }
N429多叉树的层序遍历:(多叉树比较特殊,根节点不在数组里面,但不影响,因为就是从根节点开始遍历的,根引用直接指向了根节点)
(2)图和多叉树的最大区别就是:图是可能包含环的,从某一节点开始遍历,可能又回到这个节点
所以,如果图包含环,遍历框架就需要一个visited数组进行辅助
二.设计数据结构
1.LFU
(1)LinkedHashMap,LinkedHashSet。使得链表拥有了随机访问的功能(数组具有随机访问的特点)
(2)LFU算法中可以自顶向下编程,把重要重复代码抽象出来
(3)HashMap.putIfAbsent(key,val)方法
(4)LFU的实现还是挺复杂的,得多看看
2.优先级队列
和单端队列的区别,无论怎样入队,出队的序列是有序的
3.设计循环队列
4.实现栈和队列
实现栈:
(1)开始时:topp=-1(2)入栈:arr[++top]=e(3)出栈:e=arr[top--](4)取栈顶:e=arr[top](5)栈空:top=-1(6)栈大小:size=top+1
***top指向栈顶元素
实现队列:(循环队列)
(1)开始时:front=rear=0(2)入队:rear=(rear+1)%len(3)出队:front=(front+1)%len(4)取队头:front,取队尾:(rear+len-1)%len
(5)队空:front=rear(6)队满:(rear+1)%len=front(7)队长:(rear-front+len)%len
***因为要区分队空和队满,要浪费一个存储单元
***front指向队头元素,rear指向队尾元素的下一个位置
三.数组
1.二分法
(1) 二分法前提条件:有序(单调)
(2)二分法要明白搜索区间的定义
搜索区间的定义决定了二分法的写法。写二分法,区间的定义一般为两种,左闭右闭即[left, right],或者左闭右开即[left, right)。
(3)二分法最常用的几个场景:寻找一个数,寻找左侧边界,寻找右侧边界。
(4)二分查找框架
(5)查找一个数的二分搜索(基本的二分搜索):left<=right