ゼロからLeetcode-配列をブラシ(27.3.53)

文書ディレクトリ

27.除去要素

35.検索挿入位置

53.最大サブシーケンスおよび

今日は27.35です.53題です.27と昨日の26題の思想の差は多くなくて、35は比較的に簡単で、53は確かにしばらく考えました.
27.要素の除去
配列numsと値valを与えます.valに等しいすべての数値の要素をその場で除去し、除去後の配列の新しい長さを返す必要があります.
余分な配列空間を使用しないでください.O(1)余分な空間だけを使用して、入力配列をその場で変更する必要があります.
要素の順序は変更できます.配列の中で新しい長さの後ろを超える要素を考慮する必要はありません.
1.逆ループ

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        length = len(nums)
        for i in range(length-1, -1, -1):
            if nums[i] == val:
                nums.pop(i)
            else:
                continue
        return len(nums)

前の問題の構想とそっくりで、詳しく述べないで、48 ms
2.単一ポインタ

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        length = len(nums)
        j=0
        for i in range(length):
            if nums[i] != val:
                nums[j]=nums[i]
                j = j+1
        nums = nums[:j]
        return len(nums)

60ms
3.意味のない解法

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        try:
            while True:
                nums.remove(val)
        except:
            return len(nums)

他の人のを参考にして、コードはあまり意味がなくて、スピードが速くて、36 ms
35.挿入位置の検索
ソート配列とターゲット値を指定し、配列内にターゲット値を見つけ、インデックスを返します.ターゲット値が配列に存在しない場合は、順番に挿入される位置を返します.
配列に重複要素がないと仮定できます.
1.個々の比較

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        length = len(nums)
        for i in range(length):
            if nums[i] >= target:
                return i
        return length       

言わないで簡単だ48 ms
2.二分検索

class Solution:
    def searchInsert(self, nums: List[int], target: int) -> int:
        length = len(nums)
        l=0
        r=length-1
        while(l<=r):
            mid = (l+r)//2
            if nums[mid] == target:
                return mid
            elif nums[mid] < target:
                l = mid+1
            else:
                r = mid -1
        return l

これは標準解法のはずです.44 ms、もっと速くて、どうすればいいか分かりません.
53.最大サブシーケンス和
整数配列numsを指定し、最大和を持つ連続サブ配列(サブ配列には少なくとも1つの要素が含まれている)を見つけ、その最大和を返します.
1.暴力計算

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        length = len(nums)
        max_ = nums[0]
        sum_ = nums[0]
        for i in range(1, length):
        	#                       ，                 ，        
            if sum_ + nums[i] > nums[i]:
                max_ = max(max_, sum_+nums[i])
                sum_ = sum_ + nums[i]
            #              ，          。               ,            
            else:
                max_ = max(max_, nums[i])
                sum_ = nums[i]
        return max_

基本的な考え方は1回遍歴して、2つの変数を使って、1つの記録の最大の和、1つの記録の現在の和、52 ms
2.分治アルゴリズム

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        n = len(nums)
        #      
        if n == 1:
            return nums[0]
        else:
            #            
            max_left = self.maxSubArray(nums[0:len(nums) // 2])
            #            
            max_right = self.maxSubArray(nums[len(nums) // 2:len(nums)])
        
        #          ，              ，              ，   
        max_l = nums[len(nums) // 2 - 1]
        tmp = 0
        for i in range(len(nums) // 2 - 1, -1, -1):
            tmp += nums[i]
            max_l = max(tmp, max_l)
        max_r = nums[len(nums) // 2]
        tmp = 0
        for i in range(len(nums) // 2, len(nums)):
            tmp += nums[i]
            max_r = max(tmp, max_r)
        #         
        return max(max_right,max_left,max_l+max_r)

大物のコードをすり抜けて、大体その最大のサブシーケンスと左半分にあるか、右半分にあるか、真ん中を通るか、左右のシーケンスについても、状況は同じなので、再帰的に処理することができます.中間部分は直接計算できます.速度は遅くて、180 ms、しかし思想は少し参考にすることができます
3.動的計画

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
        dp = nums[:]  #    dp  ，dp[i]   nums[i]             
        res = dp[0]
        for i in range(1, len(nums)):
            dp[i] = max(dp[i], dp[i] + dp[i - 1])  #   dp[i]
            res = max(res, dp[i]) #        
        return res

ダイナミックな計画はよく分からないので、ここに置いて、勉強してから補充します.説明原話はdp[i]が格納するのは0からiまでの範囲で得られる最大の連続サブ配列の和ではなくnums[i]を末尾とするサブ配列で達成できる最大の和である.速度も52 ms