Shortest-LeetCode-Python-Solutions

前言

🏆 里程碑

推荐

解析

1. Two Sum 2行

class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:
 d = {target - n: i for i, n in enumerate(nums)}
 return [[d[n], i] for i, n in enumerate(nums) if n in d and d[n] > i][0]

2. Add Two Numbers 5行

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def addTwoNumbers(self, l1: ListNode, l2: ListNode, carry=0) -> ListNode:
 if not (l1 or l2): return ListNode(1) if carry else None
 l1, l2 = l1 or ListNode(0), l2 or ListNode(0)
 val = l1.val + l2.val + carry
 l1.val, l1.next = val % 10, self.addTwoNumbers(l1.next, l2.next, val > 9)
 return l1

3. Longest Substring Without Repeating Characters 3行

class Solution:
 def lengthOfLongestSubstring(self, s: str) -> int:
 b, m, d = 0, 0, {}
 for i, l in enumerate(s): b, m, d[l] = max(b, d.get(l, -1) + 1), max(m, i - b), i
 return max(m, len(s) - b)

4. Median of Two Sorted Arrays 5行

class Solution:
 def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
 a, b, m = *sorted((nums1, nums2), key=len), (len(nums1) + len(nums2) - 1) // 2
 self.__class__.__getitem__ = lambda self, i: m-i-1 < 0 or a[i] >= b[m-i-1]
 i = bisect.bisect_left(self, True, 0, len(a))
 r = sorted(a[i:i+2] + b[m-i:m-i+2])
 return (r[0] + r[1 - (len(a) + len(b)) % 2]) / 2

5. Longest Palindromic Substring 5行

class Solution:
 def longestPalindrome(self, s: str) -> str:
 r = ''
 for i, j in [(i, j) for i in range(len(s)) for j in (0, 1)]:
 while i > -1 and i + j < len(s) and s[i] == s[i + j]: i, j = i - 1, j + 2
 r = max(r, s[i + 1:i + j], key=len)
 return '' if not s else r

7. Reverse Integer 2行

class Solution:
 def reverse(self, x):
 r = x // max(1, abs(x)) * int(str(abs(x))[::-1])
 return r if r.bit_length() < 32 or r == -2**31 else 0

8. String to Integer (atoi) 1行

class Solution:
 def myAtoi(self, s: str) -> int:
 return max(min(int(*re.findall('^[\+\-]?\d+', s.lstrip())), 2**31 - 1), -2**31)

9. Palindrome Number 1行

class Solution:
 def isPalindrome(self, x: int) -> bool:
 return str(x) == str(x)[::-1]

class Solution:
 def isPalindrome(self, x: int) -> bool:
 r = list(map(lambda i: int(10**-i * x % 10), range(int(math.log10(x)), -1, -1))) if x > 0 else [0, x]
 return r == r[::-1]

11. Container With Most Water 3行

class Solution:
 def maxArea(self, height: List[int]) -> int:
 res, l, r = 0, 0, len(height) - 1
 while l < r: res, l, r = (max(res, height[l] * (r - l)), l + 1, r) if height[l] < height[r] else (max(res, height[r] * (r - l)), l, r - 1)
 return res

13. Roman to Integer 2行

class Solution:
 def romanToInt(self, s: str) -> int:
 d = {'I':1, 'IV':3, 'V':5, 'IX':8, 'X':10, 'XL':30, 'L':50, 'XC':80, 'C':100, 'CD':300, 'D':500, 'CM':800, 'M':1000}
 return sum([d.get(s[max(i-1, 0):i+1], d[n]) for i, n in enumerate(s)])

14. Longest Common Prefix 2行

class Solution:
 def longestCommonPrefix(self, strs: List[str]) -> str:
 r = [len(set(c)) == 1 for c in zip(*strs)] + [0]
 return strs[0][:r.index(0)] if strs else ''

15. 3Sum 5行

class Solution:
 def threeSum(self, nums: List[int]) -> List[List[int]]:
 nums, r = sorted(nums), set()
 for i in [i for i in range(len(nums)-2) if i < 1 or nums[i] > nums[i-1]]:
 d = {-nums[i]-n: j for j, n in enumerate(nums[i + 1:])}
 r.update([(nums[i], n, -nums[i]-n) for j, n in enumerate(nums[i+1:]) if n in d and d[n] > j])
 return list(map(list, r))

