熟刷剑指三百遍，不会coding也会编(剑指OFFER JAVA版)

忘是亡心i 2021-11-02 11:58 81阅读 0赞

## 通用类： ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //Definition for TreeNode
    2 public class ListNode {
    3     int val;
    4     ListNode next = null;
    5 
    6     ListNode(int val) {
    7         this.val = val;
    8     }
    9 }

ListNode

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 public class TreeLinkNode {
     2     int val;
     3     TreeLinkNode left = null;
     4     TreeLinkNode right = null;
     5     TreeLinkNode next = null;//next指针指向中序遍历的条件下当前节点的下一个节点，从树的结构上看是指向父结点的指针
     6 
     7     TreeLinkNode(int val) {
     8         this.val = val;
     9     }
    10 }

TreeLinkNode

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //  Definition for binary tree
     2 public class TreeNode {
     3     int val;
     4     TreeNode left;
     5     TreeNode right;
     6 
     7     TreeNode(int x) {
     8         val = x;
     9     }
    10 }

TreeNode

## 题目： ##

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 *给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
 3 * */
 4 
 5 /*
 6 * 题解
 7 * 考虑到指数有可能为负数的情况
 8 * */
 9 public class 代码的完整性_数值的整数次方 {
 10 public double Power(double base, int exponent) {
 11 boolean flag = exponent >= 0? true:false;
 12 exponent = exponent >= 0? exponent:-exponent;
 13 double res = 1;
 14 for(int i = 0; i<exponent; i++){
 15 res *= base;
 16 }
 17 if(!flag)
 18 res = 1/res;
 19 return res;
 20 }
 21 }

数值的整数次方

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，
 4 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的
 5 后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
 6 * */
 7 
 8 
 9 /*
 10 *
 11 * */
 12 public class 代码的完整性_整数组顺序使奇数位于偶数前面 {
 13 
 14 //雪菜写的双指针算法
 15 public void reOrderArray(int [] array) {
 16 int i = 0;
 17 int j = array.length-1;
 18 while(i<=j){
 19 while(array[i]%2==1) i++;
 20 while(array[j]%2==0) j--;
 21 if(i<j) swap(array,i,j);
 22 }
 23 }
 24 
 25 
 26 
 27 //自己写的双指针移动
 28 public static void reOrderArray1(int [] array) {
 29 int i = 0;
 30 int j ;
 31 while(i<array.length && array[i]%2==1 )
 32 i++;
 33 j = i+1;
 34 while(j<array.length){
 35 while( j<array.length && array[j]%2==0 )
 36 j++;
 37 if(j<array.length){
 38 swap(array, i, j);
 39 while(i<array.length && array[i]%2==1 )
 40 i++;
 41 j = i+1;
 42 }
 43 }
 44 }
 45 
 46 
 47 
 48 //自己写的可以保证交换后顺序不变的写法
 49 public void reOrderArray2(int [] array) {
 50 int [] help1 = new int[array.length];
 51 int [] help2 = new int[array.length];
 52 int m = 0;
 53 int n = 0;
 54 for(int i = 0; i<array.length; i++){
 55 if(array[i]%2==1)
 56 help1[m++] = array[i];
 57 else
 58 help2[n++] = array[i];
 59 }
 60 int k = 0;
 61 for(int i = 0; i<m;i++)
 62 array[k++] = help1[i];
 63 for(int i = 0; i<n;i++)
 64 array[k++] = help2[i];
 65 }
 66 
 67 static void swap(int[] array, int i, int j){
 68 int tmp = array[i];
 69 array[i] = array[j];
 70 array[j] = tmp;
 71 }
 72 
 73 public static void main(String[] args) {
 74 int[] array = {1,2,3,4,5,6,7};
 75 int[] array1 = {1,2,4,6,5,9,7};
 76 // reOrderArray(array);
 77 for(int i:array)
 78 System.out.print(i+ " ");
 79 }
 80 }

调整数组顺序使奇数位于偶数前面

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*题目描述
     2 输入一个链表，反转链表后，输出新链表的表头。*/
     3 //解释见本文件夹下的 代码的鲁棒性_反转链表详细解释.png
     4 public class 代码的鲁棒性_反转链表 {
     5     //    递归方法
     6     public ListNode ReverseList(ListNode head) {
     7         if (head == null || head.next == null)
     8             return head;
     9         ListNode h = ReverseList(head.next);//带着成为新头节点的尾节点一直到递归最外层成为头
    10         head.next.next = head;
    11         head.next = null;
    12         return h;
    13     }
    14 
    15 //    https://blog.csdn.net/geekmanong/article/details/51097196 经典单链表反转递归与非递归算法
    16 //    非递归方法
    17 //    利用两个结点指针和一个中间结点指针temp(用来记录当前结点的下一个节点的位置)，分别指向当前结点和前一个结点，
    18 //    每次循环让当前结点的指针域指向前一个结点即可，翻转结束后，记得将最后一个节点的链域置为空。
    19 
    20     public ListNode ReverseList2(ListNode head) {
    21         ListNode pre = null;
    22         ListNode cur = head;
    23         while(cur!=null){
    24             ListNode next = cur.next;
    25             cur.next = pre;
    26             pre = cur;
    27             cur = next;
    28         }
    29         return pre;
    30     }
    31 }

反转链表

