三天刷完《剑指OFFER编程题》--Java版本实现（第三天）

野性酷女 2022-12-01 12:26 101阅读 0赞

正在更新中。。。。。。。。。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70][]

剑指offer --Python版本的实现：

# [剑指offer（1/3）第一大部分][offer_1_3] #

# [剑指offer（2/3）第二大部分][offer_2_3] #

# [剑指offer（3/3）第三大部分][offer_3_3] #

\----------------------------------------------------

### **《剑指offer》Java版本实现：** ###

# [《剑指offer》Java版本-第一天][offer_Java_-] #

# [《剑指offer》Java版本-第二天][offer_Java_- 1] #

# [《剑指offer》Java版本-第三天][offer_Java_- 2] #

### 46.圆圈后最后剩下额数 ###

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^\_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

1. 使用模仿小朋友玩游戏的过程

我们可以用链表模拟约瑟夫环的过程。当模拟到人数等于1的时候，输出剩下的人的序号即可。

import java.util.LinkedList;
    import java.util.List;
    public class Solution {
        public int LastRemaining_Solution(int n, int m) {
            if (n <= 0 || n < 0) return -1;
            
            int index = -1; // 由于是m-1个小朋友出列，所以index要先减去1 
            List<Integer> array = new LinkedList();
            for (int i = 0; i < n; i++){
                array.add(i);
            }
            while (array.size() != 1){
                index = (m + index) % array.size(); //这里array的size会更新
                array.remove(index);
                index -= 1;
            }
            return array.get(0);
        }
    }

2. 约瑟夫环

该方法的核心在于：**只关心最终活着的那个人的序号变化情况，从最终结果反推出规律**。

例如一共有 n=8 个人，每当数到 m=3 的时候就将该人给删除，我们用 F(n, m) 来表示最后剩下的那个人的序号。整个流程如下图所示：

[![image.png][]][image.png 1]

从上图可以看到，我们将这 8 个人用字母代替，在每一轮中，红色的方格表示当前需要被删除的人，绿色的方格表示最终存活下来的人。N=8 时，将 C 删除，则下一轮（N=7）将会从 D 开始报数，然后往右数 m=3 个数，再将 F 删除，以此类推。

此外，注意观察每一轮中最后活下来的 G 的索引变化情况。当最后只剩下一个人的时候，这个人的编号（索引号）一定是 0。

接下来我们看看如何进行反推，例如如何从 N=7 反推出 N=8 时的情况，如下图所示：

![image.png][image.png 2]

在从 N=7 回到 N=8 的过程中，先将被删除的 C 补充回去，即黄色方格；然后将 N=7 右移 m 个单位，由于多出 3 个人（A、B、C）越界了，因此将它们移到前面；最后得到的结果就和 N=8 一样了。

因此，从 N=7 到 N=8 的递推公式为：f(8,3)=\[f(7,3)+3\]%8

而将此公式推广到一般情况，则有：f(N,m)=\[f(N−1,3)+3\]%N

最后整理得到的递推公式：

当n=1时，f(N,m)=0

当n>1时，f(N,m)=\[f(N−1,m)+m\]%N

public class Solution {
        public int LastRemaining_Solution(int n, int m) {
            if (n <= 0 || n < 0) return -1;
            
            int remainIndex = 0;
            for (int i = 2; i<= n; i++){ // 约瑟夫环
                remainIndex = (remainIndex + m) % i;
            }
            return remainIndex;
        }
    }

### 47.求1,2.。。n的和 ###

求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

使用递归方法：

`解题思路：`

`1``.需利用逻辑与的短路特性实现递归终止。`

`2``.当n==``0``时，(n>``0``)&&((sum+=Sum_Solution(n-``1``))>``0``)只执行前面的判断，为``false``，然后直接返回``0``；`

这里可以实现不使用 if 判断

`3``.当n>``0``时，执行sum+=Sum_Solution(n-``1``)，实现递归计算Sum_Solution(n)。`

public class Solution {
        public int Sum_Solution(int n) {
            int sum = n;
            boolean ans = (n > 0)&& ((sum += Sum_Solution(n-1))>0);
            return sum;
        }
    }

### 48.不用加减乘除做相加 ###

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、\*、/四则运算符号。

使用 `^` 和 `&` 将两个整数相加

1.  两个数异或：相当于每一位相加，而不考虑进位；
2.  两个数相与，并左移一位：相当于求得进位；

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xyczEzNTMyODEwMDQ_size_16_color_FFFFFF_t_70]

![在这里插入图片描述][20190213172431556.png]

13+11 = ？;

13 的二进制 1 1 0 1 -----a 13

11 的二进制 1 0 1 1 -----b 11

