剑指offer｜51-60题解题思路及代码(Java版)

2019-04-12 本文已影响0人蓝白绛

剑指offer51到60题总览：

构建乘积数组
正则表达式匹配
表示数值的字符串
字符流中第一个不重复的字符
链表中环的入口结点
删除链表中重复的结点
二叉树的下一个结点
对称的二叉树
按之字形打印二叉树
把二叉树打印成多行

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]。不能使用除法。

解题思路

剑指offer｜51题构建乘积数组

两次遍历，第一次计算下三角，第二次计算上三角。比如计算下三角，设置一个temp，temp=A[0]，将temp赋值给B[1]；temp=temp*A[1]，将temp赋值给B[2]。

import java.util.ArrayList;
public class Solution {
    public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        if(A.length == 0){return B;}
        if(A.length == 1){
            B[0] = 1;
            return B;
        }
        B[0] = 1;//先将B[0]赋值为1，计算下三角时用不到B[0]
        int temp = 1;//用来保存当前乘积
        for(int i=1; i<A.length; i++){//计算下三角
            temp = temp * A[i-1];
            B[i] = temp;
        }
        temp = 1;//计算上三角前将temp置为0
        for(int i=A.length-2; i>=0; i--){//计算上三角
            temp = temp * A[i+1];
            B[i] *= temp;//B[i]应该在计算完下三角的基础上乘temp
        }
        return B;
    }
}

52、正则表达式匹配

题目描述

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

解题思路

考虑各种情况：

如果strIndex和patternIndex都到尾了，则匹配成功。
如果strIndex没有到尾，但patternIndex已经到尾了，str还有最后一部分没有匹配完，则匹配失败。
如果遇到pattern当前字符的下一个字符是*，有几种情况：

pattern当前字符是.，则可视作匹配0个字符，strIndex+0，patternIndex+2，继续递归；可视作匹配1个字符，strIndex+1，patternIndex+2，继续递归；可视作暂时匹配1个字符，patternIndex不移动，后面可再选择匹配0个或1个或再暂时匹配一个字符，strIndex+1，patternIndex+0，继续递归。
pattern当前字符不是.而是一个字母或者其他，则要看pattern当前字符和str当前字符是否一样：不一样，则匹配失败；一样，则和pattern当前字符是.一样，可以选择匹配0个或1个或暂时匹配一个字符，继续递归。
3.1

public class Solution {
    public boolean match_1(char[] str, char[] pattern) {
        if (str == null || pattern == null) {
            return false;
        }
        int strIndex = 0;
        int patternIndex = 0;
        return matchCore(str, strIndex, pattern, patternIndex);
    }

    public boolean matchCore(char[] str, int strIndex, char[] pattern, int patternIndex) {
        //有效性检验：str到尾，pattern到尾，匹配成功
        if (strIndex == str.length && patternIndex == pattern.length) {
            return true;
        }
        //pattern先到尾，匹配失败
        if (strIndex != str.length && patternIndex == pattern.length) {
            return false;
        }
        //模式第2个是*，则分两种情况，一种是*前面是.一种是*是一般字符。
        //如果是一般字符，则又可分为pattern当前字符与str当前字符匹配成功和不匹配两种情况
        //而*前面是.和pattern当前字符与str当前字符匹配成功的情况可以写到一起。
        if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
            if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                    || (strIndex != str.length && pattern[patternIndex] == '.')) {
                //*前面是.，或*前面的一般字符是与str的当前字符匹配成功
                return matchCore(str, strIndex, pattern, patternIndex + 2) //模式后移2，视为x*匹配0个字符
                        || matchCore(str, strIndex + 1, pattern, patternIndex + 2) //视为模式匹配1个字符，模式向后移动两位
                        || matchCore(str, strIndex + 1, pattern, patternIndex); //当前只匹配1个，模式没有移动，再递归可匹配str中的下一个或匹配0个
            } else {
                //*前面的字符与当前字符不匹配，模式向后移动两位
                return matchCore(str, strIndex, pattern, patternIndex + 2);
            }
        }
        //模式第2个不是*，且字符串第1个跟模式第1个匹配，则都后移1位，否则直接返回false
        if ((strIndex != str.length && pattern[patternIndex] == str[strIndex])
                || (strIndex != str.length && pattern[patternIndex] == '.')) {
            return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
        }
        return false;
    }
}