![1135658-20190611215033893-1038405002.png][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 *题目描述
 3 输入两个单调递增的链表，输出两个链表合成后的链表，
 4 当然我们需要合成后的链表满足单调不减规则。
 5 * */
 6 
 7 /*
 8 * 归并排序的步骤
 9 * */
 10 public class 代码的鲁棒性_合并两个排序的链表 {
 11 public ListNode Merge(ListNode list1,ListNode list2) {
 12 ListNode head = new ListNode(-1);
 13 ListNode l = head;
 14 
 15 while(list1!=null&&list2!=null){
 16 if(list1.val<list2.val){
 17 l.next = list1;
 18 l = l.next;
 19 list1 = list1.next;
 20 }else{
 21 l.next = list2;
 22 l = l.next;
 23 list2 = list2.next;
 24 }
 25 }
 26 
 27 if(list1!=null){
 28 l.next = list1;
 29 }
 30 if(list2!=null){
 31 l.next = list2;
 32 }
 33 
 34 return head.next;
 35 }
 36 }

合并两个排序的链表

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 * 题目描述
     3 输入一个链表，输出该链表中倒数第k个结点。
     4 * */
     5 
     6 /*
     7 * */
     8 public class 代码的鲁棒性_链表中倒数第k个结点 {
     9     public static ListNode FindKthToTail(ListNode head,int k) {
    10 
    11         int i = 0;
    12         ListNode l = head;
    13         while(l!=null){
    14             i++;
    15             l = l.next;
    16         }
    17 
    18         int m = i-k+1;
    19         if (k>i)
    20             return null;
    21         l = head;
    22         while(m>1){
         //注意理清节点以及遍历次数，一个好的想法是可以举例子来判断边界是否正确
    23             m--;
    24             l = l.next;
    25         }
    26         return l;
    27     }
    28 
    29     public static void main(String[] args) {
    30         ListNode head = new ListNode(1);
    31         ListNode l = head;
    32         l.next = new ListNode(2);
    33         l = l.next;
    34         l.next = new ListNode(3);
    35         l = l.next;
    36         l.next = new ListNode(4);
    37         l = l.next;
    38         l.next = new ListNode(5);
    39 
    40         FindKthToTail(head, 1);
    41     }
    42 
    43 }

链表中倒数第k个结点

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 题目描述
 3 * 输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。
 4 * */
 5 
 6 /*
 7 * 题解
 8 *迭代进行如下两步，直到 n 变成0为止：
 9 
 10 如果 n 在二进制表示下末尾是1，则在答案中加1；
 11 将 n 右移一位，也就是将 nn 在二进制表示下的最后一位删掉；
 12 这里有个难点是如何处理负数。
 13 
 14 在C++中如果我们右移一个负整数，系统会自动在最高位补1，这样会导致 n 永远不为0，就死循环了。
 15 解决办法是把 nn 强制转化成无符号整型，这样 n 的二进制表示不会发生改变，但在右移时系统会自动在最高位补0。
 16 
 17 在java里面:
 18 << 表示左移
 19 >> 表示右移 （带符号右移，负数高位补0正数高位补1）
 20 >>> 表示无符号右移（无论正负高位补0）
 21 
 22 补充雪菜关于补码的理解：
 23 在十进制下也有补码的概念:
 24 3的补码是7因为 3+7=10；
 25 22的补码是78 因为 22+78 = 100；
 26 就是能把你加到刚好到进位的那个数，就是你的补码；
 27 二进制也是一样:
 28 1的补码是
 29 1111 1111 1111 1111
 30 10的补码是
 31 1111 1111 1111 1110
 32 11的补码是
 33 1111 1111 1111 1101
 34 一个负数在计算机里，用它绝对值的补码表示,
 35 也就是说，-2用2(10)的补码 1111 1111 1111 1110 表示
 36 
 37 
 38 时间复杂度
 39 每次会将 nn 除以2，最多会除 lognlogn 次，所以时间复杂度是 O(logn)O(logn)。
 40 题解来自大雪菜
 41 * */
 42 public class 位运算_二进制中1的个数 {
 43 public int NumberOf1(int n)
 44 {
 45 int res = 0;
 46 while(n!=0){
 47 res += n&1;
 48 n = n>>>1;
 49 }
 50 return res;
 51 }
 52 }

二进制中1的个数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 *题目描述
 3 HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,
 4 常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,
 5 并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。
 6 给一个数组，返回它的最大连续子序列的和，你会不会被他忽悠住？(子向量的长度至少是1)
 7 * */
 8 
 9 /*
 10 * 解法：
 11 * —— —— —— —— ——
 12 * 令s表示到从头开始到第i-1个元素的累计和，因为要求的是最大和
 13 * 所以当s<0时，前i-1个元素对和的贡献为负数，所以如果要选第i个元素，则前i-1个元素不应该选取, 将s置为0
 14 * 所以到第i个元素时，
 15 * 若s<=0:
 16 * s = 0 + array[i];
 17 * 若s>0:
 18 * s = s + array[i];
 19 *
 20 * res 是整个过程中s能取得最大值
 21 * */
 22 public class 前缀和_连续子数组的最大和 {
 23 public int FindGreatestSumOfSubArray(int[] array) {
 24 int res = Integer.MIN_VALUE;
 25 int s = 0;
 26 for(int i: array){
 27 if(s <= 0)
 28 s = 0 ;
 29 s += i;
 30 res = Math.max(res, s);
 31 }
 32 return res;
 33 }
 34 }

连续子数组的最大和

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*题目描述
 2 写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/
 3 四则运算符号。*/
 4 
 5 /*
 6 * 解题思路：
 7 * 计算机中的加法首先将数字转为二进制，然后使用与和非这两种操作完成的
 8 * 例如要计算A+B,得到的结果用CD表示：
 9 * 如果A = 1 B = 0， 则A+B = 01(CD,C=0,D=1)
 10 * 如果A = 1 B = 1， 则A+B = 10(CD,C=1,D=0)
 11 * 如果A = 0 B = 1， 则A+B = 01(CD,C=0,D=1)
 12 * 如果A = 0 B = 0， 则A+B = 00(CD,C=0,D=0)
 13 * 可以看出D = A^B(低位是不进位加法)
 14 * C = A&B;（高位是A和B与的结果，即只有A和B同时为1时才有进位）
 15 *
 16 * 在计算时，可以先计算不进位加法 A^B = num ,
 17 * 再用计算进位 A&B = carry (carry需要左移一位加到新数上)
 18 * 再将两个结果加起来(仍然使用上面的方法做这个加法)，直到carry变为0
 19 * */
 20 public class 发散思维能力_不用加减乘除做加法 {
 21 public static int Add(int num1,int num2) {
 22 int res = num1^num2;
 23 int carry = (num1&num2)<<1;
 24 int tmp;
 25 while(carry!=0){
 26 tmp = res^carry;
 27 carry = (res&carry)<<1;
 28 res = tmp;
 29 }
 30 return res;
 31 }
 32 
 33 public static void main(String[] args) {
 34 System.out.println(Add(111,899));
 35 }
 36 }

不用加减乘除做加法

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 * 题目: https://www.acwing.com/problem/content/24/
     3 * 给你一根长度为 n 绳子，请把绳子剪成 m 段（m、n 都是整数，2≤n≤58 并且 m≥2）。
     4 
     5 每段的绳子的长度记为k[0]、k[1]、……、k[m]。k[0]k[1] … k[m] 可能的最大乘积是多少？
     6 
     7 例如当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到最大的乘积18。
     8 
     9 样例
    10 输入：8
    11 
    12 输出：18
    13 * */
    14 
    15 /*
    16 * 题解来自大雪菜
    17 * 1.至少要剪成两段；
    18 * 2.剪出长度为1的绳子对最大乘积没有贡献，因此如果想乘积最大，则一定不能剪出长度为1的绳子（绳长为2的不得不剪成两根1，绳长为3的不得不剪成1个1一个2）；
    19 * 3.当绳长足够长时(长度大于5)，使得乘积最大的剪法是剪成若干个3和0至两个2：
    20 * 证明如下:
    21 * 假设剪出的某个绳长为n(n>5),则我们可以从中再剪出一个3来,得到的乘积：
    22 * (n-3)*3 > n 的条件是2*n>9, 则说明n>5时将n剪出一个3来的乘积一定比不剪开要大;
    23 * n = 4时 剪成两个 2
    24 * 为什么不剪成多于两个的2呢？
    25 * 因为6 = 2+2+2，乘积为8，剪成3+3，乘积为9
    26 * 所以
    27 * 本题的算法是:
    28 * 如果n除3余1，则 n = 2+2 + 3 + ... +3;
    29 * 如果n除3余2，则  n =2  + 3 + ... +3;
    30 * 如果n除3余0，则  n =3 + ... +3;
    31 * n = 2，3，4的时候需要特判
    32 *
    33 *
    34 * 这道题目是数学中一个很经典的问题。
    35 下面我们给出证明：
    36 
    37 首先把一个正整数 NN 拆分成若干正整数只有有限种拆法，所以存在最大乘积。
    38 假设 N=n1+n2+…+nkN=n1+n2+…+nk，并且 n1×n2×…×nkn1×n2×…×nk 是最大乘积。
    39 
    40 显然1不会出现在其中；
    41 如果对于某 ii 有 ni≥5ni≥5，那么把 nini 拆分成 3+(ni−3)3+(ni−3)，我们有 3(ni−3)=3ni−9>ni3(ni−3)=3ni−9>ni；
    42 如果 ni=4ni=4，拆成 2+22+2乘积不变，所以不妨假设没有4；
    43 如果有三个以上的2，那么 3×3>2×2×23×3>2×2×2，所以替换成3乘积更大；
    44 综上，选用尽量多的3，直到剩下2或者4时，用2。
    45 
    46 时间复杂度分析：当 nn 比较大时，nn 会被拆分成 ⌈n/3⌉⌈n/3⌉ 个数，我们需要计算这么多次减法和乘法，所以时间复杂度是 O(n)O(n)。
    47 
    48 作者：yxc
    49 链接：https://www.acwing.com/solution/acwing/content/731/
    50 来源：AcWing
    51 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    52 * */
    53 public class 发散思维能力_剪绳子 {
    54     public static int maxProductAfterCutting(int length)
    55     {
    56         int res = 1;
    57         if(length == 2)
    58             res = 1;
    59         if(length == 3)
    60             res = 2;
    61         if(length == 4)
    62             res = 4;
    63         else if(length > 4){
    64             int n3 = 0;
    65             if(length%3 == 1){
    66                 n3 = (length-4)/3;
    67                 res *= 4*Math.pow(3,n3);
    68             }
    69             if(length%3 == 2){
    70                 n3 = length/3;
    71                 res *= 2*Math.pow(3,n3);
    72             }
    73             else if(length%3 == 0){
    74                 n3 = length/3;
    75                 res *=Math.pow(3,n3);
    76             }
    77         }
    78         return res;
    79     }
    80 
    81     public static void main(String[] args) {
    82         maxProductAfterCutting(7);
    83     }
    84 
    85 }

剪绳子

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //本题有两个，一个来自ACwing, 解法比较巧妙
 2 //还有一个见下方，来自牛客
 3 
 4 /*
 5 描述：
 6 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 7 
 8 假设数组非空，并且一定存在满足条件的数字。
 9 
 10 要求只能使用 O(n) 的时间和额外 O(1) 的空间，该怎么做呢？
 11 * */
 12 import java.util.*;
 13 
 14 /*
 15 * 题解
 16 * 用一个cnt记录次数
 17 * 一个val记录值
 18 * 如果下一个数与保存的val相同，则cnt++;
 19 * 否则
 20 * cnt--
 21 * 当cnt减到0了，就把val重新赋给新值
 22 * 因为数组中有一个数多于一半，所以最后val中保存的一定是这个数字
 23 * */
 24 public class 发散思维能力_数组中出现次数超过一半的数字 {
 25 public int MoreThanHalfNum_Solution(int[] array) {
 26 int cnt = 0;
 27 int val = -1;
 28 for (int x : array) {
 29 if (cnt == 0) {
 30 val = x;
 31 cnt = 1;
 32 } else {
 33 if (x == val)
 34 cnt++;
 35 else
 36 cnt--;
 37 }
 38 
 39 }
 40 return val;
 41 }
 42 
 43 /*
 44 题目描述
 45 * 数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。
 46 * 例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，
 47 * 超过数组长度的一半，因此输出2。如果不存在则输出0。
 48 * */
 49 
 50 // 下面的解法是牛客网上题目的解法，其实牛客的这道题目意义不大，就是统计每个数字出现次数找出出现次数最大的数字这样一个过程
 51 // 下面的解法主要训练了自己使用HashMap按照value降序排序的一个方法
 52 public static int m(int[] array) {
 53 Map<Integer, Integer> res = new HashMap<>();
 54 for (int x : array) {
 55 if (res.containsKey(x))
 56 res.put(x, res.get(x) + 1);
 57 else
 58 res.put(x, 1);
 59 }
 60 List<Map.Entry<Integer, Integer>> list = new ArrayList<>(res.entrySet());
 61 Collections.sort(list, (Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2)->o2.getValue().compareTo(o1.getValue()));
 62 int max = list.get(0).getValue();
 63 if (max > array.length / 2)
 64 return list.get(0).getKey();
 65 else
 66 return 0;
 67 }
 68 
 69 public static void main(String[] args) {
 70 发散思维能力_数组中出现次数超过一半的数字 a = new 发散思维能力_数组中出现次数超过一半的数字();
 71 int [] arr = {1,2,3,2,2,2,5,4,2};
 72 System.out.println(a.m(arr));
 73 }
 74 }

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 *求1+2+3+...+n，要求不能使用乘除法、
     3 * for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
     4 * */
     5 //链接：https://www.nowcoder.com/questionTerminal/7a0da8fc483247ff8800059e12d7caf1
     6 //        来源：牛客网
     7 /*题目说了不许用循环，那就摆明了是要递归了。*/
     8 /*链接：https://www.nowcoder.com/questionTerminal/7a0da8fc483247ff8800059e12d7caf1
     9 来源：牛客网
    10 
    11 1.需利用逻辑与的短路特性实现递归终止。
    12 2.当n==0时，(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断，为false，然后直接返回0；
    13 3.当n>0时，执行sum+=Sum_Solution(n-1)，实现递归计算Sum_Solution(n)。*/
    14 public class 发散思维能力_求1加2加3加n {
    15     public int Sum_Solution(int n) {
    16         int sum = n;
    17         boolean flag = (sum>0)&&((sum+=Sum_Solution(--n))>0); //短路特性， boolean值没有意义
    18         return sum;
    19     }
    20 }

求1加2加3加n

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 import java.util.Deque;
 2 import java.util.LinkedList;
 3 
 4 /*
 5 *题目描述
 6 地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，
 7 每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐
 8 标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能
 9 够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方
 10 格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？
 11 * */
 12 
 13 /*
 14 * 解题思路：
 15 * 宽搜
 16 * */
 17 public class 回溯法_机器人的运动范围 {
 18 public int movingCount(int threshold, int rows, int cols) {
 19 int res = 0;
 20 if (rows == 0 || cols == 0)
 21 return 0;
 22 boolean[][] mark = new boolean[rows][cols];
 23 Deque<int[]> pair = new LinkedList<>();
 24 pair.push(new int[]{0, 0});
 25 
 26 int[] dx = {-1, 0, 1, 0};
 27 int[] dy = {0, -1, 0, 1};
 28 
 29 while (!pair.isEmpty()) {
 30 int[] t = pair.poll();
 31 if (get_sum(t) > threshold || mark[t[0]][t[1]])
 32 continue;
 33 res++;
 34 mark[t[0]][t[1]] = true;
 35 for (int i = 0; i < 4; i++) {
 36 int x = t[0] + dx[i];
 37 int y = t[1] + dy[i];
 38 if(x>=0 && x<rows && y>=0 && y<cols)
 39 pair.push(new int[] {x,y});
 40 }
 41 }
 42 return res;
 43 }
 44 
 45 static int get_sum(int[] p) {
 46 return get_sum(p[0]) + get_sum(p[1]);
 47 }
 48 
 49 static int get_sum(int x) {
 50 int s = 0;
 51 while (x > 0) {
 52 s += x % 10;
 53 x /= 10;
 54 }
 55 return s;
 56 }
 57 }

机器人的运动范围

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。
 4 路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。
 5 如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。
 6 例如
 7 a b c e
 8 s f c s
 9 a d e e
 10 这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，
 11 但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，
 12 路径不能再次进入该格子。*/
 13 public class 回溯法_矩阵中的路径 {
 14 static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
 15 // 特殊情况
 16 if (matrix.length == 1)
 17 return matrix[0] == str[0];
 18 // 暴力枚举
 19 // char[][] matrix_ = new char[rows][cols];
 20 // int k = 0;
 21 // 将一维转为二维
 22 // for (int i = 0; i < rows; i++)
 23 // for (int j = 0; j < cols; j++)
 24 // matrix_[i][j] = matrix[k++];
 25 
 26 // 枚举所有起点
 27 for (int i = 0; i < rows; i++)
 28 for (int j = 0; j < cols; j++)
 29 // dfs是在该起点的基础上枚举所有方向
 30 if (dfs(matrix, str, 0, i, j, rows, cols))
 31 return true;
 32 return false;
 33 }
 34 
 35 // dfs的作用是枚举所有方向
 36 static boolean dfs(char[] matrix, char[] str, int u, int x, int y, int rows, int cols) {
 37 // 如果当前u的长度达到了要匹配的字符串的末尾，则返回true
 38 if (u == str.length) return true;
 39 // 如果当前字符和str上要找u处的字符不同，返回false
 40 if (matrix[x*cols+y] != str[u]) return false;
 41 // 枚举方向的常用方法
 42 int[] dx = {-1, 0, 1, 0};
 43 int[] dy = {0, 1, 0, -1};
 44 // 为了保证不走重复路线（不往回走），需要将走过的位置标记，但是在退出该条枚举路线之前需要还原现场
 45 char t = matrix[x*cols+y];
 46 matrix[x*cols+y] = '*';
 47 // 枚举四个方向
 48 for (int i = 0; i < 4; i++) {
 49 int a = x + dx[i];
 50 int b = y + dy[i];
 51 if (a >= 0 && a < rows && b >= 0 && b < cols) {
 52 // 如果后面递归的结果是true,那么到了本层应该把true传递到下一层
 53 if (dfs(matrix, str, u + 1, a, b, rows, cols))
 54 return true;
 55 }
 56 }
 57 matrix[x*cols+y] = t;
 58 return false;
 59 }
 60 
 61 public static void main(String[] args) {
 62 char[] a = {'A'};
 63 char[] b = {'A'};
 64 System.out.println(hasPath(a, 1, 2, b));
 65 }
 66 }
 67 //下面是通过的题解2,不用转为二维矩阵
 68 /*
 69 * static boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
 70 if (matrix.length == 1)
 71 return matrix[0] == str[0];
 72 
 73 for (int i = 0; i < rows; i++) {
 74 for (int j = 0; j < cols; j++) {
 75 if (dfs(matrix, 0, i, j, str, rows, cols))
 76 return true;
 77 }
 78 }
 79 return false;
 80 }
 81 
 82 static boolean dfs(char[] matrix, int u, int x, int y, char[] str, int rows, int cols) {
 83 if (u == str.length) return true;
 84 if (matrix[x * cols + y] != str[u]) return false;
 85 char tmp = matrix[x * cols + y];
 86 matrix[x * cols + y] = '*';
 87 int[] dx = {-1, 0, 1, 0};
 88 int[] dy = {0, 1, 0, -1};
 89 for (int i = 0; i < 4; i++) {
 90 int a = x + dx[i];
 91 int b = y + dy[i];
 92 //
 93 if (a >= 0 && a < rows && b >= 0 && b < cols) {
 94 if (dfs(matrix, u + 1, a, b, str, rows, cols))
 95 return true;
 96 }
 97 }
 98 matrix[x * cols + y] = tmp;
 99 return false;
 100 }
 101 * */
 102 //下面是通过的题解1,要先转为二维矩阵
 103 /*public class Solution {
 104 public boolean hasPath(char[] matrix, int rows, int cols, char[] str) {
 105 if(matrix.length==1)
 106 return matrix[0] == str[0];
 107 char[][] matrix_ = new char[rows][cols];
 108 int k = 0;
 109 for (int i = 0; i < rows; i++)
 110 for (int j = 0; j < cols; j++)
 111 matrix_[i][j] = matrix[k++];
 112 
 113 for (int i = 0; i < rows; i++)
 114 for (int j = 0; j < cols; j++)
 115 if (dfs(matrix_, str, 0, i, j))
 116 return true;
 117 return false;
 118 }
 119 
 120 boolean dfs(char[][] matrix, char[] str, int u, int x, int y) {
 121 if (u == str.length) return true;
 122 if (matrix[x][y] != str[u]) return false;
 123 int[] dx = {-1, 0, 1, 0};
 124 int[] dy = {0, -1, 0, 1};
 125 char t = matrix[x][y];
 126 matrix[x][y] = '*';
 127 for (int i = 0; i < 4; i++) {
 128 int a = x + dx[i];
 129 int b = y + dy[i];
 130 if (a >= 0 && a < matrix.length && b >= 0 && b < matrix[a].length) {
 131 if (dfs(matrix, str, u + 1, a, b))
 132 return true;
 133 }
 134 }
 135 matrix[x][y] = t;
 136 return false;
 137 }
 138 }*/

