classSolution: defmaxProfit(self, prices: List[int]) -> int: ans = 0 profit = 0 minprice, maxprice = prices[0], prices[0] m = len(prices)
for i inrange(1, m): if prices[i] < maxprice: ans += maxprice - minprice minprice = prices[i] maxprice = prices[i] ans += maxprice - minprice return ans # 找到阶段的最大差值,遇到小于阶段最大值的就把当前阶段的最大收益计入并开始一个新阶段
# 一个更好的写法是: """ class Solution: def maxProfit(self, prices: List[int]) -> int: profit = 0 for i in range(1, len(prices)): tmp = prices[i] - prices[i - 1] if tmp > 0: profit += tmp return profit """
classSolution: defintersect(self, nums1: List[int], nums2: List[int]) -> List[int]: hashtable = [0for _ inrange(1001)] ans = [] for i inrange(len(nums1)): hashtable[nums1[i]] += 1 for i inrange(len(nums2)): if hashtable[nums2[i]] > 0: hashtable[nums2[i]] -= 1 ans.append(nums2[i]) return ans
classSolution: defcontainsNearbyDuplicate(self, nums: List[int], k: int) -> bool: hashtable = dict() for i, num inenumerate(nums): if num in hashtable: ifabs(hashtable[num] - i) <= k: returnTrue hashtable[num] = i returnFalse
classSolution: defcontainsDuplicate(self, nums: List[int]) -> bool: hashtable = dict() for i, num inenumerate(nums): if num in hashtable: returnTrue else: hashtable[num] = 1 returnFalse
给定一个大小为 n 的数组 nums ,返回其中的多数元素。多数元素是指在数组中出现次数 大于⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的,并且给定的数组总是存在多数元素。
代码块
解法1-摩尔投票
1 2 3 4 5 6 7 8 9
classSolution: defmajorityElement(self, nums: List[int]) -> int: ans = hp = 0 for x in nums: if hp == 0: # x 是初始擂主,生命值为 1 ans, hp = x, 1 else: # 比武,同门加血,否则扣血 hp += 1if x == ans else -1 return ans