手撕字节跳动面试时出现过的算法题

# 手撕字节跳动面试时出现过的算法题

[原博客链接](https://www.nowcoder.com/discuss/425581)

## 1.买股票的最佳时机

**leetcode 原题链接**：[买股票的最佳时机](https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/)

**难度级别**：简单

**题目**：
给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
注意：你不能在买入股票前卖出股票。

**示例1**：

>输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

**示例2**:

>输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

**思路**：

先将每日的股票价格变成每日的变化量，然后求出最大子序列之和。
```java
class Solution {
public int maxProfit(int[] prices) {
if(prices.length==0)
return 0;
int[] values = new int[prices.length];
values[0] = 0;
for(int i=1;i<prices.length;i++) {
values[i] = prices[i]-prices[i-1];
}
return maxSubSum(values);
}

public int maxSubSum(int[] values) {
int res = values[0];
for(int i=1;i<values.length;i++) {
values[i] += Math.max(values[i-1], 0);
res = Math.max(res, values[i]);
}
return res;
}
}
```



## 2.跳跃游戏

**leetcode 原题链接**：[跳跃游戏](https://leetcode-cn.com/problems/jump-game/)

**难度级别**：中等

**题目**：

给定一个非负整数数组，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个位置。

**示例1**：

>输入: [2,3,1,1,4]
输出: true
解释: 我们可以先跳 1 步，从位置 0 到达 位置 1, 然后再从位置 1 跳 3 步到达最后一个位置。

**示例2**:

>输入: [3,2,1,0,4]
输出: false
解释: 无论怎样，你总会到达索引为 3 的位置。但该位置的最大跳跃长度是 0 ， 所以你永远不可能到达最后一个位置。

**思路**：

如果数组中没有 0，那么肯定能走到最后，如果有 0，那就得判断所有 0 前面的几个元素能否达到 0 以后的位置，如果不能，那就无法走到。

```java
class Solution {
public boolean canJump(int[] nums) {
if(nums.length == 1)
return true;
outter:for(int i=0;i<nums.length;i++) {
if(nums[i]!=0)
continue;
for(int j=i-1;j>=0;j--) {
if(nums[j] + j > i || nums[j] + j == nums.length-1)
continue outter;
}
return false;
}
return true;
}
}
```

或者官方思路，看最远能到的地方：

```java
public class Solution {
public boolean canJump(int[] nums) {
int n = nums.length;
int rightmost = 0;
for (int i = 0; i < n; ++i) {
if (i <= rightmost) {
rightmost = Math.max(rightmost, i + nums[i]);
if (rightmost >= n - 1) {
return true;
}
}
}
return false;
}
}
```



## 3.场景题：发红包

**题目**：

让你设计一个微信发红包的api，你会怎么设计，不能有人领到的红包里面没钱，红包数值精确到分。

**思路**：

假设一共有 N 元，一共有 K 个人，则可以每个人拿到的钱为 random(N - (K - 1) * 0.01)，然后更新N，直到最后一个人就直接 N。



## 4.合并排序的数组

**leetcode 原题链接**：[合并排序的数组](https://leetcode-cn.com/problems/sorted-merge-lcci/)

**难度级别**：简单

**题目**：

给定两个排序后的数组 A 和 B，其中 A 的末端有足够的缓冲空间容纳 B。 编写一个方法，将 B 合并入 A 并排序。
初始化 A 和 B 的元素数量分别为 m 和 n。

**示例**：

>输入:
A = [1,2,3,0,0,0], m = 3
B = [2,5,6],       n = 3
输出: [1,2,2,3,5,6]

**说明**：

* A.length == n + m

**思路**：

想到的方法有两种：
(1) 将 B 放进 A 的尾部后对整个数组进行排序

```java
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
for(int i=m;i<m+n;i++) {
A[i] = B[i-m];
}
Arrays.sort(A);
}
}
```

(2) 利用双指针法。我们知道如果从头开始，那么数组 A 的元素会被覆盖，那么我们可以从后面开始。

```java
class Solution {
public void merge(int[] A, int m, int[] B, int n) {
int i = m-1, j = n-1;
int index = m+n-1;
while(i>=0 && j>=0) {
if(A[i] > B[j]) {
A[index] = A[i];
i--;
}else {
A[index] = B[j];
j--;
}
index --;
}
while(i>=0) {
A[index] = A[i];
index--;
i--;
}
while(j>=0) {
A[index] = B[j];
index--;
j--;
}
}
}
```



## 5.剪绳子

**leetcode 原题链接**：[剑指 Offer 14- I. 剪绳子](https://leetcode-cn.com/problems/jian-sheng-zi-lcof/)

**难度级别**：中等

**题目**：

给你一根长度为 n 的绳子，请把绳子剪成整数长度的 m 段（m、n都是整数，n>1并且m>1），每段绳子的长度记为 k[0],k[1]...k[m-1] 。请问`k[0]*k[1]*...*k[m-1]`可能的最大乘积是多少？例如，当绳子的长度是 8 时，我们把它剪成长度分别为 2、3、3 的三段，此时得到的最大乘积是 18。

**示例1**：

>输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

**示例2**：

>输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

**提示**：

* 2 <= n <= 58

**思路**：

方法1：动态规划

```java
class Solution{
public int cuttingRope(int n) {

// 浪费一个空间，方便了逻辑
if(n <= 3)
return n-1;
int[] dp = new int[n+1];
dp[0] = 0;
dp[1] = 1;
dp[2] = 1;
dp[3] = 2;
for(int i=4;i<=n;i++) {
for(int j=0;j<i;j++) {
// 这边还要跟自己相比是因为每次剪的长度都要跟之前的最大值比一下。
dp[i] = Math.max(dp[i], Math.max(dp[i-j] * j, (i-j) * j));
}
}
return dp[n];
}
}
```

方法2：贪心算法。思想是长度为 3 的越多越好，其次是 2， 最次是 1。

```java
public int cuttingRope(int n) {
if(n <= 3)
return n-1;
if(n%3 == 0) return (int) Math.pow(3, n/3);
if(n%3 == 1) return (int) Math.pow(3, n/3-1) * 4;
if(n%3 == 2) return (int) Math.pow(3, n/3 - 1) * 6;
return 0;
}
```



## 6.有序数组中不重复元素的个数

**题目**：

给定一个有序数组，请算出平方后的结果可能的个数。

**思路**：

方法1：平方后进行快排并遍历。

```java
public int findElements(int[] nums) {
for(int i=0;i<nums.length;i++) {
nums[i] *= nums[i];
}
Arrays.sort(nums);
int sum = 1;
for(int i=1;i<nums.length;i++) {
if(nums[i] != nums[i-1]) {
sum ++;
}
}
return sum;
}
```

方法2：双指针，一个从前往后，一个从后往前。

```java
class Solution{
public int findElements(int[] arr) {
if(arr == null || arr.length == 0){
return 0;
}
if(arr.length == 1){
return 1;
}
for(int i = 0; i < arr.length; i++){//将所有负数转正
arr[i] =  Math.abs(arr[i]);
}
int head = 0, tail = arr.length - 1;
int lastBig = -1;//上一个数据
int count = 0;//不一样的数的个数
while(head <= tail){//注意这里是小于等于
while(head < arr.length && arr[head] == lastBig){
head++;
}
while(tail >= 0 && arr[tail] == lastBig){
tail--;
}
if(head <= tail){
count++;
if(arr[head] > arr[tail]){
lastBig = arr[head];
head++;
}else{
lastBig = arr[tail];
tail--;
}
}else{
return count;
}
}
return count;
}
}
```



## 7.找出不重复的元素个数

**题目**：

一个数据先递增再递减，找出数组不重复的个数。不能使用额外空间，复杂度o(n)

**思路**：

显然要先找到最大元素的位置，然后朝两边移动。

```java
public int findElements(int[] nums) {
int res = 0;
// 找到最大的数
int maxIndex = 0;
for(int i=1;i<nums.length;i++) {
if(nums[i] < nums[i-1]) {
maxIndex = i-1;
break;
}
}
res ++;
// 找到左右两指针开始的位置
int left = maxIndex -1, right = maxIndex + 1;
while(left - 1>=0 && nums[left] == nums[maxIndex]) left --;
while(right + 1<nums.length && nums[right] == nums[maxIndex]) right ++;
// 开始比较
int temp = nums[maxIndex] + 1;
while(left >=0 && right <nums.length) {
if(nums[left] == nums[right]) {
if(nums[left] != temp) {
res ++;
temp = nums[left];
}
left -- ;
right ++;
}else if(nums[left] < nums[right]){
res ++;
right ++;
}else {
res ++;
left --;
}
}
return res;
}
```



## 8.找范围

**题目**：

高考成绩2000万数据，分数0-750，如何快速知道你的排名，如何知道任一分数排名？

**思路**：

利用桶排序。
将分数分成 0 - 150， 151 - 300， 301 - 450， 451 - 600， 601 - 750 共五个区间（每个区间内还可以再分），将 2000 万分数据按照成绩分到对应的成绩区间中。这样就可以快速查到对应分数的排名了。



## 9.测时间

**题目**：

两根香，一根烧完1小时，如何测量15分钟

**思路**：

先将一根香的一端点燃，另一根香的两端全部点燃。当第二根香全部烧完时，此时已经过了半个小时。再将第一根香的另一端也点燃，那么此时第一根香剩下部分烧完的时间就是 15 min。



## 10.链表相交

**leetcode 原题链接**：[面试题 02.07. 链表相交](https://leetcode-cn.com/problems/intersection-of-two-linked-lists-lcci/)

**难度级别**：简单

**题目**：

给定两个（单向）链表，判定它们是否相交并返回交点。请注意相交的定义基于节点的引用，而不是基于节点的值。换句话说，如果一个链表的第 k 个节点与另一个链表的第 j 个节点是同一节点（引用完全相同），则这两个链表相交。

**示例1**：

>输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

**示例2**：

>输入：intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
输出：Reference of the node with value = 2
输入解释：相交节点的值为 2 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [0,9,1,2,4]，链表 B 为 [3,2,4]。在 A 中，相交节点前有 3 个节点；在 B 中，相交节点前有 1 个节点。

**示例3**：

输入：intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
输出：null
输入解释：从各自的表头开始算起，链表 A 为 [2,6,4]，链表 B 为 [1,5]。由于这两个链表不相交，所以 intersectVal 必须为 0，而 skipA 和 skipB 可以是任意值。
解释：这两个链表不相交，因此返回 null。

**注意**：

* 如果两个链表没有交点，返回 null 。
* 在返回结果后，两个链表仍须保持原有的结构。
* 可假定整个链表结构中没有循环。
* 程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。

**思路**：

这边为了满足 O(1) 的内存，因此不去使用 Set 来做，而是使用遍历来做。
我们先假设两条链表头分别为 A、B，他们相交的点为 C，他们的终点为 D（这边只能是 Y 型相交，即相交后两条链表合为了一条，如果是 X 型相交显然是做不了的）。那么让两个指针一起分别从 A、B 开始遍历，直到遍历到最后，然后遍历另一条链表。那么此时势必会出现这样一个情况，从 A 遍历的指针走完第一条链表长度为 AC + CD，从 B 遍历的指针走完第一条链表长度为 BC + CD，当他们都遍历第二条链表后，一定会到达这样一个节点，在这个节点两个指针走过的路长分别为 AC + CD + BC 和 BC + CD + AC，即这个点即为相交的 C 点。

```java
/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) {
*         val = x;
*         next = null;
*     }
* }
*/
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p = headA, q = headB;
// 两个指针用来记录链表的尾部
ListNode aTail = null, bTial = null;
while(p != q) {
if(p == null) {
p = headB;
}else {
if(p.next == null) {
aTail = p;
}
p = p.next;
}
if(q == null) {
q = headA;
}else {
if(q.next == null) {
bTial = q;
}
q = q.next;
}
// 当两个链表都已经遍历结束了，查看尾部是否相同，如果相同则证明有交点，不相同则证明无交点
if(aTail != null && bTial != null && aTail!=bTial) {
return null;
}
}
return q;
}
}
```



## 11.求平方根

**题目**：

（这道题目跟 leetcode 上的不一样，leetcode 上只要求整数，这个还有精度）
写一个函数，求平方根，函数参数为目标数字和精度，测试案例 fn(4.1,0.001) fn(501.1,0.001) fn(0.045,0.001)

**思路**：

使用二分法

```java
class Solution {

public float fn(float n, float e) {
// 先求 e 的精度
String d = String.valueOf(e);
int lengh = d.length() - 2;
float x = 0;
if (n > 0 && e > 0) {
float low = 0;
float high = n;
while (low < high) {
// 二分，并控制精度
float mid = Float.parseFloat(String.format("%." + lengh + "f", (low + high) / 2));
if (mid * mid < n - e) {
low = mid;
} else if (mid * mid > n + e) {
high = mid;
} else {
x = mid;
break;
}
}
}
return x;

}

}
```



## 12.场景题：互相关注表设计

**题目**：

场景题：需求：谁关注了我，我关注了谁，谁与我互相关注。表该如何设计，索引怎么建。查询语句怎么写

**思路**：

个人见解，表可以有：id、粉丝id、被追随者id 三个字段，索引可以建两个，分别是粉丝 id 和被追随者 id。




## 13.找 K 个最小值

**题目**：

10亿个数字，取最小的100个数

**思路**：

如果是几百或者几千的数字，还能用堆排给搞一下。但是 10 亿个恐怕是不行的。这边给出几种方法，是否可行还得大家自己判断，甚至可以互相叠加使用：
* (1) 单纯的堆排
* (2) 先通过 hash 去除重复元素，再通过堆排
* (3) 先桶排序，每个桶里再进行堆排序
* (4) 维持一个长度为 100 的数组，遍历 10 亿个数据，比较并加入到数组中




## 14.找出重复元素

**题目**：

1亿个正整数,范围是0-42亿。求出现次数是2的数字，空间复杂度

**思路**：

这题和 leetcode 里面的题目不太一样，这道题没有说是否只有一个次数为 2 的数字，也没有说其他数字出现的次数，因此就把题目看成是有多个出现次数为 2 的数字，并且其他数字只会出现一次。
使用位图法来做。
```java
// 这边是先遍历了一遍，找到数据中的最小值和最大值，从而减小位图法中数组的长度
public void findDuplicated(int[] a) {
int max = 0;
int min = 0;
for (int i = 0; i < a.length; i++) {
max = Math.max(max, a[i]);
min = Math.min(min, a[i]);
}

// 这边使用了 byte[]，而不是使用了 int[] 和 boolean[]，其实从原理上都可以的
int length = max / 8 - min / 8 + 1;
byte[] arry = new byte[length];
for (int i = 0; i < a.length; i++) {
int num = a[i];
int index = num / 8 - min / 8;
int k = (num - min) % 8;
// 这边使用这样的判断是因为使用的是 byte[]，使用 int[] 或者 boolean[] 则使用另一种判断方法
if((arry[index] & 1<<k) > 0) {
System.out.println(num);
}else {
arry[index] |= (1<<k);
}
}
}
```



## 15.二叉树层次遍历

**leetcode 原题链接**：[102. 二叉树的层序遍历](https://leetcode-cn.com/problems/binary-tree-level-order-traversal/)

**难度级别**：中等

**题目**：

给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。

**示例**：

二叉树：[3,9,20,null,null,15,7],

```
3
/ \
9  20
/  \
15   7

```

返回其层次遍历结果：

```
[
[3],
[9,20],
[15,7]
]
```

**思路**：

层序遍历，一般都用队列。这算是 BFS 把，还有 DFS 就不写了。

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null)
return list;
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
while(queue.size()!=0) {
int size = queue.size();
List<Integer> subList = new ArrayList<>();
for(int i =0;i<size;i++) {
TreeNode p = queue.poll();
subList.add(p.val);
if(p.left != null)
queue.add(p.left);
if(p.right!=null)
queue.add(p.right);
}
list.add(subList);
}
return list;
}
}
```



## 16.蛇形遍历二叉树

**leetcode 原题链接**：[103. 二叉树的锯齿形层次遍历](https://leetcode-cn.com/problems/binary-tree-zigzag-level-order-traversal/)

**难度级别**：中等

**题目**：

给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。

**示例**：

给定二叉树 [3,9,20,null,null,15,7],

```
3
/ \
9  20
/  \
15   7
```

返回锯齿形层次遍历如下：

```
[
[3],
[20,9],
[15,7]
]
```

**思路**：

本来还想用 BFS，但是发现用 queue 加 stack 的方法好像有点问题，于是用了深度遍历

```java
// BFS 想想看哪里有问题
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null)
return list;
int time = 1;
Queue<TreeNode> queue = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
queue.add(root);
while(queue.size()!=0 || stack.size() !=0) {
if(time == 1) {
int size = queue.size();
List<Integer> subList = new ArrayList<>();
for(int i=0;i<size;i++) {
TreeNode p = queue.poll();
subList.add(p.val);
if(p.left != null) {
stack.push(p.left);
}
if(p.right != null) {
stack.push(p.right);
}
}
time = 2;
list.add(subList);
}else {
int size = stack.size();
List<Integer> subList = new ArrayList<>();
for(int i=0;i<size;i++) {
TreeNode p = stack.pop();
subList.add(p.val);
if(p.left != null) {
queue.add(p.left);
}
if(p.right != null) {
queue.add(p.right);
}
}
time = 1;
list.add(subList);
}
}
return list;
}
```

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
// 更新后的 BFS
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
if(root == null)
return list;
int time = 1;
LinkedList<TreeNode> queue = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
stack.push(root);
while(stack.size() !=0) {
if(time % 2 == 1) {
List<Integer> subList = new ArrayList<>();
int size = stack.size();
while(stack.size()!=0) {
queue.add(stack.pop());
}
for(int i=0;i<size;i++) {
TreeNode p = queue.poll();
subList.add(p.val);
if(p.left!=null)
stack.push(p.left);
if(p.right != null)
stack.push(p.right);
}
list.add(subList);
time ++;
}else {
List<Integer> subList = new ArrayList<>();
int size = stack.size();
while(stack.size()!=0) {
queue.add(stack.pop());
}
for(int i=0;i<size;i++) {
TreeNode p = queue.poll();
subList.add(p.val);
if(p.right!=null)
stack.push(p.right);
if(p.left != null)
stack.push(p.left);
}
list.add(subList);
time ++;
}
}
return list;
}
}
```

```java
// DFS
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<List<Integer>>();
}
List<List<Integer>> results = new ArrayList<List<Integer>>();
DFS(root, 0, results);
return results;
}
public void DFS(TreeNode node, int level, List<List<Integer>> results) {
if (level >= results.size()) {
LinkedList<Integer> newLevel = new LinkedList<Integer>();
newLevel.add(node.val);
results.add(newLevel);
} else {
if (level % 2 == 0)
results.get(level).add(node.val);
else
results.get(level).add(0, node.val);
}

if (node.left != null) DFS(node.left, level + 1, results);
if (node.right != null) DFS(node.right, level + 1, results);
}
```



## 17.链表求和

**leetcode 原题链接**：[面试题 02.05. 链表求和](https://leetcode-cn.com/problems/sum-lists-lcci/)

**难度级别**：中等

**题目**：

给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。

**示例**：

>输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

**进阶**：

进阶：假设这些数位是正向存放的，请再做一遍。

**示例**：

>输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912

**思路**：

遍历，并用一个标志位来表示进位即可。

```java
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int flag = 0;
ListNode p = new ListNode(0);
ListNode t = p;
while(l1!=null && l2!=null) {
p.next = new ListNode((l1.val + l2.val + flag) %10);
p = p.next;
flag = (l1.val + l2.val + flag) /10;
l1 = l1.next;
l2 = l2.next;
}
while(l1 != null) {
p.next = new ListNode((l1.val + flag) %10);
p = p.next;
flag = (l1.val + flag) /10;
l1 = l1.next;
}
while(l2!=null) {
p.next = new ListNode((l2.val + flag) %10);
p = p.next;
flag = (l2.val + flag) /10;
l2 = l2.next;
}
if(flag == 1) {
p.next = new ListNode(1);
}
return t.next;
}
```
进阶就比较简单了，先原地反转两个链表，再执行上面的函数即可。
```java
public ListNode reverseList(ListNode l1) {
ListNode pre = null;
ListNode next = null;
while(l1 != null) {
next = l1.next;
l1.next = pre;
pre = l1;
l1 = next;
}
return pre;
}

public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 链表原地反转
l1 = reverseList(l1);
l2 = reverseList(l2);
// 链表求和
int flag = 0;
ListNode p = new ListNode(0);
ListNode t = p;
while(l1!=null && l2!=null) {
p.next = new ListNode((l1.val + l2.val + flag) %10);
p = p.next;
flag = (l1.val + l2.val + flag) /10;
l1 = l1.next;
l2 = l2.next;
}
while(l1 != null) {
p.next = new ListNode((l1.val + flag) %10);
p = p.next;
flag = (l1.val + flag) /10;
l1 = l1.next;
}
while(l2!=null) {
p.next = new ListNode((l2.val + flag) %10);
p = p.next;
flag = (l2.val + flag) /10;
l2 = l2.next;
}
if(flag == 1) {
p.next = new ListNode(1);
}
return t.next;
}
```



## 18.生成随机数

**题目**:

给定一个 0-4 随机数生成器 如何生成 0-6 随机数

**思路**：

乍一看，我想法是 0-4 生成器的结果除以 4 再乘 6 不就好了。。。但其实没有这么简单，了解了真相的我眼泪掉下来





## 19.二叉树的最近公共祖先

**leetcode 原题链接**：[剑指 Offer 68 - II. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)

**难度级别**：中等

**题目**：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

```
3
/   \
5     1
/  \  /  \
6   2  0   8
/ \
7   4
```
**示例1**:

>输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

**示例2**：

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

**说明**:

* 所有节点的值都是唯一的。
* p、q 为不同节点且均存在于给定的二叉树中。

**思路**

基本思路，DFS

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || root == p || root == q)
return root;
TreeNode left = lowestCommonAncestor(root.left,p,q);
TreeNode right = lowestCommonAncestor(root.right,p,q);
if(left == null)
return right;
if(right == null)
return left;
return root;
}
}
```



## 20.二叉树中的最大路径和

**leetcode 原题链接**：[124. 二叉树中的最大路径和](https://leetcode-cn.com/problems/binary-tree-maximum-path-sum/)

**难度级别**：困难

**题目**：

给定一个非空二叉树，返回其最大路径和。
本题中，路径被定义为一条从树中任意节点出发，达到任意节点的序列。该路径至少包含一个节点，且不一定经过根节点。

**示例1**：

```
输入: [1,2,3]