矩阵中的路径

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 import java.util.Comparator;
 2 import java.util.PriorityQueue;
 3 
 4 /*题目描述
 5 如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。
 6 如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
 7 我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。*/
 8 
 9 /*
 10 * 解题思路（来自雪菜）：
 11 * 维护两个堆（图见 堆_数据流的中位数.png）
 12 * 维护一个大根堆和一个小根堆，如图:
 13 * 小根堆在上，存的是较大的数（小根堆的堆顶是堆里最小的数，小根堆里其他数都比它大）；
 14 * 大根堆在下，存的是较小的数（大根堆的堆顶是堆里较大的数，大根堆里其他数都比它小）；
 15 * 我们的目的是维护这两个堆，使得小根堆里面存的数都比大根堆里面存的数大
 16 * 每次插入数据都从下面的小根堆插入，插入后，比较大根堆和小根堆堆顶数的大小，如果下面的大根堆的堆顶比上面的小根堆的堆顶要大，
 17 * 则交换两个堆的堆顶；
 18 * 然后再进行一步判断:如果下面的大根堆的数据的个数比上面小根堆的数据个数多2个，则直接取出下面大根堆堆顶元素插入上面的小根堆中；
 19 *
 20 * 最后判断:
 21 * 如果两个堆中元素的总个数为奇数，则中位数是下面大根堆的堆顶；
 22 * 如果两个堆中元素的总个数为偶数，则中位数是两个堆堆顶元素的平均数
 23 * */
 24 public class 堆_数据流的中位数 {
 25 
 26 // 优先队列默认是按自然顺序排序，也就是从小到大排序的
 27 PriorityQueue<Integer> min_heap = new PriorityQueue<>();
 28 PriorityQueue<Integer> max_heap = new PriorityQueue<>(Comparator.reverseOrder());
 29 public void Insert(Integer num) {
 30 max_heap.offer(num);
 31 // 每次插入数据都从下面的小根堆插入，插入后，比较大根堆和小根堆堆顶数的大小，如果下面的大根堆的堆顶比上面的小根堆的堆顶要大，
 32 // 则交换两个堆的堆顶；
 33 if(!min_heap.isEmpty() && !max_heap.isEmpty() && min_heap.peek()<max_heap.peek()){
 34 int tmp_big = max_heap.poll();
 35 int tmp_small = min_heap.poll();
 36 min_heap.offer(tmp_big);
 37 max_heap.offer(tmp_small);
 38 }
 39 //如果下面的大根堆的数据的个数比上面小根堆的数据个数多2个，则直接取出下面大根堆堆顶元素插入上面的小根堆中；
 40 if(max_heap.size() - min_heap.size() > 1){
 41 min_heap.offer(max_heap.poll());
 42 }
 43 }
 44 
 45 // 如果两个堆中元素的总个数为奇数，则中位数是下面大根堆的堆顶；
 46 // 如果两个堆中元素的总个数为偶数，则中位数是两个堆堆顶元素的平均数
 47 public Double GetMedian() {
 48 if ((max_heap.size() + min_heap.size())%2 != 0)
 49 return new Double(max_heap.peek());
 50 else
 51 return (max_heap.peek().doubleValue()+min_heap.peek().doubleValue())/2;
 52 
 53 }
 54 }

数据流的中位数

