860。レモネードチェンジ

難易度:簡単

トピック: 配列、貪欲

レモネードスタンドでは、各レモネードの価格は 5 ドルです。顧客はあなたから購入するために列に並び、一度に 1 つずつ (請求書で指定された順序で) 注文します。各顧客はレモネードを 1 つだけ購入し、5 ドル、10 ドル、または 20 ドル紙幣で支払います。顧客が正味トランザクションで 5 ドルを支払うようにするには、各顧客に正しいおつりを提供する必要があります。

最初は手持ちにお釣りがないことに注意してください。

番目 ^{の顧客が支払う請求書である場合、すべての顧客に正しいおつりを提供できる場合は} true を返し、それ以外の場合は false を返します .

例 1:

• 入力: 請求書 = [5,5,5,10,20]
• 出力: true
• 説明：
  先着 3 名のお客様から順に 5 ドル札を 3 枚集めます。
  4 番目の顧客からは 10 ドルの請求書を受け取り、5 ドルを返します。
  5 人目のお客様からは、10 ドル札と 5 ドル札を差し上げます。
  すべての顧客が正しいお釣りを取得したため、true を出力します。

例 2:

• 入力: 請求書 = [5,5,10,10,20]
• 出力: false
• 説明：
  最初の 2 人のお客様から順に、5 ドル札を 2 枚集めます。
  次の 2 人のお客様には、10 ドル札を回収し、5 ドル札をお返しします。
  最後のお客様には、10 ドル紙幣が 2 枚しかないため、15 ドルのおつりを返すことができません。
  すべての顧客が正しいお釣りを受け取ったわけではないため、答えは誤りです。

制約:

5
bills[i] は 5、10、または 20 のいずれかです。

解決：

860。レモネードチェンジ

1. 初期化: $5 と $10 を 0 に設定して開始します。これは、持っている $5 と $10 紙幣の枚数を表します。

2. 各請求書を処理中:

   • 顧客が 5 ドル紙幣で支払う場合: 単純に 5 ドル紙幣の枚数を増やします。
   • 顧客が 10 ドル紙幣で支払う場合: お釣りとして 5 ドル紙幣を 1 枚返す必要があるため、5 ドル紙幣の枚数を減らし、10 ドル紙幣の枚数を増やします。 5 ドル札がない場合は false を返します。
   • 顧客が 20 ドル紙幣で支払う場合: おつりとして 10 ドル紙幣 1 枚と 5 ドル紙幣 1 枚を優先的に渡します。それが不可能な場合は、5 ドル札を 3 枚渡すようにします。どちらのオプションも使用できない場合は、false を返します。

3. 最終チェック: おつりを使い果たすことなくすべての顧客を正常に処理した場合は、true を返します。

この関数は、必要な 5 ドル紙幣が手元になく、10 ドルまたは 20 ドルの請求書を受け取るのが早すぎた場合など、正しいおつりを渡すことができないシナリオを処理する必要があります。
制約 (最大 100,000 顧客) のため、大きな入力サイズを効率的に処理する必要があります。このソリューションは O(n) 時間の計算量で実行されるため、この問題には最適です。

連絡先リンク

リポジトリ にスターを付けるか、お気に入りのソーシャル ネットワークで投稿を共有することを検討してください。あなたのサポートは私にとって大きな意味を持ちます!

• リンクトイン
• GitHub