1
/ \
2   3

输出: 6
```

**示例2**：

```
输入: [-10,9,20,null,null,15,7]

-10
/ \
9  20
/  \
15   7

输出: 42
```

**思路**：

这道题其实不难，理解了递归很容易做出来，关键是理解题目的意思。题目的意思要求的一条**路径**的最大和，而路径是不能有岔路的。比如说：如果将上面的节点 9 替换成 11，如果是要连通节点的最大值，很明显是将所有节点都走一遍，那就是 43，但是如果是要路径，那么在节点 20 的时候，只能走 -10 -> 20 -> 15 或者 -10 -> 20 -> 7 或者 15 -> 20 -> 7 三条中的一条，而不能是 -10 -> 20 -> 15 -> 20(已走过) -> 7这样子。了解了这点以后，我们来写递归函数。

```java
class Solution{

public int max = Integer.MIN_VALUE;

public int maxPathSum(TreeNode root){
maxGain(root);
return max;
}

public int maxGain(TreeNode root){
if(root == null) return 0;
int left = Math.max(maxGain(root.left), 0);
int right = Math.max(maxGain(root.right), 0);
int value = root.val + left + right;
max = Math.max(max, value);
return root.val + Math.max(left, right);
}
}
```



## 21.快速排序

手写快排。
快排其实是分治思想的一种，通过找一个基准点，使得该基准点左边的数字都小于等于该基准，基准点右边的数字都大于等于该基准，然后将左右两部分再进行排序，使得总体有序。实现方法通常使用头尾指针。

```java
public void quickSort(int[] nums) {
quickSort(nums, 0, nums.length - 1);
}

