### 经典排序篇

#### 冒泡排序

``` public static int[]  BubbleSortTest(int[] arr){
int flag=0; //如果一轮扫描后，发现没有要冒泡的那就直接退出
for(int i=1;i<arr.length;i++){//外循环从第二个开始
for(int j=0;j<arr.length-i;j++){
if(arr[j]>arr[j+1]){
int tem=arr[j+1];
arr[j+1]=arr[j];
arr[j]=tem;
flag++;
}
}
if(flag==0){
break;
}
}
return arr;
}```

#### 归并排序

```public static void sort(int[] arr, int l, int r, int[] tmp) {
if (r > l) {
int mid = (l + r) / 2;
sort(arr, l, mid, tmp);
sort(arr, mid + 1, r, tmp);
mergeSort(arr, l, mid, r, tmp);
}
}

//真正归并
public static void mergeSort(int[] arr, int left, int mid, int right, int[] temp) {
System.out.print("Merge次数"); // 3, 4, 2, 1, -7, 0
int i = left;
int j = mid + 1;
int t = 0;
while (i <= mid && j <= right) {
if (arr[i] > arr[j]) {
temp[t++] = arr[j++];
} else {
temp[t++] = arr[i++];
}
}
while (i <= mid) {
temp[t++] = arr[i++];
}
while (j <= right) {
temp[t++] = arr[j++];
}
t = 0;
while (right >= left) {
arr[left++] = temp[t++];
}
}```

#### 插入排序

``` public static int[] InsertTest(int[] arr) {
for (int j = 1; j < arr.length; j++) {
int tar = arr[j]; //挑一个数，不断往前插入（打牌）
int count = j - 1;
while (count >= 0 && arr[count] > tar) {
arr[count + 1] = arr[count];
count--;
}
arr[count + 1] = tar;
}
return arr;
}```

#### 希尔排序

```//与插入排序类似，不过一次往前挪jap个位置
public static int[] ShellSort(int[] arr) {
for (int jap = arr.length / 2; jap > 0; jap /= 2) {
for (int i = jap; i < arr.length; i++) {
int x = i;
while (x - jap >= 0 && arr[x] < arr[x - jap]) {
int tmp = arr[x];
arr[x] = arr[x - jap];
arr[x - jap] = tmp;
x = x - jap;
}
}
}
return arr;
}```

#### 快速排序

```public static void QuickSort(int[] arr, int low, int high) {
int l = low;
int r = high;
if (l > r) {
return;
}
int tar = arr[l];
while (r > l) {
while (r > l && arr[r] > tar) {
r--;
}
arr[l] = arr[r];
while (r > l && arr[l] < tar) {
l++;
}
arr[r] = arr[l];
}
arr[l] = tar;
QuickSort(arr, low, l - 1);
QuickSort(arr, l + 1, high);
}```

#### 选择排序

```public static int[] selectSort(int arr[]) {
for (int i = 0; i < arr.length; i++) {
int min = i; //找到最小的下标
for (int j = i + 1; j < arr.length; j++) { //自从i  之前的 肯定都是有序的  下一次找最小的值 就从 i之后开始查找
min = arr[j] > arr[min] ? min : j;
}
// 前面的值和最小的下标做交换
int tmp = arr[i];
arr[i] = arr[min];
arr[min] = tmp;
}
return arr;
}```

#### 堆排序（寻找前K大）

```   // 学习使用堆 并排序返回
public static ArrayList<Integer> Solution(int[] arr, int k) {
if (arr.length < k) {
return new ArrayList<Integer>();
}
ArrayList<Integer> res =new ArrayList<Integer>();
//创建前K个数
int[] a = new int[k];
for (int i = 0; i < k; i++) {
a[i] = arr[i];
}

//前K个数 维持一个大根堆
for(int i=k/2 -1;i>=0;i--){
BigHeap(a,i,k);
}
//后面len - k个数 进入堆中维持一个大顶堆
for(int i=k;i<arr.length;i++){
if(arr[i]<a[0]){
a[0] = arr[i];
BigHeap(a,0,k);
}
}
//将大顶堆输出 就是堆排序
for(int  i =a.length-1; i>=0;i--){
int tem=a[i];
a[i] =a[0];
a[0] =tem;
BigHeap(a,0,i);
}

for(int x:a){
}

return res;
}

//维护这个堆（大根堆）
public static void BigHeap(int[] arr,int index ,int len){
int temp =arr[index];
for(int k = 2*index+1;k<len;k=2*k +1){
if((k+1)<len && arr[k+1] > arr[k]){
k++;
}
if(temp<arr[k]){
arr[index] =arr[k];
index=k;
}else{
break;
}
}
arr[index] =temp;
}```

### 链表篇

#### K个一组反转链表

```https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=190&tqId=35192&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey

public ListNode reverseKGroup (ListNode head, int k) {
ListNode res =new ListNode(0);
int length=0;
// 先知道链表长度，看看你需要分成几组进行反转
length++;
}
//链表所有的操作都是从后面往前面维护
for(int i=0;i<length/k;i++){//分成length/k个组进行反转
for(int j=1;j<k;j++){ // 类似于头插法
temp=cur.next;
cur.next=temp.next;
temp.next=pre.next; //链表所有的操作都是从后面往前面维护
pre.next=temp;
}
pre=cur;
cur=cur.next;
}

return res.next;
}
```

#### LRU缓存结构

```Least Recently Used (LRU 最近最少使用)

// 先定义类变量
HashMap<String,lrNode> map=new HashMap<>();//使用map存储双向链表
lrNode tail; //定义链表尾部
int capcity =3; //缓存的容量
//put方法
public void put(String key ,Object val){
// 如果链表为空，直接将头尾设置成该值
}
//否则的话去map中看一下这个key存在否
lrNode node=map.get(key);
if(node!=null){
node.val=val;
removeAndInsert(node);
}else{
lrNode tmp=new lrNode(key,val);
//不存在，需要放进map中，放入前先判断容量是否满了
if(map.size()>=capcity){
map.remove(tail.key);
tail=tail.pre;
tail.next=null;
}
map.put(key,tmp);
}
//get 方法
public int get(String key ){
lrNode tmp=map.get(key);
if(tmp!=null){
return tmp.val;
removeAndInsert(tmp);
}else{
return -1;
}
}
}

// 将该节点放入头节点
public void removeAndInsert(lrNode node){
//如果本身是头节点那就直接返回
return;
}else if(node ==tail ){
//删除尾节点
tail=tail.pre;
tail.next=null;
}else {
//中间节点  那也删除
node.next.pre =node.pre;
node.pre.next=node.next;
}
//删除完事了 ，然后插入到头节点
node.pre=null;
}
// 定义lrNode的数据结构
class lrNode(){
Object val;
String key ;
lrNode next;
lrNode pre;
lrNode(String key ,Object val){
this.key=key;
this.val=val;
}
}```

#### 两个链表第一个公共节点

```https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

while(p1.val!=p2.val){
p1=p1.next;
p2=p2.next;
if(p1.val==p2.val){
return p1;
}
if(p1==null){
}
if(p2==null){
}
}
return p1;
}
```

#### 两数相加

```来源：力扣（LeetCode）

public static ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode a=l1;
ListNode b=l2;
ListNode ans=new ListNode(0); //存储结果
ListNode tmp=ans;
int cary=0; //存储进位
while(a!=null||b!=null||cary!=0){
int m=a==null?0:a.val;
int n=b==null?0:b.val;
int sum =m+n+cary;
cary=sum/10;
int res=sum%10;
ListNode k=new ListNode(res);
tmp.next=k;
tmp=tmp.next;
if(a!=null){
a=a.next;
}
if(b!=null){
b=b.next;
}
}
return ans.next;
}```

