BabbleDay's Blog

默认递增，一旦递减就返回

def findMin(self, nums):
        rtn = nums[0]
        for i in range(len(nums)-1):
            if nums[i+1]<rtn:
                return nums[i+1]
        return rtn

优化至O(logN)

最基本DP

def maxSubArray(self, nums):
        output = [nums[0]]
        for i in range(1,len(nums)):
            output.append( max(output[i-1]+nums[i],nums[i]) )
        return max(output)

优化：用变量代替数组

def maxSubArray(self, nums):
        t, rtn = nums[0], nums[0]
        for i in range(1, len(nums)):
            t = max(t+nums[i], nums[i])
            rtn = max(rtn, t)
        return rtn

位操作 O(n)

class Solution:
    # @param {integer[]} nums
    # @return {boolean}
    def containsDuplicate(self, nums):
        pos, neg = 0, 0
        for x in nums:
            if x < 0:
                temp = 1 << -x
                if neg & temp != 0:
                    return True
                pos |= temp
            else:
                temp = 1 << x
                if pos & temp != 0:
                    return True
                pos |= temp
        return False

哈希表 O(n)

Python一行