【LeetCode】（动态规划ி）变态系列集锦

浅浅的花香味﹌ 2023-01-11 12:00 185阅读 0赞

## 【LeetCode】（动态规划ி）变态系列集锦 ##

### 文章目录 ###

*   *  【LeetCode】（动态规划ி）变态系列集锦
     *   *  n个骰子的点数★★
         *  满足三条件之一需改变的最少字符数★★
         *  秋叶收藏集★★
         *  正则表达式匹配★★★

--------------------

### n个骰子的点数★★ ###

[LeetCode 剑指 Offer 60. n个骰子的点数][LeetCode _ Offer 60. n]

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

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

【**示例**】

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

【**解题思路**】

若有`n`个骰子，会形成 `5 * n + 1`种投掷结果。每个骰子的每种结果概率都为 `1 / 6`。

很明显1个骰子的6中结果\[1 - 6\]概率为\[1 / 6, 1 / 6, 1 / 6, 1 / 6, 1 / 6, 1 / 6,\]，

`f(i, j)`表示第`i`个骰子的点数为`j`

在此基础上再加一枚骰子，若结果和为2，此时为两个1，概率为f(1, 1) \* f(2, 1)

若结果和为3，此时为1，2或 2， 1，概率为 f(1, 1) \* f(2, 2) + f(1, 2) + f(2, 1)

…

用`pre[]`表示前几个骰子的结果概率，`cur[]`表示当前加1个骰子的结果概率，`a`表示点数

则每一次迭代为`cur[j + a] = pre[j] * (1 / 6)`

class Solution {
        
        public double[] twoSum(int n) {
        
            double []pre = {
        1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d};
            for(int i = 2; i <= n; i++){
        
                double[] cur = new double[5 * i + 1];
                for(int j = 0; j < pre.length; j++){
        
                    for(int a = 0; a < 6; a++){
        
                        cur[j + a] += pre[j] * (1 / 6d);
                    }
                }
                pre = cur;
            }
            return pre;
        }
    }

--------------------

### 满足三条件之一需改变的最少字符数★★ ###

[LeetCode 1737. 满足三条件之一需改变的最少字符数][LeetCode 1737.]

【**题目**】给你两个字符串 a 和 b ，二者均由小写字母组成。一步操作中，你可以将 a 或 b 中的 任一字符 改变为 任一小写字母 。

操作的最终目标是满足下列三个条件 之一 ：

*  a 中的 每个字母 在字母表中 严格小于 b 中的 每个字母 。
 *  b 中的 每个字母 在字母表中 严格小于 a 中的 每个字母 。
 *  a 和 b 都 由 同一个 字母组成。

返回达成目标所需的 最少 操作数。

【**示例**】

输入：a = "aba", b = "caa"
    输出：2
    解释：满足每个条件的最佳方案分别是：
    1) 将 b 变为 "ccc"，2 次操作，满足 a 中的每个字母都小于 b 中的每个字母；
    2) 将 a 变为 "bbb" 并将 b 变为 "aaa"，3 次操作，满足 b 中的每个字母都小于 a 中的每个字母；
    3) 将 a 变为 "aaa" 并将 b 变为 "aaa"，2 次操作，满足 a 和 b 由同一个字母组成。
    最佳的方案只需要 2 次操作（满足条件 1 或者条件 3）。

【**解题思路**】

我们先来看看变为这三种情况之一需要怎样操作，先进行字符串字符统计，下面简写

*  若`a < b`，若遍历到26个字母中第`i`个字母，此时需要将a中大于等于第`i`个字母的所有字符变为比它小的，将b中小于第`i`个字母的所有字符变为比它大的，取`（2 - 26）`中操作次数最小的
 *  若`a > b`，反之，取`（1 - 25）`中操作次数最小的
 *  若 `a = b`，需要将不是第i个字母的字符均变为它，取`（1 - 26）`中操作次数最小的

然后在上述三种情况中取操作次数最小的。为了方便计算，我们使用前缀和

class Solution {
        
        public int minCharacters(String a, String b) {
        
            //频次统计
            int[] counta = new int[26];
            int[] countb = new int[26];
            for(char c : a.toCharArray()) counta[c - 'a']++;
            for(char c : b.toCharArray()) countb[c - 'a']++;
            
            //前缀和
            int[] prea = new int[27];
            int[] preb = new int[27];
            for(int i = 1; i < 27; i++) {
        
                prea[i] = prea[i - 1] + counta[i - 1];
                preb[i] = preb[i - 1] + countb[i - 1];
            }
            
            //动态规划计算三种情况
            int res = 1000000;
            for(int i = 0; i < 26; i++) {
        
                res = Math.min(res, a.length() + b.length() - counta[i] - countb[i]);
                if(i > 0)  res = Math.min(res, a.length() - prea[i] + preb[i]);
                if(i < 26) res = Math.min(res, b.length() - preb[i] + prea[i]);
            }
            
            return res;
        }
    }