16. 3Sum Closest 7行

class Solution:
 def threeSumClosest(self, nums: List[int], target: int) -> int:
 nums, r, end = sorted(nums), float('inf'), len(nums) - 1
 for c in range(len(nums) - 2):
 i, j = max(c + 1, bisect.bisect_left(nums, target - nums[end] - nums[c], c + 1, end) - 1), end
 while r != target and i < j:
 s = nums[c] + nums[i] + nums[j]
 r, i, j = min(r, s, key=lambda x: abs(x - target)), i + (s < target), j - (s > target)
 return r

20. Valid Parentheses 2行

class Solution:
 def isValid(self, s: str) -> bool:
 while any(('()' in s, '[]' in s, '{}' in s)): s = s.replace('()', '').replace('[]', '').replace('{}', '')
 return not s

21. Merge Two Sorted Lists 4行

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
 if l1 and l2:
 if l1.val > l2.val: l1, l2 = l2, l1
 l1.next = self.mergeTwoLists(l1.next, l2)
 return l1 or l2

23. Merge k Sorted Lists 4行

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def mergeKLists(self, lists: List[ListNode]) -> ListNode:
 r, n, p = [], lists and lists.pop(), None
 while lists or n: r[len(r):], n = ([n], n.next or lists and lists.pop()) if n else ([], lists.pop())
 for n in sorted(r, key=lambda x: x.val, reverse=True): n.next, p = p, n
 return n if r else []

26. Remove Duplicates from Sorted Array 3行

class Solution:
 def removeDuplicates(self, nums: List[int]) -> int:
 for i in range(len(nums)-1, 0, -1):
 if nums[i] == nums[i-1]: nums.pop(i)
 return len(nums)

28. Implement strStr() 1行

class Solution:
 def strStr(self, haystack: str, needle: str) -> int:
		return haystack.find(needle)

33. Search in Rotated Sorted Array 3行

class Solution:
 def search(self, nums, target):
 self.__class__.__getitem__ = lambda self, m: not(target < nums[0] <= nums[m] or nums[0] <= nums[m] < target or nums[m] < target <= nums[-1])
 i = bisect.bisect_left(self, True, 0, len(nums))
 return i if target in nums[i:i+1] else -1

38. Count and Say 1行

class Solution:
 def countAndSay(self, n: int) -> str:
 return '1' * (n is 1) or re.sub(r'(.)1円*', lambda m: str(len(m.group())) + m.group(1), self.countAndSay(n - 1))

43. Multiply Strings 5行

class Solution:
 def multiply(self, num1: str, num2: str) -> str:
 d = {}
 for i, n1 in enumerate(num1[::-1]):
 for j, n2 in enumerate(num2[::-1]): d[i + j] = d.get(i + j, 0) + int(n1) * int(n2)
 for k in [*d]: d[k + 1], d[k] = d.get(k + 1, 0) + int(d[k] * 0.1), d[k] % 10
 return re.sub('^0*', '', ''.join(map(str, d.values()))[::-1]) or '0'

46. Permutations 1行

class Solution:
 def permute(self, nums: List[int]) -> List[List[int]]:
 return [[n] + sub for i, n in enumerate(nums) for sub in self.permute(nums[:i] + nums[i+1:])] or [nums]

53. Maximum Subarray 2行

class Solution:
 def maxSubArray(self, nums):
 from functools import reduce
 return reduce(lambda r, x: (max(r[0], r[1]+x), max(r[1]+x,x)), nums, (max(nums), 0))[0]

54. Spiral Matrix 1行

class Solution:
 def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
 return matrix and [*matrix.pop(0)] + self.spiralOrder([*zip(*matrix)][::-1])

58. Length of Last Word 1行

class Solution:
 def lengthOfLastWord(self, s: str) -> int:
 return len(s.strip(' ').split(' ')[-1])

59. Spiral Matrix II 3行

class Solution:
 def generateMatrix(self, n: int) -> List[List[int]]:
 r, n = [[n**2]], n**2
 while n > 1: n, r = n - len(r), [[*range(n - len(r), n)]] + [*zip(*r[::-1])]
 return r

|| => |9| => |8| |6 7| |4 5| |1 2 3|
		 |9| => |9 8| => |9 6| => |8 9 4|
				 |8 7| |7 6 5|

