力は問題のガイドラインをブラシします——貪欲なアルゴリズム
7080 ワード
一、欲張りアルゴリズムとは何か
欲張りアルゴリズム(英語:greedy algorithm)は、欲張りアルゴリズムとも呼ばれ、ステップ選択ごとに現在の状態で最良または最良(すなわち最も有利)の選択を行い、結果が最良または最良になることを望むアルゴリズムである.(ウィキペディア)
欲張りアルゴリズムの核心は,毎回現在の状態で最適な解を得ることであり,ここでは分かりやすい例を挙げる.君は店だ,君の手元にはマントーだけで金がない.お客様が並んであなたのマントーを買い、一度に1つのマントーしか買いません.それからお客様はあなたに5毛、1元、2元しか支払うことができなくて、あなたはすべてのお客様に正しいおつりを探さなければなりません.私たちの手元に十分なお金があって次のお客様におつりを探すために、私たちは一歩ごとにできるだけ自分の手元の5毛のお金を最も多くすることを保証する必要があります.そうすれば、後ろのお客様におつりを探すことができます.このような考え方は欲張りアルゴリズムです.
貪欲アルゴリズムの実現は大体:(step 1)ある初期解から出発する;(step 2)反復のプロセスを採用し、目標に一歩前進できる場合、局所最適戦略に基づいて、分解を得て、問題の規模を縮小する.(step 3)すべての解を統合する.
二、LeetCodeの典型的な問題の詳細
860.レモン水お釣り(easy)【お釣り問題】
タイトルの説明:
レモン水屋台では、レモン水1杯あたり5ドルで販売されています.
お客様が並んであなたの製品を購入し、(請求書billsで支払う順番で)一度に一杯購入します.
お客様はレモン水を1杯だけ買って、5ドル、10ドル、20ドルを払います.お客様一人一人に正確におつりを探さなければなりません.つまり、純取引はお客様一人一人に5ドルを支払うことです.
最初は小銭がありませんので、気をつけてください.
お客様一人一人に正確におつりを探してtrueに戻ることができます.そうしないとfalseに戻ります.
出力サンプル:
入力:[5,5,5,10,20]出力:true解釈:上位3人のお客様から5ドル札を順番に3枚受け取りました.4番目のお客様は、10ドル札を受け取り、5ドルを返します.5番目のお客様、10ドル札と5ドル札を返します.すべてのお客様が正しいお釣りをもらったので、trueを出力します.
問題:
この問題は典型的なお釣り問題です.5ドルの枚数が最も実用的なので、欲張りな発想を使って、毎回お釣りを探すなら、1枚10ドルでお釣りができるなら、絶対に2枚5ドルでお釣りはしません.私たちは3つの変数を借りて5ドル、10ドル、20ドルの数量を保存する必要があります.もしおつりが5ドルまたは10ドルの数量を探したら、Falseに戻ります.そうしないと、ずっと続けられます.
コード:
455.ビスケット配布(Easy)【配分問題】
タイトルの説明:
もしあなたが素晴らしい保護者だとしたら、子供たちにクッキーをあげたいです.しかし、子供1人につき最大1枚のビスケットしかあげられません.子供iごとに、食欲値g[i]があり、子供たちが食欲を満たすビスケットの最小サイズです.そして各ビスケットjには、サイズs[j]が1つある.s[j]>=g[i]であれば、このクッキーjを子供iに割り当てることができ、この子は満足します.あなたの目標は、できるだけ多くの子供を満たし、この最大値を出力することです.
出力サンプル:
入力:g=[1,2]、s=[1,2,3]出力:2解釈:子供2人とビスケット3枚、子供2人の食欲値はそれぞれ1,2です.あなたが持っているビスケットの数とサイズはすべての子供を満足させるのに十分です.だからあなたは2を出力すべきです.
問題:
子供一人一人にビスケットを1枚しかあげられません.ビスケットの大きさは一致しません.貪欲なアルゴリズムを使う思想は、一歩一歩が現在の最良に達するには、食欲の最小の子供が最初にビスケットを手に入れるべきだ.だから、私たちはまずこの子の食欲に等しいビスケットの大きさの中で最小のビスケットを見つけてこの子にあげなければならない.コードで説明すると、まず食欲の大きさとビスケットの大きさを小さいものから大きいものに並べて、子供の食欲に合った最小のビスケットを順番に探してあげます.
コード:
134.ガソリンスタンド(Medium)
タイトルの説明:
1本のループにはN個のガソリンスタンドがあり、そのうちi番目のガソリンスタンドにはガソリンgas[i]リットルがある.
ガソリンタンクの容量が無限の車を持っていて、i番目のガソリンスタンドからi+1番目のガソリンスタンドに行くにはガソリンcost[i]リットルを消費する必要があります.その中のガソリンスタンドから出発すると、最初はガソリンタンクが空いていました.
ループを一周できる場合は、出発時のガソリンスタンドの番号に戻ります.そうしないと-1に戻ります.
説明:
もし問題に解があれば、その答えは唯一の答えです.入力配列はすべて空ではない配列で、長さは同じです.入力配列の要素はすべて負ではありません.
出力サンプル:
入力:gas=[1,2,3,4,5]cost=[3,4,5,1,2]
出力:3
3番ガソリンスタンド(インデックスは3カ所)から4リットルのガソリンが得られます.この时、ガソリンタンクは=0+4=4リットルのガソリンが4番のガソリンスタンドに向かっています.この时、ガソリンタンクは4-1+5=8リットルのガソリンが0番のガソリンスタンドに向かっています.この时、ガソリンタンクは8-2+1=7リットルのガソリンが1番のガソリンスタンドに向かっています.この时、ガソリンタンクは7-3+2=6リットルのガソリンが2番のガソリンスタンドに向かっています.この时、ガソリンタンクは6-4+3=5リットルのガソリンが3番のガソリンスタンドに向かっています.5リットルのガソリンを消費する必要があります.ちょうど3番のガソリンスタンドに戻るのに十分です.したがって、3は開始インデックスとすることができる.
問題:
このテーマは暴力的な方法で実現できるので、興味のあるネットユーザーは試してみてください.この問題は欲張りなアルゴリズムを採用して、iガソリンスタンドからi+1ガソリンスタンドまでのcostが自動車が持っているガソリン量より大きいことを採用して、もしそうでなければ、次の場所から始めて、さもなくば今から起点とします.
このテーマはforループで達成できます.ポイントは変数totalを設定することです.costとcurrent、このtotal_costは総自動車内のガソリンを格納する場合、currentはindexから現在位置までのガソリンを格納する場合に用いられ、current>0がindexを起点とすることを示すと、消費ガソリン量は自動車のガソリンを超える量であるため、indexを起点とすることはできず、次のi+1を起点indexとして選択し、currentを0に設定する必要がある.
最終的に私たちの判断はtotalを見ることです.costは、総消費量が給油量(すなわちtotal>0)より大きい場合は−1を返し、そうでない場合はindexを返す.
コード:
435.重複しない区間(Medium)
タイトルの説明:
1つの区間の集合を指定し、残りの区間が重ならないように、区間を除去する必要がある最小数を見つけます.
注意:
区間の終点は常にその起点より大きいと考えられる.区間[1,2]と[2,3]の境界は互いに「接触」するが,互いに重ならない
出力サンプル:
問題:
このテーマで取った欲張り戦略は末尾の最小区間を残すことであり、これはどのように実現されたのだろうか.まず,区間未の大きさに従って区間を小さいものから大きいものに並べ替え,次に末尾が最も小さく,前の選択の区間が重ならない区間を選択する.ここではどのように重なりを判断しますか?1つの区間の先頭が前の区間の末尾より小さい場合、この区間が重複していると判断し、除去する必要がある.想像できないなら、サンプルと次のコードに基づいて区間軸を描いて理解することができます.
コード:
452.最少数の矢で風船を爆発させる(Medium)
タイトルの説明:
2 D空間には球形の風船がたくさんあります.各バルーンについて、入力は水平方向、バルーン直径の開始座標と終了座標です.水平であるためy座標は重要ではないので,開始と終了のx座標を知れば十分である.開始座標は常に終了座標より小さい.平面内には最大104個の風船が存在する.
1本の弓矢はx軸に沿って異なる点から完全に垂直に射出することができる.座標xに矢を1本射出し、1つの気球の直径の開始座標と終了座標がxstart,xendであり、xstart≦x≦xendを満たすと、その気球が爆発する.射出可能な弓矢の数に制限はありません.弓矢はいったん射出されると、無限に前進することができる.すべての風船を爆発させるために必要な弓矢の最小数を見つけたい.
出力サンプル:
入力:[[10,16],[2,8],[1,6],[7,12]]
出力:2
説明:この例については,x＝6(爆発［2,8］,［1,6］両気球)とx＝11(他の2つの気球を爆発させる)である.
問題:
この問題は典型的な区間重複問題であり,この問題を解決する比較的良い方法は貪欲アルゴリズムを用いることである.まず,end位置の大きさに従って配列を小さいものから大きいものに並べ替え,何個の区間が重なり合っているかを順に調べ,重なり合った区間は1回打つ.
コード実装とはprevと重ならない区間が見つかるまで順番に探すことであり,前に1回打った.順番に行います.もちろん、最後にもう一度補充する必要があります.下書き用紙に座標を描いて見ると、私の考えが分かりやすいはずです.しかし、私の解法は最適ではないはずです.ソートの時間が複雑だからです.
コード:
三、練習問題を補充する
392.判定サブシーケンス(Easy)
122.株の売買に最適なタイミング|(Easy)
605.種花問題(Easy)
763.アルファベット区間の区分(Medium)
406.身長に応じてキューを再構築する(Medium)
1386.映画館の位置を手配する(Medium)
四、その他
1、このブログで引用したテーマはすべてLeetCodeから来ています.
2、このブログは不定期にテーマ、問題解を更新します.コメントの転送も歓迎します.
欲張りアルゴリズム(英語:greedy algorithm)は、欲張りアルゴリズムとも呼ばれ、ステップ選択ごとに現在の状態で最良または最良(すなわち最も有利)の選択を行い、結果が最良または最良になることを望むアルゴリズムである.(ウィキペディア)
欲張りアルゴリズムの核心は,毎回現在の状態で最適な解を得ることであり,ここでは分かりやすい例を挙げる.君は店だ,君の手元にはマントーだけで金がない.お客様が並んであなたのマントーを買い、一度に1つのマントーしか買いません.それからお客様はあなたに5毛、1元、2元しか支払うことができなくて、あなたはすべてのお客様に正しいおつりを探さなければなりません.私たちの手元に十分なお金があって次のお客様におつりを探すために、私たちは一歩ごとにできるだけ自分の手元の5毛のお金を最も多くすることを保証する必要があります.そうすれば、後ろのお客様におつりを探すことができます.このような考え方は欲張りアルゴリズムです.
貪欲アルゴリズムの実現は大体:(step 1)ある初期解から出発する;(step 2)反復のプロセスを採用し、目標に一歩前進できる場合、局所最適戦略に基づいて、分解を得て、問題の規模を縮小する.(step 3)すべての解を統合する.
二、LeetCodeの典型的な問題の詳細
860.レモン水お釣り(easy)【お釣り問題】
タイトルの説明:
レモン水屋台では、レモン水1杯あたり5ドルで販売されています.
お客様が並んであなたの製品を購入し、(請求書billsで支払う順番で)一度に一杯購入します.
お客様はレモン水を1杯だけ買って、5ドル、10ドル、20ドルを払います.お客様一人一人に正確におつりを探さなければなりません.つまり、純取引はお客様一人一人に5ドルを支払うことです.
最初は小銭がありませんので、気をつけてください.
お客様一人一人に正確におつりを探してtrueに戻ることができます.そうしないとfalseに戻ります.
出力サンプル:
入力:[5,5,5,10,20]出力:true解釈:上位3人のお客様から5ドル札を順番に3枚受け取りました.4番目のお客様は、10ドル札を受け取り、5ドルを返します.5番目のお客様、10ドル札と5ドル札を返します.すべてのお客様が正しいお釣りをもらったので、trueを出力します.
問題:
この問題は典型的なお釣り問題です.5ドルの枚数が最も実用的なので、欲張りな発想を使って、毎回お釣りを探すなら、1枚10ドルでお釣りができるなら、絶対に2枚5ドルでお釣りはしません.私たちは3つの変数を借りて5ドル、10ドル、20ドルの数量を保存する必要があります.もしおつりが5ドルまたは10ドルの数量を探したら、Falseに戻ります.そうしないと、ずっと続けられます.
コード:
class Solution {
public boolean lemonadeChange(int[] bills) {
int len=bills.length;
int a=0,b=0,c=0;
if(bills[0]>5) return false; // 5 ， ， False
if(len==1&&bills[0]==5) return true;// ， 5 ， True
for(int i=0;i455.ビスケット配布(Easy)【配分問題】
タイトルの説明:
もしあなたが素晴らしい保護者だとしたら、子供たちにクッキーをあげたいです.しかし、子供1人につき最大1枚のビスケットしかあげられません.子供iごとに、食欲値g[i]があり、子供たちが食欲を満たすビスケットの最小サイズです.そして各ビスケットjには、サイズs[j]が1つある.s[j]>=g[i]であれば、このクッキーjを子供iに割り当てることができ、この子は満足します.あなたの目標は、できるだけ多くの子供を満たし、この最大値を出力することです.
出力サンプル:
入力:g=[1,2]、s=[1,2,3]出力:2解釈:子供2人とビスケット3枚、子供2人の食欲値はそれぞれ1,2です.あなたが持っているビスケットの数とサイズはすべての子供を満足させるのに十分です.だからあなたは2を出力すべきです.
問題:
子供一人一人にビスケットを1枚しかあげられません.ビスケットの大きさは一致しません.貪欲なアルゴリズムを使う思想は、一歩一歩が現在の最良に達するには、食欲の最小の子供が最初にビスケットを手に入れるべきだ.だから、私たちはまずこの子の食欲に等しいビスケットの大きさの中で最小のビスケットを見つけてこの子にあげなければならない.コードで説明すると、まず食欲の大きさとビスケットの大きさを小さいものから大きいものに並べて、子供の食欲に合った最小のビスケットを順番に探してあげます.
コード:
import java.util.Arrays;
class Solution {
public int findContentChildren(int[] g, int[] s) {
Arrays.sort(g);
Arrays.sort(s);
int child=0;
int cookie=0;
while(child134.ガソリンスタンド(Medium)
タイトルの説明:
1本のループにはN個のガソリンスタンドがあり、そのうちi番目のガソリンスタンドにはガソリンgas[i]リットルがある.
ガソリンタンクの容量が無限の車を持っていて、i番目のガソリンスタンドからi+1番目のガソリンスタンドに行くにはガソリンcost[i]リットルを消費する必要があります.その中のガソリンスタンドから出発すると、最初はガソリンタンクが空いていました.
ループを一周できる場合は、出発時のガソリンスタンドの番号に戻ります.そうしないと-1に戻ります.
説明:
もし問題に解があれば、その答えは唯一の答えです.入力配列はすべて空ではない配列で、長さは同じです.入力配列の要素はすべて負ではありません.
出力サンプル:
入力:gas=[1,2,3,4,5]cost=[3,4,5,1,2]
出力:3
3番ガソリンスタンド(インデックスは3カ所)から4リットルのガソリンが得られます.この时、ガソリンタンクは=0+4=4リットルのガソリンが4番のガソリンスタンドに向かっています.この时、ガソリンタンクは4-1+5=8リットルのガソリンが0番のガソリンスタンドに向かっています.この时、ガソリンタンクは8-2+1=7リットルのガソリンが1番のガソリンスタンドに向かっています.この时、ガソリンタンクは7-3+2=6リットルのガソリンが2番のガソリンスタンドに向かっています.この时、ガソリンタンクは6-4+3=5リットルのガソリンが3番のガソリンスタンドに向かっています.5リットルのガソリンを消費する必要があります.ちょうど3番のガソリンスタンドに戻るのに十分です.したがって、3は開始インデックスとすることができる.
問題:
このテーマは暴力的な方法で実現できるので、興味のあるネットユーザーは試してみてください.この問題は欲張りなアルゴリズムを採用して、iガソリンスタンドからi+1ガソリンスタンドまでのcostが自動車が持っているガソリン量より大きいことを採用して、もしそうでなければ、次の場所から始めて、さもなくば今から起点とします.
このテーマはforループで達成できます.ポイントは変数totalを設定することです.costとcurrent、このtotal_costは総自動車内のガソリンを格納する場合、currentはindexから現在位置までのガソリンを格納する場合に用いられ、current>0がindexを起点とすることを示すと、消費ガソリン量は自動車のガソリンを超える量であるため、indexを起点とすることはできず、次のi+1を起点indexとして選択し、currentを0に設定する必要がある.
最終的に私たちの判断はtotalを見ることです.costは、総消費量が給油量(すなわちtotal>0)より大きい場合は−1を返し、そうでない場合はindexを返す.
コード:
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
//total_cost （ ）
//index
//current index cost（ ）
int total_cost=0,index=0,current=0;
for(int i=0;i0 ， ， i ， current 0
// index
if(current>0){
index=i+1;
current=0;
}
}
if(total_cost<=0) return index;
else
return -1;
}
} 435.重複しない区間(Medium)
タイトルの説明:
1つの区間の集合を指定し、残りの区間が重ならないように、区間を除去する必要がある最小数を見つけます.
注意:
区間の終点は常にその起点より大きいと考えられる.区間[1,2]と[2,3]の境界は互いに「接触」するが,互いに重ならない
出力サンプル:
: [ [1,2], [2,3], [3,4], [1,3] ]
: 1
: [1,3] ， 。問題:
このテーマで取った欲張り戦略は末尾の最小区間を残すことであり、これはどのように実現されたのだろうか.まず,区間未の大きさに従って区間を小さいものから大きいものに並べ替え,次に末尾が最も小さく,前の選択の区間が重ならない区間を選択する.ここではどのように重なりを判断しますか?1つの区間の先頭が前の区間の末尾より小さい場合、この区間が重複していると判断し、除去する必要がある.想像できないなら、サンプルと次のコードに基づいて区間軸を描いて理解することができます.
コード:
import java.util.Arrays;
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
int len=intervals.length;
if(len<=1) return 0;
//Arrays.sort(intervals, Comparator.comparingInt(o -> o[0]));//
Arrays.sort(intervals, Comparator.comparingInt(o -> o[1]));//
int total=0;
int prev=intervals[0][1];
for(int i=1;i452.最少数の矢で風船を爆発させる(Medium)
タイトルの説明:
2 D空間には球形の風船がたくさんあります.各バルーンについて、入力は水平方向、バルーン直径の開始座標と終了座標です.水平であるためy座標は重要ではないので,開始と終了のx座標を知れば十分である.開始座標は常に終了座標より小さい.平面内には最大104個の風船が存在する.
1本の弓矢はx軸に沿って異なる点から完全に垂直に射出することができる.座標xに矢を1本射出し、1つの気球の直径の開始座標と終了座標がxstart,xendであり、xstart≦x≦xendを満たすと、その気球が爆発する.射出可能な弓矢の数に制限はありません.弓矢はいったん射出されると、無限に前進することができる.すべての風船を爆発させるために必要な弓矢の最小数を見つけたい.
出力サンプル:
入力:[[10,16],[2,8],[1,6],[7,12]]
出力:2
説明:この例については,x＝6(爆発［2,8］,［1,6］両気球)とx＝11(他の2つの気球を爆発させる)である.
問題:
この問題は典型的な区間重複問題であり,この問題を解決する比較的良い方法は貪欲アルゴリズムを用いることである.まず,end位置の大きさに従って配列を小さいものから大きいものに並べ替え,何個の区間が重なり合っているかを順に調べ,重なり合った区間は1回打つ.
コード実装とはprevと重ならない区間が見つかるまで順番に探すことであり,前に1回打った.順番に行います.もちろん、最後にもう一度補充する必要があります.下書き用紙に座標を描いて見ると、私の考えが分かりやすいはずです.しかし、私の解法は最適ではないはずです.ソートの時間が複雑だからです.
コード:
import java.util.Arrays;
class Solution {
public int findMinArrowShots(int[][] points) {
int len=points.length;
int total=0;
if(len==0) return 0;
Arrays.sort(points, Comparator.comparingInt(o -> o[1]));//
int prev=points[0][1];
for(int i=1;iprev){
total++;
prev=points[i][1];
}
}
return total+1;//
}
} 三、練習問題を補充する
392.判定サブシーケンス(Easy)
122.株の売買に最適なタイミング|(Easy)
605.種花問題(Easy)
763.アルファベット区間の区分(Medium)
406.身長に応じてキューを再構築する(Medium)
1386.映画館の位置を手配する(Medium)
四、その他
1、このブログで引用したテーマはすべてLeetCodeから来ています.
2、このブログは不定期にテーマ、問題解を更新します.コメントの転送も歓迎します.