day29 题目：剑指 Offer 19. 正则表达式匹配、剑指 Offer 49. 丑数、剑指 Offer 60. n 个骰子的点数

知识点：字符串、数学、动态规划，难度为困难、中等、中等

学习计划链接：「剑指 Offer」 - 学习计划

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

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

示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。

示例 2:

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

示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。

示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。

示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

• s 可能为空，且只包含从 a-z 的小写字母。
• p 可能为空，且只包含从 a-z 的小写字母以及字符 . 和 * ，无连续的 '*' 。

注意：本题与主站 10 题相同：https://leetcode-cn.com/problems/regular-expression-matching/

# 思路及代码

不愧是困难题，想不出来^_

看完题解，wow 还有这种思路

• dp[i][j] 表示 s 中前 i 个字符是否匹配 p 中前 j 个字符
• dp[0][0] 是可行的，置为 true ，其他初始置为 false

遍历时

• 若 p 中 第 j 个字符不是 * 或 . ，则必须在 s 中匹配一个相同的字母，有 dp[i][j] = s[i] == p[j] ? dp[i-1][j-1]: false
• 若 p 中 第 j 个字符为 . 一定成功匹配 dp[i][j] = dp[i-1][j-1]
• 若为 * 则可以
  • 不匹配字符，将该组合扔掉，不再进行匹配 dp[i][j] |= dp[i][j-2]
  • 匹配 s 末尾的一个字符，将该字符扔掉，而该组合还可以继续进行匹配 dp[i][j] = dp[i-1][j] | dp[i][j-2]

/**

 * @param {string} s

 * @param {string} p

 * @return {boolean}

 */

var isMatch = function(s, p) {

    let dp = new Array(s.length+1).fill(0).map(() => new Array(p.length+1).fill(false))

    dp[0][0] = true

    for(let i = 0; i <= s.length; ++i) {

        for(let j = 1; j <= p.length; ++j) {

            let c2 = p[j-1]

            if(c2 == '*') {

                dp[i][j] |= dp[i][j-2]  // 不使用 *

                c2 = p[j-2]

                if(i != 0 && (c2 == '.' || s[i-1] == c2))

                    dp[i][j] |= dp[i-1][j]

            } else if(i != 0 && (c2 == '.' || s[i-1] == c2)) {

                    dp[i][j] |= dp[i-1][j-1]

            }

        }

    }

    return dp[s.length][p.length]

};

# 剑指 Offer 49. 丑数

我们把只包含质因子 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。

注意：本题与主站 264 题相同：https://leetcode-cn.com/problems/ugly-number-ii/

# 思路及代码

设 m1、m2、m3 表示 ×2、×3、×5 的结果，比较其指向的值，将最小的放入最终的合并数组中，并将相应指针向后移动一个元素。

/**

 * @param {number} n

 * @return {number}

 */

var nthUglyNumber = function(n) {

    let dp = new Array(n)

    dp[0] = 1

    let i2 = 0, i3 = 0, i5 = 0

    for (let i = 1; i < n; i++) {

        let m2 = dp[i2] * 2, m3 = dp[i3] * 3, m5 = dp[i5] * 5

        let m = Math.min(Math.min(m2, m3), m5)

        if (m === m2) i2++

        if (m === m3) i3++

        if (m === m5) i5++

        dp[i] = m

    }

    return dp[n-1]

};

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

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

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

示例 1:

输入: 1
输出: [0.16667,0.16667,0.16667,0.16667,0.16667,0.16667]

示例 2:

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

限制：

1 <= n <= 11

# 思路及代码

dp [i][j] 表示 i 个骰子时，点数总和取值的概率

• 如 1 个骰子的时候总和可能为 [1, 2, 3, 4, 5, 6]
• 2 个骰子时，为 [2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
• i 个骰子时，总和个数为 6*i-(i-1) 化简为 5*i+1
• 由于新增骰子的点数只可能为 1 至 6 ，因此概率 dp[i-1][x] 仅与 dp[i][x+1] , dp[i][x+2] , ... , dp[i][x+6] 相关。因此，遍历 dp[i-1] 中各点数和的概率贡献值，并将贡献值相加至 dp[i] 中所有相关项，即可完成的递推。。
• 也就是说，增加骰子的个数到 i 个时， i-1 个骰子的点数 j 会对拥有 i 个骰子时的点数 j+k 产生影响
• 由于每次都只跟 i-1 有关，故可优化空间

/**

 * @param {number} n

 * @return {number[]}

 */

var dicesProbability = function(n) {

    let dp = new Array(6).fill(1/6)

    for(let i = 2; i <= n; ++i) {   //i 个骰子

        let next = new Array(5*i+1).fill(0) // i*6-(i-1)

        for(let j = 0;  j < dp.length; ++j)

            for(let k = 0; k < 6; ++k)

                next[j+k] += dp[j]*1/6

        dp = next

    }

    return dp

};