![1135658-20190611215637303-1683623977.png][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*请实现一个函数，将一个字符串中的每个空格替换成“%20”。
 2 例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。*/
 3 public class 字符串_替换空格 {
 4 public static String replaceSpace(StringBuffer str) {
 5 int size = str.length();
 6 for (int i = 0; i < size; i++) {
 7 if (str.charAt(i) == 32) {
 8 str.replace(i, i + 1, "%20");
 9 i = i + 2;
 10 size = size + 2;
 11 }
 12 }
 13 return str.toString();
 14 }
 15 
 16 public static void main(String[] args) {
 17 System.out.println(字符串_替换空格.replaceSpace(new StringBuffer(" I love you ")));
 18 }
 19 }

替换空格

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 * 请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，
     3 * 字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。
     4 * 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。
     5 * */
     6 public class 字符串_表示数值的字符串 {
     7     public static void main(String[] args) {
     8         int[] p;
     9 
    10     }
    11 }

表示数值的字符串

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 *题目描述
 3 输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 4 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 5 * */
 6 
 7 /*
 8 *题解：
 9 *算法1
 10 (后序遍历，递归) O(n)O(n)
 11 后序遍历，数组的最后一个值是二叉树的根节点
 12 
 13 所以前面的值一部分小于根节点，一部分大于根节点，因为是二叉搜索树
 14 
 15 找到比根节点小的，则为左子树
 16 
 17 比根节点大的为右子树
 18 
 19 然后递归整个数组即可
 20 * */
 21 //本题是week4的题目
 22 public class 循环和递归_二叉搜索树的后序遍历序列 {
 23 int[] seq;
 24 public boolean VerifySquenceOfBST(int [] sequence) {
 25 if(sequence.length == 0 ) return false;
 26 seq = sequence;
 27 return dfs(0, sequence.length-1);
 28 }
 29 
 30 boolean dfs(int l, int r){
 31 if(l >= r) return true;//如果子树的长度为0，则遍历到叶子节点，为真
 32 int root = seq[r]; //后序遍历的最后一个值是搜索二叉树的根节点
 33 int k = l;
 34 while(k<r && seq[k]<root)
 35 k++;//找到以root为根的左子树序列的位置（由于二叉搜索树的属性，其左子树都比根节点要小）
 36 for(int i = k; i < r; i++){
 37 if(seq[i]<root){
 38 return false;//从左子树的右边开始是右子树，根据二叉搜索树的性质，根节点的右子树
 39 //都比根节点要大，如果出现了比根节点小的节点，则说明这棵树不合定义，返回false
 40 }
 41 }
 42 return dfs(l, k-1) && dfs(k+1,r);//递归检查左右子树
 43 }
 44 }

二叉搜索树的后序遍历序列

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 *题目描述
 3 输入一颗二叉树的跟节点和一个整数，打印出二叉树中结点值的和为输入整数的所有路径。
 4 路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。(注意: 在返回值的list中，数组长度大的数组靠前)
 5 * */
 6 
 7 /*
 8 * 题解
 9 *本题就是一个遍历,遍历每条路径,保存符合要求的路径
 10 * 如何保存并还原现场是一个难点
 11 * */
 12 
 13 import java.util.ArrayList;
 14 
 15 /**
 16 * public class TreeNode {
 17 * int val = 0;
 18 * TreeNode left = null;
 19 * TreeNode right = null;
 20 * 
 21 * public TreeNode(int val) {
 22 * this.val = val;
 23 * 
 24 * }
 25 * 
 26 * }
 27 */
 28 
 29 public class 循环和递归_二叉树中和为某一值的路径 {
 30 ArrayList<ArrayList<Integer>> ans = new ArrayList<>();
 31 ArrayList<Integer> path = new ArrayList<>();
 32 
 33 public ArrayList<ArrayList<Integer>> FindPath(TreeNode root, int target) {
 34 dfs(root, target);
 35 return ans;
 36 }
 37 
 38 void dfs(TreeNode root, int sum) {
 39 if (root == null)//如果遍历到头(即到了空节点),直接返回
 40 return;
 41 path.add(root.val);//如果当前不是空节点,把该节点放进路径链表中
 42 sum -= root.val;//将目标值减去该节点
 43 //某条路径符合要求的条件是:1.该节点是叶子节点 (root.left == null && root.right == null)
 44 // 2. 并且到该节点时路径上所有节点总和为sum (&& sum == 0)
 45 if (root.left == null && root.right == null && sum == 0)
 46 // 错误写法：
 47 // ans.add(path); path是变量，如果把path直接存进ans里面，存的是path的引用，而path在之后还会发生变化，所以存进ans里面的答案会随之
 48 // 变化(记住ans.add(path)这样在ans里面存的是path的引用),所以需要拷贝当前path的副本,把副本存到ans里面去,这样后面path的变化不会影响到
 49 // 存到ans里面的路径
 50 ans.add(new ArrayList<>(path));//将符合要求的路径保存进答案中
 51 dfs(root.left, sum);//递归遍历左子树
 52 dfs(root.right, sum);//递归遍历右子树
 53 //还原现场,因为我们不光遍历一个分支,还要遍历其他分支.所以在遍历完当前子树之后(不论当前路径是否符合要求)
 54 //要把当前节点造成的影响消除,在path中去掉当前的节点(因为当前节点所在的路径已经被考察过)
 55 path.remove(path.size()-1);
 56 //sum不用还原,因为sum传过来的时标量不是地址
 57 }
 58 
 59 public static void main(String[] args) {
 60 TreeNode h = new TreeNode(10);
 61 h.left = new TreeNode(5);
 62 h.right = new TreeNode(12);
 63 h.left.left = new TreeNode(4);
 64 h.left.right = new TreeNode(7);
 65 
 66 循环和递归_二叉树中和为某一值的路径 a = new 循环和递归_二叉树中和为某一值的路径();
 67 System.out.println(a.FindPath(h,22).toString());
 68 }
 69 }

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

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 *题目描述
     3 操作给定的二叉树，将其变换为源二叉树的镜像。
     4 输入描述:
     5 二叉树的镜像定义：源二叉树
     6             8
     7            /  \
     8           6   10
     9          / \  / \
    10         5  7 9 11
    11         镜像二叉树
    12             8
    13            /  \
    14           10   6
    15          / \  / \
    16         11 9 7  5
    17 * */
    18 
    19 /*
    20 * 题解
    21 * */
    22 public class 循环和递归_二叉树的镜像 {
    23     public void Mirror(TreeNode root) {
    24         if(root == null)
    25             return;
    26         else{
    27             //后序
    28             Mirror(root.left);
    29             Mirror(root.right);
    30             //执行交换
    31             TreeNode tmp = root.left;
    32             root.left = root.right;
    33             root.right = tmp;
    34 //            前序也可以
    35 /*            Mirror(root.left);
    36             Mirror(root.right);
    37             TreeNode tmp = root.left;
    38             root.left = root.right;
    39             root.right = tmp;*/
    40         }
    41     }
    42 }

二叉树的镜像

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。
 4 求该青蛙跳上一个n级的台阶总共有多少种跳法。
 5 * */
 6 public class 循环和递归_变态跳台阶 {
 7 // 递归
 8 static public int JumpFloorII(int target) {
 9 if (target < 2)
 10 return 1;
 11 else {
 12 int res = 0;
 13 for (int i = 0; i < target; i++)
 14 res = res + JumpFloorII(i);
 15 return res;
 16 }
 17 }
 18 
 19 // 动态规划
 20 static public int JumpFloorIII(int target) {
 21 int[] val = new int[target];
 22 int res = 0;
 23 for (int i = 0; i < target; i++)
 24 res = res + dp(i, val);
 25 return res;
 26 }
 27 
 28 static int dp(int target, int[] val) {
 29 if (target < 2) {
 30 val[target] = 1;
 31 return val[target];
 32 } else {
 33 if (val[target] == 0) {
 34 for (int i = 0; i < target; i++) {
 35 val[target] += dp(i, val);
 36 }
 37 }
 38 return val[target];
 39 }
 40 }
 41 
 42 public static void main(String[] args) {
 43 System.out.println(JumpFloorIII(4));
 44 System.out.println(JumpFloorII(4));
 45 }
 46 }

变态跳台阶

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*题目描述
 2 大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0）。
 3 n<=39*/
 4 public class 循环和递归_斐波那契数列 {
 5 public static int Fibonacci(int n) {
 6 int[] dp = new int[n + 1];
 7 return Fib(n, dp);
 8 }
 9 
 10 static int Fib(int i, int[] dp) {
 11 if (i < 2) {
 12 dp[i] = i;
 13 return dp[i];
 14 } else {
 15 if (dp[i] == 0)
 16 dp[i] = Fib(i - 1, dp) + Fib(i - 2, dp);
 17 return dp[i];
 18 }
 19 }
 20 
 21 public static void main(String[] args) {
 22 System.out.println(Fibonacci(0));
 23 }
 24 
 25 }

斐波那契数列

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 *题目描述
     3 输入两棵二叉树A，B，判断B是不是A的子结构。
     4 （ps：我们约定空树不是任意一个树的子结构）
     5 * */
     6 
     7 /*
     8 *题解:
     9 * 代码分为两个部分：
    10 
    11 遍历树A中的所有非空节点R；
    12 判断树A中以R为根节点的子树是不是包含和树B一样的结构，且我们从根节点开始匹配；
    13 对于第一部分，我们直接递归遍历树A即可，遇到非空节点后，就进行第二部分的判断。
    14 
    15 对于第二部分，我们同时从根节点开始遍历两棵子树：
    16 
    17 如果树B中的节点为空，则表示当前分支是匹配的，返回true；
    18 如果树A中的节点为空，但树B中的节点不为空，则说明不匹配，返回false；
    19 如果两个节点都不为空，但数值不同，则说明不匹配，返回false；
    20 否则说明当前这个点是匹配的，然后递归判断左子树和右子树是否分别匹配即可；
    21 时间复杂度
    22 最坏情况下，我们对于树A中的每个节点都要递归判断一遍，每次判断在最坏情况下需要遍历完树B中的所有节点。
    23 所以时间复杂度是 O(nm)O(nm)，其中 nn 是树A中的节点数， mm 是树B中的节点数。
    24 
    25 链接：https://www.acwing.com/solution/acwing/content/745/
    26 * */
    27 public class 循环和递归_树的子结构 {
    28     public boolean HasSubtree(TreeNode root1,TreeNode root2) {
    29         if(root1 == null || root2 == null) return false;
    30         if(isPart(root1, root2)) return true;
    31         return HasSubtree(root1.left, root2)||HasSubtree(root1.right, root2);
    32     }
    33 
    34     public boolean isPart(TreeNode p1, TreeNode p2){
    35         if(p2 == null) return true;
    36         if(p1 == null || p1.val!=p2.val) return false;
    37         return isPart(p1.left, p2.left)&&isPart(p1.right, p2.right);
    38     }
    39 }

树的子结构

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 我们可以用2*1的小矩形横着或者竖着去覆盖更大的矩形。
 3 * 请问用n个2*1的小矩形无重叠地覆盖一个2*n的大矩形，总共有多少种方法？
 4 * */
 5 
 6 /*
 7 * 解题思路：
 8 　　观察题目中的矩形，2*n的，是个长条形。本来脑中想象的是复杂的华容道，但是既然只是简单的长条形，
 9 那么依然逆向分析。既然是长条形的，那么从后向前，最后一个矩形2*2的，只有两种情况：
 10 
 11 　　 第一种是最后是由一个2*(n-1)的矩形加上一个竖着的2*1的矩形
 12 　　另一种是由一个2*(n-2)的矩形，加上两个横着的2*1的矩形
 13 　　因此我们可以得出，
 14 　　第2*n个矩形的覆盖方法等于第2*(n-1)加上第2*(n-2)的方法。使用代码可以表示为：
 15 for(i=3;i<71;i++){
 16 arr[i] = arr[i-1]+arr[i-2];
 17 }
 18 　　仍然要注意数据类型，为long long型
 19 题解来自 https://www.cnblogs.com/xing901022/p/3753718.html
 20 * */
 21 public class 循环和递归_矩形覆盖 {
 22 public int RectCover(int target) {
 23 int[] res = new int[1000000];
 24 res[0] = 0;
 25 res[1] = 1;
 26 res[2] = 2;
 27 if(target<3)
 28 return res[target];
 29 else
 30 return cal(target, res);
 31 }
 32 
 33 public int cal(int n, int[] res){
 34 if(res[n]!=0)
 35 return res[n];
 36 else{
 37 int tmp = cal(n-1,res)+cal(n-2,res);
 38 res[n] = tmp;
 39 return res[n];
 40 }
 41 }
 42 }

矩形覆盖

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*一只青蛙一次可以跳上1级台阶，也可以跳上2级。
 2 求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）。*/
 3 public class 循环和递归_跳台阶 {
 4 // 递归
 5 public int JumpFloor(int target) {
 6 if (target < 2)
 7 return 1;
 8 else
 9 return JumpFloor(target - 1) + JumpFloor(target - 2);
 10 }
 11 
 12 // 动态规划
 13 
 14 public int JumpFloorI(int target) {
 15 int[] val = new int[target + 1];
 16 return dp(target, val);
 17 }
 18 
 19 public int dp(int target, int[] val) {
 20 if (target < 2) {
 21 val[target] = 1;
 22 return val[target];
 23 } else {
 24 if (val[target] == 0)
 25 val[target] = dp(target - 1, val) + dp(target - 2, val);
 26 return val[target];
 27 }
 28 }
 29 }

跳台阶

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 给定一个数字，我们按照如下规则把它翻译为字符串：
 3 0翻译成”a”，1翻译成”b”，……，11翻译成”l”，……，25翻译成”z”。
 4 一个数字可能有多个翻译。例如12258有5种不同的翻译，它们分别是”bccfi”、”bwfi”、”bczi”、”mcfi”和”mzi”。
 5 请编程实现一个函数用来计算一个数字有多少种不同的翻译方法。
 6 样例
 7 输入："12258"
 8 输出：5
 9 * */
 10 
 11 /*
 12 *这是一个DP问题：
 13 * 1.状态怎么表示
 14 * f[i]表示前i位数字有多少种不同的翻译方式：
 15 * a.如果将第i位翻译成一个单独的字母，则f[i] = f[i-1];
 16 * b.如果i-1位和第i位共同翻译成一个字母，则f[i] = f[i-2]+f[i-1]
 17 * 前i个字母翻译结果的所有情况会被这两部分完全覆盖，且这两部分没有交集。
 18 * 这两类加起来就是所有的情况。
 19 *
 20 * 2.状态如何计算
 21 * 3.边界
 22 * */
 23 public class 把数字翻译成字符串 {
 24 public static int getTranslationCount(String s) {
 25 char[] sc = s.toCharArray();
 26 int n = sc.length;
 27 int[] f = new int[n + 1];
 28 f[1] = 1;
 29 for (int i = 2; i <= n; i++) {
 30 
 31 f[i] = f[i - 1];//第i位数字单独翻译成一个字母时，前i个数字的翻译方案数等于前i-1个数字的翻译方案数
 32 // 检查第i-1和第i-2位是否可以组成合法的可翻译为一个字母的数字
 33 // 注意这里下标在f[]中和在sc[]中表示的数位有偏移，在sc中，下标从0开始； 在f[]中，下标从1开始；所以前i位的方案数用f[i]表示，但第i个字符用sc[i-1]表示
 34 int t = (sc[i - 2] - '0') * 10 + sc[i - 1] - '0';//t表示由第i位和第i-1位数字组成的两位数字
 35 // 第i和第i-1位的组合结果有两种状态不能被翻译成一个字母：一、05这样的前面有0的；二、>=26的。
 36 // 所以只有在10~26之间的数字可以合法的被一个字母翻译
 37 if (t >= 10 && t <= 25)
 38 // 如果满足上述条件，则前i个数字的翻译方案还可以是前i-2位数字的翻译方案数，
 39 f[i] += f[i - 2];
 40 }
 41 return f[n];
 42 }
 43 
 44 public static void main(String[] args) {
 45 getTranslationCount("12258");
 46 }
 47 }

把数字翻译成字符串

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。
 4 例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。
 5 * */
 6 
 7 import java.util.Arrays;
 8 //import java.util.Comparator;
 9 
 10 /*
 11 *我们想，如果比较大小的时候，可以按照拼接结果的大小来对数组进行排序，则排序结果天然就能满足要求
 12 *1.需要定义一个新的比较大小的规则
 13 * 比较a和b两个数，如果a ab < ba (ab表示将数字a和数字b直接连接成一个新的数字ab)
 14 *2.利用上述定义的大小比较规则将给定的数组排序
 15 *3.从排好序的数组里按从小到大的顺序取出数字来拼接成最终答案
 16 * 就是最小数字了
 17 *
 18 * 首先，满足上述大小比较规则的结果一定能是最小的结果，这是不言而喻的（a ab < ba 这个性质决定的）
 19 * 其次，如果要定义一种大小比较规则，则离散数学告诉我们，这个规则必须满足一下两个定律该大小比较规则才能成立:
 20 * a.反对称性:a<=b, b<=a 则 => a=b
 21 * b.传递性: a<=b, b<=c, 则 => a<=c
 22 * 可以自行证明一下上面两条规律
 23 * */
 24 public class 把数组排成最小的数 {
 25 
 26 /* class cmp implements Comparator<String>{
 27 @Override
 28 public int compare(String o1, String o2) {
 29 return (o1+o2).compareTo(o2+o1);
 30 }
 31 }*/
 32 
 33 public String PrintMinNumber(int [] numbers) {
 34 // 先转为字符串
 35 String [] snum = new String[numbers.length];
 36 int j = 0;
 37 for(int i: numbers)
 38 snum[j++] = String.valueOf(i);
 39 // 重写大小比较规则
 40 Arrays.sort(snum,(String s1, String s2)->(s1+s2).compareTo(s2+s1));
 41 StringBuilder res = new StringBuilder();
 42 for(String x:snum)
 43 res.append(x);
 44 return res.toString();
 45 }
 46 }

把数组排成最小的数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 * 数字以0123456789101112131415…的格式序列化到一个字符序列中。
     3 在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。
     4 请写一个函数求任意位对应的数字。
     5 样例
     6 输入：13
     7 输出：1
     8 来源:Acwing
     9 * */
    10 
    11 /*
    12 *
    13 * */
    14 public class 数字序列中某一位的数字 {
    15 }

数字序列中某一位的数字

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 数字以0123456789101112131415…的格式序列化到一个字符序列中。
 3 在这个序列中，第5位（从0开始计数）是5，第13位是1，第19位是4，等等。
 4 请写一个函数求任意位对应的数字。
 5 
 6 样例
 7 输入：13
 8 输出：1
 9 * */
 10 
 11 /*
 12 * 题解:
 13 * 我们要求的是该字符串中位置p上的数字
 14 * 1.确定该位置p所属数字n是几位数: 假设n-10-90*2-900*3 = 256，说明n是四位数字，且p的位置在从1000开始往后数的第256位，
 15 * 2.确定数字n是哪个数: 四位数字的开始是1000，又四位数每个数字有四位，故n=1000+256/4 =1064
 16 * 3.确定位置p属于数字n的第几位：256除以4余数为0，故是该位数字的最后一位
 17 * */
 18 public class 数字题_数字序列中某一位的数字 {
 19 public int digitAtIndex(int n) {
 20 long i = 1;
 21 long s = 9;
 22 long base = 1;
 23 while(n>i*s){
 24 n -= i*s;
 25 i++;
 26 s *= 10;
 27 base *= 10;
 28 }
 29 // 2.算出p位置所属的数字n是多少
 30 // n除以i,上取整的写法：(n+i-1)/i-1
 31 long number = base + (n+i-1)/i-1;
 32 // 3.求p在数字n中是第几个数字，如果余数为零是左后一位数字，将r置为i
 33 long r = n%i!=0? n%i:i;
 34 // 取出i位数的第r位出来
 35 for(int j = 0; j<i-r; j++)
 36 number/=10;
 37 return (int)number%10;
 38 }
 39 }

数字序列中某一位的数字

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*题目描述
 2 在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 3 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一
 4 个整数，判断数组中是否含有该整数*/
 5 public class 数组_二维数组中的查找 {
 6 public static boolean Find(int target, int[][] array) {
 7 if (array == null || array.length==0 ||(array.length==1&&array[0].length==0)||array[0][0] > target)
 8 return false;
 9 else {
 10 
 11 for (int i = 0; i < array.length; i++) {
 12 if (array[i][0] > target || array[i][array.length - 1] < target)
 13 continue;
 14 else if (二分查找_判断有无给定元素.binarySearch2(target, array[i]))
 15 return true;
 16 }
 17 return false;
 18 }
 19 }
 20 
 21 
 22 public static void main(String[] args) {
 23 // int[][] a = {
 {1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}};
 24 // int[][] a = {
 {}};
 25 // System.out.println(Find(1, a));
 26 int[] a = {1, 2, 8, 9};
 27 System.out.println(二分查找_判断有无给定元素.binarySearch(1, a, 0, a.length-1));
 28 }
 29 }