(a&b) <<1 -> 1 0 0 1 **0** \-----d 18

a^b -> 0 1 1 **0** \-----e 6

(d&e) <<1 -> 0 0 1 **0 0** \------f 4

d^e -> 1 0 1 **0 0** \-----g 20

(f&g) <<1 -> 0 1 **0 0 0** \------h 8

f^g -> 1 0 **0 0 0**  \------i 16

(h&i) <<1 -> 0 **0 0 0 0**  \------h 0 ---- -------- 没有进位了， 则退出循环

h^i -> 1 1 0 0 0 ------i 24

public class Solution {
        public int Add(int num1,int num2) {
            if (num1 == 0) return num2;
            if (num2 == 0) return num1;
            
            while (num2 != 0){
                int carry = num1 & num2;
                num1 = num1 ^ num2; // 异或，两者相加，但是不进位
                num2 = carry << 1;  // 相与，左移，相当于进位
            }
            return num1;
        }
    }

### 49.将字符串转换成整数 ###

将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

**输入描述:**

输入一个字符串,包括数字字母符号,可以为空

**输出描述:**

如果是合法的数值表达则返回该数字，否则返回0

示例1

输入

+2147483647
    1a33

输出

2147483647
    0

public class Solution {
        public int StrToInt(String str) {
            int size = str.length();
            if (str.equals("+") && size==1) return 0;
            if (str.equals("-") && size == 1) return 0;
            if (size == 0) return 0;
            
            int sum = 0;
            for (int i = 0; i < size; i++){
                if (str.charAt(i) == '-'){
                    continue;
                }else if (str.charAt(i) == '+'){
                    continue;
                }else if (str.charAt(i) >= '0' && str.charAt(i) <= '9'){
                    sum = sum * 10 + str.charAt(i) - '0';
                }else{
                    return 0;
                }
            }
            return str.charAt(0) == '-' ? -sum : sum; // 判断第一个符号是否是 + -
        }
    }

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

在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。

例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是第一个重复的数字2。

1.使用类似哈希表的方法：

public class Solution {
        // Parameters:
        //    numbers:     an array of integers
        //    length:      the length of array numbers
        //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
        //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
        //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
        // Return value:       true if the input is valid, and there are some duplications in the array number
        //                     otherwise false
        public boolean duplicate(int numbers[],int length,int [] duplication) {
            //由于： 一个长度为n的数组里的所有数字都在0到n-1的范围内
            boolean[] sign = new boolean[length];
            
            for (int i = 0; i < length; i++){
                if (sign[numbers[i]] == true){
                    duplication[0] = numbers[i];
                    return true;
                }
                sign[numbers[i]] = true;
            }
            return false;
        }
    }

2.使用哈希表

import java.util.HashMap;
    public class Solution {
        // Parameters:
        //    numbers:     an array of integers
        //    length:      the length of array numbers
        //    duplication: (Output) the duplicated number in the array number,length of duplication array is 1,so using duplication[0] = ? in implementation;
        //                  Here duplication like pointor in C/C++, duplication[0] equal *duplication in C/C++
        //    这里要特别注意~返回任意重复的一个，赋值duplication[0]
        // Return value:       true if the input is valid, and there are some duplications in the array number
        //                     otherwise false
        public boolean duplicate(int numbers[],int length,int [] duplication) {
            if (length == 0) return false;
            HashMap<Integer, Integer> map = new HashMap();
            for (int i = 0; i< length; i++){  // 计算数组中每个元素的数量
                if (map.containsKey(numbers[i])){
                    map.put(numbers[i], map.get(numbers[i])+1);
                }else{
                    map.put(numbers[i], 1);
                }
            }
            
            for (int i= 0; i < length; i++){ // 找出value值大于1 的key值
                if (map.get(numbers[i]) > 1){
                    duplication[0] = numbers[i];
                    return true;
                }
            }
            return false;
        
        }
    }

### 51.构建乘积数组 ###

给定一个数组A\[0,1,...,n-1\],请构建一个数组B\[0,1,...,n-1\],其中B中的元素B\[i\]=A\[0\]\*A\[1\]\*...\*A\[i-1\]\*A\[i+1\]\*...\*A\[n-1\]。不能使用除法。

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

对于A长度为1的情况，B无意义，故而无法构建，因此该情况不会存在。

剑指的思路：

**B\[i\]的值可以看作下图的矩阵中每行的乘积。**

下三角用连乘可以很容求得，上三角，从下向上也是连乘。

因此我们的思路就很清晰了，先算下三角中的连乘，即我们先算出B\[i\]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

![format_png][]