61. Rotate List 4行

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def rotateRight(self, head: ListNode, k: int) -> ListNode:
 l = []
 while head: l[len(l):], head = [head], head.next
 if l: l[-1].next, l[-1 - k % len(l)].next = l[0], None
 return l[- k % len(l)] if l else None

62. Unique Paths 1行

class Solution:
 def uniquePaths(self, m: int, n: int) -> int:
 return int(math.factorial(m+n-2)/math.factorial(m-1)/math.factorial(n-1))

66. Plus One 1行

class Solution:
 def plusOne(self, digits: List[int]) -> List[int]:
 return list(map(int, str(int(''.join(map(str, digits))) + 1)))

69. Sqrt(x) 1行

class Solution:
 def mySqrt(self, x: int) -> int:
 return int(x ** 0.5)

class Solution:
 def mySqrt(self, x: int) -> int:
 r = x
 while r*r > x:
 r = (r + x/r) // 2
 return int(r)

70. Climbing Stairs 2行

class Solution:
 def climbStairs(self, n: int) -> int:
 from functools import reduce
 return reduce(lambda r, _: (r[1], sum(r)), range(n), (1, 1))[0]

78. Subsets 2行

class Solution:
 def subsets(self, nums: List[int]) -> List[List[int]]:
 from itertools import combinations
 return sum([list(combinations(nums, i)) for i in range(len(nums) + 1)], [])

88. Merge Sorted Array 1行

class Solution:
 def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
 """
 Do not return anything, modify nums1 in-place instead.
 """
 while n > 0: nums1[m+n-1], m, n = (nums1[m-1], m-1, n) if m and nums1[m-1] > nums2[n-1] else (nums2[n-1], m, n-1)

89. Gray Code 1行

class Solution:
 def grayCode(self, n: int) -> List[int]:
 return (lambda r: r + [x | 1<<n-1 for x in r[::-1]])(self.grayCode(n-1)) if n else [0]

class Solution:
 def grayCode(self, n: int) -> List[int]:
 return [i ^ i >> 1 for i in range(1 << n)]

94. Binary Tree Inorder Traversal 2行

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
 def inorderTraversal(self, root: TreeNode) -> List[int]:
 f = self.inorderTraversal
 return f(root.left) + [root.val] + f(root.right) if root else []

class Solution:
 def inorderTraversal(self, root: TreeNode) -> List[int]:
 r, stack = [], []
 while True:
 while root:
 stack.append(root)
 root = root.left
 if not stack:
 return r
 node = stack.pop()
 r.append(node.val)
 root = node.right
 return r

104. Maximum Depth of Binary Tree 1行

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
 def maxDepth(self, root: TreeNode) -> int:
 return max(map(self.maxDepth,(root.left, root.right))) + 1 if root else 0

121. Best Time to Buy and Sell Stock 2行

class Solution:
 def maxProfit(self, prices: List[int]) -> int:
 from functools import reduce
 return reduce(lambda r, p: (max(r[0], p-r[1]), min(r[1], p)), prices, (0, float('inf')))[0]

122. Best Time to Buy and Sell Stock II 2行

class Solution:
 def maxProfit(self, prices: List[int]) -> int:
 return sum(b - a for a, b in zip(prices, prices[1:]) if b > a)

124. Binary Tree Maximum Path Sum 4行

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
 def maxPathSum(self, root: TreeNode, ok=True) -> int:
 if not root: return 0
 l, r = self.maxPathSum(root.left, False), self.maxPathSum(root.right, False)
 self.max = max(getattr(self, 'max', float('-inf')), l + root.val + r)
 return self.max if ok else max(root.val + max(l, r), 0)

136. Single Number 2行

class Solution:
 def singleNumber(self, nums: List[int]) -> int:
 from functools import reduce
 return reduce(int.__xor__, nums)

141. Linked List Cycle 2行

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
 def hasCycle(self, head):
 """
 :type head: ListNode
 :rtype: bool
 """
 while head and head.val != None: head.val, head = None, head.next
 return head != None

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
 def hasCycle(self, head):
 slow = fast = head
 while fast and fast.next:
 fast = fast.next.next
 slow = slow.next
 if slow == fast:
 return True
 return False

142. Linked List Cycle II 5行

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
 def detectCycle(self, head):
 """
 :type head: ListNode
 :rtype: ListNode
 """
 s = {None}
 while head not in s:
 s.add(head)
 head = head.next
 return head

