。レモネードチェンジ

860。レモネードチェンジ

難易度: 簡単

トピック: 配列、貪欲

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

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

整数配列 bills が与えられ、bills[i] が i

番目 ^{の顧客が支払う請求書である場合、}すべての顧客に正しいおつりを提供できる場合は 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 のいずれかです。

解決策:

顧客が支払いに使用する請求書に基づいて、顧客に小銭を提供するプロセスをシミュレーションする必要があります。重要なのは、持っている 5 ドル紙幣と 10 ドル紙幣の枚数を追跡することです。これらの紙幣は高額紙幣の小銭を提供するために必要となるためです

このソリューションを PHP で実装してみましょう:

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 で

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

このような役立つコンテンツがさらに必要な場合は、お気軽にフォローしてください:

• LinkedIn
• GitHub

以上が。レモネードチェンジの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。