import java.util.ArrayList;
    public class Solution {
        public int[] multiply(int[] A) {
            int size = A.length;
            int[] B = new int[size];
            
            if (size == 0) return B;
            // 计算下三角的数值
            B[0] = 1;
            for (int i = 1; i< size; i++){
                B[i] = B[i-1] * A[i-1];
            }
            // 计算上三角的数值,与下三角的数值相乘
            int temp = 1;
            for (int j = size-2; j >= 0; j--){
                temp *= A[j+1];
                B[j] *= temp;
            }
            return B;
    
        }
    }

### 52.正则表达式匹配 ###

请实现一个函数用来匹配包括'.'和'\*'的正则表达式。模式中的字符'.'表示任意一个字符，而'\*'表示它前面的字符可以出现任意次（包含0次）。 在本题中，匹配是指字符串的所有字符匹配整个模式。

例如，字符串"aaa"与模式"a.a"和"ab\*ac\*a"匹配，但是与"aa.a"和"ab\*a"均不匹配

逻辑判断的流程：

> 1. s， pattern都为空
> 
> 2. s不为空，pattern为空
> 
> 3. s为空， pattern不为空
> 
> 3.1 如果pattern\[1\] == '\*'（前提肯定要满足 len(pattern) > 1）
> 
> 4. s不为空，pattern不为空
> 
> 4.1 如果 pattern\[1\] == '\*'（前提肯定要满足 len(pattern) > 1）
> 
> 4.1.1 在pattern\[1\] == '\*'前提下，如果s和pattern第一个字符不相同时
> 
> 4.1.2 在pattern\[1\] == '\*'前提下， 如果s和pattern第一个字符相同时：
> 
> 3 种情况------
> 
> 4.2 否则（如果 pattern\[1\] ！= '\*'）：
> 
> 4.2.1 如果s和pattern第一个字符相同，True
> 
> 4.2.2 否则，False

public class Solution {
        public boolean match(char[] str, char[] pattern)
        {
            if (str == null || pattern == null) return false;
            return matchHelper(str, 0, pattern, 0);
        }
        
        private boolean matchHelper(char[] str, int sIndex, char[] pattern, int pIndex){
            // 如果两者为空，则返回true
            if(sIndex == str.length && pIndex == pattern.length) return true;
            // 如果 str 不为空，p为空，则不能匹配
            if (sIndex != str.length && pIndex == pattern.length) return false;
            // 如果str为空，但p不为空
            if (sIndex == str.length && pIndex != pattern.length){
                // 此时 * 号刚好抵消，继续递归判断pattern后面的字符
                if (pIndex + 1 < pattern.length && pattern[pIndex+1] == '*'){
                    return matchHelper(str, sIndex, pattern, pIndex+2);
                }else{
                    return false;
                }
            }
            // 如果两者都不为空的情况下
            if (pIndex + 1 < pattern.length && pattern[pIndex+1] == '*'){
                // 如果第一个字符相同，且pattern第一个字符为 ‘*’
                if (pattern[pIndex] == str[sIndex] || 
                   (pattern[pIndex] == '.' && sIndex != str.length)){
                    return matchHelper(str, sIndex, pattern, pIndex+2)  // s ='bcd', pattern = 'a*bcd', 相当于 * 为0, 不进行匹配
                        || matchHelper(str, sIndex+1, pattern, pIndex+2) //s = 'abcd'. pattern = 'a*bcd"  匹配成功了 1 位
                        || matchHelper(str, sIndex+1, pattern, pIndex); // s = 'aaaaabcd'. pattern = 'a*bcd"
                }else{
                    return matchHelper(str, sIndex, pattern, pIndex+2);
                }
            }
            
            // 第一个字符相同情况下
            if (pattern[pIndex] == str[sIndex] || 
               (pattern[pIndex] == '.' && sIndex != str.length)){
                return matchHelper(str, sIndex+1, pattern, pIndex+1);
            }
            return false;
            
        }
        
        
    }

### 53.表示数值的字符串 ###

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。

例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。

但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

需要注意的是，指数E后面必须跟一个整数，不能没有数，也不能为小数。

public class Solution {
        public boolean isNumeric(char[] str) {
            int size = str.length;
            if (size == 0) return false;
            
            boolean hasE = false, hasDot = false, hasSign = false;
            for (int i = 0; i < size; i++){
                // 如果当前字符是 e， E
                if (str[i] == 'e' || str[i] == 'E'){
                    // 1.首部出现，2.尾部出现，3.重复出现,均不是
                    if (i == 0) return false;
                    if (i == size-1) return false;
                    if (hasE) return false;
                    hasE = true;
                    // 如果当前字符是 +， -
                }else if (str[i] == '+' || str[i] == '-'){
                    // 1.如果当前不是第一位，且前一位不是E， e
                    // 2.如果已经出现过+-， 且前一位不是 E， e,均为false
                    if(i != 0 && str[i-1] != 'E' && str[i-1] != 'e') return false;
                    if (hasSign && str[i-1] != 'E' && str[i-1] != 'e') return false;
                    hasSign = true;
                }else if (str[i] == '.'){
                    // 1.存在多个 . 2. 在 E 后面
                    if (hasDot) return false;
                    if (hasE) return false;
                    hasDot = true;
                }else if (str[i] < '0' || str[i] > '9'){
                    return false;
                }
            }
            return true;
        }
    }

