每日一题之《剑指offer》51,52,53,54题

第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];

题目分析：
我想很多人肯定会写出这样的代码：

public class Solution {
    public int[] multiply(int[] A) {
        int[] B = new int[A.length];
        for(int i = 0;i < B.length;i++){
            B[i] = getBOfIndexI(A,i);
        }
        return B;
    }
    
    public static int getBOfIndexI(int[] A,int i){
        int res = 1;
        for(int j = 0;j < A.length;j++){
            if(j == i){
                continue;
            }
            res *= A[j];
        }
        return res;
    }
}

这样的话，这个算法的时间复杂度就变成了O(n ^ 2),是否有更快的算法呢？
《剑指offer》本书中的思路是这样的：

将求解数组B转换为一个矩阵，可以看出B0到Bn-1的值实际上是矩阵每一个行对应的成绩，自然而然地，我们可以将矩阵划分为上倒三角和下三角形
下三角符合的范围为 index 从1到n-1 依次递增
满足：B[i] = B[i - 1] * A[i - 1];
上倒三角复合的范围为，从下到下，index n-2 到 0 依次递减
满足：temp = 1;B[i] = temp * A[i + 1];temp = B[i];
代码如下：

public class Solution {
    public int[] multiply(int[] A) {
        if(A == null){
            return null;
        }
        int[] B = new int[A.length];
        if(A.length > 1){
            B[0] = 1;
            for(int i = 1;i < A.length;i++){
                B[i] = B[i - 1] * A[i - 1];
            }
            int temp = 1;
            for(int i = A.length - 2;i >=0;i--){
                temp *= A[i + 1];
                B[i] *= temp;
            }
        }
        return B;
    }
}

只要把矩阵画出来，那么代码逻辑其实并不复杂。

第52题：正则表达式匹配

难易度：⭐⭐⭐⭐

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

题目解析：
本题是一道我觉得难度比较大的题目，重点是要看pattern的下一个字符是否为' * '
当pattern中的第二个字符是' * '的时候
如果pattern[patternIndex] == str[strIndex] 或者是pattern[patternIndex] == ' . '时
有如下几种情况：

1. pattern向后移动两个字符
2. 字符串向后移动一个字符，pattern向后移动2个字符
3. 字符串向后移动一个字符，pattern不动

否则 pattern向后移动两个字符，有可能完成匹配

当pattern中的第二个字符不是 ' * '时，只有满足pattern[patternIndex] == str[strIndex] 或者是pattern[patternIndex] == ' . '时，字符串和pattern同时向后移动1个字符可能完成匹配的情况

代码如下：

public class Solution {
    public boolean match(char[] str, char[] pattern){
        if(str == null || pattern == null){
            return false;
        }
        return process(str,pattern,0,0);
    }
    public static boolean process(char[] str,char[] pattern,int strIndex,int patternIndex){
        if(strIndex == str.length && patternIndex == pattern.length){
            return true;
        }
        if(strIndex != str.length && patternIndex == pattern.length){
            return false;
        }
        // 模式的下一个字符是'*'
        if(patternIndex + 1 < pattern.length && pattern[patternIndex + 1] == '*'){
            // 当前的pattern和str的字符匹配时，即：pattern[patternIndex] == str[strIndex] || pattern[patternIndex] == '.'
            if(strIndex < str.length && pattern[patternIndex] == str[strIndex] || strIndex < str.length && pattern[patternIndex] == '.'){
                return process(str,pattern,strIndex + 1,patternIndex)
                    || process(str,pattern,strIndex,patternIndex + 2)
                    || process(str,pattern,strIndex + 1,patternIndex + 2);
            }else{
                return process(str,pattern,strIndex,patternIndex + 2);
            }
        }
        if(strIndex < str.length && pattern[patternIndex] == str[strIndex] || strIndex < str.length && pattern[patternIndex] == '.' ){
            return process(str,pattern,strIndex + 1,patternIndex + 1);
        }
        return false;
    }
}

第53题：表示数值的字符串

难易度：⭐⭐⭐

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

解析：
又是一道憋了半天没想出来的题目
看了原书的解析，可以将数字的格式用如下的形式表示

A[.[B]][e|EC]或者.B[e|EC]来表示

其中A和C都是整数可以带有正负号，而B则是一个无符号的整数
代码如下：

public class Solution {
   
    private int index = 0;
    
    public boolean isNumeric(char[] str) {
        boolean res = scanInteger(str);
        if(index < str.length && str[index] == '.'){
            index++;
            res = scanUnsignedInteger(str) || res;
        }
        if(index < str.length && (str[index] == 'e' || str[index] == 'E')){
            index++;
            res = res && scanInteger(str);
        }
        return res && index == str.length;
    }
    
    private boolean scanInteger(char[] str){
        if(index < str.length && (str[index] == '+' || str[index] == '-')){
            index++;
        }
        return scanUnsignedInteger(str);
    }
    
    private boolean scanUnsignedInteger(char[] str){
        int before = index;
        while(index < str.length && str[index] <= '9' && str[index] >= '0'){
            index++;
        }
        return index > before;
    }
}

值得一提的是第一次我提交的代码中

或运算的顺序写反了，这个是一个很容易踩到坑的地方，因为断路特性，所以应该将scanUnsignedInteger(str)写到前面，说到底还是对代码的理解程度不够，二刷的时候一定好好把这道题写上个几百遍(吹牛逼的)

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

难易度：⭐

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

本题的思路应该很快就能想到使用哈希表这种数据结构
代码如下：

import java.util.HashMap;
import java.util.Map.Entry;
public class Solution {
    private int index = 0;
    private HashMap<Character,Integer> map = new HashMap<>();
    //Insert one char from stringstream
    public void Insert(char ch)
    {
        if(map.containsKey(ch)){
            map.put(ch,-1);
        }else{
            map.put(ch,index++);
        }
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce(){   
        char res = '#';
        int minIndex = Integer.MAX_VALUE;
        for(Entry<Character,Integer> entry : map.entrySet()){
            if(entry.getValue() != -1 && entry.getValue() < minIndex){
                minIndex = entry.getValue();
                res = entry.getKey();
                
            }
        }
        return res;
    }
}