53、表示数值的字符串

题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示数值。但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是。

解题思路

用正则表达式。

public class Solution {
    public boolean isNumeric(char[] str) {
        String s = String.valueOf(str);
        return s.matches("[\\+-]?[0-9]*(\\.[0-9]*)?([eE][\\+-]?[0-9]+)?");
    }
}

54、字符流中第一个不重复的字符

题目描述

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符"go"时，第一个只出现一次的字符是"g"。当从该字符流中读出前六个字符“google"时，第一个只出现一次的字符是"l"。
输出描述:
如果当前字符流没有存在出现一次的字符，返回#字符。

public class Solution {
    int arr[] = new int[256];//建立所有可能字符的数组
    int index;
    public Solution(){
        for(int i=0; i<arr.length; i++){//将数组所有值赋值为-1
            arr[i] = -1;
        }
        index = 0;//index为当前插入的字符的个数
    }
    //Insert one char from stringstream
    public void Insert(char ch)//因为要频繁插入，所以不建议在insert方法中设置循环
    {
        if(arr[ch] == -1){//-1表示之前没有出现过，现在出现了
            arr[ch] = index;//将对应字符的位赋值为字符流的index
        }else if(arr[ch] >= 0){//>=0表示之前出现过一次，而且是唯一一次，而此时出现了第二次
            arr[ch] = -2;//出现了第二次，将对应字符的位赋值为-2，>=0的情况只保存当前只出现了一次，并记录在字符流中的index
        }
        index++;//插入了一个字符，index+1
    }
    //return the first appearence once char in current stringstream
    public char FirstAppearingOnce()
    {
        int result_index = index;//给返回结果一个初始值
        for(int i=0; i<arr.length; i++){//遍历数组
            if(arr[i] >= 0){//遇到一个只出现一次的字符
                if(result_index == index){result_index = i;}//如果是第一个只出现一次的字符，则将result_index更新
                else{
                    if(arr[i] < arr[result_index]){//找到了新的只出现一次的字符，且其保存的字符流的位置更靠前，更新result_index。
                        result_index = i;
                    }
                }
            }
        }
        if(result_index == index){return '#';}//如果整个遍历没有找到只出现一次的字符，返回#
        else{return (char)result_index;}//将int类型的下标转化为char类型
    }
}

55、链表中环的入口结点

题目描述

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

解题思路

方法很多，记录两种，都是快慢指针的思想。设置一个慢指针slow，一次走一步；设置一个快指针fast，一次走两步。如果存在环，则快慢指针一定会在环内相遇。如果不存在环，则fast会率先走到链表尾，则返回null。在环内相遇之后，有两种方法寻找入环结点：

从快慢指针相遇的结点开始，fast结点不走，slow再走一圈，得到环内包含的结点数c。然后令p1=pHead，p1先走c步(此时已经知道有环，不用担心会走到空结点)，令p2=pHead，然后p1和p2一起走，每次都走一步(p1始终超前p2 c步)。则他们第一次相等的时候指向的节点，就是入环结点。
从快慢指针相遇的结点开始，我们有以下推导：
参考链接：https://www.nowcoder.com/questionTerminal/253d2c59ec3e4bc68da16833f79a38e4
剑指offer｜55题链表中环的入口结点
假设x为环前面的路程（黑色路程），a为环入口到相遇点的路程（蓝色路程，假设顺时针走）， c为环的长度（蓝色+橙色路程）
当快慢指针相遇的时候：
此时慢指针走的路程为 $S_{slow}= x + m * c + a$ ， $m$ 为慢指针在环内转的圈数，这个圈数并不重要。
快指针走的路程为 $S_{fast} = x + n * c + a$ ， $n$ 为快指针在环内转的圈数。
我们设置快指针一次走两步，慢指针一次走一步，则相遇时他们的路程有如下关系： $2S_{slow} = S_{fast}$
则有： $2 * ( x + m*c + a ) = (x + n *c + a)$
从而可以推导出： $\begin{aligned} x &= (n - 2 * m )*c - a\\ &= (n - 2 *m -1 )*c + c - a \end{aligned}$
上式第二步中，我们提出一个 $c$ ，则 $c-a$ 可以表示相遇点后，环后面部分的路程。（橙色路程）
所以，我们可以让一个指针p从起点A开始走，让slow指针从相遇点B开始继续往后走，p和slow指针速度一样，每次只走一步，则当指针p走到环入口点的时候（此时刚好走了x）slow指针也一定刚好到达环入口点。p和slow恰好相遇在环的入口点。返回p或slow即可。这种方法需要一点推导所以可能想不到，但是推出来之后写代码就变得更简单了。