### 54.字符流中第一个不重复的元素 ###

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。

输出描述:

如果当前字符流没有存在出现一次的字符，返回#字符。

public class Solution {
        //Insert one char from stringstream
        String str = "";
        char[] hash = new char[256];
        public void Insert(char ch)
        {
            str += ch;  // 拼接字符串
            hash[ch] += 1; // 对字符 计数
        }
      //return the first appearence once char in current stringstream
        public char FirstAppearingOnce()
        {
            for (int i = 0; i < str.length(); i++){
                char ch = str.charAt(i);
                if (hash[ch] == 1){
                    return ch;
                }
            }
            return '#';
        }
    }

### 55.链表中环的入口 ###

给一个链表，若其中包含环，请找出该链表的环的入口结点，否则，输出null。

方法1. 使用数组，数组保存已经遍历的node，遍历每次查看节点是否在node数组中，如果在，则存在环

/*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    import java.util.ArrayList;
    public class Solution {
    
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            // 使用数组，数组保存已经遍历的node，遍历每次查看节点是否在node数组中，如果在，则存在环
            if (pHead == null || pHead.next == null) return null;
            ArrayList<ListNode> list = new ArrayList();
            
            while (pHead != null){
                if (isInArray(list, pHead)){ // 判断节点是否在数组当中
                    return pHead;
                }
                list.add(pHead);
                pHead = pHead.next;
            }
            return null;
        }
        
        private boolean isInArray(ArrayList<ListNode> list, ListNode node){
            for (ListNode n: list){
                if (n == node){
                    return true;
                }
            }
            return false;
        }
        
    }

方法二：使用快慢指针

![format_png 1][]

假设x为环前面的路程（黑色路程），a为环入口到相遇点的路程（蓝色路程，假设顺时针走）， c为环的长度（蓝色+橙色路程）

当快慢指针相遇的时候：

此时慢指针走的路程为Sslow = x + m \* c + a  
快指针走的路程为Sfast = x + n \* c + a  
2 Sslow = Sfast  
2 \* ( x + m\*c + a ) = (x + n \*c + a)  
从而可以推导出：  
x = (n - 2 \* m )\*c - a  
= (n - 2 \*m -1 )\*c + c - a  
即环前面的路程 = 数个环的长度（为可能为0） + c - a  
什么是c - a？这是相遇点后，环后面部分的路程。（橙色路程）

所以，我们可以让一个指针从起点A开始走，让一个指针从相遇点B开始继续往后走，  
2个指针速度一样，那么，当从原点的指针走到环入口点的时候（此时刚好走了x）  
从相遇点开始走的那个指针也一定刚好到达环入口点。  
所以2者会相遇，且恰好相遇在环的入口点。

最后，判断是否有环，且找环的算法复杂度为：

时间复杂度：O(n)

空间复杂度：O(1)

> 设置快慢指针fast和low，fast每次走两步，low每次走一步。假如有环，两者一定会相遇
> 
> 步骤1：使用快慢指针，找到相遇点，如果找不到则没有环
> 
> 步骤2：找到环入口，让一个指针从头开始走，让一个指针从相遇点B开始继续往后走

/*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
    
        public ListNode EntryNodeOfLoop(ListNode pHead)
        {
            if (pHead == null || pHead.next == null || pHead.next.next == null) return null;
            
            // 设置快慢指针，找到两者的相遇点
            ListNode low =  pHead.next;
            ListNode fast = pHead.next.next;
            
            while (low != fast){
                if (low == null || fast == null) return null;
                low = low.next;
                fast = fast.next.next;
            }
            // 一个从头开始遍历，一个从相遇点low开始遍历
            ListNode head = pHead;
            while (low != head){
                low = low.next;
                head = head.next;
            }
            return low;
    
        }
    }

### 56.删除链表中的重复结点 ###

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。

例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

创建一个辅助结点,方便处理第一个节点是重复的节点的情况

画图理解

删除3 节点的示例图形

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 1][]

/*
     public class ListNode {
        int val;
        ListNode next = null;
    
        ListNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        public ListNode deleteDuplication(ListNode pHead)
        {
            if (pHead == null || pHead.next == null) return pHead;
            
            ListNode dummy = new ListNode(-1);// 创建辅助节点
            dummy.next = pHead; //连接链表
            ListNode last = dummy;
            
            while (pHead != null && pHead.next != null){
                if (pHead.val != pHead.next.val){ // 更新节点
                    pHead = pHead.next;
                    last = last.next;
                }else{
                    int val = pHead.val;
                    while (pHead != null && val == pHead.val){ //找到重复节点的下一个节点
                        pHead = pHead.next;
                    }
                    last.next = pHead; // 删除重复节点
                }
            }
            return dummy.next;
        }
    }

### 57.二叉树的下一个结点 ###

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

思路：首先知道中序遍历的规则是：左根右，然后作图

![format_png 2][]

结合图，我们可发现分成两大类：

**1、有右子树的**，那么下个结点就是右子树最左边的点；（eg：D，B，E，A，C，G）

**2、没有右子树的，也可以分成两类**，

a)是父节点左孩子（eg：N，I，L） ，那么父节点就是下一个节点 ；

b)是父节点的右孩子（eg：H，J，K，M）找他的父节点的父节点的父节点...直到当前结点是其父节点的左孩子位置。如果没有eg：M，那么他就是尾节点。

**1、有右子树的**，那么下个结点就是右子树最左边的点

2、没有右子树，2.1如果有左结点，返回根节点就可以了；

2.2.如果是右叶子结点，则一直往上寻找父节点，然后继续判断其是否有左结点  
  
分析二叉树的下一个节点，一共有以下情况：  
1.二叉树为空，则返回空；  
2.节点右孩子存在，则设置一个指针从该节点的右孩子出发，一直沿着指向左子结点的指针找到的叶子节点即为下一个节点；  
3.节点不是根节点。如果该节点是其父节点的左孩子，则返回父节点；否则继续向上遍历其父节点的父节点，重复之前的判断，返回结果。

**其中next结点是指向父亲结点**

/*
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null;
    
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        public TreeLinkNode GetNext(TreeLinkNode pNode)
        {
            if(pNode == null) return null;
            // 如果有右子树的话，一直找右子树的左节点
            if (pNode.right != null){
                pNode = pNode.right;
                while (pNode.left != null){
                    pNode = pNode.left;
                }
                return pNode;
            }
            // 没有右子树的情况
            // 1. 如果root左子树不存在，则往上遍历
            // 2. 如果左子树存在，则return
            while (pNode.next != null){
                TreeLinkNode proot = pNode.next;
                if(proot.left == pNode){
                    return proot;
                }
                pNode = pNode.next;
            }
            return null;
            
        }
    }

### 58.判断是否是对称二叉树 ###

请实现一个函数，用来判断一颗二叉树是不是对称的。

注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

思路：递归判断

1. 创建一个函数，包含左右节点

2. 如果左右子树均为空，这时对称

3.如果存在一个子树不为空，则不对称

4. 递归判断，判断2个节点值是否相同，左子树的左节点与右子树右节点，左子树右节点与右子树左节点比较

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        boolean isSymmetrical(TreeNode pRoot)
        {
            if(pRoot == null) return true;
            return symHelper(pRoot.left, pRoot.right);
        }
        
        private boolean symHelper(TreeNode left, TreeNode right){
            if (left == null && right == null) return true;
            if (left == null || right == null) return false;
            return left.val == right.val && symHelper(left.left, right.right) && symHelper(left.right, right.left);
        }
        
    }

### 59.按之字形打印二叉树 ###

请实现一个函数按照之字形打印二叉树，即第一行按照从左到右的顺序打印，第二层按照从右至左的顺序打印，第三行按照从左到右的顺序打印，其他行以此类推。

**即使用层次遍历得到每一层分开的多重数组，然后按单双次打印，单次按顺序，双次反向打印。**

**使用两个栈实现，栈1 按左右子树的顺序存入栈中，栈2 按右 左的顺序存入栈中。**

![format_png 3][]

import java.util.ArrayList;
    import java.util.LinkedList;
    
    /*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
            ArrayList<ArrayList<Integer> > res = new ArrayList();
            if (pRoot == null) return res;
            LinkedList<TreeNode> stack1 = new LinkedList();
            LinkedList<TreeNode> stack2 = new LinkedList();
            stack1.push(pRoot);
            
            while (!stack1.isEmpty() || !stack2.isEmpty()){
                ArrayList<Integer> array1 = new ArrayList();  //保存奇数行二叉树数据
                ArrayList<Integer> array2 = new ArrayList();  // 保存偶数行
                while (!stack1.isEmpty()){
                    TreeNode curNode = stack1.pop();
                    if (curNode.left != null) stack2.push(curNode.left);
                    if (curNode.right != null) stack2.push(curNode.right);
                    array1.add(curNode.val);
                }
                if (array1.size() > 0) res.add(array1);
                
                while (!stack2.isEmpty()){
                    TreeNode curNode = stack2.pop();
                    if (curNode.right != null) stack1.push(curNode.right); // 先保存右子树
                    if (curNode.left != null) stack1.push(curNode.left);
                    array2.add(curNode.val);
                }
                if (array2.size() > 0) res.add(array2);
            }
            return res;
    
        }
    
    }

### 60.把二叉树打印成多行 ###

从上到下按层打印二叉树，同一层结点从左至右输出。每一层输出一行。

二叉树的层次、广度优先遍历，使用队列来实现

### 61.序列二叉树 ###

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（\#），以 ！ 表示一个结点值的结束（value!）。  
  
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

例如，我们可以把一个只有根节点为1的二叉树序列化为"1,"，然后通过自己的函数来解析回这个二叉树

![70][]

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    public class Solution {
        private int index = -1;
        
        String Serialize(TreeNode root) { // 序列化二叉树,根左右，前序序列化
            StringBuffer sb = new StringBuffer();
            if (root == null){
                sb.append("#,");
                return sb.toString();
            }
            sb.append(root.val + ",");  // 先保存根节点，
            sb.append(Serialize(root.left)); // 保存左节点的字符串
            sb.append(Serialize(root.right));
            return sb.toString();
            
      }
        TreeNode Deserialize(String str) { // 反序列化二叉树
            index += 1;
            int size = str.length();
            if (index >= size) return null;
            String[] s = str.split(",");
            TreeNode node = null;
            if (!s[index].equals("#")){
                node = new TreeNode(Integer.valueOf(s[index]));
                node.left = Deserialize(str);
                node.right = Deserialize(str);
            }
           return node;
      }
    }

### 62.二叉搜索树的第k 个结点 ###

给定一棵二叉搜索树，请找出其中的第k小的结点。

例如， （5，3，7，2，4，6，8） 中，按结点数值大小顺序第三小结点的值为4。

`思路：二叉搜索树按照中序遍历的顺序打印出来正好就是排序好的顺序。`

`// 所以，按照中序遍历顺序找到第k个结点就是结果。`

/*
    public class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
    
        public TreeNode(int val) {
            this.val = val;
    
        }
    
    }
    */
    import java.util.Stack;
    public class Solution {
        TreeNode KthNode(TreeNode pRoot, int k)
        {
            // 使用非递归中序遍历二叉树
            if (pRoot == null || k <= 0) return null;
            
            Stack<TreeNode> stack = new Stack();
            int count = 0;
            while (pRoot != null || !stack.isEmpty()){
                while (pRoot != null){
                    stack.push(pRoot); // 将左节点全部放入栈中
                    pRoot = pRoot.left;
                }
                pRoot = stack.pop();
                count += 1;  // 统计节点数量
                if (count == k) return pRoot;
                pRoot = pRoot.right; // 找到右节点
            }
            return null;
         }
    
    
    }

