LeetCode Online Judge https://leetcode.com/

1. 3Sum Closet[508ms]

#方法1：遍历第一个元素，后面加两个指针，O(n**3) class Solution(object): def threeSumClosest(self, nums, target): nums.sort() lth = len(nums) ans = 100000 for i in range(lth-2) : low, high = i+1, lth-1 while low < high : tmp = nums[i] + nums[low] + nums[high] if tmp < target : low += 1 else : high -= 1 if abs(tmp - target) < abs(ans - target) : ans = tmp return ans

2.Best Time to Buy and Sell Stock III [288ms]

#方法1：遍历两次，一个是现在之前最大利益（包括现在），一个是现在之后最大利益 class Solution(object): def maxProfit(self, prices): if len(prices) <= 1 : return 0 profit1 = [0 for i in range(len(prices))] minprice = 10000 for i in range(len(prices)) : minprice = min(minprice, prices[i]) if i-1 >= 0 : profit1[i] = max(profit1[i-1], prices[i] - minprice) print(profit1) maxprice = 0 ans = profit1[-1] for i in range(-1, -len(prices), -1) : maxprice = max(maxprice, prices[i]) ans = max(ans, profit1[i-1] + maxprice - prices[i]) return ans

3. Combination Sum II [92ms]

#方法1：dfs搜索，注意去重复 #总结： #1.把去重判断语句写在dfs前面是每个元素只能出现一次 # 写在后面是去除开始第一个元素的重复 #2.k如果是for每个传就是枚举 # 如果跟着变动则是每个元素之后 class Solution(object): import copy def combinationSum2(self, candidates, target): ans = [] tmp = [] s = 0 candidates.sort() self.dfs(0, s, tmp, ans, candidates, target) return ans def dfs(self, k, s, tmp, ans, candidates, target) : while k < len(candidates) : tmp.append(candidates[k]) s += candidates[k] if s > target : del tmp[-1] s -= candidates[k] return elif s == target : t = copy.copy(tmp) ans.append(t) del tmp[-1] s -= candidates[k] return else : #加一是一个个搜索 self.dfs(k+1, s, tmp, ans, candidates, target) s -= candidates[k] del tmp[-1] #返回时再去重复 while k+1 < len(candidates) and candidates[k] == candidates[k+1] : k += 1 k += 1

4. Game Of Life [60ms]

#方法1：既然要原地实现，就用状态转移 # 0 = 死到死； 1 = 生到生； 2 = 生到死； 3 = 死到生 # 原来是死的，只有在附近有三的才转移，原来是生的，只有在小于2和大于3才死亡。 # 其余的不变 class Solution(object): def gameOfLife(self, board): m, n = len(board), len(board[0]) dx = [-1, -1, -1, 0, 0, 1, 1, 1] dy = [-1, 0, 1, -1, 1, -1, 0, 1] for i in range(m) : for j in range(n) : cnt = 0 for k in range(8) : x, y = i+dx[k], j+dy[k] if x>=0 and x<m and y>=0 and y<n and (board[x][y] == 1 or board[x][y] == 2) : cnt += 1 if board[i][j] and (cnt < 2 or cnt > 3) : board[i][j] = 2 elif not board[i][j] and cnt == 3 : board[i][j] = 3 for i in range(m) : for j in range(n) : board[i][j] = board[i][j] % 2

5.Insert Delete GetRandon O(1) - Duplicates allowed [1112ms]

#方法1：使用一个字典保存索引和插入的数据 class RandomizedCollection(object): def __init__(self): """ Initialize your data structure here. """ import random self.l = [] self.d = {} def insert(self, val): """ Inserts a value to the collection. Returns true if the collection did not already contain the specified element. :type val: int :rtype: bool """ flag = False self.l.append(val) if str(val) in self.d.keys() : self.d[str(val)].append(len(self.l)-1) else : self.d[str(val)] = [len(self.l)-1] flag = True return flag def remove(self, val): """ Removes a value from the collection. Returns true if the collection contained the specified element. :type val: int :rtype: bool """ if str(val) not in self.d.keys() : return False else : rmindex = self.d[str(val)][0] lastvar = self.l[-1] lastindex = len(self.l) - 1 #索引不同，值也不同，防止删了值之后又加进去 if rmindex != lastindex and val != lastvar : self.l[rmindex], self.l[lastindex] = self.l[lastindex], self.l[rmindex] self.d[str(lastvar)].append(rmindex) self.d[str(val)].remove(rmindex) self.d[str(lastvar)].remove(lastindex) del self.l[-1] if len(self.d[str(val)]) == 0 : del self.d[str(val)] return True def getRandom(self): """ Get a random element from the collection. :rtype: int """ if len(self.l) == 0 : return -1 else : r = random.randint(0, len(self.l)-1) return self.l[r] # Your RandomizedCollection object will be instantiated and called as such: # obj = RandomizedCollection() # param_1 = obj.insert(val) # param_2 = obj.remove(val) # param_3 = obj.getRandom()

6. Jump Game [64ms]

#方法1：贪心，记录最高上界jump [88ms] #修改1：把最后一个return True的判断放在循环外面 [64ms] class Solution(object): def canJump(self, nums): jump = 0 for i in range(len(nums)) : if i > jump : return False tmp = i + nums[i] if tmp > jump : jump = tmp if jump >= len(nums)-1 : return True return False class Solution(object): def canJump(self, nums): jump = 0 for i in range(len(nums)) : if i > jump : return False tmp = i + nums[i] if tmp > jump : jump = tmp if jump >= len(nums)-1 : return True else : return False

7. Merge Intervals [96ms]

#方法1：有三种情况，一是两个区间相离，二是两个区间相交，三是两个区间重合 #用个low，high指针记录当前搜到的最大区间，发现想离就添加 class Solution(object): def merge(self, intervals): lth = len(intervals) if lth < 2 : return intervals ans = [] intervals = sorted(intervals, key=lambda interval : interval.start) low = intervals[0].start high = intervals[0].end for i in range(1, lth) : if intervals[i].start > high : ans.append(Interval(low, high)) low = intervals[i].start high = intervals[i].end elif intervals[i].end <= high : continue else : high = intervals[i].end ans.append(Interval(low, high)) return ans