二维数组中的查找

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 *题目描述
 3 输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，
 4 例如，如果输入如下4 X 4矩阵：
 5 1 2 3 4
 6 5 6 7 8
 7 9 10 11 12
 8 13 14 15 16
 9 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
 10 * */
 11 
 12 import java.util.ArrayList;
 13 
 14 /*
 15 *题解:
 16 * 算法
 17 (模拟) O(n2)O(n2)
 18 我们顺时针定义四个方向：上右下左。
 19 从左上角开始遍历，先往右走，走到不能走为止，然后更改到下个方向，再走到不能走为止，依次类推，遍历 n2n2 个格子后停止。
 20 
 21 时间复杂度
 22 矩阵中每个格子遍历一次，所以总时间复杂度是 O(n^2)。
 23 * */
 24 public class 数组_顺时针打印矩阵 {
 25 public ArrayList<Integer> printMatrix(int [][] matrix) {
 26 
 27 ArrayList<Integer> res = new ArrayList<>();
 28 
 29 if(matrix == null || matrix[0] == null)
 30 return res;
 31 int m = matrix.length;
 32 int n = matrix[0].length;
 33 int[][] visited = new int[m][n];//记录是否访问过
 34 
 35 int[] dx = {-1,0,1,0};
 36 int[] dy = {0,1,0,-1};
 37 
 38 int x = 0;
 39 int y = 0;
 40 int d = 1;
 41 
 42 for(int i = 0; i < m; i++){
 43 for(int j = 0; j<n; j++){
 44 res.add(matrix[x][y]);
 45 visited[x][y] = 1;
 46 int a = x+dx[d];
 47 int b = y+dy[d];
 48 if(a<0||a>=m||b<0||b>=n || visited[a][b]==1){
 49 d = (d+1)%4;
 50 a = x+dx[d];
 51 b = y+dy[d];
 52 }
 53 x = a;
 54 y = b;
 55 }
 56 }
 57 return res;
 58 }
 59 }

顺时针打印矩阵

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 求出1~13的整数中1出现的次数,并算出100~1300的整数中1出现的次数？
 3 * 为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,
 4 * 但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,
 5 * 可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。
 6 * */
 7 
 8 import java.util.ArrayList;
 9 import java.util.List;
 10 
 11 /*
 12 *
 13 * */
 14 public class 整数中1出现的个数 {
 15 public int NumberOf1Between1AndN_Solution(int n) {
 16 if (n == 0)
 17 return 0;
 18 List<Integer> number = new ArrayList<>();
 19 while (n != 0) {
 20 number.add(n % 10);
 21 n /= 10;
 22 }
 23 int res = 0;
 24 for (int i = number.size() - 1; i >= 0; i--) {
 25 int left = 0;
 26 int right = 0;
 27 int t = 1;
 28 for (int j = number.size() - 1; j > i; j--) {
 29 left = left * 10 + number.get(j);
 30 }
 31 for (int j = i - 1; j >= 0; j--) {
 32 right = right * 10 + number.get(j);
 33 t *= 10;
 34 }
 35 res += left * t;
 36 if (number.get(i) == 1) res += right+1;
 37 else if (number.get(i) > 1)
 38 res += t;
 39 }
 40 return res;
 41 }
 42 }

整数中1出现的个数

![1135658-20190611221234816-1373163006.png][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*题目描述
 2 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，
 3 则最小的4个数字是1,2,3,4,。*/
 4 
 5 import java.util.ArrayList;
 6 import java.util.PriorityQueue;
 7 import java.util.Comparator;
 8 
 9 /*
 10 * 解法:
 11 * 从一堆数字里面找到前n大的数要建最小堆，这样堆顶是当前堆里的最小数，来了一个新数，如果它比堆顶的最小数大，就把堆顶的数替换成当前数，并调整堆使得当前堆顶仍然是最小数
 12 * 同理从一堆数字里面找到前n小的数要建最大堆，因此下面的优先队列的比较器需要重写
 13 * */
 14 public class 时间效率_最小的K个数 {
 15 public ArrayList<Integer> GetLeastNumbers_Solution(int[] input, int k) {
 16 ArrayList<Integer> result = new ArrayList<>();
 17 int length = input.length;
 18 if (k > length || k == 0) {
 19 return result;
 20 }
 21 
 22 // 匿名函数
 23 /*PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
 24 @Override
 25 public int compare(Integer o1, Integer o2) {
 26 return o2.compareTo(o1);
 27 }
 28 });*/
 29 
 30 // lambda表达式
 31 /* PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(k,
 32 (Integer o1, Integer o2) -> o2.compareTo(o1)
 33 );*/
 34 
 35 // 简写
 36 PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k,
 37 Comparator.reverseOrder()//按从大到小顺序排序
 38 );
 39 
 40 
 41 for (int i = 0; i < length; i++) {
 42 /*if (maxHeap.size() != k) {
 43 maxHeap.offer(input[i]);
 44 } else if (maxHeap.peek() > input[i]) {
 45 Integer temp = maxHeap.poll();
 46 temp = null;
 47 maxHeap.offer(input[i]);
 48 }*/
 49 
 50 //这样写也是可以的，一旦超出大小就删掉堆顶元素，不用判断（来自雪菜）
 51 // 代码复杂度低，运行复杂度比上面的高
 52 // 笔试面试题中建议写这种代码复杂度较低，逻辑清晰，容易调试的代码。
 53 maxHeap.offer(input[i]);
 54 if (maxHeap.size() > k)
 55 maxHeap.poll();
 56 }
 57 result.addAll(maxHeap);
 58 return result;
 59 }
 60 }

最小的K个数

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目:
 3 * 请实现一个函数用来匹配包括'.'和'*'的正则表达式。模式中的字符'.'表示任意一个字符，
 4 * 而'*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有
 5 * 字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但是与"aa.a"
 6 * 和"ab*a"均不匹配
 7 * */
 8 
 9 /*
 10 * 题解:
 11 *
 12 * */
 13 public class 未完成_动态规划字符串_正则表达式匹配 {
 14 int[][] f;
 15 int m;
 16 int n;
 17 char[] p;
 18 char[] s;
 19 
 20 public boolean match(char[] str, char[] pattern) {
 21 p = pattern;
 22 s = str;
 23 n = s.length;
 24 m = p.length;
 25 f = new int[n+1][m+1];
 26 return dp(0, 0);
 27 }
 28 
 29 boolean dp(int x, int y) {
 30 if (f[x][y] != 0) return f[x][y] == 1;
 31 if (y == m){
 32 f[x][y] = x==n? 1:-1;
 33 return f[x][y] == 1;
 34 }
 35 boolean first_match = x<n &&(p[y] == '.' || s[x] == p[y]);
 36 if(y+1<m && p[y+1] == '*'){
 37 f[x][y] = dp(x,y+2)||dp(x+1,y)?1:-1;
 38 }
 39 else{
 40 f[x][y] = first_match && dp(x+1,y+1)?1:-1;
 41 }
 42 return f[x][y]==1;
 43 }
 44 
 45 public static void main(String[] args) {
 46 未完成_动态规划字符串_正则表达式匹配 a = new 未完成_动态规划字符串_正则表达式匹配();
 47 a.match("a".toCharArray(),"ab*a".toCharArray());
 48 }
 49 }