146. LRU Cache 7行

class LRUCache(object):
 def __init__(self, capacity):
 self.od, self.cap = collections.OrderedDict(), capacity
 def get(self, key):
 if key not in self.od: return -1
 self.od.move_to_end(key)
 return self.od[key]
 def put(self, key, value):
 if key in self.od: del self.od[key]
 elif len(self.od) == self.cap: self.od.popitem(False)
 self.od[key] = value
# Your LRUCache object will be instantiated and called as such:
# obj = LRUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)

148. Sort List 10行

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def sortList(self, head: ListNode) -> ListNode:
 if not (head and head.next): return head
 pre, slow, fast = None, head, head
 while fast and fast.next: pre, slow, fast = slow, slow.next, fast.next.next
 pre.next = None
 return self.mergeTwoLists(*map(self.sortList, (head, slow)))
 
 def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
 if l1 and l2:
 if l1.val > l2.val: l1, l2 = l2, l1
 l1.next = self.mergeTwoLists(l1.next, l2)
 return l1 or l2

155. Min Stack 每个1行

class MinStack:
 
 def __init__(self):
 self.data = [(None, float('inf'))]
 def push(self, x: 'int') -> 'None':
 self.data.append((x, min(x, self.data[-1][1])))
 def pop(self) -> 'None':
 if len(self.data) > 1: self.data.pop()
 def top(self) -> 'int':
 return self.data[-1][0]
 def getMin(self) -> 'int':
 return self.data[-1][1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

160. Intersection of Two Linked Lists 3行

# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution(object):
 def getIntersectionNode(self, headA, headB):
 """
 :type head1, head1: ListNode
 :rtype: ListNode
 """
 a, b = (headA, headB) if headA and headB else (None, None)
 while a != b: a, b = not a and headB or a.next, not b and headA or b.next
 return a

169. Majority Element 1行

class Solution:
 def majorityElement(self, nums: List[int]) -> int:
 return sorted(nums)[len(nums) // 2]

198. House Robber 2行

class Solution:
 def rob(self, nums: List[int]) -> int:
 from functools import reduce
 return reduce(lambda r, n: (max(r[0], n + r[1]), r[0]), nums, (0, 0))[0]

class Solution:
 def rob(self, nums: List[int]) -> int:
 last, now = 0, 0
 for i in nums:
 last, now = now, max(last + i, now)
 return now

206. Reverse Linked List 2行

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def reverseList(self, head: ListNode, tail=None) -> ListNode:
 if head: head.next, tail, head = tail, head, head.next
 return self.reverseList(head, tail) if head else tail

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def reverseList(self, head: ListNode) -> ListNode:
 p = None
 while head: head.next, p, head = p, head, head.next
 return p

215. Kth Largest Element in an Array 1行

class Solution:
 def findKthLargest(self, nums: List[int], k: int) -> int:
 return sorted(nums)[-k]

217. Contains Duplicate 1行

class Solution:
 def containsDuplicate(self, nums: List[int]) -> bool:
 return len(nums) != len(set(nums))

230. Kth Smallest Element in a BST 3行

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
 def kthSmallest(self, root, k):
 from itertools import chain, islice
 def gen(x): yield from chain(gen(x.left), [x.val], gen(x.right)) if x else ()
 return next(islice(gen(root), k - 1, k))

231. 2的幂 1行

class Solution:
 def isPowerOfTwo(self, n: int) -> bool:
	"""
	:type n: int
	:rtype: bool
	"""
 return n > 0 and n & n - 1 == 0

235. Lowest Common Ancestor of a Binary Search Tree 2行

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
 def lowestCommonAncestor(self, root, p, q):
 while (root.val - p.val) * (root.val - q.val) > 0: root = (root.left, root.right)[p.val > root.val]
 return root

236. Lowest Common Ancestor of a Binary Tree 2行

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
 def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
 l, r = map(lambda x: x and self.lowestCommonAncestor(x, p, q), (root.left, root.right))
 return (root in (p, q) or l and r) and root or l or r

237. Delete Node in a Linked List 1行

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def deleteNode(self, node):
 """
 :type node: ListNode
 :rtype: void Do not return anything, modify node in-place instead.
 """
 node.val, node.next = node.next.val, node.next.next

238. Product of Array Except Self 5行

class Solution:
 def productExceptSelf(self, nums: List[int]) -> List[int]:
 res, l, r = [1] * len(nums), 1, 1
 for i, j in zip(range(len(nums)), reversed(range(len(nums)))):
 res[i], l = res[i] * l, l * nums[i]
 res[j], r = res[j] * r, r * nums[j]
 return res

268. Missing Number 1行

class Solution:
 def missingNumber(self, nums: List[int]) -> int:
 return int(len(nums) * (len(nums) + 1) / 2 - sum(nums))

283. Move Zeroes 1行

class Solution:
 def moveZeroes(self, nums: List[int]) -> None:
 """
 Do not return anything, modify nums in-place instead.
 """
 nums.sort(key=bool, reverse=True)

class Solution:
 def moveZeroes(self, nums: List[int]) -> None:
 """
 Do not return anything, modify nums in-place instead.
 """
 i = 0
 for i, n in enumerate(filter(lambda x: x, nums)):
 nums[i] = n
 for i in range(i + 1, len(nums)):
 nums[i] = 0

292. Nim Game 1行

class Solution:
 def canWinNim(self, n: int) -> bool:
 return bool(n % 4)

328. Odd Even Linked List 6行

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def oddEvenList(self, head: ListNode) -> ListNode:
 if not head or not head.next: return head
 r, odd, p, head = head, head, head.next, head.next.next
 while head:
 odd.next, head.next, p.next = head, odd.next, head.next
 p, odd, head = p.next, head, p.next and p.next.next
 return r

344. Reverse String 1行

class Solution:
 def reverseString(self, s: List[str]) -> None:
 """
 Do not return anything, modify s in-place instead.
 """
 s.reverse()

412. Fizz Buzz 1行

class Solution:
 def fizzBuzz(self, n):
 return ['Fizz' * (not i % 3) + 'Buzz' * (not i % 5) or str(i) for i in range(1, n+1)]

414. Third Maximum Number 3行

class Solution:
 def thirdMax(self, nums: List[int]) -> int:
 nums = set(nums)
 for _ in range((2, 0)[len(nums) < 3]): nums.remove(max(nums))
 return max(nums)

557. Reverse Words in a String III 1行

class Solution:
 def reverseWords(self, s: str) -> str:
 return ' '.join(s.split(' ')[::-1])[::-1]

771. Jewels and Stones 1行

class Solution:
 def numJewelsInStones(self, J: str, S: str) -> int:
 return sum(S.count(i) for i in J)

938. Range Sum of BST 1行

# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
 def rangeSumBST(self, root: TreeNode, L: int, R: int) -> int:
 return root and root.val * (L <= root.val <= R) + self.rangeSumBST(root.left, L, R) + self.rangeSumBST(root.right, L, R) or 0

953. Verifying an Alien Dictionary 1行

class Solution(object):
 def isAlienSorted(self, words, order):
 return words == sorted(words, key=lambda w: [order.index(x) for x in w])

专题

数组

238. Product of Array Except Self 双指针

class Solution:
 def productExceptSelf(self, nums: List[int]) -> List[int]:
 n = len(nums)
 res = [1] * n
 
 l = 1
 for i in range(n):
 res[i] *= l
 l *= nums[i]
 
 r = 1
 for j in range(n - 1, -1, -1):
 res[j] *= r
 r *= nums[j]
 
 return res

哈希表

1. Two Sum 字典

class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:
	d = {}
	for i, n in enumerate(nums): 
	 if n in d: return [d[n], i]
	 d[target-n] = i

链表

206. Reverse Linked List 迭代遍历

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
 def reverseList(self, head: ListNode) -> ListNode:
 p = None
 while head:
 head.next, head, p = p, head.next, head
 return p

数学

268. Missing Number 等差数列

class Solution:
 def missingNumber(self, nums: List[int]) -> int:
 n = len(nums)
 s = sum(nums)
 n += 1
 return n * (n - 1) // 2 - s

双指针

344. Reverse String 双指针

class Solution:
 def reverseString(self, s: List[str]) -> None:
 """
 Do not return anything, modify s in-place instead.
 """
 i, j = 0, len(s) - 1
 while i < j:
 s[i], s[j] = s[j], s[i]
 i += 1
 j -= 1

解法汇总贡献者