public class Solution {
    public ListNode EntryNodeOfLoop(ListNode pHead){
        if(pHead==null || pHead.next==null || pHead.next.next==null){return null;}
        ListNode slow = pHead.next;//slow先走一步
        ListNode fast = pHead.next.next;//fast先走两步
        while(slow != fast){//当还没有相遇的时候
            if(fast.next!=null && fast.next.next!=null){//没有走到链表尾
                slow = slow.next;//slow和fast继续走
                fast = fast.next.next;
            }else{//如果走到了链表尾，则一定没有环，直接返回null
                return null;
            }
        }//循环出来了一定是slow和fast相遇了
        ListNode p = pHead;//p指向链表头，与slow一起走，p和slow一次都只走一步
        while(p!=slow){//p和slow一起走，此时有环则他们一定会在入环结点相遇。
            p = p.next;
            slow = slow.next;
        }
        return p;
    }
}

56、删除链表中重复的结点

题目描述

在一个排序的链表中，存在重复的结点，请删除该链表中重复的结点，重复的结点不保留，返回链表头指针。例如，链表1->2->3->3->4->4->5 处理后为 1->2->5

解题思路

如果链表最前面就有重复的，则将链表头前面的重复结点全部跳过，让pHead指向第一个不重复的结点，返回新的头结点。如果链表最前面不是重复的，则找到最后一个不重复结点，递归删除后面的重复结点。这里不加速找到最后一个不重复的结点也可以，如果头结点不是重复结点，则递归头结点后面的结点，直到递归到头结点就是重复结点。

public class Solution {
    public ListNode deleteDuplication(ListNode pHead){
        if(pHead == null){return null;}
        if(pHead.next == null){return pHead;}
        ListNode p = pHead;
        if(p.val == p.next.val){//如果p点与p后面的结点重复
            while(p.next!=null && p.val == p.next.val){//跳过所有的重复结点，直到p结点不重复，或者p为最后一个结点。
                p = p.next;//如果p为重复结点，且p后面还有结点，则p后移一位
            }
            pHead = deleteDuplication(p.next);//如果是p和p后面的结点不重复了，则递归p.next；或者p为最后一个结点了，但是p结点是重复结点，依旧递归p.next，这时递归返回null
        }else{//如果p不是重复结点，则看p的后面的结点是不是重复结点
            while(p.next.next!=null && p.next.val != p.next.next.val){//向后找重复结点，p指向最后一个不重复结点
                p = p.next;
            }//这里的循环不要也可以，直接p.next = deleteDuplication(p.next);也行
            p.next = deleteDuplication(p.next);//递归删除p结点后面的重复结点，并将删除后返回的头结点连接到p的后面
        }
        return pHead;
    }
}

57、二叉树的下一个结点

题目描述

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

解题思路

画图，可知各种情况的下一个结点。

如果pNode为空，则返回null。
如果pNode不为空，判断pNode是否有右子树，如果有右子树，则返回右子树中最左边的结点。如果没有右子树，则向上找pNode的父结点。
如果没有父结点，则pNode是根节点，中序遍历已经遍历完，返回null；如果有父结点，且如果它是父结点的左结点，直接返回pNode的父结点；如果有父结点，且如果它是父结点的右结点，则要看pNode的祖父结点。
如果没有祖父结点，则中序遍历已经遍历完，返回null；如果pNode的父结点是祖父结点的左结点，则返回祖父结点；如果有父结点，且如果pNode的父结点是祖父结点的右结点，则中序遍历已经遍历完，返回null。

