LeetCode—＜动态规划专项＞剑指 Offer 19、49、60

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

题目描述：
[19]
请实现一个函数用来匹配包含’. ‘和’‘的正则表达式。模式中的字符’.‘表示任意一个字符，而’'表示它前面的字符可以出现任意次（含0次）。在本题中，匹配是指字符串的所有字符匹配整个模式。例如，字符串"aaa"与模式"a.a"和"abaca"匹配，但与"aa.a"和"ab*a"均不匹配。
[49]
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
[60]
把n个骰子扔在地上，所有骰子朝上一面的点数之和为s。输入n，打印出s的所有可能的值出现的概率。

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

考察重点：
第19题二维状态数组，其中dp[i][j]=true表示s[0, i)与p[0, j)模式匹配
第49题三个指针分别指向2,3,5对应的位置，每次放入积最小的数
第60题令f(n,s)为二维矩阵，表示为n个骰子点数为s的情况；有f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)

第19题

func isMatch(s string, p string) bool {
	sLen, pLen := len(s), len(p)
	var dp [][]bool
	for x := 0; x <= sLen; x++ {		//建立一个存储状态的数组
		ar := make([]bool, pLen+1)		//其中dp[i][j]=true表示s[0, i)与p[0, j)模式匹配
		dp = append(dp, ar)
	}
	dp[0][0] = true //边界条件, 如果从0开始则边界为-1，因此我们将结果存放在1——(Len+1)，所以要注意dp比s和p多一位
	for i := 0; i <= sLen; i++ {
		for j := 1; j <= pLen; j++ {
			if p[j-1] == '*' {		//dp[i][j-2]表示'*'代表的次数为0，后面表示'*'代表的次数为1
				dp[i][j] = dp[i][j-2] || (i > 0 && (s[i-1] == p[j-2] || p[j-2] == '.') && dp[i-1][j])
			} else {
				dp[i][j] = i > 0 && (s[i-1] == p[j-1] || p[j-1] == '.') && dp[i-1][j-1]
			}
		}
	}
	return dp[sLen][pLen]
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第49题

func nthUglyNumber(n int) int {
    res := make([]int, n)
    res[0] = 1
    p2, p3, p5 := 0, 0, 0
    for i := 1;i < n;i ++{
        res[i] = min(res[p2] * 2, res[p3] * 3, res[p5] * 5)
        if res[i] == res[p2] * 2{   //不可以使用if else，当多个最小值相等时，应该同时后移以保障去重
            p2 ++
        }
        if res[i] == res[p3] * 3{
            p3 ++
        }
        if res[i] == res[p5] * 5{
            p5 ++
        }
    }
    return res[n-1]
}

func min(a, b, c int)int{
    if(a < b){
        if a < c{
            return a
        }
        return c
    }
    if b < c{
        return b
    }
    return c
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

第60题

// 令f(n,s)为二维矩阵，表示为n个骰子点数为s的情况
func dicesProbability(n int) []float64 {
	dp := make([][]int32, 0)        //建立一个n+1行,n*6+1列的数组。其中+1是方便处理边界。
    for i := 0;i < n+1;i ++{
        tt := make([]int32, n*6+1)
        dp = append(dp, tt)
    }
	res := make([]float64, 5*n+1)   //保存n个骰子时的结果
	allSituation := math.Pow(6, float64(n))     // 数组中保存的出现的次数，所以计算总次数以计算概率
	for j := 1; j <= 6; j++ {
		dp[1][j] = 1
	}
	for i := 1; i <= n; i++ {       // i个骰子
		for j := i; j <= n*6; j++ {     //和为j
			for k := 1; k <= 6; k++ {      // f(n,s)=f(n-1,s-1)+f(n-1,s-2)+f(n-1,s-3)+f(n-1,s-4)+f(n-1,s-5)+f(n-1,s-6)
				if j >= k {
					dp[i][j] += dp[i-1][j-k]
				}
				if i == n {
					res[j-i] = float64(dp[i][j]) / allSituation
				}
			}
		}
	}
	return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26