Review List 2
3 min readApr 15, 2020
Naive O(n²log n) TLE
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
#return [[len(nums)]*3]
nums.sort()
res = set()
for i in range(len(nums)-2):
a = nums[i]
if a>0:break
for j in range(i+1, len(nums)-1):
b = nums[j]
c = -(a+b)
if c < nums[j+1]:
continue
idx = bisect.bisect_left(nums[j+1:], c)
if idx+j+1>=len(nums) or nums[idx+j+1]!=c:
continue
else:res.add((a,b,c))
return [list(r) for r in res]Improved O(n² log n) get AC
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
cnt = collections.Counter(nums)
same3 = set()
same2 = set()
others = set()
if cnt[0]>=3:same3.add((0,0,0))
for a in cnt:
if cnt[a]>=2 and a!=0 and (0-2*a) in cnt:
same2.add(tuple(sorted([a, a, 0-2*a])))
candidates = sorted(cnt.keys())
for i in range(len(candidates)):
for j in range(i+1, len(candidates)):
a, b = candidates[i], candidates[j]
c = 0-(a+b)
if c<=candidates[j]:continue
idx = bisect.bisect(candidates, c)
if candidates[idx-1]==c:
others.add(tuple(sorted([a,b,c])))
res = same3 | same2 | others
return [list(r) for r in res]A better one from here
class Solution(object):
def threeSum(self, nums):
res = []
nums.sort()
length = len(nums)
for i in xrange(length-2): #[8]
if nums[i]>0: break #[7]
if i>0 and nums[i]==nums[i-1]: continue #[1]
l, r = i+1, length-1 #[2]
while l<r:
total = nums[i]+nums[l]+nums[r]
if total<0: #[3]
l+=1
elif total>0: #[4]
r-=1
else: #[5]
res.append([nums[i], nums[l], nums[r]])
while l<r and nums[l]==nums[l+1]: #[6]
l+=1
while l<r and nums[r]==nums[r-1]: #[6]
r-=1
l+=1
r-=1
return resImproved one
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
res = []
if len(nums)<=2:return []
N = len(nums)
for i in range(N-2):
l, r = i+1, N-1
# if the current number is the same as previous one, we have already searched the result. skip.
if i>0 and nums[i]==nums[i-1]:continue
a = nums[i]
# earlier stop
if a>0:break
twosum = -a
while l<r:
b, c = nums[l], nums[r]
if b+c==twosum:
res.append([a,b,c])
# go to find next different number
while l<r and nums[l]==nums[l+1]:
l+=1
while l<r and nums[r-1]==nums[r]:
r-=1
l += 1
r -= 1
elif b+c <twosum:
l+=1
else:
r-=1
return resNaive solution
class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
if not matrix or not matrix[0]:return []
R, C = len(matrix), len(matrix[0])
d = [(0,1),(1,0),(-1,0),(0,-1)]
res = [matrix[0][0]]
k = 0
i, j = 0, 0
seen = {(0,0)}
while True:
#print(res)
if len(res)==R*C:break
k %= 4
di, dj = d[k]
#print(di, dj)
i, j = i+di, j+dj
#print(i,j)
if 0<=i<R and 0<=j<C and (i,j) not in seen:
seen.add((i,j))
res.append(matrix[i][j])
else:
i, j = i-di, j-dj
k += 1
return resA better way from stefan
spiral_order([[1, 2, 3],
[4, 5, 6],
[7, 8, 9]])
= [1, 2, 3] + spiral_order([[6, 9],
[5, 8],
[4, 7]])
= [1, 2, 3] + [6, 9] + spiral_order([[8, 7],
[5, 4]])
= [1, 2, 3] + [6, 9] + [8, 7] + spiral_order([[4],
[5]])
= [1, 2, 3] + [6, 9] + [8, 7] + [4] + spiral_order([[5]])
= [1, 2, 3] + [6, 9] + [8, 7] + [4] + [5] + spiral_order([])
= [1, 2, 3] + [6, 9] + [8, 7] + [4] + [5] + []
= [1, 2, 3, 6, 9, 8, 7, 4, 5]class Solution:
def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
return matrix and [*(matrix[0])]+self.spiralOrder([*zip(*matrix[1:])][::-1])
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = Noneclass Solution:
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
carry = 0
dummy = ListNode(-1)
tail = dummy
while l1 is not None or l2 is not None or carry:
a, b = 0, 0
if l1 is not None:
a = l1.val
l1 = l1.next
if l2 is not None:
b = l2.val
l2 = l2.next
c = a+b+carry
carry = c//10
val = c%10
node = ListNode(val)
tail.next = node
tail = tail.next
return dummy.next
103. Binary Tree Zigzag Level Order Traversal
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = Noneclass Solution:
def zigzagLevelOrder(self, root: TreeNode) -> List[List[int]]:
res = []
if root is None:return []
def bfs():
level = [root]
d = 0
res.append([root.val])
while True:
new_level = []
for node in level:
if node.left is not None:
new_level.append(node.left)
if node.right is not None:
new_level.append(node.right)
d += 1
if new_level:
if d%2==1:
res.append([node.val for node in reversed(new_level)])
else:
res.append([node.val for node in new_level])
else:
break
level = new_level
bfs()
return res
