剣を指すオファー问题39−42 python補充学習記録

问题40:最小のkの個数

考察序列は。

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
    #冒泡排序
        alen = len(arr)
        for i in range(alen-1,0,-1):
            for j in range(i):
                if arr[j]>arr[j+1]:
                    arr[j],arr[j+1]=arr[j+1],arr[j]
        return arr[:k]

サボること:もとても妙

class Solution:
    def getLeastNumbers(self, arr: List[int], k: int) -> List[int]:
        arr.sort()
        return arr[:k]

问题42:子配列の最大の連続と

ヒント:动态计画を解く、dpは[i] i−1キャラクタ処の最大と(i−1の文字を含む)。

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

简洁版コード:学feiた

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        for i in range(1,len(nums)):
            nums[i]+=max(nums[i-1],0)
        return max(nums)
ソースネットワーク 戻る