#### 从尾到头打印链表

```https://www.nowcoder.com/practice/d0267f7f55b3412ba93bd35cfa8e8035?tpId=13&tqId=11156&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
{67,0,24,58}

[58,24,0,67]

static ArrayList<Integer> ans = new ArrayList<>();
//使用递归方式加入
public static ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
if (listNode != null) {
System.out.println(listNode.val);
}
return ans;

}```

#### 删除倒数第K个节点

```https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=117&tqId=37750&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

public static ListNode removeNthFromEnd(ListNode head, int n) {
ListNode cur = new ListNode(0);
ListNode one = cur;
ListNode two = cur;
while (n +1 != 0) { //因为前面给链表头加了头
one = one.next;
n--;
}
while (one != null) {
one = one.next;
two = two.next;
}
two.next = two.next.next;
return cur.next;
}

```

#### 删除链表中重复的节点

```public ListNode deleteDuplication(ListNode pHead) {
}
ListNode ans = new ListNode(0);
ListNode pre = ans;
ListNode last = ans.next; //试探指针
while (last != null) {
if (last.next != null && last.val == last.next.val) { //试探一下是否连续相等
while (last.next != null && last.val == last.next.val) {
last = last.next;
}
pre.next = last.next;
last = last.next;
} else {
pre = pre.next;
last = last.next;
}
}
return ans.next;
}

```

#### 判断链表是否有环

```public static boolean isLoopNodelist(ListNode head){
while(fast!=null&& fast.next!=null){
fast=fast.next.next;
slow=slow.next;
if(fast!=null&&fast.val==slow.val){
return true;
}
}
return false;
}```

#### 寻找第一个入环节点

```https://www.nowcoder.com/practice/6e630519bf86480296d0f1c868d425ad?tpId=117&tqId=37713&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

return null;
}
ListNode node = new ListNode(0);
ListNode fast = node;
ListNode slow = node;
while (fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
if (fast == slow) { //找到香蕉的点，然后快慢指针一起走
fast = node; //快指针从头开始，一次只走一步
while (fast != slow) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
return null;
}```

#### 单链表倒数第K个节点

```https://www.nowcoder.com/practice/886370fe658f41b498d40fb34ae76ff9?tpId=13&tqId=11167&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

public ListNode FindKthToTail (ListNode pHead, int k) {
//需要特殊判断k比链表长度大的情况
while(k>0&& fast!=null){ //需要判断链表空了的时候 k值还比0大的情况 那就直接返回空了
fast=fast.next;
k--;
}
if(k>0){return null;}
while(fast!=null){
fast=fast.next;
slow=slow.next;
}

return slow;
}```

#### 合并有序链表

``` https://www.nowcoder.com/practice/a479a3f0c4554867b35356e0d57cf03d?tpId=190&tqId=35188&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey

public static ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if (l1 == null) {
return l2;
}
if (l2 == null) {
return l1;
}
while (l1 != null && l2 != null) {
if (l1.val > l2.val) {
ans.next = l2;
l2 = l2.next;
} else {
ans.next = l1;
l1 = l1.next;
}
ans=ans.next;
}
if (l1 != null) {
ans.next=l1;
}
if(l2!=null){
ans.next=l2;
}
}```

#### 复杂链表的复制

```https://www.nowcoder.com/practice/f836b2c43afc4b35ad6adc41ec941dba?tpId=13&tqId=11178&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
//链表的数据结构
class RandomListNode {
int label;
RandomListNode next = null;
RandomListNode random = null;

RandomListNode(int label) {
this.label = label;
}
}
//给复制出来的节点授予指针
Map<RandomListNode, RandomListNode> ans = new HashMap<>();
while (tmp != null) {
RandomListNode res = new RandomListNode(tmp.label);
ans.put(tmp, res);
tmp = tmp.next;
}
while (tmp != null) {
RandomListNode node = ans.get(tmp);
node.next = ans.get(tmp.next);
node.random = ans.get(tmp.random);
tmp = tmp.next;
}
}```

#### 逆序打印链表

```  public static ListNode reverseOrderListNode(ListNode head) {
return null;
}
// 1  4  3  ====>  3   4   1
ListNode p = new ListNode(0);
ListNode tmp = head.next;// 4   3
}
return p.next;
}```

### 树篇

#### BFS层序遍历

```https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=190&tqId=35337&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey

public static ArrayList<ArrayList<Integer>> levelOrder(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
while (list != null && list.size() != 0) {
int size = list.size();
ArrayList<Integer> tmp = new ArrayList<>();
for (int i = 0; i < size; i++) {
TreeNode node = list.poll();
if (node.left != null) {
}
if (node.right != null) {
}
}
}
return ans;
}```

#### 之字形打印二叉树

```https://www.nowcoder.com/questionTerminal/91b69814117f4e8097390d107d2efbe0

public ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
if (pRoot == null) {
return ans;
}
int num = 0;
while (list != null && list.size() != 0) {
int count = list.size(); //放了几个节点
ArrayList<Integer> res = new ArrayList<>();
while (count != 0) { //输出一个父节点  就把左右孩子节点放入到队列中
//可以用for循环也可以用while循环，输出列表的的前size
TreeNode node = list.poll();
if (node.left != null) {
}
if (node.right != null) {
}
count--; //记录放了几个节点
}
num++; //记录当前是多少层
if (num % 2 == 0) { //偶数层 从右往左
for (int i = 0, j = res.size() - 1; i < j; i++, j--) {
int tem = res.get(i);
res.set(i, res.get(j));
res.set(j, tem);
}
} else {
}
}
return ans;
}```

#### 二叉搜索树后续遍历

```https://www.nowcoder.com/practice/a861533d45854474ac791d90e447bafd?tpId=13&tqId=11176&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

左孩子最小，右孩子最大，根节点比左小，比右大
//将数组分割成两个序列，比根节点大的 和比跟节点小的
//然后记录一下各自第一个值的下标，用来判断是否连续；

public static boolean VerifySquenceOfBST(int[] sequence) {
if (sequence.length == 0) {
return false;
}
ArrayList<Integer> list = new ArrayList<>();
for (int i = 0; i < sequence.length; i++) {
}
return solve(list);
}
private static boolean solve(ArrayList<Integer> list) {
// 递归终止的条件
if (list.size() == 0 || list.size() == 1) {
return true;
}
ArrayList<Integer> minList = new ArrayList<>(); // 用来保存小于endNumber数字的序列
ArrayList<Integer> maxList = new ArrayList<>(); // 用来保存大于endNumber数字的序列
int endNumber = list.get(list.size() - 1);
int minIndex = -1; // 用来记录minList中第一个数字的位置
int maxIndex = -1; // 用来记录maxList中第一个数字的位置
// 下面这个循环其实就是对当前list序列的一个分割(分割条件就是endNumber)
for (int i = 0; i < list.size(); i++) {
if (list.get(i) > endNumber) {
if (maxIndex == -1) {
maxIndex = i; //记录第一个大于的下标
}
} else if (list.get(i) < endNumber) {
if (minIndex == -1) {
minIndex = i;//记录第一个小于的下标
}
}
}
if (minIndex != -1 && maxIndex != -1) {
if (minIndex > maxIndex) {
return false; // 本质上使右子树的序列在左子树的前面，不满足后序遍历
}
for (int i = maxIndex; i < list.size(); i++) {
if (list.get(i) < endNumber) {
return false; // 说明在大于endNumber的序列初始位置到末尾，不连续，中间有小于endNumber的数字分割开来
}
}
}
return solve(minList) && solve(maxList); // && -> 每一个子序列都是需要满足的
}```

