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

最新推荐文章于 2022-01-17 20:44:30 发布

置顶蜘蛛侠不会飞

最新推荐文章于 2022-01-17 20:44:30 发布

阅读量787

点赞数 1

分类专栏：剑指offer 文章标签：剑指offer java 数据结构算法刷题

本文链接：https://blog.csdn.net/qq_40587575/article/details/108253489

版权

剑指offer 专栏收录该内容

17 篇文章 4 订阅

订阅专栏

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

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

剑指offer（3/3）第三大部分

----------------------------------------------------

《剑指offer》Java版本实现：

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。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) 来表示最后剩下的那个人的序号。整个流程如下图所示：

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

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

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

在从 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.不用加减乘除做相加

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

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

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

在这里插入图片描述

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]中的一部分，然后倒过来按上三角中的分布规律，把另一部分也乘进去。

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;
    }
    
}

方法二：使用快慢指针

假设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 节点的示例图形

/*
 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.二叉树的下一个结点

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

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

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

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 按右左的顺序存入栈中。

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.把二叉树打印成多行

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

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

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 {
    ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> res = new ArrayList();
        LinkedList<TreeNode> queue = new LinkedList();
        if (pRoot == null) return res;
        queue.offer(pRoot);
        while (!queue.isEmpty()){
            ArrayList<Integer> list = new ArrayList();
            int size = queue.size(); // 保存队列的长度
            for (int i = 0; i < size; i++){  // 确保打印二叉树一行的数据
                TreeNode root = queue.poll();
                if (root.left != null) queue.offer(root.left);
                if (root.right != null) queue.offer(root.right);
                list.add(root.val);
            }
            res.add(list);
        }
       return res;
    
    }
    
}

61.序列二叉树

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

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

二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

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

/*
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()方法获取当前读取数据的中位数。

思路：

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

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.矩阵中的路径

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

例如

这样的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;
    }
    
}

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

蜘蛛侠不会飞

关注

1
点赞
踩
1

收藏

觉得还不错? 一键收藏
0
评论
三天刷完《剑指OFFER编程题》--Java版本实现（第三天）

正在更新中。。。。。。。。。剑指offer --Python版本的实现：剑指offer（1/3）第一大部分剑指offer（2/3）第二大部分剑指offer（3/3）第三大部分46.圆圈后最后剩下额数每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以..
复制链接

扫一扫