1052. 爱生气的书店老板

每天一道Rust-LeetCode(2019-12-19)

坚持每天一道题,刷题学习Rust.

题目描述

今天,书店老板有一家店打算试营业 customers.length 分钟。每分钟都有一些顾客(customers[i])会进入书店,所有这些顾客都会在那一分钟结束后离开。

在某些时候,书店老板会生气。 如果书店老板在第 i 分钟生气,那么 grumpy[i] = 1,否则 grumpy[i] = 0。 当书店老板生气时,那一分钟的顾客就会不满意,不生气则他们是满意的。

书店老板知道一个秘密技巧,能抑制自己的情绪,可以让自己连续 X 分钟不生气,但却只能使用一次。

请你返回这一天营业下来,最多有多少客户能够感到满意的数量。

示例:

输入:customers = [1,0,1,2,1,1,7,5], grumpy = [0,1,0,1,0,1,0,1], X = 3
输出:16
解释:
书店老板在最后 3 分钟保持冷静。
感到满意的最大客户数量 = 1 + 1 + 1 + 1 + 7 + 5 = 16.

提示:

1 <= X <= customers.length == grumpy.length <= 20000
0 <= customers[i] <= 1000
0 <= grumpy[i] <= 1

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/grumpy-bookstore-owner
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

粗暴的方法是O(XN),优化的方法是
使用三倍的空间将复杂度降低到O(N)
分别是从左往右,按照书店老板是否生气求累加和
从右往左,按照书店老板是否生气求累加和
从左往右,不考虑书店老板是否生气求累加和

解题过程

struct Solution {}
impl Solution {
    pub fn max_satisfied(customers: Vec<i32>, grumpy: Vec<i32>, x: i32) -> i32 {
        let x = x as usize;
        let mut left = Vec::new(); //从0到i的和
        let mut right = Vec::new(); //从i到最后的和
        let mut total = Vec::new();
        //求左边
        for i in 0..customers.len() {
            right.push(0);
            let mut last = 0;
            if i > 0 {
                last = left[i - 1];
            }
            if grumpy[i] == 0 {
                left.push(last + customers[i]);
            } else {
                left.push(last);
            }
        }

        for i in (0..customers.len()).rev() {
            let mut last = 0;
            if i < customers.len() - 1 {
                last = right[i + 1];
            }
            if grumpy[i] == 0 {
                right[i] = last + customers[i];
            } else {
                right[i] = last;
            }
        }
        //求全部
        for i in 0..customers.len() {
            right.push(0);
            let mut last = 0;
            if i > 0 {
                last = total[i - 1];
            }
            total.push(last + customers[i]);
        }
        let mut max = 0;
        for i in 0..customers.len() - x + 1 {
            let mut v1 = 0;
            let mut v2 = 0;
            if i > 0 {
                v1 = left[i - 1];
            }
            if i + x <= customers.len() - 1 {
                v2 = right[i + x];
            }
            v1 += total[i + x - 1] - total[i] + customers[i];
            if v1 + v2 > max {
                max = v1 + v2;
            }
        }
        max
    }
}
#[cfg(test)]
mod test {
    use super::*;
    use crate::share::*;
    #[test]
    fn test() {
        let t = Solution::max_satisfied(
            vec![1, 0, 1, 2, 1, 1, 7, 5],
            vec![0, 1, 0, 1, 0, 1, 0, 1],
            3,
        );
        assert_eq!(t, 16);
    }
}

一点感悟

其他

欢迎关注我的github,本项目文章所有代码都可以找到.

本站总访问量 本站访客数人次