### 63.数据流中的中位数 ###

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路：

此题的核心是：将获取的最大的数字均放在最小堆，将获取的最小的值均放在最大堆

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 2][]

import java.util.PriorityQueue;
    import java.util.Comparator;
    public class Solution {
        private PriorityQueue<Integer> minHeap = new PriorityQueue(); //  最小堆
        private PriorityQueue<Integer> maxHeap = new PriorityQueue(12, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer  o2){
                return o2 - o1;
            }
        });  // 需要结合comparator 来实现最大堆
    
        private int count = 0;
        
        public void Insert(Integer num) {
            if ((count & 1) == 0){ // 如果是偶数的情况下
                // 将最大值保存在最小堆中
                maxHeap.offer(num);
                int maxValue = maxHeap.poll();// 获取堆中的最大值
                minHeap.offer(maxValue);
            }else{
                minHeap.offer(num);
                int minValue = minHeap.poll(); // 获取堆中的最小值
                maxHeap.offer(minValue);
            }
            count += 1;
        }
    
        public Double GetMedian() {
            if ((count & 1) == 0){ 
                return new Double((minHeap.peek() + maxHeap.peek()) /2.0);
            }else{
                return new Double(minHeap.peek());
            }
        }
    
    
    }

### 64.滑动窗口的最大值 ###

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。

