正则表达式匹配

Hard 原题连接：正则表达式匹配

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

示例：

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

解题思路

对于正则表达字符，只有三种可能：正常字符，任意字符 “.”，长度字符 “*”

  1. 如果是正常字符，和字符对应位置比较，不同返回false，相同就s和p各往后推一位

  2. 如果是 “.”，就直接向后推

  3. 如果是 “ * ”，需要考虑是否判断，如果前一位值相同或为 “.” ，代表字符可以匹配正则的 “ * ”，字符后移；

    ​ 如果前一位不同，代表 “ * ”取0，正则字符串后移两位

实现：

  1. 先判空

    1. 字符为空，正则不为空，需要判断：s=”” p=”a*”
    2. 字符为空，正则为空，true
    3. 字符不空，正则为空，false

  2. 判断当前首字符s和p的关系，如果p有后一位，记录（方便查看 “*” 的作用）

  3. 如果p下一位为 “ * ”，符合两者后移就递归，否则就当 “ * ”为0次出现，消除两个p首字段递归

  4. 如果不为 “ * ”，符合消除就两者后移递归，否则返回false

Java代码

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();

        if(m == 0) {
            if(n%2 != 0) return false;
            int i=1;
            while(i<n) {
                if(p.charAt(i) != '*') {
                    return false;        
                }
                i+=2;
            }
            return true;
        }
        if(n == 0) return false;

        char a1 = p.charAt(0), a2 = s.charAt(0), a3 = 'a';
        if(n > 1) a3 = p.charAt(1);

        if(a3 == '*') {
            if(a1 == a2 || a1 == '.')
                return isMatch(s.substring(1), p)
                    || isMatch(s, p.substring(2));
            else
                return isMatch(s, p.substring(2));
        }else {
            if(a1 == a2 || a1 == '.')
                return isMatch(s.substring(1), p.substring(1));
            else
                return false;
        }
    }
}

丑数

medium 原题连接：丑数

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。

示例：

输入: n = 10
输出: 12
解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。

说明:

  1. 1 是丑数。
  2. n 不超过1690。

解题思路

丑数 = min（一个较小的丑数 * 2 或 * 3 或 5），比如 4 = 2 * 2，5 = 1 5，9 = 3 * 3 即拆到最细因子只包含 2，3，5

所以利用已知的丑数推导下一个丑数，比如已知 1，2，3，4，5 下一位丑数 6 = 2*3，可为什么选2 和 3 是问题所在

下一个丑数只可能通过以下三种形式出现

已知丑数a * 2 已知丑数b * 3 已知丑数c * 5

那么就从头开始记录a, b, c

当满足某一次丑数为a * 2，b * 3，c * 5，更新对应的a b c

实现：

  1. 初始丑数为1，a，b，c均为0
  2. 向后递推丑数，每次的丑数等于 （第a个丑数 * 2，第b个丑数 * 3，第c个丑数 * 5）三者中的最小值
  3. 2种是谁的最小值，谁就+1，更新abc，直到推导到第n位

Java代码

class Solution {
    public int nthUglyNumber(int n) {
        int a = 0, b = 0, c = 0;
        int[] dp = new int[n];
        dp[0] = 1;
        for(int i=1; i< n; i++) {
            dp[i] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
            if(dp[i] == dp[a] * 2) a++;
            if(dp[i] == dp[b] * 3) b++;
            if(dp[i] == dp[c] * 5) c++;
        }
        return dp[n-1];
    }
}

n个骰子的点数

medium 原题连接：n个骰子的点数

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。

示例：

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

说明:

  1. 1 <= n <= 11

解题思路

一个骰子六个面，每个面出现概率1/6，两个骰子，共有36种组合，但是只有11种不同结果（2-12）。

以上我们可以得到的信息：

  1. 每多加一个骰子，不同的结果数量就增加5个（最大值+6，最小值+1，差为5）
  2. 多加一个骰子后，原结果第i个应该影响现结果第i+1到i+6 ,先结果第 i 个应该是原结果 i - 6 到 i - 1的累计作用
  3. 所谓累计作用：原本 i 的概率为 a,新加一个骰子后，i 对于 i+1 影响大了 a/6 ,对 i+2也是a/6,直到 i+6，相同的道理，i+1对 i+2到i+7也有相同影响

简而言之，从只有一个骰子向后递推，每增加一个筛子，扩大结果数组范围，让原结果对先数组的六位累计概率

Java代码

class Solution {
    public double[] dicesProbability(int n) {
        double[] ans = new double[6];
        for(int i=0; i<6; i++) ans[i] = 1.0/6;
        for(int i=2; i<=n; i++) {
            double[] mid = new double[5*i + 1];
            for(int j=0; j<ans.length; j++) {
                for(int k=0;k<6; k++) {
                    mid[j+k] += ans[j]/6.0;
                }
            }
            ans = mid;
        }
        return ans;
    }
}