剑指Offer（java答案）（51-60）

深藏阁楼爱情的钟 2022-10-01 06:59 149阅读 0赞

## **51、数组中重复的数** ##

> 题目描述 在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组\{2,3,1,0,2,5,3\}，那么对应的输出是重复的数字2或者3。

思路1:排序，时间复杂度O(NlogN)

思路2:Hash表,时间和空间复杂度都是O(N)

import java.util.HashMap;
    import java.util.Iterator;
    import java.util.Map.Entry;
    public class Solution {
    
        boolean duplicate(int numbers[],int length,int [] duplication) {
            HashMap<Integer, Integer> countMap = new HashMap<Integer, Integer>();
            if(length < 2||numbers==null){
                return false;
            }
            int j = 1;
            for(int i = 0;i < length;i++){
                if(countMap.get(numbers[i]) == null){
                    j = 1;
                    countMap.put(numbers[i], j);
                }else{
                    j = countMap.get(numbers[i]);
                    j++;
                    countMap.put(numbers[i], j);
                }
            }
            Iterator iter = countMap.entrySet().iterator();
            while(iter.hasNext()){
                Entry<Integer, Integer> entry = (Entry<Integer, Integer>) iter.next();
                Integer key = entry.getKey();
                Integer val = countMap.get(key);
                if(val > 1){
                    duplication[0] = key;
                    return true;
                }
            }
            return false;
        }
    }
    
    复制代码

思路3:用Set集合,因为Set集合不允许有重复的,时间和空间复杂度都是O(N)

import java.util.Set;
    import java.util.HashSet;
    public class Solution {
    	boolean duplicate(int numbers[], int length, int[] duplication) {
            if(length < 2||numbers==null){
                return false;
            }
            
    		Set<Integer> ss = new HashSet<Integer>();
    		for (int i = 0; i < numbers.length; i++) {
    			if (ss.contains(numbers[i])) {
    				duplication[0] = numbers[i];
    				return true;
    			} else {
    				ss.add(numbers[i]);
    			}
    		}
    		return false;
    	}
    }
    复制代码

**思路4better**:时间复杂度O(N),所有操作都是在输入数组上进行,所以不需要分配额外空间,空间复杂度为O(1)

\[图片上传失败...(image-c952f5-1558756468475)\]

public class Solution {
    
        public boolean duplicate(int numbers[],int length,int [] duplication) {
            if(numbers==null||length<0)return false;
             
            for(int i = 0;i < length; i++){
                if(numbers[i]<0||numbers[i]>length-1)
                    return false;
            }
             
            for(int i = 0;i< length;i++){
                while(numbers[i]!=i){
                    if(numbers[i]==numbers[numbers[i]]){
                        duplication[0] = numbers[i];
                        return true;
                    }
                    else{
                        //没有找到，然后则交换，使该数到正确的位置去
                        swap(numbers,i,numbers[i]);
                    }
                }
                
            }
             return false;
        }
         
        //交换二数
        private void swap(int[]a, int i, int j){
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
        }
    }
    复制代码

## **52、构建乘积数组** ##

> 题目描述 给定一个数组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\]。不能使用除法。

思路:1.计算前i - 1个元素的乘积，及后N - i个元素的乘积分别保存在两个数组中

\[图片上传失败...(image-d5e569-1558756468476)\]

import java.util.ArrayList;
    public class Solution {
       public int[] multiply(int[] A) {
            int len = A.length;
            int forword[] = new int[len];
            int backword[] = new int[len];
            int B[] = new int[len];
            forword[0] = 1;
            backword[0] = 1;
            for(int i = 1;i < len; i++){
                forword[i] = A[i - 1]*forword[i-1];
                backword[i] = A[len - i]*backword[i - 1];
            }
            for(int i = 0; i < len; i++){
                B[i] = forword[i] * backword[len - i -1];
            }
            return B;
        }
    }
    复制代码

## **53、正则表达式匹配** ##

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