public void quickSort(int[] arr, int low, int high) {
int i, j, temp, t;
if (low > high)
return;
i = low;
j = high;

temp = arr[low];

while (i < j) {
while (temp <= arr[j] && i < j) {
j--;
}
while (temp >= arr[i] && i < j) {
i++;
}
if (i < j) {
t = arr[j];
arr[j] = arr[i];
arr[i] = t;
}
}

arr[low] = arr[i];
arr[i] = temp;

quickSort(arr, low, j - 1);
quickSort(arr, j + 1, high);
}
```



## 22.二叉树的前序遍历非递归

**leetcode 原题链接**：[144. 二叉树的前序遍历](https://leetcode-cn.com/problems/binary-tree-preorder-traversal/)

**难度级别**：中等

**题目**：

给定一个二叉树，返回它的 前序 遍历。

**示例**：
```
输入: [1,null,2,3]
1
\
2
/
3

输出: [1,2,3]
```

**进阶**：
递归算法很简单，你可以通过迭代算法完成吗？

**思路**：

递归实现
```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();

public List<Integer> preorderTraversal(TreeNode root) {
preorderTraversal1(root);
return list;
}

public void preorderTraversal1(TreeNode root) {
if(root==null) {
return;
}
list.add(root.val);
preorderTraversal(root.left);
preorderTraversal(root.right);
}
}
```

非递归（迭代）实现
```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();
if(root!=null)
stack.push(root);
while(stack.size()!=0) {
TreeNode p = stack.pop();
list.add(p.val);
if(p.right!=null)
stack.push(p.right);
if(p.left!=null)
stack.push(p.left);
}
return list;
}
}
```



## 145.二叉树的后序遍历

**leetcode 原题链接**：[145. 二叉树的后序遍历](https://leetcode-cn.com/problems/binary-tree-postorder-traversal/)

**难度级别**：困难

**题目**：

给定一个二叉树，返回它的 后序 遍历。

**示例**：
```
输入: [1,null,2,3]
1
\
2
/
3

输出: [3,2,1]
```

**进阶**：

递归算法很简单，你可以通过迭代算法完成吗？

**思路**：

递归方法
```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<Integer> list = new ArrayList<>();

public List<Integer> postorderTraversal(TreeNode root) {
if(root != null) {
postorderTraversal1(root);
}
return list;
}

public void postorderTraversal1(TreeNode root) {
if(root.left != null)
postorderTraversal(root.left);
if(root.right != null)
postorderTraversal(root.right);
list.add(root.val);
}
}
```

非递归（迭代）方法
```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {

public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> list  = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
if(root != null)
stack.push(root);
while(!stack.isEmpty()) {
TreeNode p = stack.pop();
list.addFirst(p.val);
if(p.left != null)
stack.add(p.left);
if(p.right != null)
stack.add(p.right);
}
return list;
}
}
```



## 24.最长连续递增数列

**leetcode 原题链接**：[128. 最长连续序列](https://leetcode-cn.com/problems/longest-consecutive-sequence/)

**难度级别**：困难

**题目**：

给定一个未排序的整数数组，找出最长连续序列的长度。
要求算法的时间复杂度为 O(n)。

**示例**：
>输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。

**思路**：
先遍历数组，将数字都存入到 HashSet 中便于在常量时间内找到值是否存在。然后再次遍历数组，当 set 中不存在 num-1 的时候，表示这是起点，然后寻找 num + 1， num + 2 ... num + k 是否存在，更新结果即可。
```java
class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
HashSet<Integer> set = new HashSet<>();
for(int num : nums) {
set.add(num);
}
for(int num : nums) {
if(!set.contains(num-1)) {
int curLen = 1;
while(set.contains(num + curLen)) {
curLen ++;
}
res = Math.max(res, curLen);
}
}
return res;
}
}
```



## 25.（智力题）海盗分金币

**题目**：

有5个海盗，获得了100枚金币，于是他们要商量一个方法来分配金币。商议方式如下：
* (1) 由5个海盗轮流提出分配方案。
* (2) 如果超过半数海盗（包括提出者）同意该方案，则按照该方案分配。
* (3) 如果同意该方案的人数（包括提出者）小于等于半数，则提出者要被扔到海里喂鱼，剩下的海盗继续商议分配。
* (4) 海盗们都是绝对理性的，以自己尽可能多获得金币为目的。但是在收益相等的情况下，会倾向把提出者扔到海里。

问：第一个海盗应该提出怎样的分配方案，才能保证自己既不被扔到海里，又能使自己利益最大化？

这道题可以看这个[链接](https://mp.weixin.qq.com/s/GR7k-kKhw-U8AnnpQLzGGA)，挺有意思的。




## 26.接雨水

**leetcode 原题链接**：[42. 接雨水](https://leetcode-cn.com/problems/trapping-rain-water/)

**难度级别**：困难

**题目**：

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。


上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

**示例**：

>输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

**思路**：

方法1：
一个简单的思路就是从位置 i 出发往左右两边遍历，然后找比位置 i 高的值 leftMax 和 rightMax，那么位置 i 的蓄水为 Math.min(leftMax, rightMax) - i。
```java
class Solution {
public int trap(int[] height) {
int ans = 0;

for(int i=0;i<height.length;i++) {
int now = height[i];
int leftMax = now;
int rightMax = now;
for(int left = i;left>=0;left--) {
leftMax = Math.max(leftMax, height[left]);
}
for(int right = i;right<height.length;right++) {
rightMax = Math.max(rightMax,  height[right]);
}
ans += (Math.min(rightMax, leftMax) - now);
}

return ans;
}
}
```

方法2：
其实是对方法 1 的优化，将找最大值的过程使用数组记录下来，那么左边的最大值 lefeMax[i] = Math.max(lefMax[i-1], hegiht[i])，右边的最大值 rightMax[i] = Math.max(rightMax[i+1], height[i])。
```java
class Solution {
public int trap(int[] height) {
if(height.length==0)
return 0;
int ans = 0;
int lenght = height.length;
int[] leftMax = new int[lenght], rightMax = new int[lenght];
leftMax[0] = height[0];
rightMax[lenght-1] = height[lenght-1];
for(int i=1;i<lenght;i++) {
leftMax[i] = Math.max(leftMax[i-1], height[i]);
}
for(int i=lenght-2;i>=0;i--) {
rightMax[i] = Math.max(rightMax[i+1], height[i]);
}
for(int i=0;i<lenght;i++) {
int now = height[i];
ans += (Math.min(leftMax[i], rightMax[i])-now);
}
return ans;
}
}
```

方法3：
使用辅助栈，如果当前 height[i] 的值小于等于栈顶元素，则入栈当前索引，否则我们可以知道当前栈顶元素被当前 height[i] 和栈顶的前一个元素所包围，更新 ans，并把当前索引入栈。
```java
class Solution {
public int trap(int[] height) {
if(height.length==0)
return 0;
int ans = 0;
int lenght = height.length;
Stack<Integer> stack = new Stack<>();
stack.push(0);
for(int i=1;i<lenght;i++) {
while(stack.size() > 0 && height[stack.peek()] < height[i]) {
int stackTop = stack.pop();
if(stack.isEmpty())
break;
int before = stack.peek();
int distance = i - before -1;
ans += (Math.min(height[i],height[before]) - height[stackTop]) * distance;
}
stack.push(i);
}
return ans;
}
}
```

方法4：
双指针(有空再弄)



## 27. ip 判断

**题目**：

有一个IP地址库，假设有几十万条ip，如何判断某个ip地址是否在这个库中

**思路**：

这个没有找到原题，那么我们就不写代码直接写思路了。

方案1：布隆过滤器。
布隆过滤器就是对多个 ip 通过多次 hash，将制定位置的标志设置为 1。在判断给定 ip 是否存在时，直接使用 ip 进行多次 hash，如果多次 hash 的索引所在值都为 1，那么存在。因此，布隆过滤器常用作垃圾短信、垃圾邮件的过滤机制（ps：布隆过滤器具有拒真、纳伪的特性）

方案2：一致性 hash 加上多个表
使用一致性 hash，将 ip 放到对应地址的表中。查找时进行一次 hash，找到所在的表，再在表中进行查找。



## 28. 二叉树的路径和

（找了一圈没找到原题。。。）

**题目**：

给定一棵二叉树，求根节点到叶子节点的最小路径和。

**思路**：

显然用递归，这边要注意，一定要到叶子节点，如果该节点存在一个子节点，显然是不行的。如
```
1
/
2
/ \
3   4
```
上面的二叉树的结果应该是 6 而不是 1
```java
class Solution{
public int minSum(TreeNode root) {
if(root == null)
return 0;
if(root.left != null && root.right != null)
return root.val + Math.min(minSum(root.left), minSum(root.right));
else {
if(root.left == null)
return root.val + minSum(root.right);
else {
return root.val + minSum(root.left);
}
}
}
}
```



## 29. 反转链表 + 每 k 个反转链表

这题其实有两题，我们分开来做，不过第二题显然要用到第一题的知识。

**leetcode 原题链接**：[206. 反转链表](https://leetcode-cn.com/problems/reverse-linked-list/)

**难度级别**：简单

**题目**：

反转一个单链表。

**示例**：

>输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

**进阶**：

你可以迭代或递归地反转链表。你能否用两种方法解决这道题？

**思路**：

首先是递归
```java
/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null)
return head;
ListNode cur = reverseList(head.next);
head.next.next = head;
head.next = null;
return cur;
}
}
```
然后是迭代：
```java
/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head, next = null;
while(cur!=null) {
next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
```

**leetcode 原题链接**：[25. K 个一组翻转链表](https://leetcode-cn.com/problems/reverse-nodes-in-k-group/)

**难度级别**：困难

**题目**：

给你一个链表，每 k 个节点一组进行翻转，请你返回翻转后的链表。
k 是一个正整数，它的值小于或等于链表的长度。
如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。

**示例**：

给你这个链表：1->2->3->4->5
当 k = 2 时，应当返回: 2->1->4->3->5
当 k = 3 时，应当返回: 3->2->1->4->5

**说明**：

* 你的算法只能使用常数的额外空间。
* 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。

**思路**：

解法如下：
```java
/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 建立一个哨兵节点用来返回
ListNode dummy = new ListNode(0);
dummy.next = head;

// 两个指针用来保存需要反转数组的前后节点，用来恢复链表
ListNode pre = dummy;
ListNode next = dummy;

// 需要一个 head 和 tail 用来保存被反转链表的头和尾
ListNode tail = head;

while(next!=null) {
tail = head;
// 找到尾节点
for(int i=1;i<k && tail!=null;i++)
tail = tail.next;

// 如果不满足 k 个了，那么此时 tail 为 null，直接反转并跳出循环
if(tail== null) {
break;
}

//将尾结点的 next 保存并设为 null
next = tail.next;
tail.next = null;

// 反转节点
pre.next = reverse(head);

// 重新赋值
head.next = next;
pre = head;
head = head.next;
}
return dummy.next;
}