未完成\_动态规划字符串\_正则表达式匹配

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*题目描述
 2 把一个数组最开始的若干个元素搬到数组的末尾，我们称之为数组的旋转。
 3 输入一个非减排序的数组的一个旋转，输出旋转数组的最小元素。
 4 例如数组{3,4,5,1,2}为{1,2,3,4,5}的一个旋转，该数组的最小值为1。
 5 NOTE：给出的所有元素都大于0，若数组大小为0，请返回0。*/
 6 public class 查找和排序_旋转数组的最小数字 {
 7 /*链接：https://www.nowcoder.com/questionTerminal/9f3231a991af4f55b95579b44b7a01ba
 8 
 9 旋转之后的数组实际上可以划分成两个有序的子数组（以最小元素为分界）：前面子数组的大小都大于后面子数组中的元素
 10 
 11 本题目给出的数组一定程度上是排序的，因此我们试着用二分查找法寻找这个最小的元素。
 12 
 13 思路：
 14 
 15 （1）我们用两个指针left,right分别指向数组的第一个元素和最后一个元素。按照题目的旋转的规则，第一个元素应该是大于最后一个元素的（没有重复的元素）。
 16 
 17 但是如果不是旋转，第一个元素肯定小于最后一个元素。旋转数组的最后一个元素在原递增数组中的后继就是旋转数组的第一个元素
 18 
 19 （2）找到数组的中间元素。
 20 
 21 中间元素大于第一个元素（说明中间元素处于前一个有序子数组的有序位置），则中间元素位于前面的递增子数组，此时最小元素应该位于中间元素的后面。我们可以让第一个指针left指向中间元素。
 22 
 23 移动之后，第一个指针仍然位于前面的递增数组中。
 24 
 25 中间元素小于第一个元素，说明中间元素位于后面的递增子数组，此时最小元素位于中间元素的前面。我们可以让第二个指针right指向中间元素。
 26 
 27 移动之后，第二个指针仍然位于后面的递增数组中。
 28 
 29 
 30 
 31 （3）按照以上思路，第一个指针left总是指向前面递增数组的元素，第二个指针right总是指向后面递增的数组元素。
 32 
 33 最终第一个指针将指向前面数组的最后一个元素，第二个指针指向后面数组中的第一个元素。
 34 
 35 也就是说他们将指向两个相邻的元素，而第二个指针指向的刚好是最小的元素，这就是循环的结束条件。*/
 36 public static int minNumberInRotateArray(int[] array) {
 37 int n = array.length - 1;
 38 if (n < 0) return -1;
 39 //将n指向旋转数组尾部元素，如果尾部有多个相等的元素，则指向其中第一个
 40 // 如 {3，4，5，6，1，1，2，2}则n指向倒数第二个2
 41 while (n > 0 && array[n] == array[0]) n--;
 42 int l = 0;
 43 int r = n;
 44 // 如果最后一个比第一个元素大，说明0到n就是有序的，最小的就是array[0]
 45 if(array[n]>=array[0]) return array[0];
 46 // 接下来使用二分查找
 47 while (l < r) {
 48 int mid = l + ((r-l)>>1);//使用查找模板[l,mid], [mid+1, r]
 49 if(array[mid]<array[0])//如果array[mid]<array[0],则0和mid之间失序，mid属于右边有序数组，最小值出现在mid左边, 令 r = mid;
 50 r = mid;
 51 else//如果array[mid]>=array[0],则mid和0之间是有序数组，mid属于左边有序数组，最小值出现在mid右边, 令 l = mid+1;
 52 l = mid + 1;
 53 
 54 }
 55 // return array[l];
 56 return array[r];
 57 }
 58 
 59 public static void main(String[] args) {
 60 int[] a = {1,1,2,3,3,4,5,6,6,1,1};
 61 System.out.println(minNumberInRotateArray(a));
 62 }
 63 }

旋转数组的最小数字

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
 4 * */
 5 import java.util.Stack;
 6 public class 栈和队列_两个栈实现队列 {
 7 Stack<Integer> stackIn = new Stack<>();
 8 Stack<Integer> stackOut = new Stack<>();
 9 
 10 public void push(int node) {
 11 stackIn.push(node);
 12 }
 13 
 14 public int pop() {
 15 /*如果第二个栈是空的，要把第一个栈里面所有的数倒进第二个栈里面*/
 16 /*但第二个栈一定要是空的才能从第一个栈里倒数进来，并且要将第一个栈的数全部倒进来*/
 17 if(stackOut.empty()){
 18 while (!stackIn.empty())
 19 stackOut.push(stackIn.pop());
 20 }
 21 return stackOut.pop();
 22 }
 23 }

两个栈实现队列

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 *题目描述
 3 定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。
 4 * */
 5 
 6 /*
 7 *题解：
 8 * 算法
 9 (单调栈) O(1)O(1)
 10 我们除了维护基本的栈结构之外，还需要维护一个单调栈，来实现返回最小值的操作。
 11 下面介绍如何维护单调栈：
 12 
 13 当我们向栈中压入一个数时，如果该数 ≤≤ 单调栈的栈顶元素，则将该数同时压入单调栈中；否则，不压入，这是由于栈具有先进后出性质，所以在该数被弹出之前，栈中一直存在一个数比该数小，所以该数一定不会被当做最小数输出。
 14 当我们从栈中弹出一个数时，如果该数等于单调栈的栈顶元素，则同时将单调栈的栈顶元素弹出。
 15 单调栈由于其具有单调性，所以它的栈顶元素，就是当前栈中的最小数。
 16 时间复杂度
 17 四种操作都只有常数次入栈出栈操作，所以时间复杂度都是 O(1)O(1).
 18 
 19 https://www.acwing.com/solution/acwing/content/749/
 20 * */
 21 
 22 import java.util.Stack;
 23 
 24 public class 栈和队列_包含min函数的栈 {
 25 Stack<Integer> stk = new Stack<>();
 26 Stack<Integer> min_stk = new Stack<>();
 27 
 28 public void push(int node) {
 29 if(min_stk.isEmpty()||min_stk.peek()>=node)
 30 min_stk.push(node);
 31 stk.push(node);
 32 }
 33 
 34 public void pop() {
 35 if(min_stk.peek() == stk.pop())
 36 min_stk.pop();
 37 }
 38 
 39 public int top() {
 40 return stk.peek();
 41 }
 42 
 43 public int min() {
 44 return min_stk.peek();
 45 }
 46 }

包含min函数的栈

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 import java.util.ArrayList;
 2 import java.util.Deque;
 3 import java.util.LinkedList;
 4 
 5 /*
 6 * 题目描述
 7 给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
 8 例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，
 9 那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}；
 10 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}，
 11 {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}，
 12 {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
 13 * */
 14 /*
 15 * 时间复杂度， 每个元素只会进出窗口一次， 复杂度为O（N）*/
 16 public class 栈和队列_滑动窗口的最大值 {
 17 static public ArrayList<Integer> maxInWindows(int[] num, int size) {
 18 ArrayList<Integer> res = new ArrayList<>();
 19 if (num.length == 0 || size == 0) {
 20 // do nothing
 21 } else {
 22 // q保存的是num中的下标，从双端队列q的左边弹出元素，从右边压入元素
 23 // 保证存在q中的下标所对应在num里的元素是单调递减的，这样窗口中的最大值一直都是最左边的元素，也就是first元素
 24 Deque<Integer> q = new LinkedList<>();
 25 for (int i = 0; i < num.length; i++) {
 26 // 用来控制窗口的大小始终为size, i是当前下标（窗口的右边下标）， q的first是窗口的左边下标，保证窗口左边 >= 窗口右边 - 窗口大小;
 27 // 队列左边< i-size 的部分是过期的窗口，需要从队列中删除
 28 while (!q.isEmpty() && q.peekFirst() <= i - size)
 29 q.pollFirst();//pullFirst取出的是队列左边的元素
 30 
 31 // 从队列的右边压入元素， 压入的元素如果大于当前窗口右边的元素，则可以将窗口右边较小的元素删除（此时需要保证这个窗口的元素从左到右是单调递减的）
 32 // 注意只有从窗口的右边进行比较删除操作才能使得窗口保持单调递减
 33 while (!q.isEmpty() && num[q.peekLast()] <= num[i])
 34 q.pollLast();//pollLast取出的是队列右边，比新到的元素要小的元素
 35 // 将新到的元素从队列右边压入
 36 q.offerLast(i);
 37 // 当窗口的长度到达size长时开始输出元素。
 38 if (i >= size - 1)
 39 res.add(num[q.peekFirst()]);//一直取队列的左边元素，因为队列从左往右是单调递减的，最左边就是最大的元素
 40 }
 41 }
 42 return res;
 43 }
 44 
 45 public static void main(String[] args) {
 46 int[] num = {2, 3, 4, 2, 6, 2, 5, 1};
 47 System.out.println(maxInWindows(num, 3));
 48 }
 49 }

滑动窗口的最大值

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。
     2 注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。*/
     3 public class 树_二叉树的下一个节点 {
     4     public TreeLinkNode GetNext(TreeLinkNode pNode) {
     5 //        第一种情况，只要当前节点有右子树，则在中序遍历的条件下，
     6 //        当前节点的下一个节点是它右子树的最左边的节点
     7         if(pNode.right!=null){
     8             pNode = pNode.right;
     9 //            找到右子树中最左边的节点
    10             while(pNode.left!=null)
    11                 pNode = pNode.left;
    12             return pNode;
    13         }else{
    14 //            如果当前节点没有右子树，则根据中序的顺序，当前节点的后继是其
    15 //            这样的一个祖先，即本节点所在的子树是该祖先节点的左子树
    16             while(pNode.next!=null && pNode == pNode.next.right)//只要当前节点不是父节点的左孩子，则把指针移到父节点，往上找，直到找到满足pNode == pNode.next.left则找到了后继
    17                 pNode = pNode.next;
    18 //            返回的是pNode的父节点
    19             return pNode.next;
    20         }
    21 
    22     }
    23 }

二叉树的下一个节点

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 *题目描述
     3 请实现一个函数，
     4 用来判断一颗二叉树是不是对称的。注意，
     5 如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。
     6 * */
     7 
     8 /*
     9 *题解:https://www.acwing.com/solution/acwing/content/747/
    10 * (二叉树，递归) O(n)O(n)
    11 递归判断两个子树是否互为镜像。
    12 
    13 两个子树互为镜像当且仅当：
    14 
    15 两个子树的根节点值相等；
    16 第一棵子树的左子树和第二棵子树的右子树互为镜像，且第一棵子树的右子树和第二棵子树的左子树互为镜像；
    17 时间复杂度
    18 从上到下每个节点仅被遍历一遍，所以时间复杂度是 O(n)O(n)。
    19 
    20 * */
    21 public class 树_对称的二叉树 {
    22     boolean isSymmetrical(TreeNode pRoot)
    23     {
    24         if(pRoot == null)
    25             return true;
    26         else{
    27             return dfs(pRoot.left, pRoot.right);
    28         }
    29     }
    30 
    31     boolean dfs(TreeNode p1, TreeNode p2){
    32         if(p1==null||p2==null)
    33             return p1 == null && p2 ==null;
    34         if(p1.val!=p2.val) return false;
    35         return dfs(p1.left, p2.right) && dfs(p1.right,p2.left);
    36     }
    37 }

对称的二叉树

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //BiliBili大雪菜做法
 2 //自测可以通过，牛客上不AC
 3 public class 树_序列化二叉树 {
 4 static String Serialize(TreeNode root) {
 5 StringBuilder res = new StringBuilder();
 6 dfs_s(root, res);
 7 return res.toString();
 8 }
 9 
 10 static void dfs_s(TreeNode node, StringBuilder res) {
 11 if (node == null) {
 12 res.append("null ");
 13 return;
 14 }
 15 res.append(node.val + " ");
 16 dfs_s(node.left, res);
 17 dfs_s(node.right, res);
 18 }
 19 
 20 private static int u;
 21 
 22 static TreeNode Deserialize(String str) {
 23 u = 0;
 24 return dfs_d(str);
 25 }
 26 
 27 static TreeNode dfs_d(String str) {
 28 if (u == str.length()) return null;
 29 int k = u;
 30 while (str.charAt(k) != ' ') k++;
 31 if (str.charAt(u) == 'n') {
 32 u = k + 1;
 33 return null;
 34 }
 35 int val = 0;
 36 for (int i = u; i < k; i++)
 37 val = 10 * val + str.charAt(i) - '0';//0的ascii是48, 也可写作val = 10*val+str.charAt(i)-48
 38 u = k + 1;
 39 TreeNode root = new TreeNode(val);
 40 root.left = dfs_d(str);
 41 root.right = dfs_d(str);
 42 return root;
 43 }
 44 
 45 public static void main(String[] args) {
 46 TreeNode root = new TreeNode(1);
 47 root.left = new TreeNode(2);
 48 root.right = new TreeNode(3);
 49 root.left.left = new TreeNode(4);
 50 String s = Serialize(root);
 51 System.out.println(s);
 52 System.out.println(Serialize(Deserialize(s)));
 53 }
 54 }

