Day29_正则表达与顺序_剑指Offer

正则表达式匹配

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

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

示例：

解题思路

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

1. 如果是正常字符，和字符对应位置比较，不同返回false，相同就s和p各往后推一位
2. 如果是 “.”，就直接向后推
3. 如果是 “ * ”，需要考虑是否判断，如果前一位值相同或为 “.” ，代表字符可以匹配正则的 “ * ”，字符后移；
4. 如果前一位不同，代表 “ * ”取0，正则字符串后移两位

实现：

1. 先判空
2. 字符为空，正则不为空，需要判断：s="" p="a*"
3. 字符为空，正则为空，true
4. 字符不空，正则为空，false
5. 判断当前首字符s和p的关系，如果p有后一位，记录（方便查看 “*” 的作用）
6. 如果p下一位为 “ * ”，符合两者后移就递归，否则就当 “ * ”为0次出现，消除两个p首字段递归
7. 如果不为 “ * ”，符合消除就两者后移递归，否则返回false

Java代码

丑数

medium 原题连接：丑数

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

示例：

说明:

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代码

n个骰子的点数

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

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

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

示例：

说明:

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代码

持续加油，还有学习空间

我的博客：Day29_正则表达式与数字规律_剑指Offer | IT蛋的个人博客 (xcscx.github.io)