LeetCode: 1052. 怒りっぽい本屋さん(中等)
6799 ワード
タイトルの説明
今日、本屋の主人は店を試して営業するつもりです.length分.毎分いくつかの顧客(customers[i])が書店に入り、これらの顧客はその1分後に離れる.
ある時、本屋の主人は怒ります.書店のオーナーが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,0],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
問題解
満足する数量=ボスが正常に怒らない顧客満足数量(grumpy[i]はもともと0)+ボスが秘密のテクニックを使って顧客満足を得る数量(grumpy[i]から1->0).社長が正常に怒ってお客様の満足度を得るためにforサイクルを使用してgrumpy[i]が0の場合のcustomer[i]値 を計算します.ボス秘密テクニックを使用して顧客満足度を得る数量はスライドウィンドウで計算し、統計量はmax a)ウィンドウを拡大し、grumpy[i]を1とするcustomer[i]をb)ウィンドウがXより大きい場合、ウィンドウを縮小し、grumpy[i-X]を1とするcustomer[i-X]cを減算)現在のウィンドウ内に満足度を追加する顧客数countの値がmaxより大きい場合、更新maxはbase+max に戻る
複雑度解析時間複雑度:O(N),Nは配列長である.空間複雑度:O(1).
リファレンス
c++スライド窓1052.怒りっぽい本屋さん【スライドウィンドウ、JavaScript】スライドウィンドウ-怒りっぽい本屋さん
今日、本屋の主人は店を試して営業するつもりです.length分.毎分いくつかの顧客(customers[i])が書店に入り、これらの顧客はその1分後に離れる.
ある時、本屋の主人は怒ります.書店のオーナーが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,0],X=3出力:16説明:書店のオーナーは最後の3分間冷静さを保った.満足できる最大顧客数=1+1+1+1+7+5=16.
ヒント:
問題解
満足する数量=ボスが正常に怒らない顧客満足数量(grumpy[i]はもともと0)+ボスが秘密のテクニックを使って顧客満足を得る数量(grumpy[i]から1->0).
class Solution {
public:
int maxSatisfied(vector<int>& customers, vector<int>& grumpy, int X) {
int max=0,base=0;//max ,base ,count
for(int i=0,count=0;i<grumpy.size();i++)
{
if(grumpy[i]==0) base += customers[i];
if(i < X && grumpy[i]==1)// X count
count += customers[i];
// ,(i - X, i]
else if(i >= X)
{
// , , , , ,
if(i-X >= 0 && grumpy[i-X]==1)
count -= customers[i-X];
if(grumpy[i]==1)
count += customers[i];
}
if(count > max) max = count;// max
}
return base + max;
}
};
複雑度解析時間複雑度:O(N),Nは配列長である.空間複雑度:O(1).
リファレンス
c++スライド窓1052.怒りっぽい本屋さん【スライドウィンドウ、JavaScript】スライドウィンドウ-怒りっぽい本屋さん