IOS 算法(中级篇) ----- 爱生气的书店老板

今天，书店老板有一家店打算试营业 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

解题思路

比较典型的滑动窗口, 双指针求解问题
首先提醒大家, 生气不好, 好孩子不要学哦~

1.先计算初始用户满意度
2.依次循环找到, 每个区间变化的满意度总数, 并找到最大变化的满意度总数
3.初始满意度 + 最大变化的满意度就是我们要找的结果

1.png 2.png 3.png 4.png 5.png 6.png 7.png

代码

未翻译版

    func maxSatisfied(_ customers: [Int], _ grumpy: [Int], _ X: Int) -> Int {

        var maxsave = 0, sum = 0, last = 0, next = X - 1
        
        for i in 0..<customers.count {
            if grumpy[i] == 0 {
                sum = sum + customers[i]
            }
        }
        
        while next < customers.count {
            
            var temp = 0
            for i in last...next {
                if grumpy[i] == 1 {
                    temp += customers[i]
                }
            }
            
            maxsave = max(temp, maxsave)
            
            last += 1
            next += 1
        }
        
        return sum + maxsave
        
    }

翻译版

    func maxSatisfied(_ customers: [Int], _ grumpy: [Int], _ X: Int) -> Int {

        // 定义最大变化数, 初始总数, 起止2个指针
        var maxsave = 0, sum = 0, last = 0, next = X - 1

        // 循环, 找到初始满意度总数
        for i in 0..<customers.count {

            // 0: 满意, 1: 不满意, 我们判断0, 依次添加
            if grumpy[i] == 0 {
                sum = sum + customers[i]
            }
        }
        
        // 双指针查找新增的总数
        while next < customers.count {

            // 定义滑动区间变化初始值
            var temp = 0
            
            // 循环判断滑动窗口中的变化值
            for i in last...next {
                 
                // 不满足:1全变瞒住, 找到窗口中对应1下表的用户值, 依次增加
                if grumpy[i] == 1 {
                    
                    temp += customers[i]
                }
            }
            
            // 取每次循环的最大值
            maxsave = max(temp, maxsave)
            
            // last + 1, next + 1 继续滑动
            last += 1
            next += 1
        }
        
        // 返回最大的满意度
        return sum + maxsave
        
    }

题目来源：力扣（LeetCode） 感谢力扣爸爸 :)
IOS 算法合集地址