共计 11387 个字符，预计需要花费 29 分钟才能阅读完成。
大家好，我是 bigsai。
最近不少小伙伴跟我交换刷题肿么刷，我给的倡议就是先剑指 offer 和力扣 hot100，在这些题中还有些重要水平和呈现频率是十分十分高的，明天给大家分享当今呈现频率最高的 10 道算法题，学到就是赚到。
0X01 翻转链表
力扣 206 和剑指 offer24 原题，题意为：
给你单链表的头节点 head，请你反转链表，并返回反转后的链表。
剖析：
翻转链表，本意是不创立新的链表节点而后在原链表上实现翻转，然而这个图有点会误导人的思维，其实更好的了解你能够看上面这幅图：
具体实现上两个思路，非递归和递归的实现形式，非递归的实现形式比较简单，利用一个 pre 节点记录前驱节点，向下枚举的时候扭转指针指向就能够，实现代码为：
class Solution {public ListNode reverseList(ListNode head) {if(head==null||head.next==null)// 如果节点为 NULL 或者单个节点间接返回
return head;
ListNode pre=head;// 前驱节点
ListNode cur=head.next;// 以后节点用来枚举
while (cur!=null)
{
ListNode next=cur.next;
// 扭转指向
cur.next=pre;
pre=cur;
cur=next;
}
head.next=null;// 将原先的 head 节点 next 置 null 避免最初成环
return pre;
}
}而递归的形式比拟奇妙，借助递归归来的过程奇妙扭转指针指向和返回值传递，代码尽管精简然而了解起来有肯定难度的，这里用一张图帮忙大家了解：
具体代码为：
class Solution {public ListNode reverseList(ListNode head) {if(head==null||head.next==null)// 如果最初一个节点不操作
return head;
ListNode node =reverseList(head.next);// 先递归 到最底层 而后返回
head.next.next=head;// 前面一个节点指向本人
head.next=null;// 本人原本指向的 next 置为 null
return node;// 返回最初一个节点(始终被递归传递)
}
}0X02 设计 LRU
对应力扣 146LRU 缓存机制, 题目要求为：
使用你所把握的数据结构，设计和实现一个 LRU 缓存机制。实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存
int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1。
void put(int key, int value) 如果关键字曾经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字 - 值」。当缓存容量达到下限时，它应该在写入新数据之前删除最久未应用的数据值，从而为新的数据值留出空间。
进阶：在 O(1) 工夫复杂度内实现这两种操作
详细分析：一次倒在 LRU 上的经验
LRU 的外围就是借助 哈希 + 双链表 ，哈希用于查问，双链表实现删除只晓得以后节点也能 O(1) 的复杂度删除，不过双链表须要思考的头尾指针非凡状况。
具体实现的代码为：
class LRUCache {
class Node {
int key;
int value;
Node pre;
Node next;
public Node() {}
public Node(int key,int value) {
this.key = key;
this.value=value;
}
}
class DoubleList{
private Node head;// 头节点
private Node tail;// 尾节点
private int length;
public DoubleList() {head = new Node(-1,-1);
tail = head;
length = 0;
}
void add(Node teamNode)// 默认尾节点插入
{
tail.next = teamNode;
teamNode.pre=tail;
tail = teamNode;
length++;
}
void deleteFirst(){if(head.next==null)
return;
if(head.next==tail)// 如果删除的那个刚好是 tail 留神啦 tail 指针后面挪动
tail=head;
head.next=head.next.next;
if(head.next!=null)
head.next.pre=head;
length--;
}
void deleteNode(Node team){
team.pre.next=team.next;
if(team.next!=null)
team.next.pre=team.pre;
if(team==tail)
tail=tail.pre;
team.pre=null;
team.next=null;
length--;
}
}
Map<Integer,Node> map=new HashMap<>();
DoubleList doubleList;// 存储程序
int maxSize;
LinkedList<Integer>list2=new LinkedList<>();
public LRUCache(int capacity) {doubleList=new DoubleList();
maxSize=capacity;
}
public int get(int key) {
int val;
if(!map.containsKey(key))
return -1;
val=map.get(key).value;
Node team=map.get(key);
doubleList.deleteNode(team);
doubleList.add(team);
return val;
}
public void put(int key, int value) {if(map.containsKey(key)){// 曾经有这个 key 不思考长短间接删除而后更新
Node deleteNode=map.get(key);
doubleList.deleteNode(deleteNode);
}
else if(doubleList.length==maxSize){// 不蕴含并且长度小于
Node first=doubleList.head.next;
map.remove(first.key);
doubleList.deleteFirst();}
Node node=new Node(key,value);
doubleList.add(node);
map.put(key,node);
}
}0X03 环形链表
对应力扣 141 和力扣 142，力扣 141 环形链表要求为：
给定一个链表，判断链表中是否有环，用 O(1)内存解决。
详细分析：环形链表找入口，真的太妙了
这个问题利用快慢双指针比拟高效，快指针 fast 每次走 2 步，slow 每次走 1 步，慢指针走 n 步到尾时候快指针走了 2n 步，而环的大小肯定小于等于 n 所以肯定会相遇，如果相遇那么阐明有环，如果不相遇 fast 先为 null 阐明无环。
具体代码为：
public class Solution {public boolean hasCycle(ListNode head) {
ListNode fast=head;
ListNode slow=fast;
while (fast!=null&&fast.next!=null) {
slow=slow.next;
fast=fast.next.next;
if(fast==slow)
return true;
}
return false;
}
}力扣 142 是在力扣 141 拓展，如有有环，返回入环的那个节点，就想下图环形链表返回节点 2。
这个问题是须要数学转换的，具体的剖析能够看下面的详细分析，这外面提一下大题的步骤。
如果找到第一个交汇点，其中 一个进行，另一个持续走 ，下一次交汇时候刚好走一圈，能够算出 循环局部长度为 y 。
所以咱们晓得的货色有：交汇时候 fast 走 2x 步，slow 走 x 步，环长为 y。并且快指针和慢指针交汇时候，多走的步数刚好是换长 y 的整数倍（它两此刻在同一个地位，快指针刚好多绕整数倍圈数能力在同一个地位相聚），能够失去2x=x+ny(x=ny)。其中所以说慢指针走的 x 和快指针多走的 x 是圈长 y 的整数倍。
也就是说，从结尾走到这个点共计 x 步，从这个点走 x 步也就是绕了几圈也回到这个点 。如果说 slow 从终点登程，fast 从这个点登程(每次走一步，相当于之前两步对消 slow 走的途程)，那么走 x 步还会达到这个点，然而 这两个指针这次都是每次走一步，所以一旦 slow 达到循环圈内，两个指针就开始会合 了。
实现代码为：
public class Solution {public ListNode detectCycle(ListNode head) {
boolean isloop=false;
ListNode fast=new ListNode(0);// 头指针
ListNode slow=fast;
fast.next=head;
if(fast.next==null||fast.next.next==null)
return null;
while (fast!=null&&fast.next!=null) {
fast=fast.next.next;
slow=slow.next;
if(fast==slow)
{
isloop=true;
break;
}
}
if(!isloop)// 如果没有环返回
return null;
ListNode team=new ListNode(-1);// 头指针 下一个才是 head
team.next=head;
while (team!=fast) {//slow 和 fast 别离从终点和以后点登程
team=team.next;
fast=fast.next;
}
return team;
}
}0X04 两个栈实现队列
对应剑指 offer09，题意为：
用两个栈实现一个队列。队列的申明如下，请实现它的两个函数 appendTail 和 deleteHead，别离实现在队列尾部插入整数和在队列头部删除整数的性能。(若队列中没有元素，deleteHead 操作返回 -1)
剖析：
解决这个问题，要晓得栈是什么，队列是什么，两种常见数据结构格局很简略，栈的特点就是：后进先出 ，队列的特点就是： 先进先出 ，栈能够设想成一堆书本，越在下面的取的越早， 下面来下面出 (比喻一下)；队列就是设想成排队买货色，只能 前面进后面出，所以两者数据结构还是有区别的，尽管都是单个入口进出，然而栈进出口雷同，而队列不同。
下面形容的是一个一般栈和队列的数据结构，这外面让咱们用两个栈实现一个队列的操作，这里比拟容易想的计划就是其中一个栈 stack1 用作数据存储，插入尾时候直接插入 stack1，而删除头的时候将数据先退出到另一个栈 stack2 中，返回并删除栈顶元素，将 stack2 程序退出 stack1 中实现一个还原，然而这样操作插入工夫复杂度为 O(1), 删除工夫复杂度为 O(n)比拟高。
实现形式也给大家看下：
class CQueue {Stack<Integer>stack1=new Stack<>();
Stack<Integer>stack2=new Stack<>();
public CQueue() {}
public void appendTail(int value) {stack1.push(value);
}
public int deleteHead() {if(stack1.isEmpty())
return -1;
while (!stack1.isEmpty())
{stack2.push(stack1.pop());
}
int value= stack2.pop();
while (!stack2.isEmpty())
{stack1.push(stack2.pop());
}
return value;
}
}这样的工夫复杂度是不被喜爱的，因为删除太鸡儿耗时了，每次都要折腾一番，有没有什么好的办法可能让删除也不便一点呢？
有啊，stack1 能够程序保障程序插入，stack1 数据放到 stack2 中能够保障程序删除，所以 用 stack1 作插入，stack2 作删除，因为题目也没要求数据必须放到一个容器中，所以就这样组合应用，完满 perfect！
具体实现的时候，插入直接插入到 stack1 中，如果须要删除从 stack2 中栈顶删除，如果 stack2 栈为空那么将 stack1 中数据全副增加进来(这样又能保障 stack2 中所有数据是能够程序删除的了)，上面列举几个删除的例子
其实就是将数据分成两个局部，一部分用来插入，一部分用来删除，删除的那个栈 stack2 空了增加所有 stack1 中的数据持续操作。这个操作插入删除的工夫复杂度是 O(1), 具体实现的代码为：
class CQueue {
Deque<Integer> stack1;
Deque<Integer> stack2;
public CQueue() {stack1 = new LinkedList<Integer>();
stack2 = new LinkedList<Integer>();}
public void appendTail(int value) {stack1.push(value);
}
public int deleteHead() {
// 如果第二个栈为空 将 stack1 数据退出 stack2
if (stack2.isEmpty()) {while (!stack1.isEmpty()) {stack2.push(stack1.pop());
}
} // 如果 stack2 仍然为空 阐明没有数据
if (stack2.isEmpty()) {return -1;} else {// 否则删除
int deleteItem = stack2.pop();
return deleteItem;
}
}
}0X05 二叉树层序 (锯齿) 遍历
二叉树的遍历，对应力扣 102，107，103.
详细分析：一次面试，被二叉树层序遍历打爆了
如果一般二叉树层序遍历，也不是什么艰难的问题，然而它会有个分层返回后果的操作，就须要你具体思考了。
很多人会用两个容器 (队列) 进行分层的操作，这里其实能够间接应用一个队列，咱们首先记录枚举前队列大小 len，而后依据这个大小 len 去枚举遍历就能够失去残缺的该层数据了。
还有一个难点就是二叉树的锯齿层序(也叫之字形打印)，第一趟是从左往右，第二趟是从右往左，只须要记录一个奇偶层数进行对应的操作就能够了。
这里就拿力扣 103 二叉树的锯齿形层序遍历作为题板给大家分享一下代码：
public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> value=new ArrayList<>();// 存储到的最终后果
if(root==null)
return value;
int index=0;// 判断
Queue<TreeNode>queue=new ArrayDeque<>();
queue.add(root);
while (!queue.isEmpty()){List<Integer>va=new ArrayList<>();// 长期 用于存储到 value 中
int len=queue.size();// 以后层节点的数量
for(int i=0;i<len;i++){TreeNode node=queue.poll();
if(index%2==0)// 依据奇偶 抉择增加策略
va.add(node.val);
else
va.add(0,node.val);
if(node.left!=null)
queue.add(node.left);
if(node.right!=null)
queue.add(node.right);
}
value.add(va);
index++;
}
return value;
}0X06 二叉树中后序遍历(非递归)
二叉树的非递归遍历也是考查的重点，对于中序后序遍历递归实现很简略，非递归实现起来还是要点技巧的哦。
详细分析：二叉树的各种遍历(递归、非递归)
对于二叉树的中序遍历，其实就是失常状况第二次拜访该节点的时候才抛出输入(第一次数前序)，这样咱们枚举每个节点第一次不能删除，须要先将它存到栈中，当左子节点解决实现的时候在抛出拜访该节点。
外围也就两步，叶子节点左右都为 null，也可满足下列条件：
- 枚举以后节点 (不存储输入) 并用栈存储，节点指向左节点，直到左孩子为 null。
- 抛出栈顶拜访。如果有右节点，拜访其右节点反复步骤 1，如有没右节点，持续反复步骤 2 抛出。
实现代码为：
class Solution {public List<Integer> inorderTraversal(TreeNode root) {List<Integer>value=new ArrayList<Integer>();
Stack<TreeNode> q1 = new Stack();
while(!q1.isEmpty()||root!=null)
{while (root!=null) {q1.push(root);
root=root.left;
}
root=q1.pop();// 抛出
value.add(root.val);
root=root.right;// 筹备拜访其右节点
}
return value;
}
}而后序遍历依照递归的思路其实个别是第三次拜访该节点是从右子节点回来才抛出输入，这个实现起来的确有难度。然而具体的实现，咱们应用一个 pre 节点记录上一次被抛出拜访的点，如果 以后被抛出的右孩子是 pre 或者以后节点右为 null，那么就将这个点抛出，否则阐明它的右侧还未被拜访须要将它 ” 回炉重造 ”，前面再用！如果不了解能够看后面的具体介绍。
具体实现的代码为：
class Solution {public List<Integer> postorderTraversal(TreeNode root) {
TreeNode temp=root;// 枚举的长期节点
List<Integer>value=new ArrayList<>();
TreeNode pre=null;// 前置节点
Stack<TreeNode>stack=new Stack<>();
while (!stack.isEmpty()||temp!=null){while(temp!=null){stack.push(temp);
temp=temp.left;
}
temp=stack.pop();
if(temp.right==pre||temp.right==null)// 须要弹出
{value.add(temp.val);
pre=temp;
temp=null;// 须要从新从栈中抛出
}else{stack.push(temp);
temp=temp.right;
}
}
return value;
}
}当然，后序遍历也有用前序 ( 根右左 ) 的前序遍历后果最初翻转一下的，但面试官更想考查的还是下面提到的办法。
0X07 跳台阶(斐波那契、爬楼梯)
爬楼梯、跳台阶是一个经典问题，对应剑指 offer10 和力扣 70 题，题目的要求为：
假如你正在爬楼梯。须要 n 阶你能力达到楼顶。每次你能够爬 1 或 2 个台阶。你有多少种不同的办法能够爬到楼顶呢？留神：给定 n 是一个正整数。
剖析：
这个问题入门级别 dp，剖析以后第 k 阶的后果，每个人能够爬 1 个或者 2 个台阶，那么阐明它可能是由 k - 1 或者 k - 2 来的，所以就是两个子状况的叠加(须要非凡考虑一下初始状况)，这个思路有人会想到递归，没错用递归的确能够解决然而用递归效率较低(因为这个是个发散的递归一个拆成两个)，应用记忆化搜寻会略微好一些。
然而 dp 是比拟好的办法，外围状态转移方程为：dp[i]=dp[i-1]+dp[i-2]，有些空间优化的那就更好了，因为只用到前两个值，所以齐全能够用三个值重复使用节俭空间。
class Solution {public int climbStairs(int n) {if(n<3)return n;
int dp[]=new int[n+1];
dp[1]=1;
dp[2]=2;
for(int i=3;i<n+1;i++)
{dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];
}
public int climbStairs(int n) {
int a = 0, b = 0, c = 1;
for (int i = 1; i <= n; i++) {
a = b;
b = c;
c = a + b;
}
return c;
}
}当然，有的数据很大求余的跳台阶，能够用矩阵疾速幂解决，然而这里就不介绍啦，有趣味能够具体看看。
0X08 TOPK 问题
TOPK 问题真的十分经典，通常问的有最小的 K 个数，寻找第 K 大都是 TOPK 这种问题，这里就使劲扣 215 寻找数组第 K 大元素作为板子。
详细分析：一文拿捏 TOPK
TOPK 的问题解决思路有很多，如果优化的冒泡或者简略抉择排序，工夫复杂度为 O(nk), 应用优化的堆排序为 O(n+klogn)，不过把握快排的变形就能够应酬大体上的所有问题了(面试官要是让你手写堆排序那真是有点难为你了)。
快排每次确定一个数 pivot 地位，将数分成两局部：右面的都比这个数 pivot 小，右面的都比这个数 pivot 大，这样就能够依据这个 k 去判断刚好在 pivot 地位，还是左侧还是右侧？能够压缩空间迭代去调用递归最终求出后果。
很多人为了更快过测试样例将这个 pivot 不选第一个随机抉择(为了和刁钻的测试样例作奋斗)，不过这里我就选第一个作为 pivot 了，代码能够参考：
class Solution {public int findKthLargest(int[] nums, int k) {quickSort(nums,0,nums.length-1,k);
return nums[nums.length-k];
}
private void quickSort(int[] nums,int start,int end,int k) {if(start>end)
return;
int left=start;
int right=end;
int number=nums[start];
while (left<right){while (number<=nums[right]&&left<right){right--;}
nums[left]=nums[right];
while (number>=nums[left]&&left<right){left++;}
nums[right]=nums[left];
}
nums[left]=number;
int num=end-left+1;
if(num==k)// 找到 k 就终止
return;
if(num>k){quickSort(nums,left+1,end,k);
}else {quickSort(nums,start,left-1,k-num);
}
}
}0X09 无反复的最长子串(数组)
这个问题可能是个字符串也可能是数组，然而情理统一，无反复字符的最长子串 和最长无重复子数组 实质统一。
题目要求为：给定一个字符串，请你找出其中不含有反复字符的 最长子串 的长度。
剖析：
此题就是给一个字符串让你找出最长没有反复的一个子串。要搞清 子串和子序列 的区别：
子串 ：是间断的，能够看成原串的一部分截取。
子序列：不肯定是间断的，然而要保障各个元素之间绝对地位不变。
那么咱们如何解决呢？
暴力查找，暴力查找当然是能够的，然而简单度过高这里就不进行解说了。这里抉择的思路是滑动窗口，滑动窗口，就是用一个区间从左往右，右侧先进行试探，找到区间无反复最大值，当有反复时左侧再往右侧挪动始终到没反复，而后反复进行到最初。在整个过程中找到最大子串即可。
具体实现时候能够用数组代替哈希表会快很多：
class Solution {public int lengthOfLongestSubstring(String s) {int a[]=new int[128];
int max=0;// 记录最大
int l=0;//left 用 i 当成 right，当有反复左就往右
for(int i=0;i<s.length();i++)
{a[s.charAt(i)]++;
while (a[s.charAt(i)]>1) {a[s.charAt(l++)]--;
}
if(i-l+1>max)
max=i-l+1;
}
return max;
}
}0X10 排序
不会真的有人认为用个 Arrays.sort()就完事了吧，手写排序还是很高频的，像冒泡、插入这些简略的大家相比都会，像堆排序、希尔、基数排序等考查也不多，比拟 高频的就是快排 了，这里额定处分一个也很高频的归并排序，两个都是典型分治算法，也能够将快排和后面的 TOPK 问题比拟一番。
排序具体的十大排序都有具体讲过，大家能够自行参考：程序员必知必会十大排序
快排：
具体实现：
public void quicksort(int [] a,int left,int right)
{
int low=left;
int high=right;
// 上面两句的程序肯定不能混，否则会产生数组越界！！！very important！！！if(low>high)// 作为判断是否截止条件
return;
int k=a[low];// 额定空间 k，取最左侧的一个作为掂量，最初要求左侧都比它小，右侧都比它大。while(low<high)// 这一轮要求把左侧小于 a[low], 右侧大于 a[low]。{while(low<high&&a[high]>=k)// 右侧找到第一个小于 k 的进行
{high--;}
// 这样就找到第一个比它小的了
a[low]=a[high];// 放到 low 地位
while(low<high&&a[low]<=k)// 在 low 往右找到第一个大于 k 的，放到右侧 a[high]地位
{low++;}
a[high]=a[low];
}
a[low]=k;// 赋值而后左右递归分治求之
quicksort(a, left, low-1);
quicksort(a, low+1, right);
}归并排序:
实现代码为：
private static void mergesort(int[] array, int left, int right) {int mid=(left+right)/2;
if(left<right)
{mergesort(array, left, mid);
mergesort(array, mid+1, right);
merge(array, left,mid, right);
}
}
private static void merge(int[] array, int l, int mid, int r) {
int lindex=l;int rindex=mid+1;
int team[]=new int[r-l+1];
int teamindex=0;
while (lindex<=mid&&rindex<=r) {// 先左右比拟合并
if(array[lindex]<=array[rindex])
{team[teamindex++]=array[lindex++];
}
else {team[teamindex++]=array[rindex++];
}
}
while(lindex<=mid)// 当一个越界后残余按序列增加即可
{team[teamindex++]=array[lindex++];
}
while(rindex<=r)
{team[teamindex++]=array[rindex++];
}
for(int i=0;i<teamindex;i++)
{array[l+i]=team[i];
}
}结语
好了，明天给大家分享的 10 个问题，是真的在面试中十分十分高频，我敢说均匀每两次面试就得遇到这外面的其中一个题(毫不夸大)！
虽说题海很深学不完，然而学过缓存的都晓得要把热点数据放缓存，考过试的都晓得要把必考点把握……这十个问题曾经送到嘴边。
当然，这只是十分十分高频的问题，要想拿捏口试，必定还要一直积攒、刷题，也欢送各位退出我的 力扣打卡群保持刷题！
原创不易，求个三连！
本文首发集体技术公众号「
bigsai」，转载请附上作者和本文链接。