--------------------

### 秋叶收藏集★★ ###

[LeetCode LCP 19. 秋叶收藏集][LeetCode LCP 19.]

【**题目**】小扣出去秋游，途中收集了一些红叶和黄叶，他利用这些叶子初步整理了一份秋叶收藏集 `leaves`， 字符串 `leaves` 仅包含小写字符 `r` 和 `y`， 其中字符 `r` 表示一片红叶，字符 `y` 表示一片黄叶。  
出于美观整齐的考虑，小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等，但均需大于等于 1。每次调整操作，小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

【**示例**】

输入：leaves = "rrryyyrryyyrr"
    输出：2
    解释：调整两次，将中间的两片红叶替换成黄叶，得到 "rrryyyyyyyyrr"

【**解题思路**】

共有四种可能的状态，用`last[]`数组来保存

*  `last[0]`：表示还没开始，现在整个序列为空
 *  `last[1]`：表示现在的序列为`rrrr...r`
 *  `last[2]`：表示现在的序列为`rr...ryyyy...y`
 *  `last[3]`：表示现在的序列为`rr...ryyyy...yrrrrr...r`

现在来看看状态转换：

*  `last[0]`: `r` => last\[1\]，`y` => 无效状态
 *  `last[1]`: `r` => last\[1\]，`y` => last\[2\]
 *  `last[2]`: `r` => last\[2\], `y` => 无效状态

class Solution {
        
        public int cost(char a, char b) {
        
            return a == b ? 0 : 1;
        }
    
        public int minimumOperations(String leaves) {
        
            int[] last = new int[4];
            int[] next = new int[4];
            int inf = (int)1e8;
            Arrays.fill(last, inf);
            last[0] = 0;
            for(char c : leaves.toCharArray()) {
        
                Arrays.fill(next, inf);
                next[1] = Math.min(last[1] + cost('r', c), last[0] + cost('r', c));
                next[2] = Math.min(last[2] + cost('y', c), last[1] + cost('y', c));
                next[3] = Math.min(last[3] + cost('r', c), last[2] + cost('r', c));
                for(int i = 0; i < 4; i++) last[i] = next[i];
            }
            return last[3];
        }
    }

参考B站DaIT讲解

--------------------

### 正则表达式匹配★★★ ###

[LeetCode 剑指 Offer 19. 正则表达式匹配][LeetCode _ Offer 19.]

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

**提示**：

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

【**示例**】

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

【**解题思路**】

[参考Jerry题解][Jerry]

class Solution {
        
        public boolean isMatch(String s, String p) {
        
            int m = s.length(), n = p.length();
            boolean[][] f = new boolean[m + 1][n + 1];
            for(int i = 0; i <= m; i++) {
        
                for(int j = 0; j <= n; j++) {
        
                    if(j == 0) {
        
                        f[i][j] = i == 0;
                    }else {
        
                        if(p.charAt(j - 1) != '*') {
        
                            if(i > 0 && (s.charAt(i - 1) == p.charAt(j - 1) || p.charAt(j - 1) == '.')) {
        
                                f[i][j] = f[i - 1][j - 1];
                            }
                        }else {
        
                            if(j >= 2) {
        
                                f[i][j] |= f[i][j - 2];
                            }
                            if(i >= 1 && j >= 2 && (s.charAt(i - 1) == p.charAt(j - 2) || p.charAt(j - 2) == '.')) {
        
                                f[i][j] |= f[i - 1][j];
                            }
                        }
                    }
                }
            }
            return f[m][n];
        }
    }

--------------------

本篇持续更新中……

[LeetCode _ Offer 60. n]: https://leetcode-cn.com/problems/nge-tou-zi-de-dian-shu-lcof/
[LeetCode 1737.]: https://leetcode-cn.com/problems/change-minimum-characters-to-satisfy-one-of-three-conditions/
[LeetCode LCP 19.]: https://leetcode-cn.com/problems/UlBDOe/
[LeetCode _ Offer 19.]: https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/
[Jerry]: https://leetcode-cn.com/problems/zheng-ze-biao-da-shi-pi-pei-lcof/solution/zhu-xing-xiang-xi-jiang-jie-you-qian-ru-shen-by-je/