专栏首页用户6093955的专栏(leetcode每日打卡)秋叶收藏集【动态规划】

(leetcode每日打卡)秋叶收藏集【动态规划】

LCP 19.秋叶收藏集

题目链接

算法

动态规划

时间复杂度O(n)

1.题目要求最终形成[红、黄、红]三部分,每部分数量可以不相等,问最终调整操作数量最小是多少。这道题一开始考虑暴力去做,枚举两个分界点,即红黄,黄红之间的分界点的位置,但由于长度是1e5,时间复杂度为O(n^2)级别,故此法作废。

2.通过查看官方题解,了解到这道题可以使用动态规划去做,可以将时间复杂度优化到O(n)级别,为方便查阅复习,现结合自己的理解写下该题解。具体如下:

可以定义一个数组f[i][j],表示符合要求的最小的操作数,即使leaves[]数组从0到i的值符合题目规范的最小的操作数。i的范围是[0,leaves.length),j的范围是[0,2],其中0表示当前叶子为红色(在黄色前面),1表示当前叶子为黄色,2表示当前叶子为红色(在黄色后面)。

初始时f[0][0]的值会由第一片叶子的颜色决定。下面分情况讨论j的不同值的情况:

(1)当j=0时,f[i][0] = f[i-1][0] + isYellow(i)。isYellow函数会根据叶子的颜色返回对应的布尔值;同时需注意j=0这种情况下i最大为leaves.length-3,因为题目要求每部分叶子数量至少为1个;

(2)当j=1时,f[i][1] = min(f[i-1][0],f[i-1][1]) + isRed(i) 。该叶子左面的叶子的颜色可能是红色,也可能是黄色,取形成前面两种情况操作的最小值即可。同时需要判断当前叶子是否黄色。在这种情况下i最大值为leaves.length-2,最小值为1;

(3)当j=2时,f[i][2] = min(f[i-1][1],f[i-1][2]) + isYellow(i);。该叶子左面的叶子的颜色可能是红色,也可能是黄色,取形成前面两种情况操作的最小值即可。同时需要判断当前叶子是否为红色。在这种情况下i最大值为leaves.length-1,最小值为2;

最终返回结果为f[leaves.length - 1]

C++代码

//一开始是用函数调用的,但超时,故直接判断
class Solution {   
public:
/*
    bool isYellow(string leaves, int u){
        return (leaves[u] == 'y');
    }
    bool isRed(string leaves, int u){
        return (leaves[u] == 'r');
    }
*/
    int minimumOperations(string leaves) {
        int len = leaves.length();
        vector<vector<int> > f(len, vector<int>(3, INT_MAX));
        //f[0][0] = isYellow(leaves, 0);
        f[0][0] = (leaves[0] == 'y');
        for(int i = 1; i < len; i++){
            int yellow = (leaves[i] == 'y');
            int red = (leaves[i] == 'r');
            if(i < len - 2){
                //f[i][0] = f[i-1][0] + (int)isYellow(leaves, i);
                f[i][0] = f[i-1][0] + yellow;
            }
            if(i >= 1 && i < len - 1){
                //f[i][1] = min(f[i-1][0],f[i-1][1]) + (int)isRed(leaves, i);
                f[i][1] = min(f[i-1][0],f[i-1][1]) + red;
            }
            if(i >= 2){
                //f[i][2] = min(f[i-1][1],f[i-1][2]) + (int)isYellow(leaves, i);
                f[i][2] = min(f[i-1][1],f[i-1][2]) + yellow;
            }
        }
        return f[len - 1][2];
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 【Windows Of CCPC HDU - 6708】【打表,找规律】

    题意:给出一个整数k,要求你输出一个长和宽均为2^k^ 的符合要求的矩阵。比如k等于1时输出 \[ \begin{matrix} C & C \\ ...

    _DIY
  • 【Miscalculation UVALive - 6833 】【模拟】

    题目讲的是给你一个串,里面是加法、乘法混合运算(个人赛中误看成是加减乘除混合运算),有两种算法,一种是乘法优先运算,另一种是依次从左向右运算(不管它是否乘在前还...

    _DIY
  • 蓝桥杯突击复习准备——部分算法汇总

    当然,上面这个状态转移方程不适用于a数组长度较大的情况。比如AcWing896. 最长上升子序列 II (AC代码,思路在代码中)

    _DIY
  • [783]python使用PythonMagick将jpg图片转换成png图片

    PythonMagick库无法用pip或者easy_install来安装,因此,需要手动安装,地址如下: https://www.lfd.uci.edu/~g...

    周小董
  • LeetCode 326. Power of Three

    ShenduCC
  • 堆结构和lambda表达式的应用(IPO问题)

    之前有篇文章讲解了堆结构以及堆排序,堆可以分为大根堆和小根堆,那么我们如何使用么?笔试时需不需要自己重新实现一个堆结构呢?这个问题怎么说,从底层实现是应该会的,...

    算法工程师之路
  • C++的函数对象优于函数指针地方

    转载自:http://blog.csdn.net/huang_xw/article/details/7934156    

    Daotin
  • Github标星24.9k!适合初学者的有趣、入门级的开源项目

    仓库地址:https://github.com/521xueweihan/HelloGitHub

    黄博的机器学习圈子
  • 求两个等长有序数组的中位数的logN算法 分治法

    http://blog.csdn.net/yangliuy/article/details/7194199

    bear_fish
  • 接雨水 & 最大点

    给你 n 个非负整数 a1,a2,…,an,每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线,垂直线 i 的两个端点分别为 (i, ai) ...

    羽翰尘

扫码关注云+社区

领取腾讯云代金券