例如，如果输入数组\{2,3,4,2,6,2,5,1\}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为\{4,4,6,6,6,5\}； 针对数组\{2,3,4,2,6,2,5,1\}的滑动窗口有以下6个： \{\[2,3,4\],2,6,2,5,1\}， \{2,\[3,4,2\],6,2,5,1\}， \{2,3,\[4,2,6\],2,5,1\}， \{2,3,4,\[2,6,2\],5,1\}， \{2,3,4,2,\[6,2,5\],1\}， \{2,3,4,2,6,\[2,5,1\]\}。

使用大顶堆的

import java.util.PriorityQueue;
    import java.util.Comparator;
    import java.util.ArrayList;
    
    public class Solution {
        public ArrayList<Integer> maxInWindows(int [] num, int size)
        {
            ArrayList<Integer> res = new ArrayList();
            int len = num.length;
            if (len < size) return res;
            if (size == 0) return res;
            int gap = len - size;
            PriorityQueue<Integer> maxHeap = new PriorityQueue(3, new Comparator<Integer>(){
                public int compare(Integer o1, Integer o2){
                    return o2-o1;
                }
            }); // 最大堆
            
            for (int i = 0; i <= gap; i++){
                for (int j = i; j < size+i; j++){
                    maxHeap.offer(num[j]);
                }
                int max = maxHeap.peek(); // 获取最大值
                res.add(max);
                while(!maxHeap.isEmpty()){
                    maxHeap.poll();
                }
            }
            return res;
        }
    }