// 反转链表的迭代做法
public ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode next = cur.next;
cur.next = pre;
pre = cur;
cur = next;
}
return pre;
}
}
```



## 30. 场景题：求中位数

**题目**：

2g内存，要求一个10g文件的中位数

**思路**：

其实就是外村排序。。。
首先将 10g 的文件分成 10 * 1g，然后读入两个 g 的内存，排序后输出，然后不断进行这样的操作。




## 31. 螺旋矩阵

**leetcode 原题链接**：[59. 螺旋矩阵 II](https://leetcode-cn.com/problems/spiral-matrix-ii/)

**难度级别**：中等

**题目**：

给定一个正整数 n，生成一个包含 1 到 n^2 所有元素，且元素按顺时针顺序螺旋排列的正方形矩阵。

**示例**：
>输入: 3
输出:
[
[ 1, 2, 3 ],
[ 8, 9, 4 ],
[ 7, 6, 5 ]
]

**思路**：

设定几个边界即可
```java
class Solution {
public int[][] generateMatrix(int n) {
int l=0,r=n-1,u=0,d=n-1;
int[][] res = new int[n][n];
int num = 1, target = n * n;
while(num <= target) {
for(int i=l;i<=r;i++)
res[u][i] = num++;
u++;
for(int i=u;i<=d;i++)
res[i][r] = num++;
r--;
for(int i=r;i>=l;i--)
res[d][i] = num++;
d--;
for(int i=d;i>=u;i--)
res[i][l] = num++;
l++;
}
return res;
}
}
```



## 32. 数据结构 heap

**题目**：

讲一讲 heap 是什么？手写一个 heap

**思路**：

heap 即堆，根据性质可以分为大根堆和小根堆，存储形式是一棵完全二叉树，因此使用数组来保存。如果是大根堆，那么父节点大于等于子节点，根节点是最大的。如果是小根堆，那么父节点小于等于子节点，根节点是最小的。
手写堆就不手写了，直接附上源码
```java
import java.util.Arrays;
import java.util.Comparator;

import javax.security.auth.x500.X500Principal;

public class Heap<E> {

Object[] queue;

private int size;

private static final int DEFAULT_SIZE = 16;

private Comparator<? extends E> comparator;

public Heap() {
this(DEFAULT_SIZE, null);
}

public Heap(Comparator<? extends E> comparator) {
this(DEFAULT_SIZE, comparator);
}

public Heap(int initialCapacity, Comparator<? extends E> comparator) {
this.queue = new Object[initialCapacity];
}

public void grow(int size) {
// 当容量不足时，增加25%
int oldCapacity = queue.length;
int newCapacity = oldCapacity + (oldCapacity<=64?oldCapacity + 2:oldCapacity>>2);
queue = Arrays.copyOf(queue, newCapacity);
}

// 取出元素
public E poll() {
if (size == 0)
return null;
int s = --size;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
shiftDown(0, x);
return result;
}

// 插入元素
public boolean add(E e) {
if(e == null)
throw new NullPointerException();
int i = size;
if(i >= queue.length) {
grow(i + 1);
}
shiftUp(i, e);
size ++;
return true;
}

private void shiftDown(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}

private void shiftUp(int k, E e) {
Comparable<? super E> key = (Comparable<? super E>) e;
while(k > 0) {
int parent = (k -1) >>> 1;
Object t = queue[parent];
if(key.compareTo((E) t) >= 0) {
break;
}
queue[k] = t;
k = parent;
}
queue[k] = key;
}
}

```



## 33. 中文数字转阿拉伯数字

**问题**：

给定一个中文字符串，将其转换成对应的阿拉伯数字

**思路**：

其实就是按中文的个、十、百、千、万、亿来进行换算，想法简单但是变成比较麻烦



## 34. 重建二叉树

**leetcode 原题链接**：[剑指 Offer 07. 重建二叉树](https://leetcode-cn.com/problems/zhong-jian-er-cha-shu-lcof/)

**难度级别**：中等

**题目**：

输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出：

>前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

返回如下的二叉树：
```
3
/ \
9  20
/  \
15   7
```

**限制**：

0 <= 节点个数 <= 5000

**思路**：

方法1：采用递归的方法重建。

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
return buildTree(preorder,0, preorder.length-1, inorder,0, inorder.length-1);
}

public TreeNode buildTree(int[] preorder,int preBegin, int preEnd, int[] inorder, int inBegin, int inEnd) {
if(preBegin > preEnd)
return null;
// 找到父节点，即 preorder 位于 preBegin 的值
int val = preorder[preBegin];
TreeNode t = new TreeNode(val);

// 找到中序遍历中头结点的位置
int inIndex = 0;
for(int i=inBegin;i<=inEnd;i++) {
if(inorder[i] == val)
inIndex = i;
}

// 算出左、右子树的节点
int left = inIndex - inBegin;
int right = inEnd - inIndex;
t.left = buildTree(preorder,preBegin + 1, preBegin + left, inorder, inBegin, inIndex-1);
t.right = buildTree(preorder,preBegin + left + 1, preEnd, inorder, inIndex + 1, inEnd);

return t;
}
}
```

方法2：采用迭代的方式重建。

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {
if (preorder == null || preorder.length == 0) {
return null;
}
TreeNode root = new TreeNode(preorder[0]);
int length = preorder.length;
Stack<TreeNode> stack = new Stack<TreeNode>();
stack.push(root);
int inorderIndex = 0;
for (int i = 1; i < length; i++) {
int preorderVal = preorder[i];
TreeNode node = stack.peek();
if (node.val != inorder[inorderIndex]) {
node.left = new TreeNode(preorderVal);
stack.push(node.left);
} else {
while (!stack.isEmpty() && stack.peek().val == inorder[inorderIndex]) {
node = stack.pop();
inorderIndex++;
}
node.right = new TreeNode(preorderVal);
stack.push(node.right);
}
}
return root;
}
}
```



## 35. 路径总和

**leetcode 原题链接**：[112. 路径总和](https://leetcode-cn.com/problems/path-sum/)

**难度级别**：简单

**题目**：

给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。

说明: 叶子节点是指没有子节点的节点。

**示例**:

给定如下二叉树，以及目标和 sum = 22，

```
5
/ \
4   8
/   / \
11  13  4
/  \      \
7    2      1
```

返回 true, 因为存在目标和为 22 的根节点到叶子节点的路径 5->4->11->2。

**思路**：

看来只能疯狂遍历了，也不知道是不是全是正整数。

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public boolean hasPathSum(TreeNode root, int sum) {
if(root == null)
return false;
if(root.left == null && root.right == null) {
if(sum - root.val == 0)
return true;
}
return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val);
}
}
```



## 36. 路径总和-2

**leetcode 原题链接**：[113. 路径总和 2](https://leetcode-cn.com/problems/path-sum-ii/)

**难度级别**：中等

**题目**：

给定一个二叉树和一个目标和，找到所有从根节点到叶子节点路径总和等于给定目标和的路径。

说明: 叶子节点是指没有子节点的节点。

**示例**:
给定如下二叉树，以及目标和 sum = 22，

```
5
/ \
4   8
/   / \
11  13  4
/  \    / \
7    2  5   1
```

返回

```
[
[5,4,11,2],
[5,8,4,5]
]
```

**思路**：

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
List<List<Integer>> totalList = new ArrayList<>();

public List<List<Integer>> pathSum(TreeNode root, int sum) {
if(root == null)
return totalList;
pathSum(root, sum, new ArrayList<>());
return totalList;

}

public void pathSum(TreeNode root, int sum, List<Integer> list) {
list.add(root.val);
if(root.left == null && root.right == null && sum == root.val) {
totalList.add(list);
return;
}
if(root.left != null) {
pathSum(root.left, sum - root.val, new ArrayList<>(list));
}
if(root.right != null) {
pathSum(root.right, sum - root.val, new ArrayList<>(list));
}
}
}
```



## 37. 单例模式

**题目**：

手写单例模式

**思路**：

正好也有好久没写单例模式了，这边再重新全部写一下。一共其中方法，其中饿汉一种，饱汉四种，静态内部类一种，枚举一种。开搞。

```java
/**
* 首先是饿汉
* 饿汉的缺点就是如果长时间不用，那么从一开始就创建单例就会很浪费空间。但是饿汉是线程安全的，因为 static 属性只会被初始化一次
*/
class Singleton{

private static Singleton instance = new Singleton();

private Singleton(){}

public static Singleton getInstance(){
return Singleton.instance;
}

}
```

```java
/**
* 四种饱汉
*/

// 饱汉0，优点是不会浪费空间，缺点是多线程下会重复创建，造成问题
class Singleton0{

private static Singleton0 instance = null;

private Singleton0(){}

public static Singleton0 getInstance(){
if(instance == null)
instance = new Singleton0();
return Singleton0.instance;
}

}

// 饱汉1，优点是解决了线程安全问题，缺点是 synchronized 修饰整个方法，多线程抢锁浪费时间
class Singleton1{

private static Singleton1 instance = null;

private Singleton1(){}

public synchronized static Singleton1 getInstance(){
if(instance == null)
instance = new Singleton1();
return Singleton1.instance;
}
}

// 饱汉2, double check,优点是将同步代码块细粒度话，缺点是如果一个线程刚分配完空间还没有进行初始化，可能就被另一个线程拿去用了
class Singleton2{

private static Singleton2 instance = null;

private Singleton2(){}

public static Singleton2 getInstance(){
if(instance == null){
synchronized(Singleton2.class){
if(instance == null)
instance = new Singleton2();
}
}
return instance;
}
}

