Leetcode总结

1.两数之和 hash表，key存差值，value存下表 复杂度O(n)

def twoSum(self, nums, target): """ :type nums: List[int] :type target: int :rtype: List[int] """ dic={} for i in range(len(nums)): if nums[i] in dic: return i,dic[nums[i]] else: dic[target-nums[i]] = i

13.罗马数字转整数 字典，遍历判断加还是减

convert={'M': 1000,'D': 500 ,'C': 100,'L': 50,'X': 10,'V': 5,'I': 1} for i in range(len(s)-1): if convert[s[i]]<convert[s[i+1]]: sum=sum-convert[s[i]] else: sum=sum+convert[s[i]] return sum+convert[s[-1]]

20.有效的括号 建立字典保存对应关系 遍历，左括号入栈，右括号判断并弹出最后元素，全部弹出则有效

def isValid(self, s): """ :type s: str :rtype: bool """ if len(s) == 0: return True d = {'{': '}', '[': ']', '(': ')'} stack = [] for i in s: # in stack if i in d: stack.append(i) else: if not stack or d[stack.pop()] != i: #默认剔除列表最后一个元素，并返回其下标 return False return stack==[]

22.括号生成 回溯法递归，追踪左括号和右括号数目。

def generateParenthesis(self, N): ans = [] def backtrack(S = '', left = 0, right = 0): if len(S) == 2 * N: ans.append(S) return if left < N: backtrack(S+'(', left+1, right) if right < left: backtrack(S+')', left, right+1) backtrack() return ans

33.搜索旋转排序数组 二分法查找，左右必有一半是有序的

right = len(nums)-1 while left <= right: mid = (left + right)/2 if nums[mid] == target: return mid elif nums[mid] >= nums[left]: if target >= nums[left] and target < nums[mid]: right = mid-1 else: left = mid+1 else: if target > nums[mid] and target <= nums[right]: left = mid+1 else: right = mid-1 return -1

59.螺旋矩阵II while循环，4个choice，定时改变输出长度

def generateMatrix(self, n): """ :type n: int :rtype: List[List[int]] """ res = [[0 for x in range(n)] for x in range(n)] cnt, choice = 1, 0 i, j = 0, 0 weight = 1 res[0][0] = 1 while cnt < n * n: if choice == 0: j += 1 res[i][j] = cnt + 1 if j == n - weight: choice = 1 elif choice == 1: i += 1 res[i][j] = cnt + 1 if i == n - weight: choice = 2 elif choice == 2: j -= 1 res[i][j] = cnt + 1 if j == weight - 1: choice = 3 weight += 1 elif choice == 3: i -= 1 res[i][j] = cnt + 1 if i == weight - 1: choice = 0 cnt += 1 return res

78.子集 给定数组，输出其所有子集

def subsets(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ res = [[]] for num in nums : for temp in res[:] : #res[:]锁定此时的数组，不迭代加入的新元素 x = temp[:] #锁定temp，对x操作不改变temp x.append(num) res.append(x) return res

104.二叉树最大深度 递归，没递归一次就有一层，无子节点返回0层

def maxDepth(self, root): """ :type root: TreeNode :rtype: int """ if not root: return 0 else: left_depth = self.maxDepth(root.left) + 1 right_depth = self.maxDepth(root.right) + 1 return max(left_depth,right_depth)

108.有序数组转化为二叉树