public class Solution {
    public TreeLinkNode GetNext(TreeLinkNode pNode){
        if(pNode == null){return null;}//如果结点为空，则返回null
        if(pNode.right!=null){//如果结点有右子树，则找到子树的最左的结点
            pNode = pNode.right;
            while(pNode.left!=null){//找到最左的结点
                pNode = pNode.left;
            }
            return pNode;
        }else{//如果改结点没有右子树，就只能往上找其父结点
            if(pNode.next!=null && pNode.next.left==pNode){//有父结点，且是父结点的左结点，则直接返回pNode的父结点
                return pNode.next;
            }else if(pNode.next!=null && pNode.next.right==pNode){//有父结点，且是父极点的右结点
                if(pNode.next.next!=null && pNode.next.next.left==pNode.next){
                //如果祖父结点存在，且其父结点是祖父结点的左结点，则返回其祖父结点
                    return pNode.next.next;
                }else if(pNode.next.next!=null && pNode.next.next.right==pNode.next){
                //如果祖父结点存在，且其父结点是祖父结点的右结点，则返回null，中序遍历后面没有结点了
                    return null;
                }else{//如果祖父结点不存在，也就是其父结点就是根结点，中序遍历后面已经没有结点了，返回null
                    return null;
                }
            }else{//如果他没有父结点，则它是根节点
                return null;//这种情况就是根节点只有左子树，右边全为空，根节点就是最后一个结点，返回null
            }
        }
    }
}

58、对称的二叉树

题目描述

请实现一个函数，用来判断一颗二叉树是不是对称的。注意，如果一个二叉树同此二叉树的镜像是同样的，定义其为对称的。

解题思路

根节点只有一个，不用管其对称性，抛开根节点，看根节点的左右子树。
如果左右两颗子树是镜像的，则这两颗子树的根节点的值是一样的，且其left.left与right.right是镜像的；其left.right与right.left是镜像的。

public class Solution {
    boolean isSymmetrical(TreeNode pRoot){
        if(pRoot==null){return true;}//如果根节点为空，则返回true
        return isSym(pRoot.left, pRoot.right);//看根节点的左右子树是否是镜像的
    }
    boolean isSym(TreeNode left, TreeNode right){
        if(left==null && right==null){return true;}//如果两颗树都为空，则返回true
        if(left!=null && right==null){return false;}//如果左不空，右空，则不是镜像的
        if(left==null && right!=null){return false;}//如果左空，右不空，则不是镜像的
        if(left.val != right.val){return false;}//如果左右都不空，但是左右子树的根节点的值不一样，则不是镜像的
        //左右都不空，则查看left.left与right.right是否镜像，其left.right与right.left是否镜像
        return isSym(left.left, right.right) && isSym(left.right, right.left);
    }
}

59、按之字形打印二叉树

题目描述

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

解题思路

设置一个boolean left2right来判断是应该从左往右还是从右往左。
有一种方法是用两个栈，一个是奇数层栈，一个是偶数层栈。可参考牛客网。
层次遍历一棵树容易想到用队列，可以简单地在将结点的value插到list的最前面，但是这种方法肯定不能用于海量数据。java中的LinkedList可以用来实现队列，这个队列的实现是双向链表，是可以正向迭代和反向迭代的。

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Iterator;

