剑指 Offer 19. 正则表达式匹配

题目描述

请实现一个函数用来匹配包含'. '和'*'的正则表达式。模式中的字符'.'表示任意一个字符，而'*'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"ab*ac*a"匹配，但与"aa.a"和"ab*a"均不匹配。
输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
🔗题目链接：https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof

思路

动态规划

代码实现 

class Solution {
    public boolean isMatch(String s, String p) {
        int m = s.length();
        int n = p.length();
        // dp[i][j]表示s前i-1个字符，p前j-1个字符是否匹配
        boolean[][] dp = new boolean[m + 1][n + 1];
        // dp[0][0]：s前0个字符和p的前0个字符默认是空串=匹配
        // 注意：由于多了[0][0]，所以dp[i][j]，定位到的是s[i-1]和p[j-1]的字符
        dp[0][0] = true;
        // 初始化首行：当s为空串，p的偶数位为*才能匹配
        for (int j = 2; j < n + 1; j += 2) {
            dp[0][j] = dp[0][j - 2] && p.charAt(j - 1) == '*';
        }
        // 状态转移
        for (int i = 1; i < m + 1; i++) {
            for (int j = 1; j < n + 1; j++) {
                // 当p[j-1]=*时，有三种情况
                if (p.charAt(j - 1) == '*') {
                    if (dp[i][j - 2]) { // p[j-2]出现0次，i和j指向字符的长度均相同
                        dp[i][j] = true;
                    } else if (dp[i - 1][j] && s.charAt(i - 1) == p.charAt(j - 2)) {
                        // p[j-2]出现1次 且当前i-1和j-2指向的字符相同
                        dp[i][j] = true;
                    } else if (dp[i - 1][j] && p.charAt(j - 2) == '.') {
                        // 最特殊情况：p[j-2]=. p[j-1]=*时，是万能匹配
                        dp[i][j] = true;
                    }
                } else { // 当p[j-1]!=*时，有两种情况
                    if (dp[i - 1][j - 1] && s.charAt(i - 1) == p.charAt(j - 1)) {
                        // 前面元素之前都匹配且当前元素也相容
                        dp[i][j] = true;
                    } else if (dp[i - 1][j - 1] && p.charAt(j - 1) == '.') { 
                        //  前面元素之前都匹配且p的当期元素是.
                        dp[i][j] = true;
                    }
                }
            }
        }
        return dp[m][n];
    }
}

剑指 Offer 49. 丑数

题目描述

我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。1为丑数。 
输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12是前 10 个丑数。
🔗题目链接：https://leetcode-cn.com/problems/chou-shu-lcof/

思路

丑数的递推性质： 丑数只包含因子 2,3,5，因此有 “丑数 = 某较小丑数 × 某因子” （例如：10=5×2）。

代码实现 

class Solution {
    public int nthUglyNumber(int n) {
        if(n <= 6){
            return n;
        }
        int i2 = 0;
        int i3 = 0;
        int i5 = 0;
        int[] dp = new int[n];
        dp[0] = 1; //1为第一个丑数
        for(int i = 1; i < n; i++){
            int next2 = dp[i2] * 2; //分别乘以2，3，5求对应位置的下一个丑数
            int next3 = dp[i3] * 3;
            int next5 = dp[i5] * 5;
            //取最小值存入，从小到大的顺序
            dp[i] = Math.min(next2, Math.min(next3, next5));
            //找到当前丑数对应的下标，将指针移动到下一位，避免重复存入
            if(dp[i] == next2) i2++;
            if(dp[i] == next3) i3++;
            if(dp[i] == next5) i5++;
        }
        return dp[n-1];
    }
}

剑指 Offer 60. n个骰子的点数

题目描述

把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。你需要用一个浮点数数组返回答案，其中第 i 个元素代表这 n 个骰子所能掷出的点数集合中第 i 小的那个的概率。 
输入: 2
输出: [0.02778,0.05556,0.08333,0.11111,0.13889,0.16667,0.13889,0.11111,0.08333,0.05556,0.02778]

思路

暴力解***超时，这里使用动态规划

代码实现 

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