LeetCode-Tencent Top50
2020-02-24 本文已影响0人
inspiredhss
237. 删除链表中的节点
class Solution:
def deleteNode(self, node):
node.val = node.next.val
node.next = node.next.next
104. 二叉树的最大深度
class Solution:
def maxDepth(self, root):
stack = []
if root is not None:
stack.append((1, root))
depth = 0
while stack != []:
current_depth, root = stack.pop()
if root is not None:
depth = max(depth, current_depth)
stack.append((current_depth + 1, root.left))
stack.append((current_depth + 1, root.right))
return depth
class Solution:
def maxDepth(self, root):
if root is None:
return 0
else:
left_height = self.maxDepth(root.left)
right_height = self.maxDepth(root.right)
return max(left_height, right_height) + 1
292. Nim 游戏
class Solution:
def canWinNim(self, n: int) -> bool:
# """解法一，动态规划"""
if n <= 3:
return True
dp = [False] * n
dp[0], dp[1], dp[2] = True, True, True
for i in range(3, n):
if not dp[i - 1] or not dp[i - 2] or not dp[i - 3]:
dp[i] = True
return dp[-1]
def canWinNim(self, n: int) -> bool:
"""解法二，空间优化版的动归"""
if n<=3:
return True
dp1,dp2,dp3=True,True,True
for i in range(3,n):
if not dp1 or not dp2 or not dp3:
dp=True
else:
dp=False
dp1, dp2, dp3 = dp2, dp3, dp
return dp
def canWinNim(self, n: int) -> bool:
# """解法三，其实只要保证你你一直你一直面对的是4的倍数就行"""
return n%4!=0
557. 反转字符串中的单词 III
# 557. 反转字符串中的单词 III
# 输入: "Let's take LeetCode contest"
# 输出: "s'teL ekat edoCteeL tsetnoc"
class Solution:
def reverseWords(self, s: str) -> str:
return ' '.join(s.split(' ')[::-1])[::-1]
344. 反转字符串
# 344. 反转字符串
# 输入：["h","e","l","l","o"]
# 输出：["o","l","l","e","h"]
class Solution:
def reverseString(self, s: List[str]) -> None:
left, right = 0, len(s) - 1
while left < right:
s[left], s[right] = s[right], s[left]
left, right = left + 1, right - 1
206. 反转链表
class Solution(object):
def reverseList(self, head):
# 申请两个节点，pre和 cur，pre指向None
pre = None
cur = head
# 遍历链表
while cur:
# 记录当前节点的下一个节点
tmp = cur.next
# 然后将当前节点指向pre
cur.next = pre
# pre和cur节点都前进一位
pre = cur
cur = tmp
return pre
class Solution(object):
def reverseList(self, head):
# 递归终止条件是当前为空，或者下一个节点为空
if(head==None or head.next==None):
return head
# 这里的cur就是最后一个节点
cur = self.reverseList(head.next)
# 这里请配合动画演示理解
# 如果链表是 1->2->3->4->5，那么此时的cur就是5
# 而head是4，head的下一个是5，下下一个是空
# 所以head.next.next 就是5->4
head.next.next = head
# 防止链表循环，需要将head.next设置为空
head.next = None
# 每层递归函数都返回cur，也就是最后一个节点
return cur
169. 多数元素
# 169. 多数元素
# 大小为 n 的数组==>多数元素; 出现次数大于 ⌊ n/2 ⌋ 的元素。
# 摩尔投票法
# 众数出现的次数>>其他数字出现次数之和
# 初始化res=0count=0
# 遍历数组：
# 若count==0，则将res更新为nums[i]，并令count=1
# 否则：
# 若nums[i]==res，令count+=1
# 若nums[i]!=res，令count-=1
# 若最终count>0，则返回res
class Solution:
def majorityElement(self, nums: List[int]) -> int:
n=len(nums)
res=0
count=0
for i in range(n):
if(count==0):
res=nums[i]
count=1
else:
if(nums[i]==res): count+=1
else: count-=1
if(count>0): return res
# 哈希表
class Solution:
def majorityElement(self, nums: List[int]) -> int:
hash={}
n=len(nums)
if(n==1):
return nums[0]
max_count=n//2
for i in range(n):
if(nums[i] not in hash):
hash[nums[i]]=1
else:
hash[nums[i]]+=1
if(hash[nums[i]]>max_count):
return nums[i]
21. 合并两个有序链表
# Definition for singly-linked list.
# 21. 合并两个有序链表
# 输入：1->2->4, 1->3->4
# 输出：1->1->2->3->4->4
class Solution:
def mergeTwoLists(self, l1, l2):
prehead = ListNode(-1)
prev = prehead
while l1 and l2:
if l1.val <= l2.val:
prev.next = l1
l1 = l1.next
else:
prev.next = l2
l2 = l2.next
prev = prev.next
prev.next = l1 if l1 is not None else l2
return prehead.next
122. 买卖股票的最佳时机 II
# 算法流程：
# 遍历整个股票交易日价格列表 price，策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。
# 设 tmp 为第 i-1 日买入与第 i 日卖出赚取的利润，即 tmp = prices[i] - prices[i - 1] ；
# 当该天利润为正 tmp > 0，则将利润加入总利润 profit；当利润为0 或为负，则直接跳过；
# 遍历完成后，返回总利润 profit。
# 时间复杂度 O(N) ： 只需遍历一次price；
# 空间复杂度 O(1) ： 变量使用常数额外空间。
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
9. 回文数
# 方法二: 将int转化成str类型: 双指针 (指针的性能一直都挺高的)
# 复杂度: O(n)
def isPalindrome(x: int) -> bool:
lst = list(str(x))
L, R = 0, len(lst)-1
while L <= R:
if lst[L] != lst[R]:
return False
L += 1
R -= 1
return True
160. 相交链表
# 一：两个指针分别指向两个链表头部，一起向前走直到其中一个到达末端，另一个与末端距离则是两链表的长度差。 再通过长链表指针先走的方式消除长度差，最终两链表即可同时走到相交点。
# 换个方式消除长度差： 拼接两链表。
# 设长-短链表为C，短-长链表为D，则当C走到长短链表交接处时，D走在长链表中，且与长链表头距离为长度差;
# 当 ha == hb 时跳出，返回即可
# 找到两个单链表相交的起始节点
class Solution:
def getIntersectionNode(self, headA, headB):
ha, hb = headA, headB
while ha != hb:
ha = ha.next if ha else headB
hb = hb.next if hb else headA
return ha
121. 买卖股票的最佳时机
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) == 0:
return 0
prev = prices[0]
max_profit = 0
max_here = 0
for t in prices[1:]:
x = t - prev
prev = t
max_here = max_here + x if max_here > 0 else x
max_profit = max(max_profit, max_here)
return max_profit
217. 存在重复元素
class Solution:
def containsDuplicate(self, nums: List[int]) -> bool:
return len(nums) != len(set(nums))
155. 最小栈
class MinStack:
# 辅助栈和数据栈不同步
# 关键 1：辅助栈的元素空的时候，必须放入新进来的数
# 关键 2：新来的数小于或者等于辅助栈栈顶元素的时候，才放入（特别注意这里等于要考虑进去）
# 关键 3：出栈的时候，辅助栈的栈顶元素等于数据栈的栈顶元素，才出栈，即"出栈保持同步"就可以了
def __init__(self):
# 数据栈
self.data = []
# 辅助栈
self.helper = []
def push(self, x):
self.data.append(x)
# 关键 1 和关键 2
if len(self.helper) == 0 or x <= self.helper[-1]:
self.helper.append(x)
def pop(self):
# 关键 3：【注意】不论怎么样，数据栈都要 pop 出元素
top = self.data.pop()
if self.helper and top == self.helper[-1]:
self.helper.pop()
return top
def top(self):
if self.data:
return self.data[-1]
def getMin(self):
if self.helper:
return self.helper[-1]
53. 最大子序和
# 在整个数组或在固定大小的滑动窗口中找到总和或最大值或最小值的问题可以通过动态规划（DP）在线性时间内解决。
# 有两种标准 DP 方法适用于数组：
# 常数空间，沿数组移动并在原数组修改。
# 线性空间，首先沿 left->right 方向移动，然后再沿 right->left 方向移动。 合并结果。
# 我们在这里使用第一种方法，因为可以修改数组跟踪当前位置的最大和。
# 下一步是在知道当前位置的最大和后更新全局最大和。
# 时间复杂度：O(N)。只遍历了一次数组。
# 空间复杂度：O(1)，使用了常数的空间。
class Solution:
def maxSubArray(self, nums: 'List[int]') -> 'int':
n = len(nums)
max_sum = nums[0]
for i in range(1, n):
if nums[i - 1] > 0:
nums[i] += nums[i - 1]
max_sum = max(nums[i], max_sum)
return max_sum
26. 删除排序数组中的重复项
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
for i in range(len(nums))[::-1]:
if i-1 != -1:
if nums[i-1] == nums[i]:
del nums[i]
return len(nums)
def main():
n = [1]
a=Solution()
print(Solution.removeDuplicates(a,n))
if __name__ == '__main__':
main()
# Ps:
# python的GC也就是垃圾回收机制：
# 由于python都是引用，而python有GC机制，所以，del语句作用在变量上，而不是数据对象上。
# 将a和b del之后，1的引用计数仍然为1，所以不会被清除。
# a=1 # 对象 1 被 变量a引用，对象1的引用计数器为1
# b=a # 对象1 被变量b引用，对象1的引用计数器加1 = 2
# c=a #1对象1 被变量c引用，对象1的引用计数器加1 = 3
# del a #删除变量a，解除a对1的引用
# del b #删除变量b，解除b对1的引用
# print(c) #最终变量c仍然引用1
70. 爬楼梯
class Solution:
def climbStairs(self, n: int) -> int:
climb = {}
climb[0] = 0
climb[1] = 1
climb[2] = 2
for i in range(3,n+1):
climb[i] = climb[i-1] + climb[i-2]
return climb[n]
231. 2的幂
class Solution:
def isPowerOfTwo(self, n):
if n == 0:
return False
while n % 2 == 0:
n /= 2
return n == 1
141. 环形链表
class Solution:
def hasCycle(self, head: ListNode) -> bool:
if(head == None or head.next == None):
return False
node1 = head
node2 = head.next
while(node1 != node2):
if(node2 == None or node2.next == None):
return False
node1 = node1.next
node2 = node2.next.next
return True
20. 有效的括号
class Solution:
def isValid(self, s):
# The stack to keep track of opening brackets.
stack = []
# Hash map for keeping track of mappings. This keeps the code very clean.
# Also makes adding more types of parenthesis easier
mapping = {")": "(", "}": "{", "]": "["}
# For every bracket in the expression.
for char in s:
# If the character is an closing bracket
if char in mapping:
# Pop the topmost element from the stack, if it is non empty
# Otherwise assign a dummy value of '#' to the top_element variable
top_element = stack.pop() if stack else '#'
# The mapping for the opening bracket in our hash and the top
# element of the stack don't match, return False
if mapping[char] != top_element:
return False
else:
# We have an opening bracket, simply push it onto the stack.
stack.append(char)
# In the end, if the stack is empty, then we have a valid expression.
# The stack won't be empty for cases like ((()
return not stack
14. 最长公共前缀
class Solution:
def longestCommonPrefix(self, strs):
if len(strs) == 0:
return ''
for i in range(len(strs[0])):
c = strs[0][i]
for j in range(1,len(strs)):
if i == len(strs[j]) or strs[j][i] != c:
return strs[0][0:i]
return strs[0]
7. 整数反转
# 算法思路： 为对当前数取对 10 的余数，再一项项填入res尾部，即可完成 intint 翻转。
# 边界情况处理： intint 取值范围为，如果翻转数字溢出，则立即返回 0 。
# Python： 存储数字理论上是无限长度，因此每次计算完后判断res与of的大小关系即可；
# Java： 数字计算会溢出，因此要判断res和of / 10的大小关系（即确定再添 11 位是否会溢出）。
# Python的坑： 由于Python的 // 操作是向下取整，导致正负数取余 % 操作结果不一致，因此需要将原数字转为正数操作。
# 代码：
class Solution:
def reverse(self, x: int) -> int:
y, res = abs(x), 0
of = (1 << 31) - 1 if x > 0 else 1 << 31
while y != 0:
res = res * 10 + y % 10
if res > of: return 0
y //= 10
return res if x > 0 else -res
59. 螺旋矩阵 II
class Solution:
def generateMatrix(self, n: int) -> List[List[int]]:
l, r, t, b = 0, n - 1, 0, n - 1
mat = [[0 for _ in range(n)] for _ in range(n)]
num, tar = 1, n * n
while num <= tar:
for i in range(l, r + 1): # left to right
mat[t][i] = num
num += 1
t += 1
for i in range(t, b + 1): # top to bottom
mat[i][r] = num
num += 1
r -= 1
for i in range(r, l - 1, -1): # right to left
mat[b][i] = num
num += 1
b -= 1
for i in range(b, t - 1, -1): # bottom to top
mat[i][l] = num
num += 1
l += 1
return mat
回溯问题
经典的回溯算法解决的问题很多，如八皇后、0-1背包问题、图的着色、旅行商问题、全排列问题。
78. 子集
# 给定不含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
res = []
n = len(nums)
def helper(i, tmp):
res.append(tmp)
for j in range(i, n):
helper(j + 1,tmp + [nums[j]] ) #子串拼接
helper(0, [])
return res
90. 子集 II
# 给定一个可能包含重复元素的整数数组 nums，返回该数组所有可能的子集（幂集）。
# 说明：解集不能包含重复的子集。
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
n = len(nums)
res = []
nums.sort()
# 思路1
def helper1(idx, n, temp_list):
if temp_list not in res:
res.append(temp_list)
for i in range(idx, n):
helper1(i + 1, n, temp_list + [nums[i]])
# 思路2
def helper2(idx, n, temp_list):
res.append(temp_list)
for i in range(idx, n):
if i > idx and nums[i] == nums[i - 1]:
continue
helper2(i + 1, n, temp_list + [nums[i]])
helper2(0, n, [])
return res
39. 组合总和
# 给定一个无重复元素的数组 candidates 和一个目标数 target ，
# 找出 candidates 中所有可以使数字和为 target 的组合。
# candidates 中的数字可以无限制重复被选取。
class Solution:
def combinationSum(self, candidates, target):
if not candidates: return []
if min(candidates) > target: return []
candidates.sort()
res = []
def helper(candidates, target, temp_list):
if target == 0: res.append(temp_list)
if target < 0: return
for i in range(len(candidates)): # 可以重复出现多次
if candidates[i] > target: break
helper(candidates[i:], target - candidates[i], temp_list + [candidates[i]])
helper(candidates,target,[])
return res
46. 全排列
# 给定一个没有重复数字的序列，返回其所有可能的全排列。
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
if not nums:
return
res = []
n = len(nums)
visited = [0] * n
# def helper1(temp_list,length):
# if length == n:
# res.append(temp_list)
# for i in range(n):
# if visited[i] :
# continue
# visited[i] = 1
# helper1(temp_list+[nums[i]],length+1)
# visited[i] = 0
def helper2(nums,temp_list,length):
if length == n:
res.append(temp_list)
for i in range(len(nums)):
helper2(nums[:i]+nums[i+1:],temp_list+[nums[i]],length+1)
# helper1([],0)
helper2(nums, [], 0)
return res
47. 全排列 II
# 给定一个可包含重复数字的序列，返回所有不重复的全排列。
class Solution:
def permuteUnique(self, nums: List[int]) -> List[List[int]]:
if not nums:
return []
nums.sort()
n = len(nums)
visited = [0] * n
res = []
def helper1(temp_list, length):
# if length == n and temp_list not in res:
# res.append(temp_list)
if length == n:
res.append(temp_list)
for i in range(n):
if visited[i] or (i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]):
continue
visited[i] = 1
helper1(temp_list + [nums[i]], length + 1)
visited[i] = 0
# def helper2(nums, temp_list, length):
# if length == n and temp_list not in res:
# res.append(temp_list)
# for i in range(len(nums)):
# helper2(nums[:i] + nums[i + 1:], temp_list + [nums[i]], length + 1)
helper1([],0)
# helper2(nums, [], 0)
return res
7. 整数反转
# 算法思路： 为对当前数取对 10 的余数，再一项项填入res尾部，即可完成 intint 翻转。
# 边界情况处理： intint 取值范围为，如果翻转数字溢出，则立即返回 0 。
# Python： 存储数字理论上是无限长度，因此每次计算完后判断res与of的大小关系即可；
# Java： 数字计算会溢出，因此要判断res和of / 10的大小关系（即确定再添 11 位是否会溢出）。
# Python的坑： 由于Python的 // 操作是向下取整，导致正负数取余 % 操作结果不一致，因此需要将原数字转为正数操作。
# 代码：
class Solution:
def reverse(self, x: int) -> int:
y, res = abs(x), 0
of = (1 << 31) - 1 if x > 0 else 1 << 31
while y != 0:
res = res * 10 + y % 10
if res > of: return 0
y //= 10
return res if x > 0 else -res
# Tips:
# << 左移动运算符：运算数的各二进位全部左移若干位，由 << 右边的数字指定了移动的位数，高位丢弃，低位补0。
# a << 2 输出结果 240 ，二进制解释： 1111 0000
# >> 右移动运算符：把">>"左边的运算数的各二进位全部右移若干位，>> 右边的数字指定了移动的位数
# a >> 2 输出结果 15 ，二进制解释： 0000 1111
88. 合并两个有序数组
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
# two get pointers for nums1 and nums2
p1 = m - 1
p2 = n - 1
# set pointer for nums1
p = m + n - 1
# while there are still elements to compare
while p1 >= 0 and p2 >= 0:
if nums1[p1] < nums2[p2]:
nums1[p] = nums2[p2]
p2 -= 1
else:
nums1[p] = nums1[p1]
p1 -= 1
p -= 1
# add missing elements from nums2
nums1[:p2 + 1] = nums2[:p2 + 1]
class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
# The length of the input array
length = len(nums)
# The answer array to be returned
answer = [0]*length
# answer[i] contains the product of all the elements to the left
# Note: for the element at index '0', there are no elements to the left,
# so the answer[0] would be 1
answer[0] = 1
for i in range(1, length):
# answer[i - 1] already contains the product of elements to the left of 'i - 1'
# Simply multiplying it with nums[i - 1] would give the product of all
# elements to the left of index 'i'
answer[i] = nums[i - 1] * answer[i - 1]
# R contains the product of all the elements to the right
# Note: for the element at index 'length - 1', there are no elements to the right,
# so the R would be 1
R = 1;
for i in reversed(range(length)):
# For the index 'i', R would contain the
# product of all elements to the right. We update R accordingly
answer[i] = answer[i] * R
R *= nums[i]
return answer
215. 数组中的第K个最大元素
# 未排序的数组中找到第 k 个最大的元素
class Solution:
def findKthLargest(self, nums, k):
def partition(left, right, pivot_index):
pivot = nums[pivot_index]
# 1. move pivot to end
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
# 2. move all smaller elements to the left
store_index = left
for i in range(left, right):
if nums[i] < pivot:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
# 3. move pivot to its final place
nums[right], nums[store_index] = nums[store_index], nums[right]
return store_index
def select(left, right, k_smallest):
if left == right: # If the list contains only one element,
return nums[left] # return that element
# select a random pivot_index between
pivot_index = random.randint(left, right)
# find the pivot position in a sorted list
pivot_index = partition(left, right, pivot_index)
# the pivot is in its final sorted position
if k_smallest == pivot_index:
return nums[k_smallest]
# go left
elif k_smallest < pivot_index:
return select(left, pivot_index - 1, k_smallest)
# go right
else:
return select(pivot_index + 1, right, k_smallest)
# kth largest is (n - k)th smallest
return select(0, len(nums) - 1, len(nums) - k)
230. 二叉搜索树中第K小的元素
# 递归转换为迭代，这样可以加快速度，因为这样可以不用遍历整个树，可以在找到答案后停止。
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
230. 二叉搜索树中第K小的元素
# 递归转换为迭代，这样可以加快速度，因为这样可以不用遍历整个树，可以在找到答案后停止。
class Solution:
def kthSmallest(self, root: TreeNode, k: int) -> int:
stack = []
while True:
while root:
stack.append(root)
root = root.left
root = stack.pop()
k -= 1
if not k:
return root.val
root = root.right
89. 格雷编码
class Solution:
def grayCode(self, n: int) -> List[int]:
res, head = [0], 1
for i in range(n):
for j in range(len(res) - 1, -1, -1):
res.append(head + res[j])
head <<= 1
return res
236. 二叉树的最近公共祖先
class Solution:
def __init__(self):
self.ans = None
def lowestCommonAncestor(self, root, p, q):
def recurse_tree(current_node):
if not current_node:
return False
left = recurse_tree(current_node.left)
right = recurse_tree(current_node.right)
mid = current_node == p or current_node == q
# If any two of the three flags left, right or mid become True.
if mid + left + right >= 2:
self.ans = current_node #递归子树里第一个满足俩公共的节点
# Return True if either of the three bool values is True.
return mid or left or right
# Traverse the tree
recurse_tree(root)
return self.ans
class Solution:
def lowestCommonAncestor(self, root, p, q):
# Stack for tree traversal
stack = [root]
# Dictionary for parent pointers
parent = {root: None}
while p not in parent or q not in parent:
node = stack.pop()
# While traversing the tree, keep saving the parent pointers.
if node.left:
parent[node.left] = node
stack.append(node.left)
if node.right:
parent[node.right] = node
stack.append(node.right)
ancestors = set()
# Process all ancestors for node p using parent pointers.
while p:
ancestors.add(p)
p = parent[p]
# The first ancestor of q which appears in
# p's ancestor set() is their lowest common ancestor.
while q not in ancestors:
q = parent[q]
return q
215. 数组中的第K个最大元素
class Solution:
def findKthLargest(self, nums: List[int], k: int) -> int:
return heapq.nlargest(k, nums)[-1]
class Solution:
def findKthLargest(self, nums, k):
def partition(left, right, pivot_index):
pivot = nums[pivot_index]
# 1. move pivot to end
nums[pivot_index], nums[right] = nums[right], nums[pivot_index]
# 2. move all smaller elements to the left
store_index = left
for i in range(left, right):
if nums[i] < pivot:
nums[store_index], nums[i] = nums[i], nums[store_index]
store_index += 1
# 3. move pivot to its final place
nums[right], nums[store_index] = nums[store_index], nums[right]
return store_index
def select(left, right, k_smallest):
if left == right: # If the list contains only one element,
return nums[left] # return that element
# select a random pivot_index between
pivot_index = random.randint(left, right)
# find the pivot position in a sorted list
pivot_index = partition(left, right, pivot_index)
# the pivot is in its final sorted position
if k_smallest == pivot_index:
return nums[k_smallest]
# go left
elif k_smallest < pivot_index:
return select(left, pivot_index - 1, k_smallest)
# go right
else:
return select(pivot_index + 1, right, k_smallest)
# kth largest is (n - k)th smallest
return select(0, len(nums) - 1, len(nums) - k)
# 时间复杂度 : 平均情况 O(N)，最坏情况 O(N2)。
# 空间复杂度 : O(1)。
142. 环形链表 II
class Solution:
def detectCycle(self, head):
visited = set()
node = head
while node is not None:
if node in visited:
return node
else:
visited.add(node)
node = node.next
return None
class Solution(object):
def getIntersect(self, head):
tortoise = head
hare = head
while hare is not None and hare.next is not None:
tortoise = tortoise.next
hare = hare.next.next
if tortoise == hare:
return tortoise
return None
def detectCycle(self, head):
if head is None:
return None
intersect = self.getIntersect(head)
if intersect is None:
return None
ptr1 = head
ptr2 = intersect
while ptr1 != ptr2:
ptr1 = ptr1.next
ptr2 = ptr2.next
return ptr1
62. 不同路径
# 令 dp[i][j] 是到达 i, j 最多路径
# 动态方程：dp[i][j] = dp[i-1][j] + dp[i][j-1]
# 第一行 dp[0][j]，第一列 dp[i][0],边界为 1
# 时间复杂度：O(m*n)O(m∗n)
# 空间复杂度：O(m * n)O(m∗n)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
dp = [[1]*n] + [[1]+[0] * (n-1) for _ in range(m-1)]
for i in range(1, m):
for j in range(1, n):
dp[i][j] = dp[i-1][j] + dp[i][j-1]
return dp[-1][-1]
# 优化1：空间复杂度 O(2n)O(2n)
# 每次只需要 dp[i-1][j],dp[i][j-1]
# 只记录这两个数
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
pre = [1] * n
cur = [1] * n
for i in range(1, m):
for j in range(1, n):
cur[j] = pre[j] + cur[j-1]
pre = cur[:]
return pre[-1]
# 优化2：空间复杂度 O(n)
class Solution:
def uniquePaths(self, m: int, n: int) -> int:
cur = [1] * n
for i in range(1, m):
for j in range(1, n):
cur[j] += cur[j-1]
return cur[-1]
146. LRU缓存机制
# 方法 1：有序字典
# 实现 LRU 缓存机制，O(1) 时间内完成如下：
# 获取键 / 检查键是否存在
# 设置键
# 删除最先插入的键
# 前两个操作,哈希表在 O(1)时间。
# 有序字典，综合哈希表和链表，在 Python 中为 OrderedDict，在 Java 中为 LinkedHashMap。
# 首先，对于OrderedDict()中元素的存储，是等同把元素放入了一个可变数组一样
# popitem(last=False)输出标号为0的元素的popitem()，输出标号为len-1的元素。
# 但是这里如果修改了值，就好像a[key]=value，字典在数组中的顺序不变！
# move_to_end，将第一个元素移到最后位置上
from collections import OrderedDict
class LRUCache(OrderedDict):
def __init__(self, capacity):
self.capacity = capacity
def get(self, key):
if key not in self:
return - 1
self.move_to_end(key)
return self[key]
def put(self, key, value):
if key in self:
self.move_to_end(key)
self[key] = value
if len(self) > self.capacity:
self.popitem(last = False)
# LRUCache 对象会以如下语句构造和调用:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
# 时间复杂度：put 和 get 操作复杂度是 O(1)
# 有序字典中的所有操作：get/in/set/move_to_end/popitem（get/containsKey/put/remove）都可以在常数时间内完成。
# 空间复杂度：O(capacity)，因为空间只用于有序字典存储最多 capacity + 1 个元素。
# 方法 2：哈希表 + 双向链表
# 哈希表，辅以双向链表记录键值对的信息。
# O(1) 时间内完成 put 和 get 操作，
# 支持 O(1)删除第一个添加的节点。
# 不需要额外信息删除节点，常数时间内从头部或尾部插入删除节点。
# 双向链表实现中，伪头部和伪尾部标记界限，更新的时不需要检查null 节点。
class DLinkedNode():
def __init__(self):
self.key = 0
self.value = 0
self.prev = None
self.next = None
class LRUCache():
def _add_node(self, node):
node.prev = self.head
node.next = self.head.next
self.head.next.prev = node
self.head.next = node
def _remove_node(self, node):
prev = node.prev
new = node.next
prev.next = new
new.prev = prev
def _move_to_head(self, node):
"""
Move certain node in between to the head.
"""
self._remove_node(node)
self._add_node(node)
def _pop_tail(self):
res = self.tail.prev
self._remove_node(res)
return res
def __init__(self, capacity):
self.cache = {}
self.size = 0
self.capacity = capacity
self.head, self.tail = DLinkedNode(), DLinkedNode()
self.head.next = self.tail
self.tail.prev = self.head
def get(self, key):
node = self.cache.get(key, None)
if not node:
return -1
# move the accessed node to the head;
self._move_to_head(node)
return node.value
def put(self, key, value):
node = self.cache.get(key)
if not node:
newNode = DLinkedNode()
newNode.key = key
newNode.value = value
self.cache[key] = newNode
self._add_node(newNode)
self.size += 1
if self.size > self.capacity:
# pop the tail
tail = self._pop_tail()
del self.cache[tail.key]
self.size -= 1
else:
# update the value.
node.value = value
self._move_to_head(node)
4. 寻找两个有序数组的中位数
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
n1 = len(nums1)
n2 = len(nums2)
if n1 > n2:
return self.findMedianSortedArrays(nums2,nums1)
k = (n1 + n2 + 1)//2
left = 0
right = n1
while left < right :
m1 = left +(right - left)//2
m2 = k - m1
if nums1[m1] < nums2[m2-1]:
left = m1 + 1
else:
right = m1
m1 = left
m2 = k - m1
c1 = max(nums1[m1-1] if m1 > 0 else float("-inf"), nums2[m2-1] if m2 > 0 else float("-inf") )
if (n1 + n2) % 2 == 1:
return c1
c2 = min(nums1[m1] if m1 < n1 else float("inf"), nums2[m2] if m2 <n2 else float("inf"))
return (c1 + c2) / 2
124. 二叉树中的最大路径和
# 124. 二叉树中的最大路径和
class Solution:
def maxPathSum(self, root: TreeNode) -> int:
def max_gain(node):
nonlocal max_sum
# global全局变量；
# nonlocal上一级函数中局部变量，只能用于嵌套函数中，且外层定义了相应局部变量；
if not node:
return 0
left_gain = max(max_gain(node.left), 0)
right_gain = max(max_gain(node.right), 0)
price_newpath = node.val + left_gain + right_gain
max_sum = max(max_sum, price_newpath)
return node.val + max(left_gain, right_gain)
max_sum = float('-inf')
max_gain(root)
return max_sum
23. 合并K个排序链表
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
amount = len(lists)
interval = 1
while interval < amount:
for i in range(0, amount - interval, interval * 2):
lists[i] = self.merge2Lists(lists[i], lists[i + interval])
interval *= 2
return lists[0] if amount > 0 else lists
def merge2Lists(self, l1, l2):
head = point = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l1
l1 = point.next.next
point = point.next
if not l1:
point.next=l2
else:
point.next=l1
return head.next
23. 合并K个排序链表
# 将 k 个链表配对并将同一对中的链表合并
# 第一轮合并以后，k 个链表被合并成了 k/2 个链表
class Solution:
def mergeKLists(self, lists: List[ListNode]) -> ListNode:
amount = len(lists)
interval = 1
while interval < amount:
for i in range(0, amount - interval, interval * 2):
lists[i] = self.merge2Lists(lists[i], lists[i + interval])
# 0 2 4 6 8 & 1 3 5 7 9
# 0 2 4 6 8 & 1 3 5 7 9
interval *= 2
return lists[0] if amount > 0 else lists
def merge2Lists(self, l1, l2):
head = point = ListNode(0)
while l1 and l2:
if l1.val <= l2.val:
point.next = l1
l1 = l1.next
else:
point.next = l2
l2 = l1
l1 = point.next.next
point = point.next
if not l1:
point.next=l2
else:
point.next=l1
return head.next
33. 搜索旋转排序数组
class Solution:
def search(self, nums: List[int], target: int) -> int:
def find_rotate_index(left, right):
if nums[left] < nums[right]: return 0
while left <= right:
pivot = (left + right) // 2
if nums[pivot] > nums[pivot + 1]: return pivot + 1
else:
if nums[pivot] < nums[left]: right = pivot - 1
else: left = pivot + 1
def searchf(left, right):
while left <= right:
pivot = (left + right) // 2
if nums[pivot] == target: return pivot
else:
if target < nums[pivot]: right = pivot - 1
else:left = pivot + 1
return -1
n = len(nums)
if n == 0: return -1
if n == 1: return 0 if nums[0] == target else -1
rotate_index = find_rotate_index(0, n - 1)
if nums[rotate_index] == target: return rotate_index
if rotate_index == 0: return searchf(0, n - 1)
if target < nums[0]: return searchf(rotate_index, n - 1)
return searchf(0, rotate_index)
124. 二叉树中的最大路径和
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
R, C = len(matrix), len(matrix[0])
seen = [[False] * C for _ in matrix]
ans = []
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
r = c = di = 0
for _ in range(R * C):
ans.append(matrix[r][c])
seen[r][c] = True
cr, cc = r + dr[di], c + dc[di]
if 0 <= cr < R and 0 <= cc < C and not seen[cr][cc]:
r, c = cr, cc
else:
di = (di + 1) % 4
r, c = r + dr[di], c + dc[di]
return ans
15. 三数之和
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res, k = [], 0
for k in range(len(nums) - 2):
if nums[k] > 0: break # 1. because of j > i > k.
if k > 0 and nums[k] == nums[k - 1]: continue # 2. skip the same `nums[k]`.
i, j = k + 1, len(nums) - 1
while i < j: # 3. double pointer
s = nums[k] + nums[i] + nums[j]
if s < 0:
i += 1
while i < j and nums[i] == nums[i - 1]: i += 1
elif s > 0:
j -= 1
while i < j and nums[j] == nums[j + 1]: j -= 1
else:
res.append([nums[k], nums[i], nums[j]])
i += 1
j -= 1
while i < j and nums[i] == nums[i - 1]: i += 1
while i < j and nums[j] == nums[j + 1]: j -= 1
return res
54. 螺旋矩阵
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix: return []
R, C = len(matrix), len(matrix[0])
seen = [[False] * C for _ in matrix]
ans = []
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]
r = c = di = 0
for _ in range(R * C):
ans.append(matrix[r][c])
seen[r][c] = True
cr, cc = r + dr[di], c + dc[di]
if 0 <= cr < R and 0 <= cc < C and not seen[cr][cc]:
r, c = cr, cc
else:
di = (di + 1) % 4
r, c = r + dr[di], c + dc[di]
return ans
61. 旋转链表
class Solution:
def rotateRight(self, head: 'ListNode', k: 'int') -> 'ListNode':
# base cases
if not head:
return None
if not head.next:
return head
# close the linked list into the ring
old_tail = head
n = 1
while old_tail.next:
old_tail = old_tail.next
n += 1
old_tail.next = head
# find new tail : (n - k % n - 1)th node
# and new head : (n - k % n)th node
new_tail = head
for i in range(n - k % n - 1):
new_tail = new_tail.next
new_head = new_tail.next
# break the ring
new_tail.next = None
return new_head
16. 最接近的三数之和
from typing import List
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
size = len(nums)
# 特判
if size < 3:
return []
# 初始化，因为找最小值，因此把初始值设置成实数的最大值
diff = float('inf')
# 排序是前提
nums.sort()
for i in range(size - 2):
# 常见的剪枝操作
if i > 0 and nums[i] == nums[i - 1]:
continue
# 双指针：指针对撞
left = i + 1
right = size - 1
while left < right:
s = nums[i] + nums[left] + nums[right]
if abs(s - target) < diff:
diff = abs(s - target)
res = s
# 不管是变小还是变大，尝试的作用是让 s 与 target 更接近
# 即 s 与 target 的绝对值之差越来越小
if s > target:
# 如果大了，尝试右边界收缩一格，让 target 变小
right -= 1
elif s < target:
# 如果小了，尝试左边界收缩一格，让 target 变大
left += 1
else:
# 如果已经等于 target 的话, 肯定是最接近的，根据题目要求，返回这三个数的和
return target
return res
148. 排序链表
class Solution:
def sortList(self, head: ListNode) -> ListNode:
if not head or not head.next: return head # termination.
# cut the LinkedList at the mid index.
slow, fast = head, head.next
while fast and fast.next:
fast, slow = fast.next.next, slow.next
mid, slow.next = slow.next, None # save and cut.
# recursive for cutting.
left, right = self.sortList(head), self.sortList(mid)
# merge `left` and `right` linked list and return it.
h = res = ListNode(0)
while left and right:
if left.val < right.val: h.next, left = left, left.next
else: h.next, right = right, right.next
h = h.next
h.next = left if left else right
return res.next
class Solution:
def sortList(self, head: ListNode) -> ListNode:
h, length, intv = head, 0, 1
while h: h, length = h.next, length + 1
res = ListNode(0)
res.next = head
# merge the list in different intv.
while intv < length:
pre, h = res, res.next
while h:
# get the two merge head `h1`, `h2`
h1, i = h, intv
while i and h: h, i = h.next, i - 1
if i: break # no need to merge because the `h2` is None.
h2, i = h, intv
while i and h: h, i = h.next, i - 1
c1, c2 = intv, intv - i # the `c2`: length of `h2` can be small than the `intv`.
# merge the `h1` and `h2`.
while c1 and c2:
if h1.val < h2.val: pre.next, h1, c1 = h1, h1.next, c1 - 1
else: pre.next, h2, c2 = h2, h2.next, c2 - 1
pre = pre.next
pre.next = h1 if c1 else h2
while c1 > 0 or c2 > 0: pre, c1, c2 = pre.next, c1 - 1, c2 - 1
pre.next = h
intv *= 2
return res.next