#### 二叉树中和为某值的路径

```https://www.nowcoder.com/practice/b736e784e3e34731af99065031301bca?tpId=13&tqId=11177&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
ans = new ArrayList<>();
if (root == null) {
return ans;
}
ArrayList<Integer> list = new ArrayList<>();
resolve(root, 0, target, list);
ans.sort((o1,o2)->(o2.size()-o1.size()));
return ans;

}

private void resolve(TreeNode node, int sum, int target, ArrayList<Integer> list) {
if (node != null) {
sum += node.val;
if (node.left == null && node.right == null) {
if (sum == target) {
ArrayList<Integer> res = new ArrayList<>(list);

} else {
resolve(node.right, sum, target, list);
resolve(node.left, sum, target, list);
}
//需要回溯
list.remove(list.size()-1);
}
}```

#### 二叉树先中后遍历

```https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=190&tqId=35221&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey

//得到二叉树的 深度 size
public static int getTreeSize(TreeNode node) {
if (node == null) {
return 0;
}
return 1 + getTreeSize(node.left) + getTreeSize(node.right);

}
static int pre = 0, mid = 0, post = 0;
public static int[][] threeOrders(TreeNode root) {
// write code here
int treeSize = getTreeSize(root);
int[][] ans = new int[3][treeSize];
threeTree(root, ans);
return ans;
}

public static void threeTree(TreeNode node, int[][] arr) {
if (node == null) {
return;
}
arr[0][pre++] = node.val;
threeTree(node.left, arr);
arr[1][mid++] = node.val;
threeTree(node.right, arr);
arr[2][post++] = node.val;
}
```

#### 二叉树最大深度

```https://www.nowcoder.com/practice/8a2b2bf6c19b4f23a9bdb9b233eefa73?tpId=190&tqId=35335&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey

public int dfs(TreeNode node){
if(node==null){return 0;}
int left= 1+dfs(node.left);
int right=1+dfs(node.right);

return Math.max(left,right);
}```

#### 二叉树下一个节点

```https://www.nowcoder.com/practice/9023a0c988684a53960365b889ceaf5e?tpId=13&tqId=11210&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

//主要是分为三种情况，第一种情况就是pNode节点有右孩子时，那么pNode的下一个节点就是右孩子对应的那颗子树的最左侧的节点；
// 如果说当前节点的右孩子为空，并且pNode是pNode父亲节点的左孩子，那么直接返回pNode的父亲节点即可；
// 如果说当前节点的右孩子为空，并且pNode是pNode父亲节点的右孩子那么就返回pNode节点的爷爷节点。
// 当然还有些特殊情况，比如说：二叉树的最右侧节点的判断，以及父亲节点是否为空的判断

if (pNode.right != null) {
// 第一种情况，pNode节点的右孩子不为空  那么pNode的下一个节点就是右孩子对应的那颗子树的最左侧的节点；
pNode = pNode.right;
while (pNode.left != null) {
pNode = pNode.left;
}
return pNode;
} else {
if (tempNode == null) {
return null;
}
if (tempNode.left == pNode) {
// 第二种情况，当前节点右孩子为空，并且当前节点是父亲节点的左孩子
return tempNode;
} else {
// 第三种情况，当前节点右孩子为空，并且当前节点是父亲节点的右孩子
boolean flag = false;
while (tempNode.next != null) {
if (tempNode.next.left == tempNode) { //只要有一个路径 表示它在左边 那么就返回
flag = true;
break;
}
tempNode = tempNode.next;
}
return flag ? tempNode.next : null; // flag尾true时，说明pNode所指的节点不是二叉树中最右侧节点
}
}
}
}

int val;

this.val = val;
}```

#### 二叉树镜像

```https://www.nowcoder.com/practice/a9d0ecbacef9410ca97463e4a5c83be7?tpId=13&tqId=11171&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

public TreeNode Mirror (TreeNode pRoot) {
// write code here
if(pRoot!=null){
if(pRoot.left!=null){
Mirror(pRoot.left);
}
if(pRoot.right!=null){
Mirror(pRoot.right);
}
TreeNode tmp=pRoot.left;
pRoot.left=pRoot.right;
pRoot.right=tmp;
}
return pRoot;
}```

#### 对称二叉树判断

```https://www.nowcoder.com/practice/ff05d44dfdb04e1d83bdbdab320efbcb?tpId=13&tqId=11211&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

boolean resolve(TreeNode node1, TreeNode node2) {
if (node1 == null && node2 == null) {
return true;
}
if (node1 == null || node2 == null) {
return false;
}
if (node1.val != node2.val) {
return false;
}
return resolve(node1.left, node2.right) && resolve(node1.right, node2.left);
}```

#### 判断平衡二叉树

```https://www.nowcoder.com/practice/8b3b95850edb4115918ecebdf1b4d222?tpId=13&tqId=11192&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
// 输入一棵二叉树，判断该二叉树是否是平衡二叉树。

private int solve(TreeNode root) {
if (root == null) {
return 0;
}
if (ans) {
int leftsize = solve(root.left);
int rightsize = solve(root.right);
if (Math.abs(rightsize - leftsize) > 1) {
ans = false;
}
return Math.max(leftsize, rightsize)+1;
}
return 0;
}```

#### 树的子结构

```https://www.nowcoder.com/practice/6e196c44c7004d15b1610b9afca8bd88?tpId=13&tqId=11170&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

private boolean judge(TreeNode node1, TreeNode node2) { /// 第二部分，匹配
if (node2 == null) {
return true; /// 说明二叉树B的某一个方向的节点已经完全的匹配成功。
}
if (node1 == null) {
return false; /// 说明在某一方向上，二叉树A中的节点不缺少的，相对于二叉树B
}
if (node1.val == node2.val) {
boolean flag1 = true; /// 默认左子树是匹配的，假如说不匹配，它就会返回false
boolean flag2 = true; /// 默认右子树是匹配的，假如说不匹配，它就会返回false
if (node1.left != null || node2.left != null) {
flag1 = judge(node1.left, node2.left); /// 比较子树A和二叉树B的左子树
}
if (flag1 && (node1.right != null || node2.right != null)) { /// flag1 -> 剪枝
flag2 = judge(node1.right, node2.right); /// 比较子树A和二叉树B的右子树
}
return flag1 && flag2; /// && -> 不光某一个节点的左子树要完全匹配，右子树也是要完全匹配的
} else {
return false;
}
}

/// 二叉树的先序遍历
private boolean dfs(TreeNode node, TreeNode root2) {  /// 第一部分，查找
boolean flag = false;
if (node.val == root2.val) {
flag = judge(node, root2); /// 进入第二部分的匹配过程
}
if (flag) {
return true; /// 通过当前节点已经找到二叉树B的完全匹配结果了，就没有必要再往下去遍历二叉树A了。也可以说是剪枝过程
}
boolean flag1 = false; /// 用来记录当前节点的左子树中的查找结果(其实也是包含了匹配的过程)，如果查找成功（包含了匹配过程）返回true
boolean flag2 = false; /// 用来记录当前节点的右子树中的查找结果(其实也是包含了匹配的过程)，如果查找成功（包含了匹配过程）返回true
if (node.left != null) {
flag1 = dfs(node.left, root2); /// 当前节点的val不等于二叉树B的root值，那么就去遍历当前节点的左子树，看否找到二叉树B
}
if ((!flag1) && node.right != null) { /// !flag1-》剪枝
flag2 = dfs(node.right, root2); /// 当前节点的val不等于二叉树B的root值，那么就去遍历当前节点的右子树，看否找到二叉树B
}
return flag1 || flag2; /// || -》只需要找到节点的某一个方向的子树进行匹配成功就行了
}```

