【LeetCode】欲張りアルゴリズム--株を売買する最適なタイミングII(122)
一、前に書く
なぜLeetCodeで問題を書くのですか?校招であれ社招であれアルゴリズムの問題は必ず試験問題であることはよく知られていますが、この部分はちょうど多くの人の短板なので、ブラシ問題はまず自分のプログラミング能力を高めるために、アルゴリズムの面接で際立って、満足のいくofferを得ることができます.自分は大学院を受けるつもりで、コンピュータの大学院を受けるデータの構造も必ず問題を試験しなければならないので、ブラシの問題の第2の原因は自分のデータの構造の知識を強固にするためです.
どうやって問題をタッチすればいいですか?この2ヶ月は自分で順番に問題を塗ったのですが、総括する時に知識点がばらばらであることを発見しました.前の20題にはスタック、チェーンテーブル、配列などがあり、自分で総括する時に完全な体系を形成していません.はっきりした分類もありません.これは自分が望んでいるものではありません.だから、自分の後期の問題はテーマの方式を採用します.例えば、配列、チェーンテーブル、二叉木などです.
最初のテーマは欲張りアルゴリズムです前20題リンク【LeetCode】まとめ貼り(NO.1-20)
自分で1つのLeetCodeブラシの問題群を建てて、自分のブラシの問題の心得を交流して、今まだ予定の人数に着いていないで、興味のある小さい仲間は参加することができますよ、個人の微信:wxb 950917.
面接のために生まれ、あなたの参加を楽しみにしています.二、欲張りアルゴリズムとは何か
欲張りアルゴリズムはLeetCodeで41題あり,中程度の難易度が多い.では、欲張りアルゴリズムとは何でしょうか.
欲張りアルゴリズム(欲張りアルゴリズムとも呼ばれる)とは、問題を解く際に、常に現在から見れば最善の選択をすることを意味する.すなわち,全体最適化を考慮せずに,ある意味での局所最適解を行った.
欲張りアルゴリズムは、ステップごとに条件を満たさなければなりません.
1、実行可能:つまり、問題の制約を満たす必要があります.
2、ローカル最適:現在のステップのすべての実行可能な選択の中で最適なローカル選択である.
3、キャンセル不可:選択が一旦行われると、アルゴリズムの後のステップは変更できない.
欲張りアルゴリズムを学ぶときはダイナミックプランニングと組み合わせて勉強することができますが、両者は似ています.
三、今日のテーマ
株を売買する最良のタイミングII(122)
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.
あなたが得られる最大利益を計算するアルゴリズムを設計します.できるだけ多くの取引(株を複数回売買する)を完了することができます.
注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).
例1:入力:[7,1,5,3,6,4]出力:7解釈:2日目(株価=1)に購入し、3日目(株価=5)に売却し、この取引所は利益=5-1=4を得ることができる.
例2:入力:[1,2,3,4,5]出力:4解釈:1日目(株価=1)に購入し、5日目(株価=5)に売却し、この取引所は利益=5-1=4を得ることができる.
例3:入力:[7,6,4,3,1]出力:0解釈:この場合、取引が完了しないため、最大利益は0である.
四、テーマ分析
欲張りアルゴリズムは、常に現在から見れば最良の選択を行い、全体の最適化から考慮しない.つまり、現在の最適解だけに関心を持ち、欲張り戦略に従い、今後、私たちは現在の利益だけに関心を持っている.0日目に購入し、prices[0]を費やし、初日に売り出し、prices[1]を得ると、私たちの収穫はprofit=prices[1]-prices[0]であり、2つの場合がある.
(1)profit>0の場合、急いで買って売って、儲けることができます.
(2)profit<=0のとき、また買って売ると、それは馬鹿で、損をします.
このように類推すれば、最大の利益を得ることができる.
五、コード実現
class Solution:
【おすすめ読書】
【Python爬虫類】初識爬虫類(1)
Pythonで人工的に雪を作った
機械学習実戦--住宅月賃貸料予測(1)
Pythonの禅
なぜLeetCodeで問題を書くのですか?校招であれ社招であれアルゴリズムの問題は必ず試験問題であることはよく知られていますが、この部分はちょうど多くの人の短板なので、ブラシ問題はまず自分のプログラミング能力を高めるために、アルゴリズムの面接で際立って、満足のいくofferを得ることができます.自分は大学院を受けるつもりで、コンピュータの大学院を受けるデータの構造も必ず問題を試験しなければならないので、ブラシの問題の第2の原因は自分のデータの構造の知識を強固にするためです.
どうやって問題をタッチすればいいですか?この2ヶ月は自分で順番に問題を塗ったのですが、総括する時に知識点がばらばらであることを発見しました.前の20題にはスタック、チェーンテーブル、配列などがあり、自分で総括する時に完全な体系を形成していません.はっきりした分類もありません.これは自分が望んでいるものではありません.だから、自分の後期の問題はテーマの方式を採用します.例えば、配列、チェーンテーブル、二叉木などです.
最初のテーマは欲張りアルゴリズムです前20題リンク【LeetCode】まとめ貼り(NO.1-20)
自分で1つのLeetCodeブラシの問題群を建てて、自分のブラシの問題の心得を交流して、今まだ予定の人数に着いていないで、興味のある小さい仲間は参加することができますよ、個人の微信:wxb 950917.
面接のために生まれ、あなたの参加を楽しみにしています.二、欲張りアルゴリズムとは何か
欲張りアルゴリズムはLeetCodeで41題あり,中程度の難易度が多い.では、欲張りアルゴリズムとは何でしょうか.
欲張りアルゴリズム(欲張りアルゴリズムとも呼ばれる)とは、問題を解く際に、常に現在から見れば最善の選択をすることを意味する.すなわち,全体最適化を考慮せずに,ある意味での局所最適解を行った.
欲張りアルゴリズムは、ステップごとに条件を満たさなければなりません.
1、実行可能:つまり、問題の制約を満たす必要があります.
2、ローカル最適:現在のステップのすべての実行可能な選択の中で最適なローカル選択である.
3、キャンセル不可:選択が一旦行われると、アルゴリズムの後のステップは変更できない.
欲張りアルゴリズムを学ぶときはダイナミックプランニングと組み合わせて勉強することができますが、両者は似ています.
三、今日のテーマ
株を売買する最良のタイミングII(122)
配列が与えられ、そのi番目の要素は、与えられた株のi日目の価格です.
あなたが得られる最大利益を計算するアルゴリズムを設計します.できるだけ多くの取引(株を複数回売買する)を完了することができます.
注意:複数の取引に同時に参加することはできません(再購入前に前の株を売却しなければなりません).
例1:入力:[7,1,5,3,6,4]出力:7解釈:2日目(株価=1)に購入し、3日目(株価=5)に売却し、この取引所は利益=5-1=4を得ることができる.
， 4 （ = 3） ， 5 （ = 6） , = 6-3 = 3 。例2:入力:[1,2,3,4,5]出力:4解釈:1日目(株価=1)に購入し、5日目(株価=5)に売却し、この取引所は利益=5-1=4を得ることができる.
1 2 ， 。
， 。例3:入力:[7,6,4,3,1]出力:0解釈:この場合、取引が完了しないため、最大利益は0である.
四、テーマ分析
欲張りアルゴリズムは、常に現在から見れば最良の選択を行い、全体の最適化から考慮しない.つまり、現在の最適解だけに関心を持ち、欲張り戦略に従い、今後、私たちは現在の利益だけに関心を持っている.0日目に購入し、prices[0]を費やし、初日に売り出し、prices[1]を得ると、私たちの収穫はprofit=prices[1]-prices[0]であり、2つの場合がある.
(1)profit>0の場合、急いで買って売って、儲けることができます.
(2)profit<=0のとき、また買って売ると、それは馬鹿で、損をします.
このように類推すれば、最大の利益を得ることができる.
五、コード実現
class Solution:
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
profit = 0
temp=0
for i in range(1,len(prices)):
temp=prices[i] - prices[i-1]
if temp>0:
profit+=temp
return profit
【おすすめ読書】
【Python爬虫類】初識爬虫類(1)
Pythonで人工的に雪を作った
機械学習実戦--住宅月賃貸料予測(1)
Pythonの禅