// 饱汉3，改进版 double check，优点是一定程度上解决了原版的问题，缺点是如果遇到反射还是不能根本上解决不暴露构造函数的问题
class Singleton3{

private static volatile Singleton3 instance = null;

private Singleton3(){}

public static Singleton3 getInstance(){
if(instance == null){
synchronized(Singleton3.class){
if(instance == null)
instance = new Singleton3();
}
}
return instance;
}
}
```

```java
/**
* 静态内部类版
* 优点是：
* 1. 有饿汉的优点，static 关键字只会初始化一次
* 2. 静态内部类的优点在于只有在外部类调用 getInstance 时才会进行内部类的初始化。
* 3. 解决了反射的问题
*/
class Singleton{

private Singleton(){}

private static class InstanceHolder{
private final static Singleton instance = new Singleton();
}

public static Singleton getInstance(){
return InstanceHolder.instance;
}

}
```

```java
/**
* 枚举类
* 优点是：
* 除了防止了反射，还能防止反序列化重新创建新的对象的问题，最提倡的写法
*/
class Singleton{

private Singleton{}

private static enum SingletonEnum{

INSTANCE;

private Singleton instance;

private SingletonEnum(){
singleton = new Singleton();
}

public Singleton getInstance(){
return instance;
}

}

public static Singleton getInstance(){
return SingletonEnum.Instance.getInstance;
}
}
```



## 38. 合并区间

**leetcode 原题链接**：[56. 合并区间](https://leetcode-cn.com/problems/merge-intervals/)

**难度级别**：中等

**题目**：

给出一个区间的集合，请合并所有重叠的区间。

**示例1**：

>输入: [[1,3],[2,6],[8,10],[15,18]]
输出: [[1,6],[8,10],[15,18]]
解释: 区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

**示例2**：

>输入: [[1,4],[4,5]]
输出: [[1,5]]
解释: 区间 [1,4] 和 [4,5] 可被视为重叠区间。

**思路**：

我觉得吧，应该只能暴力解法了。首先将 intervals 按照左边起点进行从小到大的排序，然后判断右端点的位置，是否进行更新。

```java
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList<>();
if (intervals.length == 0 || intervals == null)
return res.toArray(new int[0][]);
// 对起点终点进行排序
Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
int i = 0;
while (i < intervals.length) {
int left = intervals[i][0];
int right = intervals[i][1];
// 如果有重叠，循环判断哪个起点满足条件
while (i < intervals.length - 1 && intervals[i + 1][0] <= right) {
i++;
right = Math.max(right, intervals[i][1]);
}
// 将现在的区间放进res里面
res.add(new int[] { left, right });
// 接着判断下一个区间
i++;
}
return res.toArray(new int[0][]);
}
}
```



## 39. 翻转字符串中的单词

**leetcode 原题链接**：[151. 翻转字符串里的单词](https://leetcode-cn.com/problems/reverse-words-in-a-string/)

**难度级别**：中等

**题目**：

给定一个字符串，逐个翻转字符串中的每个单词。

**示例1**：

>输入: "the sky is blue"
输出: "blue is sky the"

**示例2**：

>输入: "  hello world!  "
输出: "world! hello"
解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。

**示例3**：

>输入: "a good   example"
输出: "example good a"
解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

**说明**：

* 无空格字符构成一个单词。
* 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
* 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。

**进阶**：

请选用 C 语言的用户尝试使用 O(1) 额外空间复杂度的原地解法。

**思路**：

如果不考虑额外空间复杂度的话，比较简单
```java
class Solution {
public String reverseWords(String s) {
if(s.equals("")) return "";
String[] strs = s.split(" ");
StringBuilder sb = new StringBuilder();
for(int i=strs.length-1;i>=0;i--) {
if(strs[i].equals(""))
continue;
sb.append(strs[i]).append(" ");
}
return sb.toString().trim();
}
}
```

如果考虑额外空间问题的话，Java 好像根本没法做，因为 Java 的 String 类型是不可变的。。。



## 40. 和为s的连续正整数序列

**leetcode 原题链接**：[剑指 Offer 57 - II. 和为s的连续正数序列](https://leetcode-cn.com/problems/he-wei-sde-lian-xu-zheng-shu-xu-lie-lcof/)

**难度级别**：简单

**题目**：

输入一个正整数 target ，输出所有和为 target 的连续正整数序列（至少含有两个数）。
序列内的数字由小到大排列，不同序列按照首个数字从小到大排列。

**示例1**：

>输入：target = 9
输出：[[2,3,4],[4,5]]

**示例2**：

>输入：target = 15
输出：[[1,2,3,4,5],[4,5,6],[7,8]]

**限制**：

* 1 <= target <= 10^5

**思路**：

使用双指针，当 sum < target 时，sum +=j，j++；当 sum > target 时，sum -=i，i++；否则将 i 到 j 的数字添加到数组中
```java
class Solution {
public int[][] findContinuousSequence(int target) {
int i = 1;
int j = 1;
int sum = 0;
List<int[]> list = new ArrayList<>();
while(i <= target/2){
if(sum < target) {
sum += j++;
}else if(sum > target) {
sum -= i++;
}else {
int[] k = new int[j-i];
for(int t=i;t<j;t++) {
k[t-i] = t;
}
list.add(k);
sum -= i++;
}
}
return list.toArray(new int[list.size()][]);
}
}
```



## 41. 二分查找

**题目**：

介绍下二分查找，如果我想在链表中使用二分查找，怎么做比较好？

**思路**：

二分查找就是将查找有序的范围不断均分，将查找的值和中间值进行比较，从而缩小范围。

如果在链表中使用二分查找，那就得用跳表了。另外构建一个链表，链表有两个指针，一个是 next，指向下一个节点，一个是 main，指向原链表。保持每两个主链表节点有一个跳表节点。如 redis 的 zset。



## 42. 归并排序

**题目**：

介绍一下归并排序，时间复杂度多少？

**思路**：

归并排序其实就是首先将大的范围分成多个小部分，先保证整个小部分有序，然后再将各个小部分合并成较大的有序部分，直到整个部分都有序。时间复杂度为 O(nlogn)。



## 43. LRU 算法

**leetcode 原题链接**：[146. LRU缓存机制](https://leetcode-cn.com/problems/lru-cache/)

**难度级别**：中等

**题目**：

运用你所掌握的数据结构，设计和实现一个  LRU (最近最少使用) 缓存机制。它应该支持以下操作： 获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果关键字 (key) 存在于缓存中，则获取关键字的值（总是正数），否则返回 -1。
写入数据 put(key, value) - 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字/值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。

**进阶**：

你是否可以在 O(1) 时间复杂度内完成这两种操作？

**示例**：

```
LRUCache cache = new LRUCache( 2 /* 缓存容量 */ );

cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // 返回  1
cache.put(3, 3);    // 该操作会使得关键字 2 作废
cache.get(2);       // 返回 -1 (未找到)
cache.put(4, 4);    // 该操作会使得关键字 1 作废
cache.get(1);       // 返回 -1 (未找到)
cache.get(3);       // 返回  3
cache.get(4);       // 返回  4
```

**思路**：

使用一个双向队列来保存具体的键值对，并使用一个 map 来保存 key 和节点方便常数时间查找
```java
import java.util.HashMap;
import java.util.Map;

class LRUCache {

Map<Integer, DListNode> map = new HashMap<>();
int size;
int capacity;
DListNode head;
DListNode tail;

public LRUCache(int capacity) {
this.capacity = capacity;
this.size = 0;
}

public int get(int key) {
int res = -1;
// 如果 map 中存在，那么获得节点并将节点放到头部，并返回值
if(map.containsKey(key)) {
DListNode p = map.get(key);
moveToHead(p);
return p.val;
}
// 如果 map 中不存在，那么返回 -1
return res;
}

public void put(int key, int value) {
// 如果 map 中存在，获得节点并更新，并移到头部
if(map.containsKey(key)) {
DListNode p = map.get(key);
p.val = value;
moveToHead(p);
}
// 如果 map 中不存在
// 如果没有超出容量，新建节点并放在头部
// 如果超出容量，新建节点放在头部并删除尾部节点
else {
if(capacity > size) {
DListNode p = new DListNode(key, value);
moveToHead(p);
map.put(key, p);
size++;
}else {
DListNode p = new DListNode(key, value);
moveToHead(p);
map.put(key, p);
deleteTail();
}
}
}

private void moveToHead(DListNode p) {
if(head == p)
return;
if(p == tail) {
tail = p.pre;
}
else {
if(p.pre != null)
p.pre.next = p.next;
if(p.next != null)
p.next.pre = p.pre;
}
p.pre = null;
p.next = head;
if(head != null)
head.pre = p;
head = p;
if(tail ==null)
tail = head;
}

private void deleteTail() {
if(tail != null){
tail.pre.next = null;
map.remove(tail.key);
tail = tail.pre;
}
}

class DListNode{
int key;
int val;
DListNode pre;
DListNode next;

public DListNode(int key, int val) {
// TODO Auto-generated constructor stub
this.key = key;
this.val = val;
}
}
}
```



## 44. 数据库连接池

**题目**：

数据库连接池怎么设计？

**思路**：

需要考虑的事情有：
* 连接池的总数
* 空闲时的最大个数
* 饱和策略
* 归还用完的链接



## 45. 版本数字比较

**题目**：

版本数字比较，比如"1.10.0"版本比"1.8.1"版本新，不允许使用 split 等函数

**思路**：

双指针
```java
public static boolean versionCompare(String v1, String v2) {
// 如果 v1 比 v2 新，返回 true，否则返回 false
int length1 = v1.length();
int length2 = v2.length();
int l1 = 0, l2 = 0, r1 = 0, r2 = 0;
while(r1 < length1 && r2 < length2) {
while(r1 < length1 &&v1.charAt(r1) != '.') r1 ++;
while(r2 < length2 &&v2.charAt(r2) != '.') r2 ++;
int t1 = Integer.parseInt(v1.substring(l1, r1));
int t2 = Integer.parseInt(v2.substring(l2, r2));
if(t1 > t2)
return true;
else if(t1 < t2)
return false;
l1 = ++r1;
l2 = ++r2;
}
return false;
}
```



## 46. 文件拷贝

**题目**：

某一个大文件被拆成了 N 个小文件，每个小文件编号从 0 至 N-1，相应大小分别记为 S(i)。给定磁盘空间为 C ，试实现一个函数从 N 个文件中连续选出若干个文件拷贝到磁盘中，使得磁盘剩余空间最小。

**思路**：

仔细一看，这不就是数组里面找最接近 target 的连续子数组嘛。使用双指针

```java
public int[] findNearest(int[] s, int target) {
int head = 0, tail = 0;
int rH = 0, rT = 0;
int res = s[0];
int temp = 0;
while(head<s.length && tail<s.length) {
if(temp < target) {
temp += s[tail];
tail ++;
}else if(temp > target){
temp -= s[head];
head++;
}else {
break;
}
if(Math.abs(res-target) >= Math.abs(temp - target)) {
res = temp;
rH = head;
rT = tail;
}
}
int[] ans = new int[rT - rH];
for(int i=0;i<ans.length;i++) {
ans[i] = s[rH+i];
}
return ans;
}
```



## 47. 场景题：redis 高并发

**问题**：

redis 设置高并发抢单一的东西，如何避免高并发对一个键进行访问？

**思路**：

不太懂这个问题是想问什么？是想问分布式锁呢还是高并发解决流量问题



## 48. 最大栈

（leetcode 上这题是会员专享，因此我们找一题类似的“最小栈”，题目意思差不多，仅仅是把最大换成最小）

**leetcode 原题链接**：[716.最大栈](https://leetcode-cn.com/problems/max-stack/)

**难度级别**：简单

**题目**：

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最大元素的栈。

* push(x) —— 将元素 x 推入栈中。
* pop() —— 删除栈顶的元素。
* top() —— 获取栈顶元素。
* getMax() —— 检索栈中的最大元素。

**示例**：

>输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
输出：
[null,null,null,null,-3,null,0,-2]
解释：
MaxStack maxStack = new MaxnStack();
maxStack.push(-2);
maxStack.push(0);
maxStack.push(-3);
maxStack.getMax();   --> 返回 0.
maxStack.pop();
maxStack.top();      --> 返回 0.
maxStack.getMax();   --> 返回 0.
maxStack.pop();
maxStack.getMax();   --> 返回 -2.

**思路**：

```java

class MaxStack {

Stack<Integer> data, maxStack;

/** initialize your data structure here. */
public MaxStack() {
data = new Stack<>();
maxStack = new Stack<>();
}

public void push(int x) {
data.push(x);
if(maxStack.isEmpty() || maxStack.peek() <= x) {
maxStack.push(x);
}
}

public void pop() {
int x = data.pop();
if(!maxStack.isEmpty() && maxStack.peek() == x) {
maxStack.pop();
}
}

public int top() {
return data.peek();
}

public int getMax() {
return maxStack.peek();
}
}
```



## 49. 场景题：分布式生成数据

**题目**：

分布式多个机器生成id，如何保证不重复

**思路**：

* 使用 redis、数据库获取共同 id
* 使用机器码进行 id 的生成



## 50. B+树和红黑树（未完成）

**题目**：

B+树和红黑树， 红黑树和一般的平衡二叉树，增、删、改、查的过程和效率、时间复杂度

**思路**：

暂且搁置



## 51. 找出和为 k 的数对

**leetcode 原题链接**：[剑指 Offer 57. 和为s的两个数字](https://leetcode-cn.com/problems/he-wei-sde-liang-ge-shu-zi-lcof/)

**难度级别**：简单

**题目**：

输入一个递增排序的数组和一个数字s，在数组中查找两个数，使得它们的和正好是s。如果有多对数字的和等于s，则输出任意一对即可。

**示例1**：

>输入：nums = [2,7,11,15], target = 9
输出：[2,7] 或者 [7,2]

**示例2**：

输入：nums = [10,26,30,31,47,60], target = 40
输出：[10,30] 或者 [30,10]

**限制**：

* 1 <= nums.length <= 10^5
* 1 <= nums[i] <= 10^6

**思路**：

双指针

```java
class Solution {
public int[] twoSum(int[] nums, int target) {
int i=0, j=nums.length-1;
while(i<j) {
int k = nums[i] + nums[j];
if(k>target)
j--;
else if(k<target)
i++;
else {
return new int[] {nums[i], nums[j]};
}
}
return new int[2];
}
}
```



## 52. 二叉树各层节点数

**题目**：

返回二叉树各层节点数，使用递归和非递归方法，并说明时间复杂度和空间复杂度

**思路**：

```java
// 递归方法,使用 map 来保存每一层的节点，时间复杂度为 o(n)，空间复杂度为 o(n)
class Solution {

Map<Integer, Integer> map = new HashMap<>();

public int[] nodeCount(TreeNode root) {
nodeCount(root, 0);
int[] res = new int[map.size()];
for(Integer i:map.keySet()) {
res[i] = map.get(i);
}
return res;
}

public void nodeCount(TreeNode node, int level) {
map.put(level, map.getOrDefault(level, 0) + 1);
if(node.left != null)
nodeCount(node.left, level+1);
if(node.right != null)
nodeCount(node.right, level+1);
}

}
```

```java
// 非递归方法，额外使用一个 queue 来层序遍历二叉树，时间复杂度为 o(n)，空间复杂度为 o(n)
class Solution {

static Map<Integer, Integer> map = new HashMap<>();

public int[] nodeCount(TreeNode root) {
if(root == null)
return new int[0];
Queue<TreeNode> queue = new LinkedList<>();
queue.add(root);
int level = 0;
while(!queue.isEmpty()) {
int size = queue.size();
for(int i=0;i<size;i++) {
TreeNode t = queue.poll();
if(t.left != null)
queue.add(t.left);
if(t.right != null)
queue.add(t.right);
}
map.put(level, size);
level ++;
}

int[] res = new int[map.size()];
for(Integer i:map.keySet()) {
res[i] = map.get(i);
}
return res;
}

}

```



## 53. 输出下一个更大的数字

**题目**：

给定一个正整数，找到由相同数字组成的下一个更大的数字

**示例**：

>输入：314
输出：341

**思路**：

从末尾开始，尽量从低位开始将大的换到前面。比如 127374, 4 和 3 交换比 7 和 3 交换要好。

```java
class Solution {

public int nextNumber(int num) {
char[] chars = String.valueOf(num).toCharArray();
int length = chars.length;
outter: for(int i=length-1;i>0;i--) {
for(int j=i-1;j>=0;j--) {
if(chars[i] > chars[j]) {
char temp = chars[i];
chars[i] = chars[j];
chars[j] = temp;
break outter;
}
}
}
return Integer.parseInt(new String(chars));
}
}
```



## 54. 输出字符串数组？（题目看不懂）

**题目**：

（这是原博的描述）
算法：输入List<String>，删除当中形如”1_”的，返回原来的List (2)

**思路**：

其实就是将 List 中的 `数字 + '_'` 开头的给删去。考察的是 Java 中迭代器的写法，我们知道，普通的 for 在循环时修改原 List 会报错。

```java
class Solution{
public List<String> updateList(List<String> list){
Iterator<String> it = list.iterator();
while(it.hasNext()){
boolean numberFlag = false;
boolean flag = false;
String s = it.next();
// 检查格式
for(int i=0;i<s.length();i++){
if(s.charAt(i) <= '9' && s.charAt(i) >= '0')
numberFlag = true;
if(s.charAt(i) == '_'){
flag = true;
}
if((s.charAt(i) > '9' || s.charAt(i) < '0') && s.charAt(i) != '_') {
break;
}
}
if(flag && numberFlag){
it.remove();
}
}
return list;
}
}
```



## 55. 缺失的第一个正数

**leetcode 原题链接**：[41. 缺失的第一个正数](https://leetcode-cn.com/problems/first-missing-positive/)

**难度级别**：困难

**题目**：

给你一个未排序的整数数组，请你找出其中没有出现的最小的正整数。

**示例1**：

>输入: [1,2,0]
输出: 3

**示例2**：

>输入: [3,4,-1,1]
输出: 2

**示例3**：

>输入: [7,8,9,11,12]
输出: 1

**思路**：

用位图法，遍历数组将值为 i 的数字转移到下标为 i-1 的位置。再次遍历查看不对的值即可。
```java
class Solution {
public int firstMissingPositive(int[] nums) {
int n = nums.length;
for (int i = 0; i < n; ++i) {
while (nums[i] > 0 && nums[i] <= n && nums[nums[i] - 1] != nums[i]) {
int temp = nums[nums[i] - 1];
nums[nums[i] - 1] = nums[i];
nums[i] = temp;
}
}
for (int i = 0; i < n; ++i) {
if (nums[i] != i + 1) {
return i + 1;
}
}
return n + 1;
}
}
```



## 56. 场景题：抛硬币问题

**题目**：

一个硬币，正面概率0.7，反面概率0.3，现在有一瓶水，怎么掷能让两个人公平的喝到水

**思路**：

只要保证两个人喝水的概率一直即可。将硬币抛两次，那么出现情况的概率如下：
情况|正（第一次）|反（第一次）
---|---|---
正（第二次）|0.49|0.21
反（第二次）|0.21|0.09

那么显然，只要让两个一正一反的情况出现时让他们分别喝水，否则重抛即可。



## 57. 两个栈实现队列

**leetcode 原题链接**：[剑指 Offer 09. 用两个栈实现队列](https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/)

**难度级别**：简单

**题目**：

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

**示例1**：

>输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

**示例2**：

>输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]

**提示**：

* 1 <= values <= 10000
* 最多会对 appendTail、deleteHead 进行 10000 次调用

**思路**：

比较简单，直接上代码
```java
class CQueue {

Stack<Integer> stackA;
Stack<Integer> stackB;

public CQueue() {
stackA = new Stack<>();
stackB = new Stack<>();
}

public void appendTail(int value) {
stackB.push(value);
}

public int deleteHead() {
if(stackA.isEmpty()) {
while(!stackB.isEmpty()) {
stackA.push(stackB.pop());
}
}
if(stackA.isEmpty()) {
return -1;
}else {
return stackA.pop();
}
}
}

/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
```



## 58. 二叉树右视图

**题目**：

（一道看不懂说明的题）
二叉树右视图



## 59. 概率题：扑克牌

**题目**：

54张扑克牌，平均分成3份，大小王在一份的概率

**思路**：

去掉一些没用的牌，其实就变成了 6 张牌分成三堆，大小王在一堆的概率。其实就是1/(6 * 5 / 2) = 1/15。



## 60. 有序有重复数组查找范围

**leetcode 原题链接**：[34. 在排序数组中查找元素的第一个和最后一个位置](https://leetcode-cn.com/problems/find-first-and-last-position-of-element-in-sorted-array/)

**难度级别**：中等

**题目**：

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

**示例1**：

>输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]

**示例2**：

>输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

**思路**：

想要算法时间复杂度是 o(logn) 级别，那么显然得用二分查找。

```java
class Solution {
public int[] searchRange(int[] nums, int target) {
if(nums.length == 0) return new int[] {-1,-1};
int index = binaryFind(nums, target, 0, nums.length - 1);
if(index == -1)
return new int[] {-1,-1};
int left = index-1, right = index+1;
while(left>=0 && nums[left] == target) left--;
while(right<nums.length && nums[right] == target) right++;
return new int[] {left + 1, right-1};
}

public int binaryFind(int[] nums, int target, int left, int right) {
while(left < right) {
int mid = (left + right) / 2;
if(nums[mid] > target) {
right = mid;
}else if(nums[mid] < target){
left = mid + 1;
}else {
return mid;
}
}
if(nums[left] == target)
return left;
return -1;
}
}
```



## 61. 三数之和

**leetcode 原题链接**：[15. 三数之和](https://leetcode-cn.com/problems/3sum/)

**难度级别**：中等

**题目**：

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

**示例**：

>给定数组 nums = [-1, 0, 1, 2, -1, -4]，
满足要求的三元组集合为：
[
[-1, 0, 1],
[-1, -1, 2]
]

**思路**：

明显排序 + 三指针

```java
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
Arrays.sort(nums);
List<List<Integer>> res = new ArrayList<>();
for(int k = 0; k < nums.length - 2; k++){
if(nums[k] > 0) break;
if(k > 0 && nums[k] == nums[k - 1]) continue;
int i = k + 1, j = nums.length - 1;
while(i < j){
int sum = nums[k] + nums[i] + nums[j];
if(sum < 0){
while(i < j && nums[i] == nums[++i]);
} else if (sum > 0) {
while(i < j && nums[j] == nums[--j]);
} else {
res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
while(i < j && nums[i] == nums[++i]);
while(i < j && nums[j] == nums[--j]);
}
}
}
return res;
}

}
```



## 62. 扫码登录

**题目**：

扫码登录是如何实现的？

**思路**：

答案来源于[博客](https://www.jianshu.com/p/7f072ac61763)

主要分成四个步骤：
* (1) 访问网站，网站服务器为当前会话生成一个全局唯一的 ID
* (2) 手机相关 APP 扫码，提示当前账号是否登录
* (3) app 将当前登录的账号信息和扫描得到的全局唯一的 ID 提交到服务器
* (4) 服务器将该 ID 和账号信息绑定，并通知网站登录该账号



## 63. 思考题：赛马

**题目**：

64匹马，8个跑道，选跑最快的4匹马需要比赛多少次

**思路**：

首先将 64 匹马分成 8 组进行赛跑，取每组最快的 4 匹马。然后将这 32 匹分 4 组赛跑，再取 每组最快的 4 匹。再将剩下的 16 匹分两组跑，取最快的 8 匹再跑一次。因此答案是 8 + 4 + 2 + 1 = 15 次。



## 64. 思考题：抛硬币

**题目**：

两个人轮流抛硬币，先抛到正面的赢，问先抛的人赢的概率

**思路**：

题目没有额外说明，那么我们认为甲乙投硬币每次正反的概率都是 0.5。

假设甲先投，那么甲赢的概率为 0.5（第一次投直接赢了） + 0.5 * (0.5 * 0.5)（第一次投没赢，乙投也没赢，第二次投赢了） + 0.5 * (0.5 * 0.5) * (0.5 * 0.5) + ···，我们可以看出这是一个等比数列求和，因此 P(甲) = a1 * (1 - q^n) /(1-q)，这边 q 显然为 0.5 * 0.5 = 0.25，带入的 P(甲) = 3 * (1 - 0.25^n) / 8。取极限 n -> 正无穷，因此 P(甲) = 3/8



## 65. 三个线程循环打印ABC

**题目**：

三个线程循环打印ABC

**思路**：

其实考的就是多线程间通信的方法。

可以直接使用 static 变量和方法 + synchronized 争抢锁。其他方法也有，就不去搞了
```java