#### 重建二叉树

```https://www.nowcoder.com/practice/8a19cbe657394eeaac2f6ea9b0f6fcf6?tpId=190&tqId=35426&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
/**输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

int[]  pre={1,2,3,4,5,6,7};
int[]   in={3,2,4,1,6,5,7};
*/
public static TreeNode myDfs(int[] p,int pl,int pr,int[] in,int il,int ir){
if (pl>pr || il >ir){
return  null;
}
TreeNode tree = new TreeNode(p[pl]);
int mid =0;
for(int i=0;i<=ir;i++ ){
if(tree.val==in[i]){
mid =i;
break;
}
}
int leftCount = mid -il;
int rightCount =ir -mid;

tree.left=myDfs(p,pl+1,pl+leftCount,in,il,mid-1);
tree.right=myDfs(p,pr-rightCount+1,pr,in,mid+1,ir);
return  tree;
}```

### 字符串篇

#### 大数加法

``` public static String solve(String s, String t) {
StringBuilder ans = new StringBuilder();
int a = s.length() - 1;
int b = t.length() - 1;
int carry = 0;
while (a > 0 || b > 0 || carry != 0) {
int m = a < 0 ? 0 : s.charAt(a--)-'0'; //字符 需要-’0‘ 才能转换成数字
int n = b < 0 ? 0 : t.charAt(b--)-'0';
int  sum = m + n + carry;
ans.append(sum % 10);
carry = sum / 10;
}
return ans.reverse().toString();
}```

#### 字符串全排列

```https://www.nowcoder.com/practice/fe6b651b66ae47d7acce78ffdd9a96c7?tpId=13&tqId=11180&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

static ArrayList<String> res = new ArrayList<String>();

public static ArrayList<String> Permutation(String str) {
ArrayList<String> ans = new ArrayList<String>();
char[] tmp = str.toCharArray();
reserve(tmp, 0, tmp.length );
ans=new ArrayList<String>(new HashSet<>(res));
Collections.sort(ans);
return ans;
}

public static void reserve(char[] arr, int index, int length) {
if (index == length) {
System.out.println(change(arr));
return;
}
for (int i = index; i < length; i++) {
char tem = arr[i];
arr[i] = arr[index];
arr[index] = tem;
reserve(arr, index + 1, length);
tem = arr[i]; // 其实就是去为了消除当前层去递归的时候的进行交换字符的影响，如果不消除的话，那么就会造成原index位置的字符发生变化
arr[i] = arr[index];
arr[index] = tem;
}
}
//将数组转换成字符串
public static String change(char[] arr) {
StringBuilder ans = new StringBuilder();
for (int i = 0; i < arr.length; i++) {
ans.append(arr[i]);
}
return ans.toString();
}```

#### 字符串反转

```https://www.nowcoder.com/practice/3194a4f4cf814f63919d0790578d51f3?tpId=13&tqId=11197&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

public static String ReverseSentence(String str) {
if (str.length() == 0 || str == null) {
return str;
}
StringBuilder ans = new StringBuilder();
int len=str.length();
int l,r=len;
for(int i=len-1;i>=0;i--){
if(str.charAt(i)==' '){
l=i;
ans.append(str.substring(l+1,r));
ans.append(" ");
r=i;
}
}
ans.append(str.substring(0,r));
return ans.toString();
}```

#### 字符串消消乐

```// 对字符串“ABBCADDDAC“进行逐步去重

public static void cutRepit(String str) {
if (str == null || str.length() == 0) {
return;
}
StringBuilder tmp = new StringBuilder(str);
StringBuilder ans = new StringBuilder();
Boolean same = false;
tmp.append(" ");
char tp = tmp.charAt(0);
for (int i = 1; i < tmp.length(); i++) {
if (tp == tmp.charAt(i)) {
same = true;
} else {
if (!same) {
ans.append(tp);
}
tp = tmp.charAt(i);
same = false;
}
}
if (ans.length()+1  < tmp.length()) {
System.out.println(ans.toString());
cutRepit(ans.toString());
}
}```

#### 字符串转换成数字

```https://www.nowcoder.com/practice/1277c681251b4372bdef344468e4f26e?tpId=13&tqId=11202&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

//将一个字符串转换成一个整数，要求不能使用字符串转换整数的库函数。

public int StrToInt(String str) {
if(str == null || str.length()<=0)
return 0;
char[] chars = str.toCharArray();
long num=0;  //先用long来存储，以防止越界。换算出来的数可能整型溢出
boolean minus=false;
for(int i=0; i<chars.length; i++){
if(i==0 && chars[i]=='-'){
minus=true;
}else if(i==0 && chars[i]=='+'){
minus=false;
}else{
int a=(int) (chars[i]-'0');
if(a<0 || a>9){
return 0;
}
num= (minus==false) ? num*10+a : num*10-a;

if((!minus && num>Integer.MAX_VALUE)//Integer.MAX_VALUE  0x7FFFFFFF
||(minus && num<Integer.MIN_VALUE)){//Integer.MIN_VALUE  0x80000000
return 0;
}
}
}
return (int)num;
}```

#### 循环左移字符串

```https://www.nowcoder.com/practice/12d959b108cb42b1ab72cef4d36af5ec?tpId=13&tqId=11196&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

public static String LeftRotateString(String str, int n) {
if(str==null||str.length()==0){return "";}
int k = n % str.length();
char[] tmp = str.toCharArray();
StringBuilder ans=new StringBuilder();
for(int i=k;i<tmp.length;i++){
ans.append(tmp[i]);
}
for(int i=0;i<k;i++){
ans.append(tmp[i]);
}

return ans.toString();
}```

#### 最长公共子串

```https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac?tpId=117&tqId=37799&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

public static String LCS (String str1, String str2) {
// write code here
String result = "";
int start = 0;
int end = 1;
while(end<=str2.length()){
String subStr = str2.substring(start,end);
if(str1.contains(subStr)){
result = subStr;
}else{
start++;
}
end++;
}
return result;
}```

#### 最长字串NewCode

```https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=190&tqId=35220&rp=1&ru=%2Fta%2Fjob-code-high-rd&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
//给定一个数组arr，返回arr的最长无的重复子串的长度(无重复指的是所有数字都不相同)。

public static int maxLength(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}

int maxLength = 0;
for(int i = 0 ; i < arr.length ; i++){
while (list.contains(arr[i])){
list.removeFirst();
}
if (list.size() > maxLength){
System.out.println(list);
maxLength = list.size();
}
}
return maxLength;
}```

#### 有效括号序列

```https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=117&tqId=37749&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey

public static boolean isValid(String s) {
// write code here
if (s == null) return false;
Stack<Character> res = new Stack<>();
char[] arr = s.toCharArray();
for (char c : arr) {
if (c == '{') {
res.push('}');
} else if (c == '(') {
res.push(')');
} else if (c == '[') {
res.push(']');
} else {
if (res.isEmpty() || res.pop() != c) {
return false;
}
}
}
return res.isEmpty();
}```