使用双端队列，复杂度为O(n)

`用一个双端队列，队列第一个位置保存当前窗口的最大值，当窗口滑动一次`

`1.判断当前最大值是否过期`

`2.新增加的值从队尾开始比较，把所有比他小的值丢掉`

import java.util.ArrayList;
    import java.util.LinkedList;
    
    public class Solution {
        public ArrayList<Integer> maxInWindows(int [] num, int size)
        {
            ArrayList<Integer> res = new ArrayList();
            int len = num.length;
            if (len < size || size <= 0 || len == 0) return res;
            
            LinkedList<Integer> indexQueue = new LinkedList(); // 用于保存索引值的双端队列,队首保存最大值的索引
            for (int i = 0; i < len; i++){
                while (indexQueue.size()!=0 && num[i] > num[indexQueue.peekLast()]){
                    //如果当前值比队首索引值的大小大的话，这删除队首索引
                    indexQueue.pollLast();
                }
                indexQueue.addLast(i);
                // 判断队首元素是否过期，如6,2,5,1,size为3
                if (indexQueue.size()!=0 && (i-indexQueue.peekFirst())==size){
                    indexQueue.pollFirst();
                }
                if (i >= size-1){
                    res.add(num[indexQueue.peekFirst()]);
                }
            }
            return res;
    }}

### 65.矩阵中的路径 ###

请设计一个函数，用来判断在一个矩阵中是否存在一条包含某字符串所有字符的路径。路径可以从矩阵中的任意一个格子开始，每一步可以在矩阵中向左，向右，向上，向下移动一个格子。如果一条路径经过了矩阵中的某一个格子，则之后不能再次进入这个格子。

例如

![20200901132529922.png][]

这样的3 X 4 矩阵中包含一条字符串"bcced"的路径，但是矩阵中不包含"abcb"路径，因为字符串的第一个字符b占据了矩阵中的第一行第二个格子之后，路径不能再次进入该格子。

解题思路：

**采用回溯法（探索与回溯法），它是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。 但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。**

基本思想：

0.根据给定数组，初始化一个标志位数组，初始化为false，表示未走过，true表示已经走过，不能走第二次

1.根据行数和列数，遍历数组，先找到一个与str字符串的第一个元素相匹配的矩阵元素，进入judge

2.根据i和j先确定一维数组的位置，因为给定的matrix是一个一维数组

3.确定递归终止条件：越界，当前找到的矩阵值不等于数组对应位置的值，已经走过的，这三类情况，都直接false，说明这条路不通

4.若pathLength，就是待判定的字符串str的索引已经判断到了最后一位，此时说明是匹配成功的

5.下面就是本题的精髓，递归不断地寻找周围四个格子是否符合条件，只要有一个格子符合条件，就继续再找这个符合条件的格子的四周是否存在符合条件的格子，直到k到达末尾或者不满足递归条件就停止。

6.走到这一步，说明本次是不成功的，我们要还原一下标志位数组index处的标志位，进入下一轮的判断。

public class Solution {
        public boolean hasPath(char[] matrix, int rows, int cols, char[] str)
        {
            int size = matrix.length;
            if (rows * cols != size || size == 0 || str.length==0) return false;
            // 初始化时，全部元素为 false
            boolean[] visited = new boolean[size]; // 如果被访问，则位true，记录matrix元素访问
            int pathLength = 0; // 记录遍历的索引值
    
            for (int i = 0; i < rows; i++){
                for (int j = 0; j< cols; j++){
                     // 如果有一条路径满足，则为 true
                    if (hasPathHelper(matrix, rows, cols, str, i, j, visited, pathLength)){
                        return true;
                    }
                }
            }
            return false;
        }
        
