「剑指Offer」Day29：动态规划（困难）
剑指 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
思路
动态规划
🔗参考题解：（LeetCode K神）https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/jian-zhi-offer-19-zheng-ze-biao-da-shi-pi-pei-dong/
代码实现
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]
思路
暴力解***超时，这里使用动态规划
🔗参考题解：（LeetCode K神）https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/solution/jian-zhi-offer-60-n-ge-tou-zi-de-dian-sh-z36d/
代码实现
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;
}
}
