leetcode-ブラシ日記(構想整理と学習の大物たちのアルゴリズムを含む)-[コードはGithubに同期して更新]

leetcode毎日1題Githubアドレス
主なのは自分に問題を書くように促すためであり、もう一つは問題を書く過程で大物たちの問題を解く構想を学び、整理するのに便利である.
GitHubホームページ:https://github.com/zht2649825643
day 1-株を売買するベストタイミングII
day 2-重複要素の存在
day 3-一度しか現れない数字
day 4-2つの配列の交差II
day 5-プラス1
初日-株を売買するベストタイミングII
配列が与えられ、その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日目に株を相次いで購入してから売ることはできないことに注意してください.これは同時に複数の取引に参加しているので、再購入する前に前の株を売却しなければなりません.

def maxProfit(self, prices: List[int]) -> int:
        """
        LeeTCode：     

          ：                 。

            ：76 ms

            ：15 MB
        """
        profit = 0
        if len(prices) == 0:
            return 0
        for i in range(len(prices)-1):
            if prices[i] < prices[i+1]:
                profit += (prices[i+1] - prices[i])
                pass
        return profit

問題解決の考え方:
ここでは貪欲な戦略を採用して解決することができます.まず、i日目の購入、j日目の販売で得た収益とi日目の購入、i+p日目の販売、i+p+1日目の購入、j日目の販売で得た収益は同じであることを理解する必要があります.例えば[1,2,3,4,5]は,最大収益が4であることが明らかであり,初日購入,5日目販売と見なすことができるが,1日目購入,2日目販売,同時に購入,3日目販売,同時に購入・・・と見なすことができる.
翌日-重複要素が存在します
整数配列を指定し、重複要素が存在するかどうかを判断します.
いずれかの値が配列に少なくとも2回現れると、関数はtrueを返します.配列内の各要素が異なる場合はfalseを返します.
例1
入力:[1,2,3,1]出力:true
例2
入力:[1,1,1,3,3,4,3,2,4,2]出力:true
例3
入力:[1,2,3,4]出力:false

def containsDuplicate(self, nums: List[int]) -> bool:
        """
        LeeTCode：     

          ：   ，         。

            ：56 ms

            ：16.9 MB
        """
        nums.sort()
        for i in range(1, len(nums)):
            if nums[i] == nums[i-1]:
                return True
        return False

問題解決の考え方:
一:無秩序配列を先に並べ替え、連続する数字があるかどうかを判断する.二:pythonのメタグループデータ構造を用いて判断する.(メタグループに重複するデータは表示されません)
3日目-1回のみ表示される数値
空でない整数配列が与えられ、ある要素が1回しか現れない以外は、各要素が2回現れます.それが一度しか現れなかった要素を見つけます.
説明:
あなたのアルゴリズムは線形時間の複雑さを持つべきです.余分なスペースを使わずに実現できますか?
例1
入力:[1,2,2,1,3]出力:3
例2
入力:[1,2,2]出力:1
例3
入力:[4,1,2,1,2]出力:4

def singleNumber(self, nums: List[int]) -> int:
        nums.sort()
        lens = len(nums)
        if lens == 1:
            return nums[0]
        if nums[1] != nums[0]:
            return nums[0]
        for i in range(1, lens, 2):
            if nums[i] != nums[i-1]:
                return nums[i-1]
        return nums[lens-1]

問題解決の考え方:
一:無秩序配列を先に並べ替え、連続した数字があるかどうかを判断し、配列を巡るときに一度に2桁進む.二:pythonの異或演算を使用する.(0^num = num/num ^ num = 0/n ^ m = m -n)
4日目-2つの配列の交差II
2つの配列を指定し、関数を記述して交差を計算します.
説明:
出力結果の各要素の出現回数は、要素が2つの配列に現れる回数と一致する必要があります.出力結果の順序を考慮しなくてもよい.
ステップ:
与えられた配列が順番に並んでいたら?アルゴリズムをどのように最適化しますか?nums 1のサイズがnums 2よりずっと小さい場合、どの方法が優れていますか?nums 2の要素がディスクに格納されている場合、ディスクメモリが限られており、すべての要素を一度にメモリにロードできない場合は、どうすればいいですか?
例1
入力:nums 1=[1,2,2,1]、nums 2=[2,2]出力:[2,2]
例2
入力:nums 1=[4,9,5]、nums 2=[9,4,9,8,4]出力:[4,9]

def intersect(self, nums1: List[int], nums2: List[int]) -> List[int]:
        list_add = []
        num1 = set(nums1)
        num2 = set(nums2)
        for i in num1:
            if i in num2:
                count = min(nums1.count(i), nums2.count(i))
                for j in range(count):
                    list_add.append(i)
        return list_add

問題解決の考え方:
一:無秩序配列を先に並べ替え、左右の配列の大きさを1つずつ判断し、同じ値を見つける.二:pythonのメタグループデータ構造を用いて判断し、メタグループ構造を用いて重複する値を探し出し、リスト統計値の個数を用いる.(メタグループに重複するデータは表示されません)
5日目-プラス1
整数からなる非空配列で表される非負の整数を与え、その数に1を加える.
最上位の数値は配列の先頭に格納され、配列内の各要素には単一の数値のみが格納されます.
整数0を除いて、この整数はゼロで始まると仮定できます.
例1
入力:[1,2,3]出力:[1,2,4]解釈:入力配列は数値123を表す.
例2
入力:[4,3,2,1]出力:[4,3,2,2]解釈:入力配列は数字4321を表す.

def plusOne(self, digits: List[int]) -> List[int]:
        """
        LeeTCode：     

          ：         ，         。

            ：36 ms

            ：13.9 MB
        """
        lens = len(digits)
        data = []
        num = 0
        for i in range(lens):
            num = (num * 10) + digits[i]
        num += 1
        while num != 0:
            data.append(num % 10)
            num = num // 10
        data.reverse()
        return data

問題解決の考え方:
一:二:
6日目-移動ゼロ
配列numsが与えられ、ゼロ以外の要素の相対的な順序を維持しながら、すべての0を配列の末尾に移動する関数が記述される.
例1
入力:[0,1,0,3,12]出力:[1,3,12,0]

def plusOne(self, digits: List[int]) -> List[int]:
        """
        LeeTCode：     

          ：         ，         。

            ：36 ms

            ：13.9 MB
        """
        lens = len(digits)
        data = []
        num = 0
        for i in range(lens):
            num = (num * 10) + digits[i]
        num += 1
        while num != 0:
            data.append(num % 10)
            num = num // 10
        data.reverse()
        return data

問題解決の考え方:
一:二: