剑指offer之51-55题解

r囧r小猫 2021-12-10 00:29 201阅读 0赞

# 剑指offer之51-55题解 #

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

## 目录 ##

1.  构建乘积数组
2.  正则表达式匹配
3.  表示数值的字符串
4.  字符流中第一个不重复的字符
5.  链表中环的入口节点

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

### 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\]。不能使用除法。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]

（二）思路

（三）代码实现

import java.util.ArrayList;
    public class Solution {
        
        public int[] multiply(int[] A) {
        
            int n = A.length;
            int[] B = new int[n];
            for (int i = 0, product = 1; i < n; product *= A[i], i++) {
        
                B[i] = product;
            }
            for (int i = n - 1, product = 1; i >= 0; product *= A[i], i--) {
        
                B[i] *= product;
            }
            return B;
        }
    }

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

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

（一）题目描述

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

（二）思路

（三）代码实现

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

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

（一）题目描述

请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+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) {
        
            if (str == null || str.length == 0)
                return false;
            return new String(str).matches("[+-]?\\d*(\\.\\d+)?([eE][+-]?\\d+)?");
        }
    }

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

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

（一）题目描述

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

（二）思路

（三）代码实现

import java.util.LinkedList;
    import java.util.Queue;
    public class Solution {
        
        private int[] cnts = new int[256];
        private Queue<Character> queue = new LinkedList<>();
    
        public void Insert(char ch) {
        
            cnts[ch]++;
            queue.add(ch);
            while (!queue.isEmpty() && cnts[queue.peek()] > 1)
                queue.poll();
        }
        
        public char FirstAppearingOnce() {
        
            return queue.isEmpty() ? '#' : queue.peek();
        }
    }

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

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

（一）题目描述

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

（二）思路

1.  使用双指针，一个指针fast每次移动两个节点，一个指针slow每次移动一个节点。因为存在环，所以两个指针一定会相遇，这时再把fast指针重头开始移动，一次一个节点，相遇的点就是环入口。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]  
    （三）代码实现

/*
     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 slow = pHead, fast = pHead;
            do {
        
                fast = fast.next.next;
                slow = slow.next;
            } while (fast != slow);
            fast = pHead;
            while (fast != slow) {
        
                fast = fast.next;
                slow = slow.next;
            }
            return slow;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70]: /images/20211209/784a09146bf44f1fbb72e0aff3c0d041.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 1]: /images/20211209/d6649ee214fb41eab6bdf4fb36ac1ca0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MTkxMDY5NA_size_16_color_FFFFFF_t_70 2]: /images/20211209/5d759624031242e9b1da31a8ff7928b0.png