序列化二叉树

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 //来自https://www.nowcoder.com/questionTerminal/cf7e25aa97c04cc1a68c8f040e71fb84
     2 //本题在牛课上AC
     3 public class 树_序列化二叉树牛客论坛做法 {
     4     static String Serialize(TreeNode root) {
     5         StringBuilder res = new StringBuilder();
     6         if (root == null)
     7             return res.toString();
     8         else {
     9             dfs_s(root, res);
    10             return res.toString();
    11         }
    12     }
    13 
    14     static void dfs_s(TreeNode node, StringBuilder res) {
    15         if (node == null) {
    16             res.append("#,");
    17             return;
    18         } else {
    19             res.append(node.val + ",");
    20             dfs_s(node.left, res);
    21             dfs_s(node.right, res);
    22         }
    23     }
    24 
    25     static int index;
    26     static TreeNode Deserialize(String str){
    27         if(str.equals(""))
    28             return null;
    29         index = -1;
    30         String[] strr = str.split(",");
    31         return dfs_d(strr);
    32     }
    33 
    34     static TreeNode dfs_d(String[] strr){
    35         index++;
    36         TreeNode node = null;
    37         if(!strr[index].equals("#")){
    38             node = new TreeNode(Integer.valueOf(strr[index]));
    39             node.left = dfs_d(strr);
    40             node.right = dfs_d(strr);
    41         }
    42         return node;
    43     }
    44 }

序列化二叉树牛客论坛做法

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。
 4 * */
 5 
 6 import java.util.ArrayList;
 7 import java.util.Collections;
 8 import java.util.LinkedList;
 9 import java.util.Queue;
 10 
 11 /*
 12 *题解:
 13 * 每次遍历到该层最后一个位置的时候人为的添加一个null节点来标记下一层的所有节点都已经添加进队列
 14 * 取出的时候如果碰到null节点就做分行处理
 15 * */
 16 public class 树_把二叉树打印成多行 {
 17 public static ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
 18 ArrayList<ArrayList<Integer>> res = new ArrayList<>();
 19 ArrayList<Integer> arr = new ArrayList<>();
 20 Queue<TreeNode> queue = new LinkedList<>();
 21 
 22 queue.offer(pRoot);
 23 queue.offer(null);
 24 while(!queue.isEmpty()){
 25 TreeNode tmp = queue.poll();
 26 if(tmp == null){
 27 if(arr.isEmpty()) break;
 28 //res.add(arr)这样是错误的! 后面arr会变！
 29 res.add(new ArrayList<>(arr));
 30 arr.clear();
 31 queue.offer(null);
 32 }else{
 33 arr.add(tmp.val);
 34 if(tmp.left != null)
 35 queue.offer(tmp.left);
 36 if(tmp.right != null)
 37 queue.offer(tmp.right);
 38 }
 39 }
 40 return res;
 41 }
 42 
 43 public static void main(String[] args) {
 44 TreeNode head = new TreeNode(8);
 45 head.left = new TreeNode(6);
 46 head.right = new TreeNode(10);
 47 head.left.left = new TreeNode(5);
 48 head.left.right = new TreeNode(7);
 49 head.right.left = new TreeNode(9);
 50 head.right.right = new TreeNode(11);
 51 ArrayList<ArrayList<Integer>> res =Print(head);
 52 System.out.println();
 53 }
 54 }

把二叉树打印成多行

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，
 4 第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。
 5 * */
 6 
 7 import java.util.ArrayList;
 8 import java.util.Collections;
 9 import java.util.LinkedList;
 10 import java.util.Queue;
 11 
 12 /*
 13 *题解:
 14 * 本题与 树_把二叉树打印成多行 十分类似
 15 * 只要在每层的时候判断一下是否对该层结果逆序放到最终的结果中去
 16 * */
 17 public class 树_按之字形顺序打印二叉树 {
 18 public static ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
 19 ArrayList<ArrayList<Integer>> res = new ArrayList<>();
 20 ArrayList<Integer> arr = new ArrayList<>();
 21 Queue<TreeNode> queue = new LinkedList<>();
 22 
 23 queue.offer(pRoot);
 24 queue.offer(null);
 25 boolean zigzag = false;
 26 while(!queue.isEmpty()){
 27 TreeNode tmp = queue.poll();
 28 if(tmp == null){
 29 if(arr.isEmpty()) break;
 30 //res.add(arr)这样是错误的! 后面arr会变！
 31 if(zigzag)
 32 Collections.reverse(arr);
 33 res.add(new ArrayList<>(arr));
 34 arr.clear();
 35 queue.offer(null);
 36 zigzag = !zigzag;
 37 }else{
 38 arr.add(tmp.val);
 39 if(tmp.left != null)
 40 queue.offer(tmp.left);
 41 if(tmp.right != null)
 42 queue.offer(tmp.right);
 43 }
 44 }
 45 return res;
 46 }
 47 }

按之字形顺序打印二叉树

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。
 3 * 假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
 4 * 例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，
 5 * 则重建二叉树并返回。二叉树重建的结果是按层序遍历返回的数组。
 6 * */
 7 
 8 import java.util.HashMap;
 9 import java.util.Map;
 10 
 11 /*
 12 * 1. 从前序中得到根节点1， 在中序中找到1所在的位置，1 的左边{4，7，2}是左子树的中序， 1的右边{5，3，8，6}是右子树中序
 13 * 2. 在中序中得到左子树的长度为3，右子树长度为4， 所以在前序中可以得到左子树的前序是{2，4，7}， 右子树前序是{3，5，6，8}
 14 * 3. 有了左子树的前序和中序，可以重复上面的步骤1和步骤2的过程； 同理有了右子树的前序和中序，也可以递归上述过程；
 15 * */
 16 public class 树_重建二叉树 {
 17 Map<Integer, Integer> hash = new HashMap<>();
 18 int[] pre, in;
 19 
 20 public TreeNode reConstructBinaryTree(int[] _pre, int[] _in) {
 21 pre = _pre;
 22 in = _in;
 23 
 24 for (int i = 0; i < pre.length; i++)
 25 hash.put(in[i], i);
 26 return dfs(0, pre.length - 1, 0, in.length - 1);
 27 }
 28 
 29 public TreeNode dfs(int pl, int pr, int il, int ir) {
 30 if (pl > pr)
 31 return null;
 32 else {
 33 TreeNode root = new TreeNode(pre[pl]);
 34 // int position = hash.get(pre[pl]);
 35 int positon = hash.get(root.val);
 36 // dfs（子树在前序数组中的左边界，子树在前序数组的右边界（=左边界+子树长度，长度可由中序数组推出），子树在中序数组中的左边界，子树在中序数组的右边界（=左边界+左子树长度，长度可由中序数组推出））
 37 TreeNode left = dfs(pl+1, pl+positon-il, il, positon-1);
 38 TreeNode right = dfs(pl+positon-il+1,pr, positon+1,il);
 39 root.left = left;
 40 root.right = right;
 41 return root;
 42 }
 43 }
 44 }

重建二叉树

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 * 题目描述
     3 输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。
     4 要求不能创建任何新的结点，只能调整树中结点指针的指向。
     5 见 树_链表_二叉搜索树与双向链表_题目描述.png
     6 * */
     7 
     8 /*
     9 题解:
    10 见 树_链表_二叉搜索树与双向链表.png
    11 * */
    12 public class 树_链表_二叉搜索树与双向链表 {
    13     public TreeNode Convert(TreeNode pRootOfTree) {
    14         if (pRootOfTree == null)
    15             return null;
    16         TreeNode[] sides = dfs(pRootOfTree);
    17         return sides[0];
    18     }
    19 
    20     TreeNode[] dfs(TreeNode root) {
    21         TreeNode[] res = {};
    22         if (root.left == null && root.right == null)
    23             res = new TreeNode[]{root, root};
    24         if (root.left != null && root.right != null) {
    25             TreeNode[] lsides = dfs(root.left);
    26             TreeNode[] rsides = dfs(root.right);
    27             lsides[1].right = root;
    28             root.left = lsides[1];
    29             rsides[0].left = root;
    30             root.right = rsides[0];
    31             res = new TreeNode[]{lsides[0], rsides[1]};
    32         }
    33         if (root.right == null && root.left != null) {
    34             TreeNode[] lsides = dfs(root.left);
    35             lsides[1].right = root;
    36             root.left = lsides[1];
    37             res = new TreeNode[]{lsides[0], root};
    38         }
    39         if (root.left == null && root.right != null) {
    40             TreeNode[] rsides = dfs(root.right);
    41             rsides[0].left = root;
    42             root.right = rsides[0];
    43             res = new TreeNode[]{root, rsides[1]};
    44         }
    45         return res;
    46     }
    47 }

二叉搜索树与双向链表

![1135658-20190611222553738-1518813954.png][]

![1135658-20190611222533896-152199433.png][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 *题目描述
 3 从上往下打印出二叉树的每个节点，同层节点从左至右打印。
 4 * */
 5 
 6 /*
 7 *宽搜
 8 * */
 9 
 10 import java.util.ArrayList;
 11 import java.util.LinkedList;
 12 import java.util.Queue;
 13 
 14 public class 模拟_上往下打印二叉树 {
 15 public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
 16 ArrayList<Integer> res = new ArrayList<>();
 17 Queue<TreeNode> queue = new LinkedList<>();
 18 queue.offer(root);
 19 while(!queue.isEmpty()){
 20 TreeNode tmp = queue.poll();
 21 if(tmp!=null){
 22 res.add(tmp.val);
 23 queue.offer(tmp.left);
 24 queue.offer(tmp.right);
 25 }
 26 }
 27 return res;
 28 }
 29 }

上往下打印二叉树

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 输入两个整数序列，第一个序列表示栈的压入顺序，
 4 请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。
 5 例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的
 6 一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（
 7 注意：这两个序列的长度是相等的）
 8 * */
 9 
 10 import java.util.Stack;
 11 
 12 /*
 13 *题解:
 14 * (栈) O(n)O(n)
 15 用一个新栈s来模拟实时进出栈操作：
 16 
 17 在for loop里依次喂数，每push一个数字就检查有没有能pop出来的。
 18 
 19 如果最后s为空（或者popId==popV.size())，说明一进一出刚刚好。
 20 
 21 时间复杂度分析：一共push n次，pop n次。
 22 
 23 * */
 24 public class 模拟_栈的压入弹出序列 {
 25 public boolean IsPopOrder(int [] pushA,int [] popA) {
 26 if(pushA.length!=popA.length) return false;
 27 
 28 Stack<Integer> stk = new Stack<>();
 29 int j = 0;
 30 for(int i = 0; i<pushA.length;i++){
 31 stk.push(pushA[i]);
 32 while(!stk.isEmpty()){
 33 if(stk.peek() == popA[j]){
 34 stk.pop();
 35 j++;
 36 }else{
 37 break;
 38 }
 39 }
 40 }
 41 return stk.isEmpty();
 42 }
 43 
 44 }