#### 求平方根

```https://www.nowcoder.com/practice/09fbfb16140b40499951f55113f2166c?tpId=190&tqId=35187&rp=1&ru=%2Factivity%2Foj&qru=%2Fta%2Fjob-code-high-rd%2Fquestion-ranking&tab=answerKey
public static void main(String[] args) {
int sqrt = sqrt(8);
System.out.println(sqrt);
}

public static int sqrt(int x) {
if (x == 0 || x == 1) {
return x;
}
long left = 0, right = x;
while (right > left) {
long mid = left + (right - left+1 ) / 2;
long square = mid * mid;
if (square == x) {
return (int) mid;
} else if (square > x) {
right = mid - 1;
} else {
left = mid;
}
}
return (int) left;

}```

#### 第一次只出现一次的字符位置

```https://www.nowcoder.com/practice/1c82e8cf713b4bbeb2a5b31cf5b0417c?tpId=13&tqId=11187&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey

public static void main(String[] args) {
}

public int FirstNotRepeatingChar(String str) {
Map<Character, Integer> ans = new HashMap<>();
for(int i=0;i<str.length();i++){
ans.put(str.charAt(i),ans.getOrDefault(str.charAt(i),0)+1);
}
for(int i=0;i<str.length();i++){
if(ans.get(str.charAt(i))==1){
return i;
}
}
return -1;
}```

### 数组篇

#### 岛屿数量问题

```/* 一个矩阵中只有0和1  每个位置都可以和自己的上下左右 四个位置相连
如果一片1 连在一起，这个部分叫做一个岛  求一个矩阵中有几个岛*/
//测试用例1
public static void main(String[] args) {
int[][] m1 = {
{0, 0, 1, 0, 1, 0},
{1, 1, 1, 0, 1, 0},
{1, 0, 0, 1, 0, 0},
{0, 0, 0, 0, 0, 0}
};
int alent = alent(m1);
System.out.println(alent);
}

//获取岛屿数量
public static int alent(int[][] m) {
if (m.length == 0) {
return 0;
}
int M = m.length;
int N = m[0].length;
int res = 0;
for (int i = 0; i < M; i++) {
for (int j = 0; j < N; j++) {  //循环所有
if (m[i][j] == 1) { //如果有岛屿 那么数量++  然后将这一片都给感染掉  下次遍历的时候 就不进行岛屿数量++操作了
res++;
infect(m, i, j, M, N); //感染函数
}
}
}
return res;
}
//感染函数
private static void infect(int[][] m, int i, int j, int M, int N) {
if (i < 0 || i >= M || j < 0 || j >= N || m[i][j] != 1) {
return;
}
m[i][j] = 2;
infect(m, i + 1, j, M, N);
infect(m, i - 1, j, M, N);
infect(m, i, j + 1, M, N);
infect(m, i, j - 1, M, N);
} ```

#### TwoSum

```//leetcode第一题
public static int[] twoSum(int[] arr, int tar) {
HashMap<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
map.put(arr[i], i);
}

for (int j = 0; j < arr.length; j++) {
if (map.containsKey(tar - arr[j])) {
if (j != map.get(tar - arr[j])) {
return new int[]{j, map.get(tar - arr[j])};
}
}
}

return null;
}
```

#### 三数之和

```//链接：https://leetcode-cn.com/problems/3sum
/**给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> ans = new ArrayList<>();
Arrays.sort(nums);// -7, -1, 0, 4, 5, 8
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
return ans;
}//-4  -1  -1  0  1  1  2
if (i > 0 && nums[i] == nums[i - 1]) { //上一次已经算过了 那就跳过 直接下一次循环
continue;
}
int L = i + 1;
int R = nums.length - 1;
while (R > L) {
int sum = nums[i] + nums[R] + nums[L];
if (sum == 0) {
while (R > L && nums[R] == nums[R - 1]) {
R--;
}
while (R > L && nums[L] == nums[L + 1]) {
L++;
}
R--;
L++;
} else if (sum > 0) {
R--;
} else if (sum < 0) {
L++;
}

}
}
return ans;
}```

#### 乘积最大子数组

```//请你找出数组中乘积最大的连续子数组
//https://leetcode-cn.com/problems/maximum-product-subarray/submissions/
//最小可能变最大，最大可能变最小
public static int maxProduct(int[] nums) {
int maxF = nums[0], minF = nums[0], ans = nums[0];
for (int i = 1; i < nums.length; i++) {
int mx = maxF, mn = minF;
maxF = Math.max(mx * nums[i], Math.max(nums[i], mn * nums[i]));//维护最大的值
minF = Math.min(mn * nums[i], Math.min(nums[i], mx * nums[i]));//维护最小的值
ans = Math.max(maxF, ans);
}

return ans;
}```

#### 二分查找

```//https://www.nowcoder.com/practice/4f470d1d3b734f8aaf2afb014185b395?tpId=117&tqId=37829&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
//从左到右，查找到第1个为4的，下标为2，返回2
//二分查找前提是有序（部分或者全部）
public static int search(int[] nums, int target) {
if (nums.length == 0) {
return -1;
}
int l = 0;
int r = nums.length - 1;
while (r > l) {
int tmp = l + (r - l) / 2;
if (nums[tmp] > target) {
r = tmp - 1;
} else if (nums[tmp] < target) {
l = tmp + 1;
} else {
r = tmp;
}
}
return nums[l] == target ? l : -1;
}```

#### 二维数组中的查找

```//https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13&tqId=11154&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
/**在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，

//可以从左上角 或者右下角开始找
public static boolean Find(int target, int[][] array) {
int row = array.length - 1;
int column = array[0].length - 1;
int r = 0;
while (r <= row && column >= 0) {
if (target == array[r][column]) {
return true;
} else if (target > array[r][column]) {
r++;
} else {
column--;
}
}
return false;
}```

#### 和为S的两个数字

```//https://www.nowcoder.com/practice/390da4f7a00f44bea7c2f3d19491311b?tpId=13&tqId=11195&rp=1&ru=%2Fta%2Fcoding-interviews&qru=%2Fta%2Fcoding-interviews%2Fquestion-ranking&tab=answerKey
// 输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
public ArrayList<Integer> FindNumber(int[] array, int sum) {
int l = 0;
int r = array.length - 1;
ArrayList<Integer> ans = new ArrayList<>();
while (r > l) {
int tmp = array[r] + array[l];
if (tmp > sum) {
r--;
} else if (tmp < sum) {
l++;
} else {
return ans;
}
}
return ans;
}```

#### 奇偶数组顺序问题

```//https://www.nowcoder.com/practice/ef1f53ef31ca408cada5093c8780f44b?tpId=117&tqId=37776&rp=1&ru=%2Fta%2Fjob-code-high&qru=%2Fta%2Fjob-code-high%2Fquestion-ranking&tab=answerKey
//输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

public static int[] reOrderArray(int[] array) {
// write code here
int[] arr = new int[array.length];
int nums=0;
//先求出奇数的个数
for(int n:array){
if(n%2!=0){
nums++;
}
}
int l = 0;
int r = nums;
for (int m : array) {
if (m % 2 != 0) {
arr[l++] = m;
} else {
arr[r++] = m;
}
}
return arr;
}```