public class Solution {
        public boolean match(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;
            }
            //str未到尾，pattern到尾，匹配失败
            if (strIndex != str.length && patternIndex == pattern.length) {
                return false;
            }
            //str到尾，pattern未到尾(不一定匹配失败，因为a*可以匹配0个字符)
            if (strIndex == str.length && patternIndex != pattern.length) {
                //只有pattern剩下的部分类似a*b*c*的形式，才匹配成功
                if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
                    return matchCore(str, strIndex, pattern, patternIndex + 2);
                }
                return false;
            }
    
            //str未到尾，pattern未到尾
            if (patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*') {
                if (pattern[patternIndex] == str[strIndex] || (pattern[patternIndex] == '.' && strIndex != str.length)) {
                //三种可能：
                    //1、模式串当前字符出现0次，即*表示当前字符出现0次，则str=str,pattern=pattern+2;
                    //2、模式串当前字符出现1次，即*表示当前字符出现1次，则str=str+1,pattern=pattern+2;
                    //3、模式串当前字符出现2次或2次以上，即*表示当前字符出现2次或以上，则str=str+1,pattern=pattern;
                    return matchCore(str, strIndex, pattern, patternIndex + 2)//*匹配0个，跳过
                            || matchCore(str, strIndex + 1, pattern, patternIndex + 2)//*匹配1个，跳过
                            || matchCore(str, strIndex + 1, pattern, patternIndex);//*匹配1个，再匹配str中的下一个
                } else {
                    //直接跳过*（*匹配到0个）
                     //如果当前字符不匹配，则只能让*表示当前字符出现0次，则str=str，pattern=pattern+2;
                    return matchCore(str, strIndex, pattern, patternIndex + 2);
                }
            }
    
          //模式串下一字符不为*
            if (pattern[patternIndex] == str[strIndex] || (pattern[patternIndex] == '.' && strIndex != str.length)) {
                return matchCore(str, strIndex + 1, pattern, patternIndex + 1);
            }
    
            return false;
        }
    }
    复制代码

## **54、表示数值的字符串** ##

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

思路1：正则表达式

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

思路2：

public class Solution {
    	boolean isNumeric(char[] s) {
    		if (s.length == 0)
    			return false;
    		if ((s.length == 1) && (s[0] < '0' || s[0] > '9'))
    			return false;
    		if (s[0] == '+' || s[0] == '-') {
    			if (s.length == 2 && (s[1] == '.'))
    				return false;
    		} else if ((s[0] < '0' || s[0] > '9') && s[0] != '.')
    			return false;// 首位既不是符号也不是数字还不是小数点，当然是false
    		int i = 1;
    		while ((i < s.length) && (s[i] >= '0' && s[i] <= '9'))
    			i++;
    		if (i < s.length && s[i] == '.') {
    			i++;
    			// if(i>=s.length) return false;
    			while ((i < s.length) && (s[i] >= '0' && s[i] <= '9'))
    				i++;
    		}
    		if (i < s.length && (s[i] == 'e' || s[i] == 'E')) {
    			i++;
    			if ((i < s.length) && (s[i] == '+' || s[i] == '-')) {
    				i++;
    				if (i < s.length)
    					while ((i < s.length) && (s[i] >= '0' && s[i] <= '9'))
    						i++;
    				else
    					return false;
    			} else if (i < s.length) {
    				while ((i < s.length) && (s[i] >= '0' && s[i] <= '9'))
    					i++;
    			} else
    				return false;
    		}
    		if (i < s.length)
    			return false;
    		return true;
    	}
    }
    复制代码

## **55、字符流中第一个不重复的字符** ##

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

import java.util.*;
    public class Solution {
        HashMap<Character, Integer> map=new HashMap();
        ArrayList<Character> list=new ArrayList<Character>();
        //Insert one char from stringstream
        public void Insert(char ch)
        {
            if(map.containsKey(ch)){
                map.put(ch,map.get(ch)+1);
            }else{
                map.put(ch,1);
            }
             
            list.add(ch);
        }
         
        //return the first appearence once char in current stringstream
        public char FirstAppearingOnce()
        {   char c='#';
            for(char key : list){
                if(map.get(key)==1){
                    c=key;
                    break;
                }
            }
             
            return c;
        }
    }
    复制代码

## **56、链表中环的入口结点** ##

> 题目描述 一个链表中包含环，请找出该链表的环的入口结点。