public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
        if(pRoot==null){return final_list;}
        boolean left2right = true;
        ArrayList<Integer> list = new ArrayList<>();
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(null);//分隔符在一层结点的前面比较方便
        queue.offer(pRoot);
        while(queue.size()!=1){//到最后只剩下一个null的时候结束循环
            TreeNode node = queue.poll();//队头结点出队列
            if(node == null){//遇到分界符号
                Iterator<TreeNode> iter = null;//对队列中的结点进行迭代，但不出队列
                if(left2right){
                    iter = queue.iterator();//正向迭代器
                }else{
                    iter = queue.descendingIterator();//反向迭代器
                }
                left2right = !left2right;//将迭代方向反向
                while(iter.hasNext()){
                    TreeNode temp = (TreeNode)iter.next();//迭代队中的每个元素，加入list
                    list.add(temp.val);
                }//一般遍历树时我们将结点出队，并将val加入list，但是这里只对队中的元素迭代，并不出队。另外，此时遍历时，队中只有结点，没有null
                final_list.add(new ArrayList<Integer>(list));//拷贝一个list加入final_list
                list.clear();//清空list
                queue.offer(null);//队中元素迭代完了之后加入null
            }else{
                if(node.left!=null){queue.offer(node.left);}//我们将元素迭代完了之后再将元素遍历一遍，此时只需要将这里元素的左右结点加入队即可
                if(node.right!=null){queue.offer(node.right);}
            }
        }
        return final_list;
    }
}

60、把二叉树打印成多行

题目描述

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

解题思路

层次遍历很容易想到用队列。牛客评论区还有利用递归方法的，递归是深度优先，但是他通过对方法传入深度值来指定将结点加入哪一个list，从而使返回结果看起来像层次遍历。
队列版本：

import java.util.ArrayList;
import java.util.LinkedList;

public class Solution {
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
        if(pRoot==null){return final_list;}
        LinkedList<TreeNode> queue = new LinkedList<>();
        queue.offer(pRoot);
        queue.offer(null);//分界符号
        final_list.add(new ArrayList<Integer>());//新建一个list加入fianl_list
        while(queue.size()!=1){//如果队列只剩下一个元素，则这个元素一定是分界符号
            TreeNode node = queue.poll();//取队头元素
            if(node!=null){//如果队头不是分界符号
                final_list.get(final_list.size()-1).add(node.val);//将val加入相应list
                if(node.left!=null){queue.offer(node.left);}//如果左子树非空，则将左子树的根节点加入队列
                if(node.right!=null){queue.offer(node.right);}//如果右子树非空，则将右子树的根节点加入队列
            }else{//如果遇到了分界符号，则分界符号前面的层已经遍历完
                final_list.add(new ArrayList<Integer>());//新建一个list，为下一层的遍历做准备
                queue.offer(null);//下一层已经全部入队列，最后加入分界符号
            }
        }
        return final_list;
    }
}

递归版本：

import java.util.ArrayList;

public class Solution {
    ArrayList<ArrayList<Integer>> Print(TreeNode pRoot) {
        ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
        if(pRoot==null){return final_list;}
        return depth(pRoot, 1, final_list);
    }
    ArrayList<ArrayList<Integer>> depth(TreeNode p, int depth, ArrayList<ArrayList<Integer>> final_list){
        if(depth > final_list.size()){//当前要遍历新层
            final_list.add(new ArrayList<Integer>());//建一个新层对应的list加入final_list
            final_list.get(depth-1).add(p.val);//将当前结点加入对应的list
        }else{//当前层对应的list已经建立，则将当前结点的val加入对应list
            final_list.get(depth-1).add(p.val);
        }
        if(p.left!=null){depth(p.left, depth+1, final_list);}//左不为空则递归左
        if(p.right!=null){depth(p.right, depth+1, final_list);}//右不为空则递归右
        return final_list;
    }
}

结尾

如果您发现我的文章有任何错误，或对我的文章有什么好的建议，请联系我！如果您喜欢我的文章，请点喜欢~*我是蓝白绛，感谢你的阅读！

剑指offer｜51-60题解题思路及代码(Java版)

剑指offer51到60题总览：

51、构建乘积数组

题目描述

解题思路

52、正则表达式匹配

题目描述

解题思路

53、表示数值的字符串

题目描述

解题思路

54、字符流中第一个不重复的字符

题目描述

55、链表中环的入口结点

题目描述

解题思路

56、删除链表中重复的结点

题目描述

解题思路

57、二叉树的下一个结点

题目描述

解题思路

58、对称的二叉树

题目描述

解题思路

59、按之字形打印二叉树

题目描述

解题思路

60、把二叉树打印成多行

题目描述

解题思路

结尾

猜你喜欢

热点阅读