        private boolean hasPathHelper(char[] matrix, int rows, int cols, char[] str, int x, int y, boolean[] visited, int pathLength){
            
            if (str.length == pathLength){
                return true;
            }
            // 使用递归回溯的方法
            int index = x * cols + y; // matrix的索引
            boolean result = false;
            // 最后2个满足的条件是：没有别访问，且找到指定字符
            if (0 <= x && x < rows && 0 <= y && y < cols && visited[index] == false && matrix[index]== str[pathLength]){
                pathLength += 1;
                visited[index] = true;
                // 遍历上下左右 四个方位
                boolean x1 = hasPathHelper(matrix, rows, cols, str, x-1, y, visited, pathLength);
                boolean x2 = hasPathHelper(matrix, rows, cols, str, x+1, y, visited, pathLength);
                boolean x3 = hasPathHelper(matrix, rows, cols, str, x, y-1, visited, pathLength);
                boolean x4 = hasPathHelper(matrix, rows, cols, str, x, y+1, visited, pathLength);
                result = x1 || x2 || x3|| x4;
                
                if (result == false){ //回溯上一层
                    pathLength -= 1;
                    visited[index] = false;
                }
            }
            return result;
    
        }
    
    
    }

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

地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。

例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？

public class Solution {
        public int movingCount(int threshold, int rows, int cols)
        {
            boolean[][] flag = new boolean[rows][cols]; // 创建二维矩阵，走过则为true
            int result = counterHelper(flag, threshold, rows, cols, 0, 0); // 从原点开始遍历
            return result;
            
        }
        
        private int counterHelper(boolean[][] flag, int threshold, int rows, int cols, int i, int j){
            boolean isFit = countNumber(i) + countNumber(j) <= threshold;
            if (i >= 0 && i < rows && j >= 0 && j < cols && flag[i][j] == false && isFit){
                flag[i][j] = true;
    // 计算上下左右的符合的数量
                return counterHelper(flag, threshold, rows, cols, i-1, j) +
                    counterHelper(flag, threshold, rows, cols, i+1, j) +
                    counterHelper(flag, threshold, rows, cols, i, j-1) +
                    counterHelper(flag, threshold, rows, cols, i, j+1) + 1;
            }
            return 0;
        }
        
        // 计算数字 各百分十分等位数 的 和
        private int countNumber(int num){
            int res = 0;
            while (num != 0){
                res += num%10;
                num /= 10;
            }
            return res;
        }
        
    }

终于。。。。。。。。。。。。。完结。。。。。。。。。。。。。。。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70]: /images/20221123/b5bf7d3be6e148b9aed8184eda3dc179.png
[offer_1_3]: https://blog.csdn.net/qq_40587575/article/details/88675889
[offer_2_3]: https://blog.csdn.net/qq_40587575/article/details/88767488
[offer_3_3]: https://blog.csdn.net/qq_40587575/article/details/88920399
[offer_Java_-]: https://blog.csdn.net/qq_40587575/article/details/106996017
[offer_Java_- 1]: https://blog.csdn.net/qq_40587575/article/details/108098502
[offer_Java_- 2]: https://blog.csdn.net/qq_40587575/article/details/108253489
[image.png]: /images/20221123/952662b78a75449e85ca85ecbc87d66b.png
[image.png 1]: https://i.loli.net/2020/05/24/p6lzsfCYA8BVM7X.png
[image.png 2]: /images/20221123/badea4554cb9481aa7d7a1ba79cd45c1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xyczEzNTMyODEwMDQ_size_16_color_FFFFFF_t_70]: /images/20221123/7c193cc5727845789f0b33c12a0b847a.png
[20190213172431556.png]: /images/20221123/6db451c0a58f4b2d9ed57e2064e14253.png
[format_png]: /images/20221123/1b04acceb6444c83a9c0e1429866e64e.png
[format_png 1]: /images/20221123/cd618109ddd549d6999ee3792d3c0e52.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 1]: /images/20221123/8cc9e025f69e426a8b32c620540a4a17.png
[format_png 2]: /images/20221123/2ca9f0f75e3644b3a8081ffb9b75997a.png
[format_png 3]: /images/20221123/35a021271d044cbb8de3ba2441434378.png
[70]: /images/20221123/de61e62c16f44396b2ee6c65a4d1db3f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1_size_16_color_FFFFFF_t_70 2]: /images/20221123/d3ed5126853844ac8b741854855f9e82.png
[20200901132529922.png]: /images/20221123/1022e55029e6478eae5149dfa2a55b5e.png