#### 子数组最大和问题

```/**

[要求]

*/

public static int maxsumofSubarray(int[] arr) {
if (arr.length == 0 || arr == null) {
return 0;
}
if (arr.length == 1) {
return arr[0];
}
int sum = arr[0];
int ans = 0;
for (int i = 1; i < arr.length; i++) {
if ((arr[i] + sum) > arr[i]) {
sum = arr[i] + sum;
if(sum>0){
}
ans = Math.max(sum, ans);
} else {
sum = arr[i];
if(sum>ans){
res.clear();
}
ans = Math.max(sum, ans);
}
}
return ans;
}```

#### 寻找峰值79

```//leetcode 79题
/**峰值元素是指其值大于左右相邻值的元素。

//1、暴力法，直接遍历，只要后一个比前一个小，就是峰值

//2、使用二分思想
public static int findNum(int[] arr) {
return search(arr, 0, arr.length - 1);
}

public static int search(int[] arr, int l, int r) {
if (l == r) {
return l;
}
int mid = l + (r - l) / 2;
if (arr[mid] > arr[mid+1]) { //表示下降 那么峰值 一定在前面
return search(arr, l, mid);
} else {
return search(arr, mid + 1, r);
}
}```

#### 把数字排成最小的数

```/*

[3,32,321]

"321323"
*/
public static String PrintMinNumber(int[] numbers) {
StringBuilder ans = new StringBuilder();
if (numbers.length == 0) {
return ans.toString();
}
ArrayList<String> tmp = new ArrayList<>();
for (int a : numbers) {
}
//使用自定义比较器
tmp.sort((o1, o2) -> {
String a = o1 + o2;
String b = o2 + o1;
return a.compareTo(b);
});
for (String m : tmp) {
ans.append(m);
}
return ans.toString();
}```

#### 数字在升序数组中出现的次数

```/*
[1,2,3,3,3,3,4,5],3
return 4
*/
public int GetNumberOfK(int[] array, int k) {
if (array.length == 0) return 0;
int firstPosition = findFirstPosition(array, k);
int lastPosition = findLastPosition(array, k);
if (array[firstPosition] != k) {
return 0;
}
//两个位置的差值（下标差值）
return lastPosition - firstPosition + 1;
}
//使用二分，找到该数字第一次出现的位置
private int findFirstPosition(int[] array, int k) {
int l = 0;
int r = array.length - 1;
while (r > l) {
int mid = (r + l) >> 1;
if (array[mid] == k) {
if (mid - 1 >= 0 && array[mid - 1] == k) {
r = mid - 1;
} else {
r = mid;
}
} else if (array[mid] > k) {
r = mid - 1;
} else {
l = mid + 1;
}
}
return l;
}
//使用二分，找到该数字最后出现的位置
private int findLastPosition(int[] array, int k) {
int l = 0;
int r = array.length - 1;
while (r > l) {
int mid = (r + l) >> 1;
if (array[mid] == k) {
if (mid + 1 < array.length && array[mid + 1] == k) {
l = mid + 1;
} else {
l = mid;
}
} else if (array[mid] > k) {
r = mid - 1;
} else {
l = mid + 1;
}

}
return l;
}```

#### 数组中出现次数超过一半的数字

```/*

*/
public static int MoreThanHalfNum_Solution(int[] array) {
Map<Integer,Integer> ans = new HashMap<>();
int target=0;
int sum=0;
for(int x:array){
ans.put(x,ans.getOrDefault(x,0)+1);
if(sum<ans.get(x)){
target=x;
sum=ans.get(x);
}
}
if(sum>array.length/2){
return target;
}else {
return 0;
}
}```

#### 数组中只出现一次的数字

```/*

*/
public static int[] FindNumsAppearOnce(int[] array) {
int[] ans = new int[2];
if (array.length == 0) {
return ans;
}
Map<Integer, Integer> tmp = new HashMap<>();
for (int a : array) {
tmp.put(a, tmp.getOrDefault(a, 0) + 1);
}
int index = 0;
for (Map.Entry<Integer, Integer> a : tmp.entrySet()) {
if (a.getValue() == 1) {
ans[index++] = a.getKey();
}
}
return ans;
}
```

#### 数组中的第K个最小元素

```/** leetcode 92题

public static int findK1(int[] arr, int k) {
if (k > arr.length) {
return 0;
}
int[] arry = new int[k];
System.arraycopy(arr, 0, arry, 0, k);

for (int i = k / 2 - 1; i >= 0; i--) {
BigHeap(arry, i, k); //前K个数 构建大根堆
}
//        后面的所有的数 维护大根堆
for (int i = k; i < arr.length; i++) {
if (arr[i] < arry[0]) {
arry[0] = arr[i];
BigHeap(arry, 0, k);
}
}
return arry[0];//输出堆顶数字
}

//（调整成大根堆从最后一个非叶子节点开始，维护大根堆从第0个位置开始）
public static void BigHeap(int[] arr, int index, int len) {
int temp = arr[index];
for (int k = 2 * index + 1; k < len; k = 2 * k + 1) {
if (k + 1 < len && arr[k + 1] > arr[k]) {
k++;
}
if (temp < arr[k]) {
arr[index] = arr[k];
index = k;
} else {
break;
}
}
arr[index] = temp;
}```

#### 数组中的逆序对

```/*

*/
private static long sum;

public static int InversePairs(int[] array) {
int l = 0;
int r = array.length - 1;
divide(l, r, array);
System.out.println(sum);
return (int) (sum % 1000000007);
}

private static void divide(int l, int r, int[] array) {
if (r != l) {
int mid = (r + l) >> 1;
divide(l, mid, array);
divide(mid + 1, r, array);
merge(l, mid, r, array);
}
}

private static void merge(int l, int mid, int r, int[] arr) {
int[] ans = new int[r - l + 1];
int i = l;
int j = mid + 1;
int index = 0;
while (i <= mid && j <= r) {
if (arr[i] > arr[j]) {
ans[index++] = arr[j++];
sum += mid - i + 1;
} else {
ans[index++] = arr[i++];
}
}
while (i <= mid) {
ans[index++] = arr[i++];
}
while (j <= r) {
ans[index++] = arr[j++];
}
index = 0;
while (r >= l) {
arr[l++] = ans[index++];
}
}```

#### 数组中重复的数字

```/*
在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，
但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任一一个重复的数字。
例如，如果输入长度为7的数组[2,3,1,0,2,5,3]，那么对应的输出是2或者3。存在不合法的输入的话输出-1
*/

public static int duplicate(int[] numbers) {
if (numbers.length == 0) {
return -1;
}
HashSet<Integer> ans = new HashSet<>();
for (int i = 0; i < numbers.length; i++) {
if (ans.contains(numbers[i])) {
return numbers[i];
} else {
}
}
return -1;
}```

#### 构建乘积数组

```/*

（注意：规定B[0] = A[1] * A[2] * ... * A[n-1]，B[n-1] = A[0] * A[1] * ... * A[n-2];）

[1,2,3,4,5]

[120,60,40,30,24]
*/

public static int[] multiply(int[] A) {
int[] ans=new int[A.length];
for(int i=0;i<A.length;i++){
int res=1;
for(int j=0;j<A.length;j++){
if(i!=j){
res=res*A[j];
}
}
ans[i]=res;
}
return ans;
}```

#### 查找旋转数组最小值

