Leetcode日记—LCP 19.秋叶收藏集

发布于 2020-10-01  109 次阅读


碎碎念:今儿国庆中秋双节,还在刷leetcode的都是真爱了 :)好想吃海甘鲳还有超新鲜的🦑。对了,今儿早上吃了海南月饼,海南月饼,永远滴神!

题目如下:

小扣出去秋游,途中收集了一些红叶和黄叶,他利用这些叶子初步整理了一份秋叶收藏集 leaves, 字符串 leaves 仅包含小写字符 r 和 y, 其中字符 r 表示一片红叶,字符 y 表示一片黄叶。


出于美观整齐的考虑,小扣想要将收藏集中树叶的排列调整成「红、黄、红」三部分。每部分树叶数量可以不相等,但均需大于等于 1。每次调整操作,小扣可以将一片红叶替换成黄叶或者将一片黄叶替换成红叶。请问小扣最少需要多少次调整操作才能将秋叶收藏集调整完毕。

示例 1:

输入:leaves = "rrryyyrryyyrr"

输出:2

解释:调整两次,将中间的两片红叶替换成黄叶,得到 "rrryyyyyyyyrr"

示例 2:

输入:leaves = "ryr"

输出:0

解释:已符合要求,不需要额外操作

提示:

  • 3 <= leaves.length <= 10^5
  • leaves 中只包含字符 'r' 和字符 'y'

补充说明:这里的替换是直接把某个 r 换成 y,而不是和现有的 y 交换(即不受限于现有的 r 和 y 的数量。

补充知识—动态规划(Dynamic Programming):

动态规划和高中的数列题有一些相似,他的本质思想就是1.通过数学推导得到一个通项公式;2.存下来并利用之前计算的结果;3.从小的,已知的往大的数一步一步地计算。比方说你知道ƒ(n)= ƒ(n-1)+ƒ(n-2),那你就算出ƒ(1)和ƒ(2)如何可以知道后面的结果,同时你也要确定动态规划最终要的ƒ(n)的n是多少。

下面引用一个知乎大佬回答中的解释:

举个例子,如果一个人上台阶可以上一级或者两级那么,总的走法数就可以用上图的有向图的路径数来抽象出来。

那么如果我在计算出了从5到10的路径数,这个路径数是不是可以保存下来?

为什么要保存?因为这个信息- -会儿还要再次被用到!

因为不管我是从3走过来的,还是从4走过来的,走到5之后,存在的路径就是第- -次计算出的结果,你无需重复计算!

如果是暴力遍历的话,从3到10的时候,你肯定会把5-10的可能路径数都算--遍,然后从4到10的时候,你又会把5- 10的路径算- -遍, 也就是重复计算了~

那么既然这样,我们创建-个数组a[],专门来存放位点x到10的所有可能路径数,初始值记为0,然后每当要计算x到10的路径数时,先检测一下该路径数的值是不是大于0,如果大于,就说明它之前已经被计算过,并存在了a[x]中了!

那么我们马,上可以得到一个递推关系:

a[x] = a[x+1] + a[x+2];

那么举个例子:

a[6]= a[7]+ a[8];

a[7]= a[8]+ a[9];

我们发现,在计算a[6]和a[7]的时候,我们都用了a[8],也就是被重复利用了结果。

思路:

说来惭愧,我这道题毫无思路。

以前都没有写过动态规划的题,感觉确实有一点难。

正如前面的上楼梯的例子,我们也可以进行一下抽象。如何用上一步的结果辅助得到下一步的最小变化次数。

首先我们定义一个二维数组,res[n][3],n是leaves的长度,3列中,当列数为0则表示若这一个位置为最左边的红叶时的最小变化次数;当列数为1时表示若这个位置为中间的黄叶时的最小变化次数;列数为2时表示这个位置为右边的红叶时的最小变化次数。

可以知道,若当前叶片为左边红叶则前面的叶片都应该为左红,那么当前叶片位置的最小变化次数就等于:

res[i][0] = res[i-1][0] + isYellow(当叶片是黄色的时候isYellow==1,否则==0)

同理,若当前叶片为中黄,则前面的叶片可以为左红也可以为中黄,那么我们取两种情况中变化次数较小的那个,则有:

res[i][1] = Math.min(res[i-1][0],res[i-1][1])+isRed;

当前叶片为右红时前面的叶片可以是右红,也可以是中黄,则有(注意,其前面至少要有两片叶子):

if(i>=2)                

res[i][2] = Math.min(res[i-1][2],res[i-1][1])+isYellow;

这里的isRed和isYellow这两个变量是在确定第某个叶子是否是需要的叶子种类时决定是否多一次变化(即变成需要的种类)

根据一步一步的计算,我们最终需要的结果是res[n-1][2]中存的结果,那么我们return这个数就可以了。

代码如下:

class Solution {
    public int minimumOperations(String leaves) {
        int n = leaves.length();
        int res[][] = new int[n][3];
        res[0][0] = leaves.charAt(0)=='y'?1:0;
        res[0][1]=res[0][2]=res[1][2]=Integer.MAX_VALUE;
        for(int i =1;i<n;i++){
            //isRed和isYellow这两个变量是在确定第某个叶子是否是需要的叶子种类时决定是否多一次变化(即变成需要的种类)
            int isRed = leaves.charAt(i)=='r'?1:0;
            int isYellow = leaves.charAt(i)=='y'?1:0;
            res[i][0] = res[i-1][0] + isYellow;
            res[i][1] = Math.min(res[i-1][0],res[i-1][1])+isRed;
            if(i>=2)
                res[i][2] = Math.min(res[i-1][2],res[i-1][1])+isYellow;
        }

        return res[n-1][2];
    }
}

据说还有什么降维的方法可以把存res的数组替代掉,从而使得空间复杂度变成O(1)但是我还没研究出来,如果有思路了再回来更新。

官方还有一种数学推导的解法,我认为普适性不是很大,就没有在本博客中记录,若有需要可以在官方题解中看一看。


你好哇!欢迎来到雷公马碎碎念的地方:)