/*
     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)
    			return null;
    		// 先判断是否有环
    		ListNode n1 = pHead;// 走一步
    		ListNode n2 = pHead;// 走两步
    		ListNode n = null;// 记录n1,n2碰面的点
    		while (n2 != null && n2.next != null) {
    			n2 = n2.next.next;
    			n1 = n1.next;
    			if (n2 == n1) {
    				n = n2;// 记录碰头节点
    				break;
    			}
    		}
    		// 求出环中节点数量
    		int num = 0;
    		ListNode temp = n;// n的镜像
    		do {
    			temp = temp.next;
    			num++;
    		} while (temp != n);
    
    		ListNode node1 = pHead;
    		ListNode node2 = pHead;
    		// node1先走num步，然后node1,node2同时走，碰头的地方即入口节点
    		for (int i = 0; i < num; i++) {
    			node1 = node1.next;
    		}
    		int num1 = 0;
    
    		while (node1 != node2) {
    			node1 = node1.next;
    			node2 = node2.next;
    			num1++;
    		}
    		return node1;
    	}
    }
    复制代码

## **57、删除链表中重复的结点** ##

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

思路：重点是第一个也可能是重复的点，因此新建一个preNode节点保存前一个节点

/**
     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)return null;
             
            ListNode preNode = null;
            ListNode node = pHead;
            while(node!=null){
                ListNode nextNode = node.next;
                boolean needDelete = false;//判断相邻两个点是否相等
                if(nextNode!=null&&nextNode.val==node.val){
                    needDelete = true;
                }
                if(!needDelete){
                    preNode = node;
                    node = node.next;
                }else{
                    int value = node.val;
                    ListNode toBeDel = node;
                    while(toBeDel!=null&&toBeDel.val == value){
                        nextNode = toBeDel.next;
                        toBeDel = nextNode;
                        //此处不能少，找到第一个pHead，以后的preNode就不为null了
                        if(preNode==null)
                            pHead = nextNode;
                        else
                            preNode.next = nextNode;
                        node = nextNode;
                    }
                }
            }
             
            return pHead;
        }
    }
    
    复制代码

## **58、二叉树的下一个结点** ##

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

思路：画图分析，考虑三种情况 \[图片上传失败...(image-af1795-1558756468476)\]

/**
    public class TreeLinkNode {
        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode parent= null;
    
        TreeLinkNode(int val) {
            this.val = val;
        }
    }
    */
    public class Solution {
        TreeLinkNode GetNext(TreeLinkNode node)
        {
            if(node==null) return null;
            if(node.right!=null){    //如果有右子树，则找右子树的最左节点
                node = node.right;
                while(node.left!=null) node = node.left;
                return node;
            }
            while(node.parent!=null){ //没右子树，则找第一个当前节点是父节点左孩子的节点
                if(node.parent.left==node) return node.parent;
                node = node.parent;
            }
            return null;   //退到了根节点仍没找到，则返回null
        }
    }
    复制代码

## **59、对称的二叉树** ##

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

/**
    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) {    
            return isSymmetrical(pRoot,pRoot);
        }
       
        //定义两个遍历，一个前序遍历，一个是和前序遍历相反的，先右后左的遍历
        boolean isSymmetrical(TreeNode pRoot1, TreeNode pRoot2) {
            if (pRoot1 == null && pRoot2 == null)
                return true;
             
            if (pRoot1 == null || pRoot2 == null)
                return false;
            
            if (pRoot1.val != pRoot2.val)
                return false;
                  
            return isSymmetrical(pRoot1.left,pRoot2.right) && isSymmetrical(pRoot1.right, pRoot2.left);
        }
    }
    复制代码

## **60、把二叉树打印成多行** ##

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

import java.util.*;
    
    /**
    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>> result = new ArrayList<ArrayList<Integer>>();
            if(pRoot == null){
                return result;
            }
            //使用队列，先进先出
            Queue<TreeNode> layer = new LinkedList<TreeNode>();
            ArrayList<Integer> layerList = new ArrayList<Integer>();
            layer.add(pRoot);
            int start = 0, end = 1;//start记录本层打印了多少个，end记录下一层要打印多少个
            while(!layer.isEmpty()){
                TreeNode cur = layer.remove();
                layerList.add(cur.val);//添加本行打印的List里
                start++;
                //每打印一个节点，就把此节点的下一层的左右节点加入队列，并记录下一层要打印的个数
                if(cur.left!=null){
                    layer.add(cur.left);           
                }
                if(cur.right!=null){
                    layer.add(cur.right);
                }
                //本层打印完毕
                if(start == end){
                    end = layer.size();
                    start = 0;
                    result.add(layerList);
                    layerList = new ArrayList<Integer>();
                }
            }
            return result;
        }
    }
    复制代码

声明：此文章为本人原创，如有转载，请注明出处

如果您觉得有用，欢迎关注我的公众号，我会不定期发布自己的学习笔记、AI资料、以及感悟，欢迎留言，与大家一起探索AI之路。

转载于:https://juejin.im/post/5ce8c1f7f265da1bad56e0b0