```public static void main(String[] args) {
int [] arr = {4,5,7,1,2,3}; //排序数组 切割后拼接到后面
//        暴力法  直接遍历
//        int min=arr[2];
//        for(int i=0;i<arr.length;i++){
//            min=arr[i]<min?arr[i]:min;
//        }
}

/**二分查找法*/
public static int BinarySearch(int[] arr){
if(arr.length==0){
return 0;
}
int l = 0;
int r=arr.length-1;
while(r>l){
int m =l+(r-l)/2;
if(arr[m]>arr[r]){ //中值比you侧大  那么最小值在 中值的右边
l = m+1; // 4 5 7 1 2 3
}else if(arr[m]<arr[r]){
r=m;
}else{ //有重复的值 那么不断往左边靠
r--;
}
}
return arr[r];
}```

#### 滑动窗口最大值

```/*

*/
public static ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> ans = new ArrayList<Integer>();
if (size > num.length || num == null || num.length == 0 || size == 0) {
return ans;
}
int max = num[0];
int pos = 0;
// 寻找第一个窗口中的最大值
for (int i = 0; i < size; i++) {
if (max < num[i]) {
max = num[i];
pos = i;
}
}
for (int i = size; i < num.length; i++) {
if (i - size + 1 <= pos) {// 新窗口的第一个值 是否在最大值的下标前面
if (num[i] > max) { //在的话  判断新加入的第一个值 是否比最大值大
max = num[i];
pos = i;
}
} else {  //否则的话需要重写选举出最大值 上一个最大值已经滑过了
max = num[i - size + 1]; //重新选举最大值 需要进行初始化
for (int j = i - size + 1; j <= i; j++) {
if (num[j] > max) {
max = num[j];
pos = j;
}
}
}
}
return ans;
}```

#### 矩阵中的路径

```/*

矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，
因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子
y --->
x [[a,b,c,e],
| [s,f,c,s],
| [a,d,e,e]],

"abcced"
true
*/

public boolean hasPath(char[][] matrix, String word) {
boolean[][] flag = new boolean[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (solve(matrix, word, i, j, flag, 0)) {
return true;
}
}
}
return false;
}

private boolean solve(char[][] matrix, String word, int x, int y, boolean[][] flag, int index) {
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || flag[x][y]) {
return false;
}
if (matrix[x][y] != word.charAt(index)) {
return false;
}
if (index == word.length() - 1) {
return true;
}
flag[x][y]=true;
boolean fl= solve(matrix, word,  x+1, y, flag,index+1)||
solve(matrix, word,  x-1, y, flag,index+1)||
solve(matrix, word,  x, y+1, flag,index+1)||
solve(matrix, word,  x, y-1, flag,index+1);
flag[x][y]=false;
return fl;
}```

#### 路径和问题

```/*
https://leetcode-cn.com/problems/unique-paths/description/
一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为 “Start” ）。

*/
public static int uniquePaths(int m, int n) {
int[][] ans = new int[m][n];
for (int i = 0; i < m; i++) {
ans[i][0] = 1;
}
for (int i = 0; i < n; i++) {
ans[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
ans[i][j] = ans[i - 1][j] + ans[i][j - 1];
}
}
return ans[m - 1][n - 1];
}```

#### 顺时针打印矩阵

```/*

1 2 3 4
5 6 7 8
9 10 11 12
13 14 15 16
则依次打印出数字
y---->
x 1,2,3,4,
| 8,12,16,15,
| 14,13,9,5,
6,7,11,10.
*/
public ArrayList<Integer> printMatrix(int[][] matrix) {
ArrayList<Integer> ans = new ArrayList<>();
int flag = 1;// 1->right, 2->down, 3->left, 4->up
int x = 0;
int y = 0;
boolean[][] vis = new boolean[matrix.length][matrix[0].length]; // 这个就是用来标记已经走过的点
while (ans.size() < matrix.length * matrix[0].length) {
if (x < 0 || x >= matrix.length || y < 0 || y >= matrix[0].length || vis[x][y]) { // vis[x][y] -> 已经遍历过的位置也当作越界处理
if (flag == 1) {
flag = 2; // 往下走
y--; // 消除越界的影响
x++; // 本质上就是到达下一个位置的横坐标
} else if (flag == 2) {
flag = 3; // 往左走
x--; // 消除越界的影响
y--; // 本质上就是到达下一个位置的纵坐标
} else if (flag == 3) {
flag = 4; // 往上走
y++; // 消除越界的影响
x--; // 本质上就是到达下一个位置的横坐标
} else {
flag = 1;//往右走
x++; // 消除越界的影响
y++; // 本质上就是到达下一个位置的纵坐标
}

} else {
vis[x][y] = true; // 去标记已经遍历过的位置
// 根据flag的值更新遍历矩阵的下标x，y的值
if (flag == 1) {
y++;
} else if (flag == 2) {
x++;
} else if (flag == 3) {
y--;
} else {
x--;
}
}
}
return ans;
}```

### 数字篇

#### 不用加减乘除做加法

```/*

1,2

3
*/

public int Add(int num1,int num2) {
int sum1, sum2;
do{
sum1 = num1 ^ num2;
sum2 = (num1 & num2) << 1;
num1 = sum1;
num2 = sum2;
}while (num2 != 0);
return num1;
}```

#### 丑数

```/*

*/
public static int GetUglyNumber_Solution(int index) {
if(index==0){
return 0;
}
int[] ans = new int[index];
int index1 = 0;
int index2 = 0;
int index3 = 0;
ans[0] = 1;
for (int i = 1; i < index; i++) {
ans[i] = Math.min(ans[index1] * 2, Math.min(ans[index2] * 3, ans[index3] * 5));
if (ans[i] == ans[index1]*2) {
index1++;
}
if (ans[i] == ans[index2]*3) {
index2++;
}
if (ans[i] == ans[index3]*5) {
index3++;
}
}

return ans[index - 1];
}```

#### 二进制中1的个数

```/*
*/
public static int NumberOf1(int n) {
int res=0;
//        while(n!=0){
//            res=res+(n&1);
//            n=n>>>1;
//        }
while(n!=0){
res++;
n=n&(n-1);
}
return res;
}```

#### 变态跳台阶

```/*

*/
public static int jumpFloorII(int target) {
if (target <= 1) {
return target;
}
int[] ans = new int[target + 1];
int sum = 1;
for (int i = 2; i <= target; i++) {
ans[i] = sum + 1; //第i阶 等于第i-1阶的情况加上 从起点直接跳到i的情况（需要+1）
sum = sum + ans[i]; //更新1到第i阶的情况（记录走到当前阶 的所有步数）
}
System.out.println(sum);
return ans[target];
}```

#### 变种跳台阶--II

```/**
* 1、有n阶台阶 可以一次跳a步，也可以一次跳b步  求所有的走法
* n=11 a=3 b=5
* 输出：
* 335 533 353
*/
public static void jump(int[] arr, int target, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> ans) {
if (target < 0) {
return;
}
if(target==0){
return;
}
for(int i=0;i<arr.length;i++){
int sum = target-arr[i];
jump(arr,sum,path,ans);
path.remove(path.size()-1);
}
}```

#### 和为S的正数序列