class TestThread implements Runnable{

private static char[] ch = {'A', 'B', 'C'};

private static int count = 0;

@Override
public void run() {
// TODO Auto-generated method stub
for(;;)
print();
}

private static synchronized void print() {
System.out.print(ch[count % 3]);
count ++;
}

}

class Solution {

public static void main(String[] args) {
new Thread(new TestThread()).start();
new Thread(new TestThread()).start();
new Thread(new TestThread()).start();

}

}
```



## 66. 数组中第K大的数

**leetcode 原题链接**：[215. 数组中的第K个最大元素](https://leetcode-cn.com/problems/kth-largest-element-in-an-array/)

**难度级别**：中等

**题目**：

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

**示例1**：

>输入: [3,2,1,5,6,4] 和 k = 2
输出: 5

**示例2**：

>输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4

**思路**：

首先想到的是堆排。

```java
class Solution{
public int findKthLargest(int[] nums, int k) {
final PriorityQueue<Integer> queue = new PriorityQueue<>();
for (int val : nums) {
queue.add(val);
if (queue.size() > k)
queue.poll();
}
return queue.peek();
}
}
```

快排也行
```java
class Solution{
public int findKthLargest(int[] nums, int k) {
Arrays.sort(nums);
return nums[nums.length - k];
}
}
```



## 67. top k

**题目**：

返回一个数组中前 k 个大的或者小的数字

**思路**：

先排序后输出。可用的排序方法比如说快排，不过最接近的思想应该是堆排



## 68. 狼和羊的故事（未解决）

**题目**：

一个农场中有狼和羊，现在要将他们用围栏分开，问最少需要多少围栏。

**思路**：

最小割算法



## 69. 二叉排序树找第k大的元素

**题目**：

利用二叉排序树的性质找第k大的元素

**思路**：

我们知道，二叉排序树的前序遍历时递增的，因此可以先将二叉排序树的节点前序遍历后返回倒数第 k 个即可。

或者采用前序遍历的逆思想，从最右节点开始遍历，遍历到第 k 个即可。



## 70. 链表求和

**leetcode 原题链接**：[面试题 02.05. 链表求和](https://leetcode-cn.com/problems/sum-lists-lcci/)

**难度级别**：中等

**题目**：

给定两个用链表表示的整数，每个节点包含一个数位。
这些数位是反向存放的，也就是个位排在链表首部。
编写函数对这两个整数求和，并用链表形式返回结果。

**示例**：

>输入：(7 -> 1 -> 6) + (5 -> 9 -> 2)，即617 + 295
输出：2 -> 1 -> 9，即912

进阶：假设这些数位是正向存放的，请再做一遍。

**示例**：

>输入：(6 -> 1 -> 7) + (2 -> 9 -> 5)，即617 + 295
输出：9 -> 1 -> 2，即912

**思路**：

加一个标志位即可

```java
/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int flag = 0;
ListNode head = new ListNode(0);
ListNode p = head;
while(l1 != null && l2 != null){
int newVal = l1.val + l2.val + flag;
flag = newVal / 10;
p.next = new ListNode(newVal % 10);
p = p.next;
l1 = l1.next;
l2 = l2.next;
}
while(l1 != null){
int newVal = l1.val + flag;
flag = newVal / 10;
p.next = new ListNode(newVal % 10);
p = p.next;
l1 = l1.next;
}
while(l2 != null){
int newVal = l2.val + flag;
flag = newVal / 10;
p.next = new ListNode(newVal % 10);
p = p.next;
l2 = l2.next;
}
if(flag == 1){
p.next = new ListNode(1);
}
return head.next;
}
}
```

进阶：

只需要将链表先反转一下即可。

```java
/**
* Definition for singly-linked list.
* public class ListNode {
*     int val;
*     ListNode next;
*     ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 反转链表
ListNode dummy = null;
while(l1 != null){
ListNode temp = l1.next;
l1.next = dummy;
dummy = l1;
l1 = temp;
}
l1 = dummy;
dumm = null;
while(l2 != null){
ListNode temp = l2.next;
l2.next = dummy;
dummy = l2;
l2 = temp;
}
l2 = dummy;
// 反转结束，开始相加
int flag = 0;
ListNode head = new ListNode(0);
ListNode p = head;
while(l1 != null && l2 != null){
int newVal = l1.val + l2.val + flag;
flag = newVal / 10;
p.next = new ListNode(newVal % 10);
p = p.next;
l1 = l1.next;
l2 = l2.next;
}
while(l1 != null){
int newVal = l1.val + flag;
flag = newVal / 10;
p.next = new ListNode(newVal % 10);
p = p.next;
l1 = l1.next;
}
while(l2 != null){
int newVal = l2.val + flag;
flag = newVal / 10;
p.next = new ListNode(newVal % 10);
p = p.next;
l2 = l2.next;
}
if(flag == 1){
p.next = new ListNode(1);
}
return head.next;
}
}
```



## 71. 穿墙术（未解决）

**题目**：

可以看[博客](https://blog.csdn.net/xiaoqitu7/article/details/50397208?locationNum=3&fps=1)




## 72. 场景题：定时任务

**题目**：

系统中有几万个任务需要在各自的特定时刻触发执行，怎么做？

**思路**：

使用 Quartz，或者使用这种思想。



## 73. 二叉树的最近公共祖先 + 搜索二维矩阵 II +  最长不含重复字符的子字符串

这里有三题。

### (1) 二叉树的最近公共祖先(同题 19)

**leetcode 原题链接**：[236. 二叉树的最近公共祖先](https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/)

**难度级别**：中等

**题目**：

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树:  root = [3,5,1,6,2,0,8,null,null,7,4]

```
3
/   \
5 1
/ \   / \
6   2 0   8
/ \
7   4
```

**示例1**：

>输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

**示例2**：

>输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

**说明**：

* 所有节点的值都是唯一的。
* p、q 为不同节点且均存在于给定的二叉树中。

**思路**：

递归

```java
/**
* Definition for a binary tree node.
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null || p == root || q == root)
return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left == null)
return right;
if(right == null)
return left;
return root;
}
}
```

### (2) 搜索二维矩阵 II

**leetcode 原题链接**：[240. 搜索二维矩阵 II](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/)

**难度级别**：中等

**题目**：

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：

* 每行的元素从左到右升序排列。
* 每列的元素从上到下升序排列。

**示例**：

现有矩阵 matrix 如下：

```
[
[1,   4,  7, 11, 15],
[2,   5,  8, 12, 19],
[3,   6,  9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
```

给定 target = 5，返回 true。

给定 target = 20，返回 false。

**思路**：

切割数组

```java
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if(matrix.length == 0)
return false;
int m = matrix.length, n = matrix[0].length;
int i=0,j=n-1;
while(i<m && j>=0) {
if(matrix[i][j] < target) {
i++;
}else if(matrix[i][j] > target) {
j--;
}else {
return true;
}
}
return false;
}
}
```

### (3) 最长不含重复字符的子字符串

**leetcode 原题链接**：[剑指 Offer 48. 最长不含重复字符的子字符串](https://leetcode-cn.com/problems/search-a-2d-matrix-ii/)

**难度级别**：中等

**题目**：

请从字符串中找出一个最长的不包含重复字符的子字符串，计算该最长子字符串的长度。

**示例1**：

>输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

**示例2**：

>输入: "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

**示例3**：

>输入: "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

**提示**：

* s.length <= 40000

**思路**：

使用双指针加 set

```java
class Solution {
public int lengthOfLongestSubstring(String s) {
Set<Character> set = new HashSet<>();
int left = 0, right = 0, max = 0;
while(right < s.length()) {
while(set.contains(s.charAt(right))) {
set.remove(s.charAt(left));
left++;
}
set.add(s.charAt(right));
right++;
max = Math.max(right - left, max);
}
return max;
}
}
```



## 73. 场景题：微博关注列表

**题目**：

一个很复杂的场景，大概是微博用户有个关注列表，以及知道各种大V的动态，设计数据结构啥的，到最后在用户这边显示一个更新微博列表

**思路**：

可以看[博客](https://www.cnblogs.com/linguoguo/p/11565553.html)



## 74. 场景题：游戏中的 debuff

**题目**：

游戏里，一个玩家可能吃到很多种debuff，每个debuff有一定持续时间。给你一个定时器，怎么设计数据结构，来维护玩家的debuff状态？

**思路**：

这个不太懂。。可能用一个队列加定时器？



## 75. 场景题：红黑树，B+树，跳表应用场景

**题目**：

红黑树，B+树，跳表应用场景

**思路**：

红黑树 - HashMap；
B+ 树 - Mysql inoodb 索引结构；
跳表 - redis 的数据结构 zset



## 76. “马”在棋盘上的概率

**leetcode 原题链接**：[688. “马”在棋盘上的概率](https://leetcode-cn.com/problems/knight-probability-in-chessboard/)

**难度级别**：中等

**题目**：

已知一个 NxN 的国际象棋棋盘，棋盘的行号和列号都是从 0 开始。即最左上角的格子记为 (0, 0)，最右下角的记为 (N-1, N-1)。

现有一个 “马”（也译作 “骑士”）位于 (r, c) ，并打算进行 K 次移动。

如下图所示，国际象棋的 “马” 每一步先沿水平或垂直方向移动 2 个格子，然后向与之相垂直的方向再移动 1 个格子，共有 8 个可选的位置。


现在 “马” 每一步都从可选的位置（包括棋盘外部的）中独立随机地选择一个进行移动，直到移动了 K 次或跳到了棋盘外面。

求移动结束后，“马” 仍留在棋盘上的概率。

**示例**：

>输入: 3, 2, 0, 0
输出: 0.0625
解释:
输入的数据依次为 N, K, r, c
第 1 步时，有且只有 2 种走法令 “马” 可以留在棋盘上（跳到（1,2）或（2,1））。对于以上的两种情况，各自在第2步均有且只有2种走法令 “马” 仍然留在棋盘上。
所以 “马” 在结束后仍在棋盘上的概率为 0.0625。


**注意**：

* N 的取值范围为 [1, 25]
* K 的取值范围为 [0, 100]
* 开始时，“马” 总是位于棋盘上


**思路**：

方法1：

一共的可能性有 8 ^ K 个，那我们只要返回总共的可能性即可。因此写一个递归函数计算最终可以走的方法就好了。(但是超时，仅通过了 11/21 个用例)

```java
class Solution {
public double knightProbability(int N, int K, int r, int c) {
return knightPath(N, K, r, c) * 1.0 / Math.pow(8, K);
}

// 返回一共有多少种走法
public int knightPath(int N, int K, int r, int c) {
if(r < 0 || r >N-1 || c < 0 || c > N-1)
return 0;
if(K==0)
return 1;
return knightPath(N, K-1, r + 2, c+1) + knightPath(N, K-1, r + 2, c-1)+knightPath(N, K-1, r + 1, c+2)+
knightPath(N, K-1, r + 1, c-2)+knightPath(N, K-1, r -2, c+1)+knightPath(N, K-1, r-2, c-1)+
knightPath(N, K-1, r -1, c+2)+knightPath(N, K-1, r -1, c-2);

}
}
```

方法2：

动态规划。[题解](https://leetcode-cn.com/problems/knight-probability-in-chessboard/solution/ma-zai-qi-pan-shang-de-gai-lu-by-leetcode/)

```java
class Solution {
public double knightProbability(int N, int K, int sr, int sc) {
double[][] dp = new double[N][N];
int[] dr = new int[]{2, 2, 1, 1, -1, -1, -2, -2};
int[] dc = new int[]{1, -1, 2, -2, 2, -2, 1, -1};

dp[sr][sc] = 1;
for (; K > 0; K--) {
double[][] dp2 = new double[N][N];
for (int r = 0; r < N; r++) {
for (int c = 0; c < N; c++) {
for (int k = 0; k < 8; k++) {
int cr = r + dr[k];
int cc = c + dc[k];
if (0 <= cr && cr < N && 0 <= cc && cc < N) {
dp2[cr][cc] += dp[r][c] / 8.0;
}
}
}
}
dp = dp2;
}
double ans = 0.0;
for (double[] row: dp) {
for (double x: row) ans += x;
}
return ans;
}
}
```



## 77. 场景题：大文件中的 id 计算

**题目**：

一个5T的文件，里面全是id，1-10^9 ，如何计算不同id的个数

**思路**：

如果是文件比较小，但是数字比较大的情况，可以使用位图法。但是这边正好相反，因此我们采用外部排序的方法，将 5T 的文件进行排序，然后分块遍历，计算不同 id 的个数。



## 78. 求中位数

**题目**：

一个有序数组，从随即一位截断，把前段放在后边，如 4 5 6 7 1 2 3求中位数

**思路**：

首先找到数组中被截断的位置，计算出前后的个数，判断中位数出现的位置在哪里，然后分类讨论。

* 如果中位数出现的位置在前半段，那就重新遍历对应个数；
* 如果中位数出现的位置跟前后半段都有关，即前半段的第一位和最后一位的平均值，那么直接计算即可；
* 如果中位数出现的位置在后半段，那么继续遍历即可。

但其实可以通过下标求余的情况来做。

```java
class Solution{
public double findMedian(int[] nums){
int loc = 0;
for(int i=1;i<nums.length;i++){
if(nums[i] < nums[i-1]){
loc = i-1;
break;
}
}
int length = nums.length;
// 计算被搬到后边去的元素的个数
int sub = length - 1 - loc;

if(length % 2 == 0)
return (nums[(sub + length / 2)/length] + nums[(sub + length / 2 + 1)/length])/2.0;
else{
return nums[(sub + length / 2)/length];
}
}
}
```



## 79. 输出第 n 个字符（未解决）

**题目**：

一个形如 123456789101112…… 的字符串，输入一个 n（很大很大），输出字符串第 n 个字符

**思路**：

？？？



## 80. 公交车超载

**题目**：

一辆公交车，有 m 站，最多坐 n 人，输入一路上票的信息（即上车下车站），输出会不会超载。

例如：

>输入：
7 11 [7， 2 ，-2， -1， 4， 3， 5]
输出：
true

**思路**：

这题感觉莫名简单啊，就加呗。

```java
class Solution{
public boolean overload(int m, int n, int[] nums){
int load = n;
int count = 0;
for(int i=0;i<m;i++){
count += nums[i];
if(cout > load)
return true;
}
return false;
}
}
```



## 81. 全排列

**题目**：

没有题目



## 82. 场景题：台球入洞

**题目**：

坐标系中有一个球桌，四个角坐标：(0,0), (0,4), (2,4), (2,0)，一颗球在 (1,1)，请问从哪些角度可以射入洞内（可无限次碰撞）？

**思路**：

画画图，大概 6 种？



## 83. 完全二叉树的节点个数

**题目**：

求完全二叉树的节点个数，小于O(n)，并分析复杂度

**思路**：

遍历就完了啊。。。



## 84. 链表实现一个栈

**题目**：

链表实现一个栈

**思路**：

这个比较简单，使用双向队列，然后通过一个尾指针来进行操作即可。

```java
class ListNode<T>{
ListNode pre;
ListNode next;
T value;

public ListNode(T value){
this.value = value;
}
}
class MyStack<T>{

ListNode<T> tail;

public MyStack(){

}

public ListNode put(T val){
ListNode p = new ListNode(val);
p.pre = tail;
if(tail == null)
tail = p;
else {
tail.next = p;
}
tail = p;
return p;
}

public ListNode peek() {
return tail;
}

public T pop() {
ListNode p = tail;
if(tail != null && tail.pre != null) {
tail = tail.pre;
tail.next = null;
}
return (T)p.value;
}

}
```



## 85. 加油站 + 柠檬水找零

### (1) 加油站

**leetcode 原题链接**：[134. 加油站](https://leetcode-cn.com/problems/gas-station/)

**难度级别**：中等

**题目**：

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

**说明**:

* 如果题目有解，该答案即为唯一答案。
* 输入数组均为非空数组，且长度相同。
* 输入数组中的元素均为非负数。

**示例1**：

>输入:
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

**示例2**：

>输入:
gas  = [2,3,4]
cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

**思路**：

暴力法就不谈了。

```java
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int n = gas.length;

int total_tank = 0;
int curr_tank = 0;
int starting_station = 0;
for (int i = 0; i < n; ++i) {
total_tank += gas[i] - cost[i];
curr_tank += gas[i] - cost[i];
// If one couldn't get here,
if (curr_tank < 0) {
// Pick up the next station as the starting one.
starting_station = i + 1;
// Start with an empty tank.
curr_tank = 0;
}
}
return total_tank >= 0 ? starting_station : -1;
}
}
```

### (2) 柠檬水找零

**leetcode 原题链接**：[860. 柠檬水找零](https://leetcode-cn.com/problems/lemonade-change/)

**难度级别**：简单

**题目**：

在柠檬水摊上，每一杯柠檬水的售价为 5 美元。

顾客排队购买你的产品，（按账单 bills 支付的顺序）一次购买一杯。

每位顾客只买一杯柠檬水，然后向你付 5 美元、10 美元或 20 美元。你必须给每个顾客正确找零，也就是说净交易是每位顾客向你支付 5 美元。

注意，一开始你手头没有任何零钱。

如果你能给每位顾客正确找零，返回 true ，否则返回 false 。

**示例1**：

>输入：[5,5,5,10,20]
输出：true
解释：
前 3 位顾客那里，我们按顺序收取 3 张 5 美元的钞票。
第 4 位顾客那里，我们收取一张 10 美元的钞票，并返还 5 美元。
第 5 位顾客那里，我们找还一张 10 美元的钞票和一张 5 美元的钞票。
由于所有客户都得到了正确的找零，所以我们输出 true。

**示例2**：

>输入：[5,5,10]
输出：true

**示例3**：

>输入：[10,10]
输出：false

**示例4**：

输入：[5,5,10,10,20]
输出：false
解释：
前 2 位顾客那里，我们按顺序收取 2 张 5 美元的钞票。
对于接下来的 2 位顾客，我们收取一张 10 美元的钞票，然后返还 5 美元。
对于最后一位顾客，我们无法退回 15 美元，因为我们现在只有两张 10 美元的钞票。
由于不是每位顾客都得到了正确的找零，所以答案是 false。

**提示**：

* 0 <= bills.length <= 10000
* bills[i] 不是 5 就是 10 或是 20

**思路**：

用一个 hashMap 或者一个长度为 3 的数组记录每个面值的钞票数量，并且在找零时，先把大的换出去，再换小的。比如给你 20，你应该返回 10 + 5 而不是 3 * 5，简而言之就是贪心。

```java
class Solution{
public boolean lemonadeChange(int[] bills) {
int[] cash = new int[3];
for(int i=0;i<bills.length;i++) {
if(bills[i] == 5)
cash[0] ++;
if(bills[i] == 10) {
cash[1] ++;
cash[0]--;
if(cash[0] < 0)
return false;
}
if(bills[i] == 20) {
cash[2] ++;
if(cash[1] > 0) {
cash[1] --;
cash[0]--;
if(cash[0] < 0)
return false;
}else {
cash[0] -= 3;
if(cash[0] < 0)
return false;
}
}
}
return true;
}
}
```



## 86. 堆

**题目**：

手写jdk中的优先级队列 PriorityQueue（最小堆）

**思路**：

直接看源码把，略




## 87. 圆圈剩下的数字（约瑟夫环）

**leetcode 原题链接**：[剑指 Offer 62. 圆圈中最后剩下的数字](https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-de-shu-zi-lcof/)

**难度级别**：简单

**题目**：

0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。

**示例1**：

>输入: n = 5, m = 3
输出: 3

**示例2**：

>输入: n = 10, m = 17
输出: 2

**限制**：

* 1 <= n <= 10^5
* 1 <= m <= 10^6

**思路**：

数学推论

```java
class Solution {
public int lastRemaining(int n, int m) {
int ans = 0;
// 最后一轮剩下2个人，所以从2开始反推
for (int i = 2; i <= n; i++) {
ans = (ans + m) % i;
}
return ans;
}
}
```



## 88. 和为K的子数组

**leetcode 原题链接**：[560. 和为K的子数组](https://leetcode-cn.com/problems/subarray-sum-equals-k/)

**难度级别**：中等

**题目**：

给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

**示例1**：

>输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

**说明**：

* 数组的长度为 [1, 20,000]。
* 数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。

**思路**：

使用一个 HashMap 来保存已经遍历过的数值，然后求 target - nums[i] 是否在 map 中出现过即可。

```java
class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0, pre = 0;
HashMap<Integer, Integer> mp = new HashMap<>();
mp.put(0, 1);
for (int i = 0; i < nums.length; i++) {
pre += nums[i];
if (mp.containsKey(pre - k))
count += mp.get(pre - k);
mp.put(pre, mp.getOrDefault(pre, 0) + 1);
}
return count;
}
}
```



## 89. 设计模式

**题目**：

说说你知道的设计模式，说说项目里用到的设计模式，说说策略模式，设计一个下棋的场景问如何结合设计模式使用，设计模式什么时候继承，什么时候委托？

**思路**：

略




## 90. 代码输出

**题目**：

以下代码题输出什么？

```java
Map<Short, String> map = new HashMap<>();
for(short i = 0; i <100; i++) {
map.put(i, String.valueOf(i));
map.remove(i-1);
}
System.out.println(map.size());
```

**思路**：

答案是`100`。

归根结底是因为`map.remove(i-1)`这句代码并没有对 map 进行修改。为什么呢？尝试给 i-1 做强制类型转换，`(Short)(i-1)`，结果报`cannot cast from int to Short`，因此我们可以知道 remove 的 key 使用的是 int 类型，因此 map 根本不会删除对应的 key。

但是可能有人会问了，明明上面声明 map 的时候限定了 key 是 Short 类型啊，为什么使用 int 不会报错呢？这就涉及到泛型的类型擦除问题了，其实无论你声明的时候用的 key 是 Integer 还是 String，在编译后都不会保存这些信息。
#字节提前批##字节跳动##笔试题目#