栈的压入弹出序列

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 输入一个字符串,按字典序打印出该字符串中字符的所有排列。
 4 例如输入字符串abc,则打印出由字符a,b,c所能排列出来的
 5 所有字符串abc,acb,bac,bca,cab和cba。
 6 输入描述:
 7 输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。
 8 * */
 9 
 10 import java.util.ArrayList;
 11 import java.util.Arrays;
 12 import java.util.Collections;
 13 
 14 /*
 15 * 题解:
 16 *
 17 * 与
 18 *循环和递归_二叉树中和为某一值的路径
 19 * 类似
 20 *
 21 * 这里我们如何保证在有相同的字符的情况下，如何保证排列的结果是不重复不遗漏的呢？
 22 * 根据要排列的字符串的长度，新建一个等长的字符数组path来记录排列的路径；
 23 * 然后把字符串分解成字符数组arr，并对其排列，使得相同的字符都在一起;
 24 * 我们从头开始遍历这个字符数组arr，每次把一个字符放到路径path中的一个位置，用来保证不重不漏的规则是:
 25 * 1.如果当前从arr中取出的字符是唯一的，则在path中从头开始寻找一个空的位置放入该字符；
 26 * 2. 如果当前从arr中取出的字符与上一个从arr中取出的字符相同，则在path数组中，从上一个字符放入的位置往后开始，
 27 * 寻找一个空的位置放入
 28 *当所有字符被放入，则构成一个合法的排列；
 29 * 并且以上规则保证排列不会重复；
 30 *
 31 * */
 32 public class 递归_分类_字符串的排列 {
 33 ArrayList<String> ans = new ArrayList<>();//存贮符合要求的排列
 34 char[] path;//存储每个遍历的路径
 35 
 36 public ArrayList<String> Permutation(String str) {
 37 path = new char[str.length()];//path的长度等于字符串的长度
 38 char[] arr = str.toCharArray();
 39 Arrays.sort(arr);
 40 dfs(arr, 0, 0, 0);
 41 Collections.sort(ans);//对答案按字典顺序排序
 42 return ans;
 43 }
 44 
 45 //u是当前需要放入path的字符在arr中的位置
 46 //start是上一个被放入path中字符在path中的位置
 47 //state表示path中位置被占用的情况，用它的二进制形式来表示，如5 的二进制是101则表示
 48 void dfs(char[] arr, int u, int start, int state) {
 49 if (u == arr.length) {
 50 //如果u达到了字符数组的末尾，说明找到了一条符合要求的路径，将其放入结果集中
 51 ans.add(new String(path));
 52 return;
 53 }
 54 if (u == 0 || arr[u] != arr[u - 1])//如果u==0（刚开始遍历），或者当前要放入的字符和上一个已经放入path的字符相等
 55 //则把start置为0，意思是当前字符可以放到任意位置（也就是从头寻找一个空位置放入）
 56 start = 0;
 57 for (int i = start; i < arr.length; i++) {
 //开始放入
 58 if((state>>i & 1)==0){
 //用state来记录path数组中被放入的情况，state >> i & 1用来检查state的第i位是否为1，如果为1表示path的第i位已经被占据
 59 path[i] = arr[u];//将arr中的第u个数放入path路径中
 60 dfs(arr,u+1,i+1,state+(1<<i)); //state + (1<<i)表示将state的第i位置1
 61 }
 62 }
 63 }
 64 }

字符串的排列

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。*/
 3 import java.util.ArrayList;
 4 import java.util.Stack;
 5 
 6 public class 链表_从尾到头打印链表 {
 7 // 非递归做法
 8 public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
 9 Stack<Integer> tmp = new Stack<>();
 10 while(listNode!=null){
 11 tmp.push(listNode.val);
 12 listNode = listNode.next;
 13 }
 14 ArrayList<Integer> res = new ArrayList<>();
 15 while (!tmp.empty())
 16 res.add(tmp.pop());
 17 return res;
 18 }
 19 
 20 // 递归做法
 21 public ArrayList<Integer> printListFromTailToHead1(ListNode listNode) {
 22 ArrayList<Integer> re = new ArrayList<>();
 23 if(listNode==null)
 24 return re;
 25 else{
 26 printListRev(listNode, re);
 27 return re;
 28 }
 29 }
 30 
 31 public void printListRev(ListNode l, ArrayList re){
 32 if(l==null)
 33 return;
 34 else{
 35 printListRev(l.next, re);
 36 re.add(l.val);
 37 }
 38 }
 39 }

从尾到头打印链表

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2  * 在一个排序的链表中，存在重复的结点，
     3  * 请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。
     4  * 例如，链表1->2->3->3->4->4->5 处理后为 1->2->5
     5  * */
     6 public class 链表_删除链表中重复的结点 {
     7     public ListNode deleteDuplication(ListNode pHead) {
     8 //        设置一个虚拟节点,用来处理头节点有可能被删除的情况.
     9 //        这个节点的值随便,因为在后面的匹配中,我们并不涉及到这个头节点的值.返回的头节点时候记得返回的是虚拟节点的next
    10         ListNode dumy = new ListNode(-1);
    11         dumy.next = pHead;
    12 
    13         ListNode p = dumy;//p一开始室指向虚拟节点不是头节点！
    14         /*每次考察,将q指向p后面一个节点*/
    15         while (p.next != null) {
    16             ListNode q = p.next;
    17 //            如果q存在且p的下一个节点的值和q节点的值相等，说明遇到了重复节点, 就将p往后移动一个节点考察下一个节点
    18 //            用图示模拟一下就懂了:
    19 //            V 1 2 2 3 3
    20 //            p q
    21 //            * p q
    22             while (q!=null && p.next.val == q.val) q = q.next;
    23 //            如果p的下下个节点是q,说明q从p的下个节点往后只移动了一次,变成了下下个节点,说明从p的下一个位置开始没有重复的元素, p往后移动移位考察下个位置
    24             if (p.next.next == q)
    25                 p = p.next;
    26 //            只要q的位置不在p的下下个位置,说明q移动了超过了一次,说明遇到了相同的元素,将p的next指针指向q,跳过中间所有相同的元素.
    27             else
    28                 p.next = q;
    29         }
    30         return dumy.next;
    31     }
    32 
    33 //    思考,本题是去除所有重复的元素,也就是说如果一个元素有超过了两个,则把他们全部删除;
    34 //    如果要保留至少一个元素应该怎么处理?
    35 //    双指针,如果第二个指针的值等于第一个指针,第一个的next直接指向第二个指针的next,第二个指针指向第一个指针的next.next
    36 //    ListNode dumy = new ListNode(-1);
    37 //    ListNode p1 = dumy;
    38 //    while(p1.next!=null){
    39 //        ListNode p2 = p1.next;
    40 //          if(p2!=null && p1.val == p2.val){
    41 //              p1.next = p2.next;
    42 //          }
    43 //    }
    44 //    return dumy.next;
    45 }

删除链表中重复的结点

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*题目：https://www.acwing.com/problem/content/85/
     2 * 给定单向链表的一个节点指针，定义一个函数在O(1)时间删除该结点。
     3 
     4 假设链表一定存在，并且该节点一定不是尾节点。
     5 
     6 样例
     7 输入：链表 1->4->6->8
     8       删掉节点：第2个节点即6（头节点为第0个节点）
     9 
    10 输出：新链表 1->4->8
    11 * */
    12 
    13 /*
    14 * 题解：
    15 * 将链表的下一个节点的值赋给当前节点，然后跳过当前节点的下一个节点
    16 * 将下一个节点复制到当前节点的位置取代当前节点，然后删除掉下一个节点；这样相当于删除了本节点。
    17 * */
    18 public class 链表_在O1时间删除链表结点 {
    19     public void deleteNode(ListNode node) {
    20         node.val = node.next.val;
    21         node.next = node.next.next;
    22     }
    23 }

在O1时间删除链表结点

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
     2 * 题目描述
     3 输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，
     4 另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。
     5 （注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）
     6 */
     7 
     8 /*
     9  * 题解
    10  * 见 链表_复杂链表的复制.png
    11  * */
    12 public class 链表_复杂链表的复制 {
    13     public RandomListNode Clone(RandomListNode pHead) {
    14 //        第一步，复制链表中的每个节点，并将其插入到该节点和其后面节点之间
    15         for(RandomListNode p = pHead; p!=null;){
    16             RandomListNode np = new RandomListNode(p.label);
    17             RandomListNode next = p.next;
    18             np.next = next;
    19             p.next = np;
    20             p = next;
    21         }
    22 
    23 //        第二步，依据主链表在副链表上连接相应的random指针
    24         for(RandomListNode p = pHead;p!=null;p = p.next.next){
    25             if(p.random!=null)
    26                 p.next.random = p.random.next;
    27         }
    28 
    29 //        第三步,将副链表从主链表上拆下来，串成新链表，并将主链表还原
    30 //        为副链表做一个虚拟头节点
    31         RandomListNode dummy = new RandomListNode(-1);
    32         RandomListNode cur = dummy;
    33         for(RandomListNode p = pHead;p!=null;){
    34             cur.next=p.next;
    35             cur = cur.next;
    36             p.next = cur.next;//将主链表重新连接
    37             p = p.next;
    38         }
    39         return dummy.next;
    40     }
    41 }
    42 
    43 class RandomListNode {
    44     int label;
    45     RandomListNode next = null;
    46     RandomListNode random = null;
    47 
    48     RandomListNode(int label) {
    49         this.label = label;
    50     }
    51 }

复杂链表的复制

![1135658-20190611222948376-688812994.png][]

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 /*
 2 * 题目描述
 3 给一个链表，若其中包含环，
 4 请找出该链表的环的入口结点，否则，输出null。
 5 * */
 6 
 7 import java.util.HashSet;
 8 
 9 
 10 public class 链表_链表中环的入口结点 {
 11 /*
 12 * 题解1:见 链表_链表中环的入口节点.JPG
 13 * */
 14 public ListNode EntryNodeOfLoop1(ListNode pHead) {
 15 ListNode i = pHead;
 16 ListNode j = pHead;
 17 while (i != null && j != null) {
 18 i = i.next;
 19 j = j.next;
 20 if (j != null)
 21 j = j.next;
 22 else
 23 return null;
 24 if (i == j) {
 25 i = pHead;
 26 while (i != j) {
 27 i = i.next;
 28 j = j.next;
 29 }
 30 return i;
 31 }
 32 }
 33 return null;
 34 }
 35 /*
 36 * 题解2:用set依次保存节点，主要依据set不能存储重复元素的性质
 37 * */
 38 public ListNode EntryNodeOfLoop(ListNode pHead){
 39 HashSet<ListNode> res = new HashSet<>();
 40 while(pHead!=null){
 41 if(res.add(pHead))
 42 pHead = pHead.next;
 43 else
 44 return pHead;
 45 }
 46 return null;
 47 }
 48 }

链表中环的入口节点

![1135658-20190611223202698-1121636772.png][]

转载于:https://www.cnblogs.com/greatLong/p/11006711.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211101/4b73300aa4e0409e94d8fe97b1745aa1.png
[1135658-20190611215033893-1038405002.png]: /images/20211101/6200792f12d0427c86620c76af99442a.png
[1135658-20190611215637303-1683623977.png]: /images/20211101/3d4407aeca054308ac5b4b5b555f635d.png
[1135658-20190611221234816-1373163006.png]: /images/20211101/e9f4dddaa0054fd8a6dd17fbabcd38bd.png
[1135658-20190611222553738-1518813954.png]: /images/20211101/1f847482cf37452e97490d83c95caad9.png
[1135658-20190611222533896-152199433.png]: /images/20211101/08a673d9d08b4dd4abb2c8b4601d39f8.png
[1135658-20190611222948376-688812994.png]: /images/20211101/fb04a950514c4b1b970ffec896e48167.png
[1135658-20190611223202698-1121636772.png]: /images/20211101/06237085be834773a79eb0c5a053379f.png