```/*
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。
但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,
他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你
能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输入
9
返回值
[[2,3,4],[4,5]]
*/
public static ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
//存放结果
ArrayList<ArrayList<Integer> > result = new ArrayList<>();
//两个起点，相当于动态窗口的两边，根据其窗口内的值的和来确定窗口的位置和大小
int plow = 1,phigh = 2;
while(phigh > plow){
//由于是连续的，差为1的一个序列，那么求和公式是(a0+an)*n/2
int cur = (phigh + plow) * (phigh - plow + 1) / 2;
//相等，那么就将窗口范围的所有数添加进结果集
if(cur == sum){
ArrayList<Integer> list = new ArrayList<>();
for(int i=plow;i<=phigh;i++){
}
plow++;
//如果当前窗口内的值之和小于sum，那么右边窗口右移一下
}else if(cur < sum){
phigh++;
}else{
//如果当前窗口内的值之和大于sum，那么左边窗口右移一下
plow++;
}
}
return result;
}```

#### 孩子们的游戏

```/*
随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,
然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,
继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,
并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,
哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
*/
public static void main(String[] args) {
LastRemaining_Solution(5,3);
}

public static int LastRemaining_Solution(int n, int m) {
if (n < 1 || m < 1) return -1;
int[] array = new int[n];
int i = -1, step = 0, count = n;
while (count > 0) {   //跳出循环时将最后一个元素也设置为了-1
i++;          //指向上一个被删除对象的下一个元素。
if (i >= n) { //模拟环。
i = 0;
}
if (array[i] == -1) {
continue;
} //跳过被删除的对象。
step++;                     //记录已走过的。
if (step == m) {               //找到待删除的对象。
array[i] = -1;
step = 0;
count--;
}
}
return i;//返回跳出循环时的i,即最后一个被设置为-1的元素
}```

#### 快乐数

```/*
*https://leetcode-cn.com/problems/happy-number/solution/kuai-le-de-zhi-shi-dian-zeng-jia-liao-by-sweetiee/
* 输入: 19
* 输出: true
* 解释:  1*1+9*9=82
* 8*8 + 2*2 = 68
* 6*6 + 8*8 = 100
* 1*1 + 0*0 + 0*0 = 1
**/
public int squareSum(int n) {
int sum = 0;
while(n > 0){
int digit = n % 10;
sum += digit * digit;
n /= 10;
}
return sum;
}

public boolean isHappy(int n) {
//类似快慢指针
int slow = n, fast = squareSum(n);
while (slow != fast){
slow = squareSum(slow);
fast = squareSum(squareSum(fast));
};
return slow == 1;
}```

#### 扑克牌顺子

```/*
LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...

“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他

[0,3,2,6,4]

true
*/

// 先去统计出数组中0的个数，然后在对数组排序，最后判断数组中相邻两个位置之间是否需要0填充以及0的个数是否够用即可
public static boolean IsContinuous(int[] numbers) {
if (numbers.length == 0) {
return false;
}
int sum=0;
for(int x:numbers){
if(x==0){
sum++;
}
}
Arrays.sort(numbers);
for(int i=sum+1;i<numbers.length;i++){
sum-=numbers[i]-numbers[i-1]-1;
if(sum<0||numbers[i]==numbers[i-1]){
return false;
}
}
return true;
}```

#### 数字的整数次方

```/*

*/
public static double Power(double base, int exponent) {
if (exponent == 0) {
return 1;
}
double ans = 1;
int ex = exponent >= 0 ? exponent : -exponent;
for (int i = 0; i < ex; i++) {
ans = ans * base;
}
if (exponent > 0) {
return ans;
} else {
return 1 / ans;
}
}```

#### 数据流中的中位数

```/*

*/
private PriorityQueue<Integer> queue1 = new PriorityQueue<>(((o1, o2) -> (o2 - o1))); // 中位数的左区间 > 大顶堆
private PriorityQueue<Integer> queue2 = new PriorityQueue<>(); // 中位数的右区间 > 小顶堆
private int sum = 0; // 数据流中个数

public void Insert(Integer num) {
if (sum % 2 == 0) { //  1 2 3 4 5
// 当两个堆的元素个数一样的时候，此时新增一个元素，放入大顶堆(左区间)
} else {
}
if (!queue2.isEmpty() && queue1.peek() > queue2.peek()) {
int temp1 = queue1.poll();
int temp2 = queue2.poll();
}
sum++;
}

public Double GetMedian() {
if (sum % 2 == 1) {
return (double) queue1.peek();
} else {
return (queue1.peek() + queue2.peek()) / 2.0;
}
}```

#### 整数中1出现的次数

```/*

*/
public int NumberOf1Between1AndN_Solution(int n) {
if(n==0){return 0;}
int sum = 1;
for (int i = n; i >= 1; i--) {
int m = i;
while (m > 9) {
if (m % 10 == 1) {
sum++;
}
m = m / 10;
if(m==1) {
sum++;
}
}
}
return sum;
}```

#### 机器人的运动范围

```/*

5,10,10

21
*/
int sum=0;
public int movingCount(int threshold, int rows, int cols) {
sum=0;
boolean[][] vis = new boolean[rows][cols];
solve(0, 0, rows, cols, vis, threshold);
return sum;
}
//计算当前位置是否能到达
private int cule(int x,int y){
int res=0;
while(x!=0){
res+=x%10;
x=x/10;
}
while(y!=0){
res+=y%10;
y=y/10;
}
return res;
}
private void solve(int x, int y, int rows, int cols, boolean[][] vis, int k) {
if(x<0||y<0||x>=rows||y>=cols||vis[x][y]||cule(x,y)>k){
return ;
}
vis[x][y]=true;
sum++;
solve( x-1,  y,  rows,  cols,  vis,  k);
solve( x+1,  y,  rows,  cols,  vis,  k);
solve( x,  y-1,  rows,  cols,  vis,  k);
solve( x,  y+1,  rows,  cols,  vis,  k);
}```

#### 跳台阶

```public static int Jump3(int n) {
if (n <= 2) {
return n;
}
int[] dp = new int[n + 1];
dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2];
}
return dp[n];
}```

### 栈篇

#### 两个栈实现队列

```Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();

// 入栈 直接入
//如果你要出栈  自己出  为空了 那就找我要  我一次全部给你
public void push(int node) {
stack1.push(node);
}

public int pop() {
//出
if (stack2.empty()) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
return stack2.pop();
}```

#### 包含Min函数的栈

```/*

*/
Stack<Integer> data = new Stack<>();
Stack<Integer> min = new Stack<>();

public void push(int node) {
if (min.isEmpty()) {
min.push(node);
} else {
if (min.peek() > node) {
min.push(node);
} else {
min.push(min.peek());
}
}
data.push(node);
}

public void pop() {
data.pop();
min.pop();
}

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

public int min() {
return min.peek();
}```

#### 栈的压入弹出顺序

```/*
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。
假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，
序列4,5,3,2,1是该压栈序列对应的一个弹出序列，
但4,3,5,1,2就不可能是该压栈序列的弹出序列。
（注意：这两个序列的长度是相等的）
*/
public static void main(String[] args) {
int[] t1 = {1, 2, 3, 4, 5};
int[] t2 = {4, 5, 3, 2, 1};
boolean b = IsPopOrder(t1, t2);
System.out.println(b);
}

public static boolean IsPopOrder(int[] pushA, int[] popA) {
if (pushA.length == 0 || popA.length == 0 || popA.length != pushA.length) {
return false;
}
Stack<Integer> ans = new Stack<>();
int popindex = 0;
for (int i = 0; i < pushA.length; i++) {
ans.push(pushA[i]);
while (!ans.isEmpty() && ans.peek() == popA[popindex]) {
ans.pop();
popindex++;
}
}
return ans.isEmpty();
}```