from typing import List
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> List[int]:
buff=[]
print(type(buff))
for i in range(m):
buff.append(nums1[i])
print(type(buff))
for i in range(n):
buff.append(nums2[i])
print(type(buff))
buff.sort()
print(type(buff))
return buff
#for i in range(m,m+n):
# nums1[i]=nums2[i-m]
#nums1.sort()
#return nums1
def removeElement(self, nums: List[int], val: int) -> List[int]:
#buff=[]
while val in nums:
print(val)
nums.remove(val)
#for var in nums:
# if var==val:
# print(var)
# nums.remove(var)
return nums
def removeDuplicates(self, nums: List[int]) -> int:
buf = []
if not nums:
return 0
i = 0 # Slow pointer
for j in range(1, len(nums)): # Fast pointer
if nums[j] != nums[i]: # Found a unique element
i += 1
nums[i] = nums[j] # Place it at the correct position
print(nums)
return i + 1 # Return the count of unique elements
def removeDuplicates1(self, nums: List[int],n: int) -> int:
l = n
for i in range(n, len(nums)):
if nums[i] > nums[l - n]:
nums[l] = nums[i]
l += 1
print(nums)
return l
def majorityElement(self, nums: List[int]) -> int:
buf = {}
myval = 0
mykey = 0
for var in nums:
if var in buf.keys():
buf[var]+=1
else:
buf[var] =1
print(buf)
for key,val in buf.items():
print(key, myval, val)
if val > myval:
mykey,myval=key,val
print('set',mykey,myval)
print(mykey)
print(myval)
return mykey
def rotate(self, nums: List[int], k: int) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
for i in range(k):
a = nums.pop(-1)
nums.insert(0, a)
print (nums)
def maxProfit(self, prices: List[int]) -> int:
buy, sell = 0, 1
profit = 0
if len(prices) == 1:
return profit
while sell < len(prices):
if prices[sell] > prices[buy]: #get deal if buy < sell
profit = max(profit, prices[sell] - prices[buy])
sell += 1
else: # move forward if buy > sell
buy = sell
sell = buy + 1
return profit
def maxProfit1(self, prices: List[int]) -> int:
profit = 0
for i in range(1, len(prices)):
if prices[i] > prices[i - 1]:
profit += (prices[i] - prices[i - 1])
return profit
def canJump(self, nums: List[int]) -> bool:
max_reachable = 0
for i in range(len(nums)):
if i > max_reachable:
return False # Can't reach this index
max_reachable = max(max_reachable, i + nums[i])
if max_reachable >= len(nums) - 1:
return True # Can reach or exceed the last index
return False # If the loop completes without reaching the last inde
def jump(self, nums: List[int]) -> int:
# Initialize reach (maximum reachable index), count (number of jumps), and last (rightmost index reached)
reach, count, last = 0, 0, 0
for i in range(len(nums)-1):
# Update reach to the maximum between reach and i + nums[i]
reach = max(reach, i + nums[i])
# If i has reached the last index that can be reached with the current number of jumps
if i == last:
# Update last to the new maximum reachable index
last = reach
# Increment the number of jumps made so far
count += 1
# Return the minimum number of jumps required
return count
#论文被引用的次数，返回该研究人员的 h 指数
def hIndex(self, citations: List[int]) -> int:
citations.sort(reverse=True)
h = 0 # h-index
#while h < len(citations) and
while h < citations[h]:
h += 1
return h
'''
#add or delete from set.
import random
class RandomizedSet:
def __init__(self):
self.s = set()
def insert(self, val: int) -> bool:
if val in self.s:
return False
else:
self.s.add(val)
return True
def remove(self, val: int) -> bool:
if val in self.s:
self.s.remove(val)
return True
else:
return False
def getRandom(self) -> int:
return random.choice(tuple(self.s))
input=["RandomizedSet", "insert", "remove", "insert", "getRandom", "remove", "insert", "getRandom"]
ls=[[], [1], [2], [2], [], [1], [2], []]
obj = RandomizedSet()
param_1 = obj.insert(val)
param_2 = obj.remove(val)
param_3 = obj.getRandom()
'''
adj = { i:[] for i in range(5)}
ls=[1,2,3]
s='aabca'
print(adj)
for i,j in enumerate(ls):
print(i,j)
import collections
print(type(collections.Counter(s) ))
#print(len(ls[0]))
#75 Find 123/132 Pattern in List - Leetcode 456 - Python
nums = [1,2,3,4]
Output=False
class Solution:
def find132(self, nums: List[int])->bool:
stack = []# hold num min
curMin = nums[0]
for n in nums[1:]:
while stack and n >= stack[-1][0] :
stack.pop()
if stack and n > stack[-1][1]:
return True
stack.append([n, curMin])
curMin = min(curMin, n)
return False
print(Solution().find132([3,1,4,2]))
#76 Check K bianry in string if a '01'String Contains all '01'Binary Codes of Size K - Leetcode 1461 - Python easy
class Solution:
def hasAllBin(self, s: str, k: int)->bool:
codeSet = set() #haset
for i in range(len(s)-k+1):
codeSet.add(s[i: i+k])
print(codeSet)
return len(codeSet)==2**k
print(Solution().hasAllBin('0011011',2))
'''
1
/ \
2 3
/ \ / \
4 5 6 7
'''
#74. Find next point at the same level
# Populating Next Right Pointers in Each Node - Leetcode 116
root = [1,2,3,4,5,6,7]
Output=[1,'#',2,3,'#',4,5,6,7,'#']
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
self.next= None
class BinaryTree:
def __init__(self):
self.root = None
def insert_level_order(self, values):
if not values:
return None
nodes = [Node(value) for value in values]
print(nodes)
self.root = nodes[0]
for i in range(len(values) // 2):
if 2 * i + 1 < len(values):
#print('a',nodes[2 * i + 1].value)
nodes[i].left = nodes[2 * i + 1]
if 2 * i + 2 < len(values):
#print('b',nodes[2 * i + 2].value)
nodes[i].right = nodes[2 * i + 2]
return self.root
def inorder_traversal(self, node):
if node is not None:
self.inorder_traversal(node.left)
print(node.value, end=' ')
self.inorder_traversal(node.right)
def connect(self, node: 'Optional[Node]')->'Optional[Node]':
cur,nxt=node, node.left if node else None
while cur and nxt:
cur.left.next=cur.right
if cur.next:
cur.right.next=cur.next.left
cur=cur.next
if not cur:
cur=nxt
nxt=cur.left
return node
#Create binary tree and insert nodes from 1 to 7
tree = BinaryTree()
tree.insert_level_order([1, 2, 3, 4, 5, 6, 7])
node=tree.connect(tree.root)
# Print inrder traversal
tree.inorder_traversal(node)
#73 Find mini cost for Two City Scheduling - Leetcode 1029 - Python
costs = [[10,20],[30,200],[400,50],[30,20]]
Output= 110
class Solution:
def twoCity(self, costs: List[int])->int:
diffs = []
for c1,c2 in costs:
diffs.append([c2-c1,c1,c2])
diffs.sort()
res = 0
for i in range(len(diffs)):
if i<len(diffs)//2:
res += diffs[i][2]
else:
res += diffs[i][1]
return res
costs = [[10,20],[30,200],[400,50],[30,20]]
print(Solution().twoCity(costs))
#72 Binary Search Tree Iterator - Leetcode 173 - Python
input=[7, 3, 15, None, None, 9, 20]
Output=[None, 3, 7, True, 9, True, 15, True, 20, False]
class TreeNode:
def __init__(self,val=0,left=None,right=None):
self.val=val
self.left=left
self.right=right
class BSTIterator:
def __init__(self, root: TreeNode):
self.stack = []
while root:
self.stack.append(root)
root = root.left
def next(self) -> int:
res = self.stack.pop()
cur = res.right
while cur:
self.stack.append(cur)
cur = cur.left
return res.val
def hasNext(self) -> bool:
return self.stack != []
def test_bst_iterator():
# Construct the BST:
# 7
# / \
# 3 15
# / \
# 9 20
root = TreeNode(7)
root.left = TreeNode(3)
root.right = TreeNode(15)
root.right.left = TreeNode(9)
root.right.right = TreeNode(20)
# Initialize iterator
iterator = BSTIterator(root)
# Expected output: [3, 7, 9, 15, 20]
result = []
while iterator.hasNext():
result.append(iterator.next())
# Print the results
print("In-order Traversal Output:", result)
# Validate the output
assert result == [3, 7, 9, 15, 20], "Test failed!"
print("Test passed!")
# Run the test
test_bst_iterator()
#71 Pop Maximum Frequency item in Stack - Leetcode 895 - Python
Input=[[], [5], [7], [5], [7], [4], [5], [], [], [], []]
Output=[None, None, None, None, None, None, None, 5, 7, 5, 4]
class FreqStack:
def __init__(self):
self.cnt = {} #map
self.stacks = {} #hashmap
self.maxCnt = 0
def push(self, val: int) -> None:
valCnt= 1+ self.cnt.get(val,0)
self.cnt[val]=valCnt
if valCnt > self.maxCnt:
self.maxCnt = valCnt
self.stacks[valCnt]=[]
self.stacks[valCnt].append(val)
def pop(self) -> int:
res=self.stacks[self.maxCnt].pop()
self.cnt[res]-=1
if not self.stacks[self.maxCnt]:
self.maxCnt -=1
return res
freqStack = FreqStack()
# Push elements onto the stack
freqStack.push(5) # Stack: [5]
freqStack.push(7) # Stack: [5, 7]
freqStack.push(5) # Stack: [5, 7, 5]
freqStack.push(7) # Stack: [5, 7, 5, 7]
freqStack.push(4) # Stack: [5, 7, 5, 7, 4]
freqStack.push(5) # Stack: [5, 7, 5, 7, 4, 5]
# Pop elements from the stack
print(freqStack.pop()) # Output: 5, Stack becomes: [5, 7, 5, 7, 4]
print(freqStack.pop()) # Output: 7, Stack becomes: [5, 7, 5, 4]
print(freqStack.pop()) # Output: 5, Stack becomes: [5, 7, 4]
print(freqStack.pop()) # Output: 4, Stack becomes: [5, 7]
#70 Find Pattern: Repeated DNA Sequences - Leetcode 187 - Python
s = "AAAAACCCCCAAAAACCCCCCAAAAAGGGTTT"
Output=["AAAAACCCCC","CCCCCAAAAA"]
class Solution:
def findPattern(self, s:str,ln:int)->List[str]:
res=set() #match case
seen=set() #all combination
for i in range(len(s)-ln+1):
cur = s[i:i+ln]
#print(seen)
if cur in seen: #find in combination
res.add(cur)
seen.add(cur) #gen all combination
return list(res)
print(Solution().findPattern(s,10))
#69 Find 4Sum equal target - Leetcode 18 - Python
nums = [1,0,-1,0,-2,2]
target = 0
Output=[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
class Solution:
def fourSum(self, nums: List[int], target:int):
nums.sort()
res,quad=[],[]
def kSum(k,start,target):
if k==2:
l,r=start,len(nums)-1
while l < r:
if nums[l]+nums[r]<target:
l+=1
elif nums[l]+nums[r]> target:
r-=1
else:
res.append(quad+[nums[l],nums[r]])
l+=1
while l<r and nums[l]==nums[l-1]:
l+=1
else:
for i in range(start, len(nums)-k+1):
if i> start and nums[i]==nums[i-1]:
continue
quad.append(nums[i])
kSum(k-1,i+1,target-nums[i])
quad.pop()
return
kSum(4,0,target)
return res
print(Solution().fourSum(nums,0))
#68 Remove Overlay/Covered Intervals - Leetcode 1288 - Python
intervals = [[1,4],[3,6],[2,8]]
Output= 2
class Solution:
def removeOverlap(self, nums:List[List[int]])->List[List[int]]:
nums.sort(key=lambda i:(i[0],-i[1]))
res= [nums[0]]
for l,r in nums[1:]:
preL,preR=res[-1]
if preL<=l and preR>=r:
continue
res.append([l,r])
return res
print(Solution().removeOverlap(intervals))
#67 Make it small by Remove K Digits - Leetcode 402 - Python
num = "1432219"
k = 3
Output= "1219"
class Solution:
def removeDigits(self, num:str, k:int)->str:
stack=[]
for c in num:
while k>0 and stack and stack[-1]>c:
k-=1
stack.pop() #=pop(-1)
stack.append(c)
stack=stack[:len(stack)-k]
res="".join(stack)
return str(int(res)) if res else "0"
print(Solution().removeDigits(num,k))
#66 Check Valid Parenthesis（） String - Leetcode 678 - Python
class Solution:
def checkBracket(self, s:str)->bool:
min,max=0,0
for ch in s:
if ch == '(':
min,max=min+1,max+1
elif ch==')':
min,max=min-1,max-1
elif ch=='*':
min,max=min-1,max+1
if min<0:
min=0
if max<0:
return False
return min==0
s='((*))'
print(Solution().checkBracket(s))
#65 Open combination Lock without deadend - Leetcode 752 - Python
deadends = ["0201","0101","0102","1212","2002"]
target = "0202"
Output= 6
from collections import deque
class Solution:
def openLock(self, deads:List[str],target: int)->int:
def children(lock):
res=[]
for i in range(4):
for turn in [1,-1]:
digit=str((int(lock[i])+10+turn)%10)
res.append(lock[:i]+digit+lock[i+1:])
return res
q=deque()
q.append(['0000',0])
visit=set(deads)
while q:
lock,turns=q.popleft()
if lock==target:
return turns
for ch in children(lock):
if ch not in visit:
visit.add(ch)
q.append([ch,turns+1])
return -1
print(Solution().openLock(deadends,target))
#64 Snakes and Ladders - Leetcode 909 - Python BFS using visit
board = [[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,-1,-1,-1,-1,-1],
[-1,35,-1,-1,13,-1],
[-1,-1,-1,-1,-1,-1],
[-1,15,-1,-1,-1,-1]]
Output= 4
class Solution:
def snakeLaders(self, board:List[List[int]])->int:
print('snakeLaders...')
ln = len(board)
board.reverse()
def toPosition(num,ln):
row=(num-1)//ln
col=(num-1)%ln
if row%2:
col=ln-1-col
return [row,col]
visit=set()
que=deque()
que.append((1,0))
while que:
num, mvs=que.popleft()
for i in range(1,7):
nextNum=num+i
row, col=toPosition(nextNum,ln)
if board[row][col]!=-1:
nextNum=board[row][col]
if nextNum==ln*ln:
return mvs+1
if nextNum not in visit:
visit.add(nextNum)
que.append((nextNum,mvs+1))
return -1
print(Solution().snakeLaders(board))
#63 List all Subsets II - Backtracking - Leetcode 90
nums = [1,2,2]
Output= [[],[1],[1,2],[1,2,2],[2],[2,2]]
class Solution:
def subsetDup(self, nums: List[int])->List[List[int]]:
res=[]
nums.sort()
def backtrack(start, path):
res.append(path[:]) # Add the current subset to the result
for i in range(start, len(nums)):
# Skip duplicates
if i > start and nums[i] == nums[i - 1]:
continue
path.append(nums[i]) # Include nums[i] in the subset
backtrack(i + 1, path) # Move to the next element
path.pop() # Backtrack (exclude nums[i] from the subset)
backtrack(0,[])
return res
print(Solution().subsetDup(nums))
#62 Find bigest Island Calculate Max Area of Island - Leetcode 695 - Python
grid = [[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
Output= 6
class Solution:
def maxAreaOfIsland(self, grid: List[List[int]]):
rows, cols=len(grid), len(grid[0])
visit=set()
def dfs(r,c):
if (r<0 or r==rows or c<0 or c==cols or
grid[r][c]==0 or (r,c) in visit):
return 0
visit.add((r,c))
return (1+ dfs(r+1, c)+
dfs(r-1, c)+
dfs(r, c+1)+
dfs(r, c-1))
area=0
for r in range(rows):
for c in range(cols):
area=max(area,dfs(r,c))
return area
print(Solution().maxAreaOfIsland(grid))
#61 Divid string by most frequent Partition Labels - Leetcode 763 - Python
s = "babcbacadefegdehijhklij"
o=[9, 7, 8]
class Solution:
def partitionStr(self, s:int)->List[int]:
lastInd={} #hash
for i,c in enumerate(s):
lastInd[c]=i #hash
#print(lastInd)
res=[]
size,end=0,0
for i,c in enumerate(s):
size+=1
end=max(end,lastInd[c])
if i==end:
res.append(size)
size=0
return res
print(Solution().partitionStr(s))
#60 Add +- get Target Sum - Dynamic Programming - Leetcode 494 - Python
nums ,target= [1,1,1,1,1], 3
out= 5
class Solution:
def targetSum(self, nums:int,target:int)->int:
dp={} #(idx, total): ways
def backtrack(i, total):
if i==len(nums):
return 1 if total == target else 0
if (i,total) in dp:
return dp[(i,total)]
dp[i,total]=(backtrack(i+1, total+nums[i]) +
backtrack(i+1, total-nums[i]))
return dp[(i,total)]
return backtrack(0,0)
print(Solution().targetSum(nums,target))
#59 Restore IP Addresses - Leetcode 93 - Python
s = "25525511135"
Out=["255.255.11.135","255.255.111.35"]
class Solution:
def restoreIP(self,s:str)->List[str]:
res=[]
if len(s)>12:
return res
def backtrack(i, dots,curIP):
#print(i, dots,curIP)
if dots==4 and i==len(s):
res.append(curIP[:-1])
print('mon:',curIP)
return
if dots>4:
return
for j in range(i, min(i+3, len(s))):
if int(s[i:j+1])<256 and (i==j or s[i]!='0'):
backtrack(j+1, dots+1, curIP+s[i:j+1]+'.')
backtrack(0,0,'')
return res
print(Solution().restoreIP(s))
def restoreIpAddresses(s):
def backtrack(start, path):# idx vs result
# 如果已经生成了四个整数且字符串被完全用完
#print(start, path)
if len(path) == 4:
if start == len(s):
result.append(".".join(path))
return
# 尝试取 1 到 3 个字符作为当前整数
for i in range(1, 4):
if start + i > len(s):
break
segment = s[start:start+i]
# 检查当前段是否有效
if (segment[0] == '0' and len(segment) > 1) or int(segment) > 255:
continue
backtrack(start + i, path + [segment])
result = []
backtrack(0, [])
return result
print(restoreIpAddresses(s))
#58 Find Missing Observations by mean - Leetcode 2028 Weekly Contest Problem - Python
rolls = [1,5,6]
mean = 3
n = 4
o=[2,3,2,2]
class Solution:
def missRolls(self, rolls:List[int],mean:int,n:int)->List[int]:
res=[]
m=len(rolls) #12
nTot=(mean*(m+n))-sum(rolls) #7*3-12=9
if nTot<n or nTot>6*n:
return []
print('ntot=',nTot)
while nTot:
print(nTot-n+1)
dice=min(nTot-n+1,6)
print(nTot,dice)
res.append(dice)
nTot-=dice
n-=1
return res
print('case1:',Solution().missRolls([3, 2, 4, 3], 4, 2))
print('case2',Solution().missRolls([1, 5, 6], 3, 4)) #应该多重解
#57 Collect Minum and Maxum Grid Game - Leetcode Weekly Contest Problem 2017 - Python
grid = [[2,5,4],[1,5,1]]
Output = 4
class Solution:
def gridGame(self, grid:List[List[int]])->int:
n=len(grid[0])
res=float('inf')
preRow1=grid[0].copy()
preRow2=grid[1].copy()
for i in range(1,n):
preRow1[i] += preRow1[i-1]
preRow2[i] += preRow2[i-1]
for i in range(n):
top=preRow1[-1]-preRow1[i]
bottom=preRow2[i-1]
secondRobot=max(top,bottom)
res=min(res, secondRobot)
return res
print(Solution().gridGame(grid))
#56 Add/Detect Squares - Leetcode Weekly Contest - Problem 2013 - Python
'''x,py----px,py
x,y-----px,y
'''
ls=[[3, 10], [11, 2], [3, 2], [11, 10]]
from collections import defaultdict
class Solution:
def __init__(self):
self.ptsCount=defaultdict(int) #inital dict
self.pts = []
def add(self, point: List[int])->None:
self.ptsCount[tuple(point)]+=1
self.pts.append(point)
def count(self, point: List[int])->int:
res=0
px,py=point
for x,y in self.pts:
if( abs(py-y) != abs(px-x) or x==px or y==py):
continue
res += self.ptsCount[(x,py)]*self.ptsCount[(px,y)]
return res
detectSquares = Solution()
detectSquares.add([3, 10])
detectSquares.add([11, 2])
detectSquares.add([3, 2])
print(detectSquares.count([11, 10])) # 输出 1
print(detectSquares.count([14, 8])) # 输出 0
detectSquares.add([11, 2])
print(detectSquares.count([11, 10])) # 输出 2
#49 leetcode 1984. Find Minimum Difference Between Highest and Lowest of K elements
nums,k = [9,4,1,7], 3
#Output: 2
class Solution:
def minDiff(self, nums:List[int],k:int)->int:
nums.sort()
l,r=0,k-1
res=float('inf')
while r<len(nums):
res=min(res, nums[r]-nums[l])
l,r=l+1,r+1
return res
print('res',Solution().minDiff(nums,k)) # 输出 2
#50 lock/unlock for user leetcode 1993. Operations on Tree
##Input: nums = [[[-1, 0, 0, 1, 1, 2, 2]], [2, 2], [2, 3], [2, 2], [4, 5], [0, 1], [0, 1]]
#Output: 0
'''
0
/ \
1 2
/ \ / \
3 4 5 6
'''
class Solution:
def __init__(self,parent:List[int]):
self.parent=parent
self.locked=[None]*len(parent)
self.child={i:[] for i in range(len(parent))}
for i in range(1, len(parent)):
self.child[parent[i]].append(i)
def lock(self, num: int, user: int) -> bool:
if self.locked[num]: return False
self.locked[num]=user
return True
def unlock(self, num: int, user: int)->bool:
if self.locked[num] != user: return False
self.locked[num]=None
return True
def upgrade(self, num: int, user: int)->bool:
i=num
while i!=-1:
if self.locked[i]: return False
i = self.parent[i]
lockedCount,q = 0,deque([num])
while q:
print('1',q)
n=q.popleft()
if self.locked[n]:
self.locked[n]=None
lockedCount+=1
print('2',self.child[n])
q.extend(self.child[n])
print('3',q)
if lockedCount>0:
self.locked[num]=user
return lockedCount>0
ls=[1,2]
lockingtree = Solution([-1, 0, 0, 1, 1, 2, 2])
print(lockingtree.parent)
print('locked:',lockingtree.locked)
print(lockingtree.child)
print(lockingtree.lock(2, 2)); # Returns true because node 2 is unlocked.
print(lockingtree.unlock(2, 3)); # Returns false because user 3 cannot unlock node 2.
print(lockingtree.unlock(2, 2)); # Returns true because node 2 is locked by user 2.
print(lockingtree.lock(4, 5)); # Returns true because node 4 is unlocked.
print(lockingtree.upgrade(0, 1)); # Returns true because node 0 is unlocked and has at least one locked descendant (node 4).
print(lockingtree.lock(0, 1)); # return false
#52 Xiangshixing leetcode 2001. Number of Pairs of Interchangeable Rectangles easy!!1!
rectangles = [[4,8],[1,3],[10,20],[15,45]]
Output= 6
class Solution:
def similarRect(self, rects: List[List[int]])->int:
count={} #bash
res=0
for w,h in rects:
count[w/h]=1+count.get(w/h,0)
print(count)
for c in count.values():
if c>1:
res+=(c*(c-1))//2
return res
print(Solution().similarRect(rectangles));
#53. Max(） Leetcode 1899. Merge Triplets to Form Target Triplet
triplets,target = [[2,5,3],[1,8,4],[1,7,5]], [2,7,5]
Output= True
class Solution:
def mergeCheck(self, triplets: List[List[int]],target: List[int])->bool:
good=set()
for t in triplets:
if t[0]>target[0] or \
t[0]>target[0] or \
t[0]>target[0]: # ignore large ones
continue
for i, v in enumerate(t): # t=[x,y,z] vs target[2,7,5]
if v == target[i]: #
print(i, v, target[i])
good.add(i)
return len(good)==3
print(Solution().mergeCheck(triplets,target));
#54. Convert Binary Tree to Linked List 54 Flatten Binary Tree to Linked List - Leetcode 114
root = [1,2,5,3,4,None,6]
Output= [1,None,2,None,3,None,4,None,5,None,6]
from typing import Optional
class TreeNode:
def __init__(self, val=0, left=None,right=None):
self.val=val
self.left=left
self.right=right
def buildTree(nodes):
if not nodes: return None
root=TreeNode(nodes[0])
queue=[root]
i=1
while queue and i<len(nodes):
cur=queue.pop(0)
if nodes[i] is not None:
cur.left=TreeNode(nodes[i])
queue.append(cur.left)
i+=1
if i<len(nodes) and nodes[i] is not None:
cur.right=TreeNode(nodes[i])
queue.append(cur.right)
i+=1
return root
def flatten_tree_to_list(root):
"""
将展开后的链表转换为列表（便于验证）
"""
result = []
while root:
result.append(root.val)
root = root.right
return result
class Solution:
#def convert(self, Optional[TreeNode])->None:
def flatten(self, root: Optional[TreeNode]) -> None:
def dfs(root):
if not root: return None
leftTail=dfs(root.left)
rightTail=dfs(root.right)
if root.left:
leftTail.right=root.right
root.right=root.left
root.left=None
print(rightTail , leftTail , root)
last=rightTail or leftTail or root
print(last)
return last
dfs(root)
'''
1 root
/ \ / \
2 5 =None =left
/ \ \
3 4 6 to 1 -2 -3 -4 -5 -6
'''
nodes = [1, 2, 5, 3, 4, None, 6]
root = buildTree(nodes)
print(flatten_tree_to_list(root))
Solution().flatten(root)
print('vs:::::',flatten_tree_to_list(root))#[1, 2, 3, 4, 5, 6]
#55 leetcode 1845. Seat Reservation Manager
##Input: nums = [90], k = 1
#Output: 0
import heapq
class Solution:
def __init__(self, num: int):
self.reserv=[i for i in range(1,n+1)]
heapq.heapify(self.reserv)
def reserve(self)->int:
return heapq.heappop(self.reserv)
def unreserve(self, seat: int)-> None:
heapq.heappush(self.reserv, seat)
seatManager = Solution(5) # Seats: [1, 2, 3, 4, 5]
print("res:",seatManager.reserve()) # Output: 1 (smallest seat)
print(seatManager.reserve()) # Output: 2
print(seatManager.unreserve(2)) # Unreserve seat 2
print(seatManager.reserve()) # Output: 2 (now available again)
print(seatManager.reserve()) # Output: 3
#30 Get 3 Huiwen number-Unique Length-3 Palindromic Subsequences - Leetcode 1930 - Python
s = "aabca"
#Output: 3
#class TreeNode:
class Solution:
def countPalin(self, s:str)->set:
firstCur,lastCur={},{} # ch : pos
res=set()
for i,ch in enumerate(s):
if ch not in firstCur:
firstCur[s[i]]=i
lastCur[s[i]]=i
for ch in firstCur:
start=firstCur[ch]+1
end=lastCur[ch]
if start == end:
continue
print('check',start, end)
for i in range(start,end):
print(ch,i)
res.add((ch,s[i], ch))
return res
print(Solution().countPalin(s)) # Output: 3r
#31 Reorder Array not Average With Elements Not Equal to Average of Neighbors - Leetcode 1968 - Python
nums = [1,2,3,4,5,6]
Output= [1,2,4,5,3]
class Solution:
def rearrangeArray(self, ls: List[int]) -> List[int]:
nums.sort() # Step 1: Sort the array
res=[]
l,r = 0,len(ls)-1
while len(res) != len(ls):
print('com:',l, r)
res.append(ls[l])
print('ap:',res)
l+=1
if l<=r:
res.append(ls[r])
print('app:',res)
r-=1
return res
print('res=',Solution().rearrangeArray(nums)) # Output: 3
#32 Sort Array Colors - Quicksort Partition - Leetcode 75 - Python
ls = [2,0,2,1,1,0]
Output= [0,0,1,1,2,2]
class Solution:
def sortColor(self,ls:List[int])->List[int]:
l, r = 0, len(ls)-1
i=0
def swap(i,j):
ls[i],ls[j] = ls[j],ls[i]
while i<=r:
if ls[i] ==0:
swap(l,i)
l+=1
elif ls[i]==2:
swap(i,r)
r-=1
i-=1
i+=1
return ls
print('res=',Solution().sortColor(ls)) # Output: 3
#33 Find a Missing Number - Blind 75 - Leetcode 268 - Python
ls = [3,0,1]
#Output: 2
class Solution:
def missNum(self, ls: List[int]):
res=len(ls)
print(res)
for i in range(len(ls)):
res+=i-ls[i]
return res
print('res=',Solution().missNum(ls)) # Output: 2
#34 Encode and Decode Strings - Leetcode 271 - Python #easy
s = ['I','love','code']
#Output= [1,None,2,None,3,None,4,None,5,None,6]
class Solution:
def encode(self, ls: List[str])->str:
res=''
for s in ls:
res+=str(len(s))+'#'+s
return res
def decode(self, s:str)->List[str]:
res=[]
i=0
while i<len(s):
ii=i
while s[ii]!='#':
ii+=1
ln=int(s[i:ii])
i=ii+1+ln
res.append(s[ii+1:i])
return res
sln=Solution()
print(sln.encode(s))
s=sln.encode(s)
print(sln.decode(s))
#35 Get remove numbers Maximum Number of Removable Characters - Binary Search - Leetcode 1898 - Python
s = "abcacb"
p = "ab"
removable = [3,1,0]
Output=2
class Solution:
def removeChar(self, s:str, p:str,remove:List[int])->int:
def isSubseq(s, subseq):
i,j=0,0
while i<len(s) and j<len(subseq):
if i in removed or s[i]!=subseq[j]:
i+=1
continue
i+=1
j+=1
return i==len(subseq)
revmoved=set()
res=0
l,r=0,len(removable)-1
while l<=r:
m=(l+r)//2
removed=set(removable[:m+1])
print(s,p)
if isSubseq(s,p):
res=max(res,m+1)
l=m+1
else:
r=m-1
return res
print(Solution().removeChar(s,p,removable))
def maximumRemovals(s: str, p: str, removable: List[int]) -> int:
def is_subsequence(mid):
print('0:',mid+1, removable)
removed = set(removable[:mid+1]) #[3,1,0]
print('1:',mid, removed)
i = 0
for j in range(len(s)):
if j in removed:
continue
if i < len(p) and s[j] == p[i]:
i += 1
return i == len(p)
l, r = 0, len(removable) - 1 # 0, 3-1
while l <= r:
m = (l + r) // 2
print('callcheck:',l,r,m)
if is_subsequence(m):
l = m + 1
print('callcheck1:',l,r,m)
else:
r = m - 1
print('callcheck2:',l,r,m)
print('callcheck3:',l,r,m)
return l
print(maximumRemovals(s,p,removable))
s=[3, 1, 0]
print(s[:2])
#36 Make up with Coin Change 2 - Dynamic Programming Unbounded Knapsack - Leetcode 518 - Python #dfs
amount = 5
coins = [1,2,5]
#Output: 4
class Solution:
def change(self, amount:int,coins:List[int])->int:
dp = [0]*(amount+1)
dp[0] = 1
for coin in coins:
for way in range(coin,amount+1):
dp[way]+=dp[way-coin]
print(dp)
return dp[amount]
print(Solution().change(amount,coins))
#37 Count Sub Islands - DFS - Leetcode 1905 - Python
grid1 = [[1,1,1,0,0],[0,1,1,1,1],[0,0,0,0,0],[1,0,0,0,0],[1,1,0,1,1]]
grid2 = [[1,1,1,0,0],[0,0,1,1,1],[0,1,0,0,0],[1,0,1,1,0],[0,1,0,1,0]]
Output= 3
class Solution:
def countSubisland(self,grid1: List[List[int]], grid2:List[List[int]])->int:
m,n=len(grid1),len(grid1[0])
directs=[(0,1),(1,0),(0,-1),(-1,0)]
count=0
#dfs grid2
def dfs(i,j):
#outbound count
if (i<0 or i>=m or
j<0 or j>=n or grid2[i][j]==0):
return True
grid2[i][j]=0 #visited
#check
isSubIslad=(grid1[i][j]==1)
#visit 4 direction
for x,y in directs:
isSubIslad &=dfs(i+x,j+y)
return isSubIslad
#main logic grid2
for i in range(m):
for j in range(n):
if grid2[i][j]==1: #valid
if dfs(i,j):
count+=1
return count
print('res:',Solution().countSubisland(grid1,grid2))
#38 Rotate List K times - Linked List - Leetcode 61 - Python
head = [1,2,3,4,5]
k = 2
Output= [4,5,1,2,3]
class ListNode:
def __init__(self, val: int, next=None):
self.val=val
self.next=next
class Solution:
def buildList(self, head:List[int])->Optional[ListNode]:
tail=None
for val in reversed(head):
tail=ListNode(val,tail)
return tail
def printList(self, head:Optional[ListNode]):
res=[]
while head:
res.append(head.val)
head = head.next
return res
def rotateList(self, head: Optional[ListNode],k: int)->Optional[ListNode]:
if not head: return head
#getlength
ln,tail=1,head
while tail.next:
tail=tail.next
ln+=1
#check k
k=k%ln
if k==0: return head
cur=head
for i in range(ln-k-1):
cur=cur.next
newHead=cur.next
cur.next=None
tail.next=head
return newHead
sln=Solution()
head=sln.buildList(head)
print(sln.printList(head))
newHead=sln.rotateList(head,k)
print(sln.printList(newHead))
#39 Get Kth Closest Points to Origin - Heap / Priority Queue - Leetcode 973 - Python
points = [[3,3],[5,-1],[-2,4]]
k = 2
Output= [[3,3],[-2,4]]
import heapq
class Solution:
def kClosed(self, points: List[List[int]],k:int)->List[List[int]]:
heap=[] # keep (dist,x,y)
res=[]
for x, y in points:
dist=-(x*x+y*y)
if len(heap)< k:
heapq.heappush(heap,(dist,x,y))
else:
heapq.heappushpop(heap,(dist,x,y)) # heappush() followed by a separate call to heappop().
for dist,x,y in heap:
res.append((x,y))
return res
print(Solution().kClosed(points,k))
#40 Eliminate Maximum Number of Monsters - Leetcode 1921 - Weekly Contest 248 - Python
dist = [1,3,4]
speed = [1,1,1]
Output= 3
class Solution:
def eliminateMaximum(self,dist, speed):
n = len(dist)
time_to_reach = []
for i in range(n):
t = (dist[i] + speed[i] - 1) // speed[i] # Equivalent to math.ceil(dist[i] / speed[i])
time_to_reach.append(t)
time_to_reach.sort()
res = 0
for i in range(n):
if time_to_reach[i] > i:
res += 1
else:
break
return res
print(Solution().eliminateMaximum(dist,speed))
#41 Get Right Side View for Binary Tree Right Side View - Breadth First Search - Leetcode 199 - Python
root = [1,2,3,None,5,None,4]
Output=[1,3,4]
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
class Solution:
def rightSideView1(self,root)->List[int]:
res=[]
q=deque([root])
while q:
rightSide=None
qLen=len(q)
for i in range(qLen):
node = q.popleft()
if node:
rightSide=node
q.append(node.left)
q.append(node.right)
if rightSide:
res.append(rightSide.val)
return res
def rightSideView(self,root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level_size = len(queue)
for i in range(level_size):
node = queue.popleft()
if i == level_size - 1:
result.append(node.val)
if node.left:
queue.append(node.left)
if node.right:
queue.append(node.right)
return result
# Helper function to create a binary tree from a list
def create_tree(self,values):
if not values:
return None
root = TreeNode(values[0])
queue = [root]
i = 1
while queue and i < len(values):
node = queue.pop(0)
if values[i] is not None:
node.left = TreeNode(values[i])
queue.append(node.left)
i += 1
if i < len(values) and values[i] is not None:
node.right = TreeNode(values[i])
queue.append(node.right)
i += 1
return root
# Test cases
def test_rightSideView():
# Test case 1
sln=Solution()
tree1 = sln.create_tree([1, 2, 3, None, 5, None, 4])
print( sln.rightSideView1(tree1)) # [1, 3, 4],
#tree2=sln.buildTree([1, 2, 3, None, 5, None, 4])
#print( sln.rightSideView1(tree2)) # [1, 3, 4],
print("All test cases passed!")
# Run the tests
test_rightSideView()
#42 Find Gas Station can go around - Greedy - Leetcode 134 - Python
gas = [1,2,3,4,5]
cost = [3,4,5,1,2]
Output= 3
class Solution:
def canDoCircuit(self, gas, cost):
total_gas=0
cur_gas=0
start_stn=0
for stn in range(len(gas)):
total_gas +=gas[stn]-cost[stn]
cur_gas +=gas[i]-cost[stn]
if cur_gas < 0:
start_stn = stn+1
cur_gas=0
return start_stn if total_gas >=0 else -1
print(Solution().canDoCircuit(gas,cost))
#43 Check if Move is Legal - Biweekly Leetcode Contest - 1958 - Python
board = [[".",".",".","B",".",".",".","."],
[".",".",".","W",".",".",".","."],
[".",".",".","W",".",".",".","."],
[".",".",".","W",".",".",".","."],
["W","B","B",".","W","W","W","B"],
[".",".",".","B",".",".",".","."],
[".",".",".","B",".",".",".","."],
[".",".",".","W",".",".",".","."]]
rMove = 4
cMove = 3
color = "B"
class Solution:
def isMoveLegal(self, board: List[List[str]], rMove: int, cMove: int, color: str) -> bool:
if board[rMove][cMove] != '.':
return False
directions = [(-1, -1), (-1, 0), (-1, 1),
(0, -1), (0, 1),
(1, -1), (1, 0), (1, 1)]
opponent = 'B' if color == 'W' else 'W'
for dr, dc in directions:
r, c = rMove + dr, cMove + dc
if 0 <= r < 8 and 0 <= c < 8 and board[r][c] == opponent:
r += dr
c += dc
while 0 <= r < 8 and 0 <= c < 8:
if board[r][c] == '.':
break
if board[r][c] == color:
return True
r += dr
c += dc
return False
print(Solution().isMoveLegal(board, rMove, cMove, color))
#44 Find Unique Binary String - Leetcode Weekly Contest 1980 - Python
nums = ["01","10"]
Output= "11"
class Solution:
def findDifference(self, nums: List[int]):
n = len(nums)
res = []
for i in range(n):
char = '1' if nums[i][i]=='0' else '0'
res.append(char)
return ''.join(res)
print(Solution().findDifference(nums))
#45 Find the Kth Largest Integer in the Array - Leetcode Weekly Contest - 1985 Python
nums = ["3", "6", "7", "10"]
k = 4
Output= "3"
class Solution:
def findLargest(self, nums: List[int], k:int)->str:
nums = sorted(nums, key=lambda x: int(x), reverse=True)
return nums[k-1]
print(Solution().findLargest(nums,k))
#46 Remove Surrounded Regions - Graph - Leetcode 130 - Python
board = [["X","X","X","X"],["X","O","O","X"],["X","X","O","X"],["X","O","X","X"]]
Output= [["X","X","X","X"],["X","X","X","X"],["X","X","X","X"],["X","O","X","X"]]
class Solution:
def solve(self, board):
if not board:
return
rows, cols = len(board), len(board[0])
# 定义DFS函数
def dfs(r, c):
if r < 0 or r >= rows or c < 0 or c >= cols or board[r][c] != 'O':
return
board[r][c] = 'T' # 标记为'T'
dfs(r + 1, c)
dfs(r - 1, c)
dfs(r, c + 1)
dfs(r, c - 1)
# 遍历边界，找到所有与边界相连的'O'并标记为'T'
for r in range(rows):
for c in range(cols):
if (r == 0 or r == rows - 1 or c == 0 or c == cols - 1) and board[r][c] == 'O':
dfs(r, c)
# 遍历整个矩阵，将所有'O'替换为'X'，并将'T'恢复为'O'
for r in range(rows):
for c in range(cols):
if board[r][c] == 'O':
board[r][c] = 'X'
elif board[r][c] == 'T':
board[r][c] = 'O'
return board
print(Solution().solve(board))
#47 Get mininum for each Point Prim's Algorithm - Minimum Spanning Trere
# - Min Cost to Connect all Points - Leetcode 1584 - Python
points = [[0,0],[2,2],[3,10],[5,2],[7,0]]
Output= 20
class Solution:
def findMiniCost(self, point):
n = len(points)
visited = [False]*n
heap = [(0,0)] #cost , point index
total_cost = 0
while heap:
cost, u=heapq.heappop(heap)
if not visited[u]:
visited[u]=True
total_cost+=cost
for v in range(n):
if not visited[v]:
next_cost=abs(points[u][0]-points[v][0])+abs(points[u][1]-points[v][1])
heapq.heappush(heap, (next_cost,v))
return total_cost
print(Solution().findMiniCost(points))
#48 Get two Huiwens Maximum Product of the Length of Two Palindromic Subsequences - Leetcode 2002 - Python
s = "leetcodecom"
Output=9
class Solution:
def maxString(self, s: str)->int:
n = len(s)
pali = {} #bitmask vs length
for mask in range(1, 1<<n):
subseq = ''
for i in range(n):
if mask & (1<<i):
subseq+=s[i]
if subseq==subseq[::-1]:
pali[mask]=len(subseq)
res=0
for m1 in pali:
for m2 in pali:
if m1&m2 ==0: #disjoint
res=max(res, pali[m2]*pali[m2])
return res
print(Solution().maxString(s))
#49 Get all Combinations C2/4 - Leetcode 77 - Python
n = 4
k = 2
Output= [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]
class Solution:
def combination(self, n:int,k:int)->List[List[int]]:
res=[]
def backtrack(start, path):
if len(path)==k:
res.append(path[:])
return
for i in range(start, n+1):
path.append(i)
backtrack(i+1, path)
path.pop() # reverse above
backtrack(1, [])
return res
print(Solution().combination(n,k))
#4. Get sublist make 3Sum equal to zero - Leetcode 15 - Python
nums = [-1,0,1,2,-1,-4]
Output= [[-1,-1,2],[-1,0,1]]
class Solution:
def threeSum(self, nums:List[int])->List[List[int]]:
nums.sort()
res=[]
for i,a in enumerate(nums):
if i>0 and a ==nums[i-1]:
continue
l,r=i+1, len(nums)-1
while l<r:
threeSum=a+nums[l]+nums[r]
if threeSum>0:
r-=1
elif threeSum<0:
l+=1
else:
res.append([a,nums[l],nums[r]])
l+=1
while nums[l]==nums[l-1] and l<r:
l+=1
return res
print(Solution().threeSum(nums))
#5. Backtracking: Permutations of array - Leetcode 46 - Python
nums = [1,2,3]
Output=[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
class Solution:
def permute(self, nums:List[int])->List[List[int]]:
res=[]
if len(nums)==1:
return [nums[:]]
for i in range(len(nums)):
n=nums.pop(0)
perms=self.permute(nums)
for perm in perms:
perm.append(n)
res.extend(perms)
nums.append(n)
return res
#def backtrack(path, used)
print(Solution().permute(nums))
#6. Get Longest Substring Without Repeating Characters - Leetcode 3 - Pytho
s = "abcabcbb"
Output= 3
class Solution:
def longestSub(self, s:str)->int:
charSet=set()
res=0
l=0
for r in range(len(s)):
while s[r] in charSet:
charSet.remove(s[l])
l+=1
charSet.add(s[r])
res=max(res,r-l+1)
return res
print(Solution().longestSub(s))
#7. Get number for amount using Coin Change - Dynamic Programming Bottom Up - Leetcode 322
coins = [1,2,5]
amount = 11
Output= 3
class Solution:
def coinChange(self, coins: List[int],amount:int)->int:
dp=[amount+1]*(amount+1)
dp[0]=0
res=-1
for i in range(1, amount+1): #every amount
for coin in coins: #every coin
if coin<=i:
dp[i]=min(dp[i],dp[i-coin]+1)
if dp[amount]<=amount:
res=dp[amount]
return res
def count_ways(self,coins, amount):
# 初始化 dp 数组，大小为 amount + 1，初始值为 0
dp = [0] * (amount + 1)
dp[0] = 1 # 组成金额 0 的方法数为 1
# 遍历每个硬币
for coin in coins:
# 更新 dp 数组
for i in range(coin, amount + 1):
dp[i] += dp[i - coin]
return dp[amount]
print(Solution().coinChange(coins,amount))
print(Solution().count_ways([1,5,10,25,50],100))
#8. Get Container hold Most Water - Leetcode 11 - Python
height = [1,8,6,2,5,4,8,3,7]
Output= 49
class Solution:
def maxArea(self, height: List[int])->int:
area=0
l,r=0,len(height)-1
while l<r:
area=max(area, (r-l)*min(height[l],height[r]))
if height[l]<height[r]:
l+=1
else: r-=1
return area
print(Solution().maxArea(height))
#9.Find a Word Search in Matrix - Backtracking - Leetcode 79 - Python #dfs
board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]]
word = "ABCCED"
Output= True
class Solution:
def checkWord(self, board: List[List[str]],word:str)->bool:
rows, cols=len(board), len(board[0])
path=set()
def dfs(r,c,i):
if i==len(word): return True
if (r<0 or c<0 or r>=rows or c>=cols or
(r,c) in path or word[i]!=board[r][c]):
return False
path.add((r,c)) # to add
res=(dfs(r+1,c,i+1) or
dfs(r-1,c,i+1) or
dfs(r,c+1,i+1) or
dfs(r,c-1,i+1) )
path.remove((r,c)) #remove
return res
for r in range(rows):
for c in range(rows):
if dfs(r,c,0): return True
return False
print('9:',Solution().checkWord(board,word))
#10.Get all Subsets of Array - Backtracking - Leetcode 78 #dfs
nums = [1,2,3]
Output= [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
class Solution:
def subsets(self, nums:List[int])->List[List[int]]:
res=[]
def backtrack(start,path):
res.append(path[:])
for i in range(start,len(nums)):
path.append(nums[i]) #append
backtrack(i+1, path)
path.pop() #remove
backtrack(0, [])
return res
print(Solution().subsets(nums))
############# dynamic programing ###################
#1. recursive backtracking
def f1(n):
if n==0: return 0
if n==1: return 1
return (f1(n-1)+f1(n-2))
print('f1:',f1(10))
#2. topdown DP(dynamic programing) memorizaton
def fib(n): #O(n)O(n)
memo={0:0, 1:1}
def f(n):
if n in memo:
return memo[n]
memo[n]=f1(n-1)+f1(n-2)
return memo[n]
return f(n)
print('f2:',fib(10))
#3. Bottomup DP tabulation
def fib1(n):#O(n)O(n)
dp=[0,1]
for i in range(2, n+1):
new=dp[i-2]+dp[i-1]
dp.append(new)
return dp[n]
print('f3:',fib1(10))
#4. Bottomup No-mem DP
def fib2(n):#O(n)O(1)
if n<2: return n
prev,cur=0,1
for i in range(2,n+1):
prev,cur=cur,cur+prev
return cur
print('f4:',fib2(10))
#11.List All Permutations II - Backtracking - Leetcode 47 #dfs
nums = [1,1,2]
Output=[[1,1,2],[1,2,1],[2,1,1]]
class Solution:
def permutation(self, nums:List[int]):
res=[]
def backtrack(start):
if start==len(nums):
res.append(nums[:])
return
used=set()
for i in range(start, len(nums)):
if nums[i] in used:
continue
used.add(nums[i])
nums[start],nums[i]=nums[i],nums[start]
backtrack(start+1)
nums[start],nums[i]=nums[i],nums[start]
nums.sort()
backtrack(0)
return res
print(Solution().permutation(nums))
#12。Set Row/Cols zero in Matrix Zeroes - In-place - Leetcode 73
Input=[[1,1,1],[1,0,1],[1,1,1]]
Output=[[1,0,1],[0,0,0],[1,0,1]]
class Solution:
def setZero(self, matrix: List[List[int]])->List[List[int]]:
rows,cols=len(matrix),len(matrix[0])
rowZero=False
#check row/col to be zero
for r in range(rows):
for c in range(cols):
if matrix[r][c]==0:
matrix[0][c]=0
if r>0:
matrix[r][0]=0
else:
rowZero=True
for r in range(1,rows):
for c in range(1, cols):
if matrix[0][r]==0 or matrix[r][0]==0:
matrix[r][c]=0
if matrix[0][0]==0:
for r in range(rows):
matrix[r][0]=0
if rowZero:
for c in range(cols):
matrix[0][r]=0
return matrix
print(Solution().setZero(Input))
#13 How many Meeting Rooms II - Leetcode 253 - Python
Input= [[0, 30],[5, 10],[15, 20]]
Output= 2
class Solution:
def meetingRooms(self, intervals):
start=sorted([i[0] for i in intervals])
end=sorted([i[1] for i in intervals])
res,count=0,0
s,e=0,0
while s<len(intervals):
if start[s]<end[e]:
s+=1
count+=1
else:
e+=1
count-=1
res=max(res,count)
return res
print(Solution().meetingRooms(Input))
#14 Get Cell Both Pacific Atlantic Water Flow - Leetcode 417 - Python
heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output= [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]
class Solution:
def pacificAlantic(self, heights):
rows,cols=len(heights), len(heights[0])
pac,atl=set(),set()
res=[]
def dfs(r,c,visit,preHeight):
if ((r,c) in visit or r<0 or c<0 or r==rows or c==cols or heights[r][c]<preHeight):
return
visit.add((r,c))
dfs(r+1,c,visit,heights[r][c])
dfs(r-1,c,visit,heights[r][c])
dfs(r,c+1,visit,heights[r][c])
dfs(r,c-1,visit,heights[r][c])
for c in range(cols):
dfs(0,c,pac,heights[0][c])
dfs(rows-1,c,atl,heights[rows-1][c])
for r in range(rows):
dfs(r,0,pac,heights[r][0])
dfs(r,cols-1,atl,heights[r][c])
for r in range(rows):
for c in range(cols):
if (r,c) in pac and (r,c) in atl:
res.append([r,c])
return res
print(Solution().pacificAlantic(heights))
#15 Get All Subarrays Sum Equals K - Prefix Sums - Leetcode 560 - Python
nums = [1,1,1]
k = 2
Output: 2
class Solution:
def subarraySum(self,nums,k):
res=0
curSum=0
prefixSums={0:1}
for i in nums:
curSum+=i
diff=curSum-k
res+=prefixSums.get(diff,0)
prefixSums[curSum]=1+prefixSums.get(curSum,0)
return res
print(Solution().subarraySum(nums,k))
#16.Get/Find Minimum element in Rotated Sorted Array - Binary Search - Leetcode 153 - Python
nums = [3,-1,0,1,2]
Output= 1
class Solution:
def findMin(self, nums):
l,r=0, len(nums)-1
res=nums[0]
while l<=r:
if nums[l]< nums[r]:
res=min(res,nums[l])
print(res)
break
mid=(l+r)//2
res=min(res,nums[mid])
print(res)
if nums[mid]>=nums[l]: l=mid+1
else: r=mid-1
return res
print('num:',Solution().findMin(nums))
##18. List Node for Binary Tree Level Order Traversal - BFS - Leetcode 102
# #bfs From root to layer by layer
# #dfs from root to left by left
root = [3,9,20,None,None,15,7]
Output= [[3],[9,20],[15,7]]
class TreeNode:
def __init__(self,val=0,left=None,right=None):
self.val=val
self.left=left
self.right=right
class Solution:
def createTree(self, level_order: List[Optional[int]]) -> Optional[TreeNode]:
if not level_order or level_order[0] is None:
return None
root = TreeNode(level_order[0])
queue = deque([root])
i = 1
while queue and i < len(level_order):
node = queue.popleft()
# 处理左子节点
if i < len(level_order) and level_order[i] is not None:
node.left = TreeNode(level_order[i])
queue.append(node.left)
i += 1
# 处理右子节点
if i < len(level_order) and level_order[i] is not None:
node.right = TreeNode(level_order[i])
queue.append(node.right)
i += 1
return root
def createTreeRecursive(self, values: List[Optional[int]]) -> Optional[TreeNode]:
if not values:
return None
def helper(index: int) -> Optional[TreeNode]:
if index >= len(values) or values[index] is None:
return None
node = TreeNode(values[index])
node.left = helper(2 * index + 1)
node.right = helper(2 * index + 2)
return node
return helper(0)
def printTree(self, root: Optional[TreeNode]) -> List[Optional[int]]:
if not root:
return []
result = []
queue = [root]
while queue:
node = queue.pop(0)
if node:
result.append(node.val)
queue.append(node.left)
queue.append(node.right)
else:
result.append(None)
while result and result[-1] is None:
result.pop()
return result
def printTreeRecursive(self, root: Optional[TreeNode]) -> List[Optional[int]]:
result = []
def helper(node: Optional[TreeNode]):
if not node:
result.append(None)
return
result.append(node.val)
helper(node.left)
helper(node.right)
if root:
helper(root)
while result and result[-1] is None:
result.pop()
return result
def levelOrder(self, root: Optional[TreeNode]) -> List[List[int]]:
q=collections.deque()
q.append(root)
res=[]
while q:
qlen=len(q)
level=[]
for i in range(qlen):
node=q.popleft()
if node:
level.append(node.val)
q.append(node.left)
q.append(node.right)
if level:
res.append(level)
return res
s=Solution()
print('input:',root)
root = s.createTreeRecursive(root)
print('check:',s.printTree(root))
print(s.levelOrder(root))
#19. Check Minimum Number of Swaps to Make String Balanced - Leetcode 1963 Weekly Contest - Python
s = "][]["
Output= 1
class Solution:
def minSwaps(self, s: str) -> int:
close,maxClose=0,0
for c in s:
if c=='[]':
close-=1
else:
close+=1
maxClose=max(close,maxClose)
return (maxClose+1)//2
print(Solution().minSwaps(s))
#20.Find minimum Path in Triangle - Dynamic Programming made Easy - Leetcode 120
triangle = [[2],[3,4],[6,5,7],[4,1,8,3]]
Output= 11
class Solution:
def minimumTotal(self, triangle: List[List[int]]) -> int:
dp=[0]*(len(triangle)+1)
for row in triangle[::-1]: #地翻天
for i,n in enumerate(row):
dp[i]=n+min(dp[i],dp[i+1])
print(dp)
return dp[0]
print(Solution().minimumTotal(triangle))
#21.Move and Flips to make Binary String Alternating - Sliding Window - Leetcode 1888 - Python??
s = "111000"
Output= 2
class Solution:
def minFlips(self, s: str) -> int:
print('enter minFlips')
n=len(s)
s=s+s
a1,a2='',''
for i in range(len(s)):
a1+='0' if i%2 else '1'
a2+='1' if i%2 else '0'
res=len(s)
dif1,dif2=0,0
l=0
for r in range(len(s)):
if s[r]!=a1[r]:
dif1+=1
if s[r]!=a2[r]:
dif2+=1
if (r-l+1)>n:
if s[r]!=a1[r]:
dif1-=1
if s[r]!=a2[r]:
dif2-=1
l+=1
if (r-l+1)==n:
res=min(res,dif1,dif2)
return res
print('======')
print(Solution().minFlips(s))
#22 To Swap Nodes in Pairs - Apple Interview Question - Leetcode 24
head = [1,2,3,4]
Output= [2,1,4,3]
class Solution:
def swapPairs(self, head: Optional[ListNode]) -> Optional[ListNode]:
print('enter swapPair')
dummy=ListNode(0,head)
pre,cur=dummy,head
while cur and cur.next:
nxtPair=cur.next.next
second=cur.next
second.next=cur
cur.next=nxtPair
pre.next=second
pre=cur
cur=nxtPair
return dummy.next
def swapPairsRecursive(self, head: Optional[ListNode]) -> Optional[ListNode]:
print('enter swapPairRecursive')
if not head or not head.next:
return head
first = head
second = head.next
# 第一个节点指向后面已经处理好的链表
first.next = self.swapPairsRecursive(second.next)
# 第二个节点指向第一个节点
second.next = first
# 返回新的头节点
return second
def createList(self, lst):
dummy = ListNode(0)
current = dummy
for val in lst:
current.next = ListNode(val)
current = current.next
return dummy.next
def printList(self,head):
result = []
while head:
result.append(head.val)
head = head.next
return result
s=Solution()
head=s.createList(head)
print(s.printList(head))
r=s.swapPairs(head)
print(s.printList(r))
r=s.swapPairsRecursive(r)
print(s.printList(r))
#23 Partition to get Equal Subset Sum - Dynamic Programming - Leetcode 416 - Python
nums = [1,5,11,5]
Output= True
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums)%2:
return False
dp=set()
dp.add(0)
target=sum(nums)//2
for i in range(len(nums)-1,-1,-1):
nxtDP=set()
for t in dp:
if (t+nums[i])==target:
return True
nxtDP.add(t+nums[i])
nxtDP.add(t)
dp=nxtDP
return True if target in dp else False
def canPartition1(self,nums):
total_sum = sum(nums)
if total_sum % 2 != 0:
return False
target = total_sum // 2
dp = [False] * (target + 1)
dp[0] = True # 空集的和为0
for num in nums:
for j in range(target, num - 1, -1):
dp[j] = dp[j] or dp[j - num]
return dp[target]
print(Solution().canPartition1(nums))
#24 Check Graph Valid Tree - Leetcode 261 - Python #dfs
n = 5
edges = [[0,1], [0,2], [0,3], [1,4]]
Output= True
class Solution:
def validTree(self,n,edges):
if not n: return True
adj={ i:[] for i in range(n) }
for n1,n2 in edges:
adj[n1].append(n2)
adj[n2].append(n1)
visit=set()
def dfs(i,prev):
if i in visit: return False
visit.add(i)
for j in adj[i]:
if j==prev:
continue
if not dfs(j,i):
return False
return True
return dfs(0,-1)
from collections import defaultdict, deque
def validTree1(self,n, edges):
if len(edges) != n - 1:
return False
# Build adjacency list
adj = defaultdict(list)
for u, v in edges:
adj[u].append(v)
adj[v].append(u)
visited = set()
queue = deque([0])
parent = {0: -1} # To keep track of the parent node
while queue:
node = queue.popleft()
visited.add(node)
for neighbor in adj[node]:
if neighbor == parent[node]:
continue
if neighbor in visited:
return False # Cycle detected
parent[neighbor] = node
queue.append(neighbor)
return len(visited) == n
print(Solution().validTree1(n,edges))
#25 Get Maximum Alternating Subsequence Sum(-+) - Dynamic Programming - Leetcode 1911 - Python
nums = [4,2,5,3]
Output= 7
class Solution:
def maxAlternatingSum(self, nums: List[int]) -> int:
add,sub=0,0
for num in nums:
add=max(sub+num,add)
sub=max(add-num, sub)
return add
print(Solution().maxAlternatingSum(nums))
#26 People can attend Meeting Rooms - Leetcode 252 - Python. #easy
Input=[[0,30],[5,10],[15,20]]
Output= False
class Solution:
def canAttendMeetings(self, intervals: List[List[int]]) -> bool:
intervals.sort(key=lambda x: x[0])
for i in range(1, len(intervals)):
if intervals[i][0]<intervals[i-1][1]: return False
return True
print(Solution().canAttendMeetings(Input))
#27 Increase get equal Frequency of the Most Frequent Element - Sliding Window - Leetcode 1838
nums = [1,2,4]
k = 5
Output= 3
class Solution:
def maxFrequency(self, nums: List[int], k: int) -> int:
nums.sort()
l,r=0,0
res,total=0,0
while r<len(nums):
total+=nums[r]
while nums[r]*(r-1+1)>total+k:
total-=nums[l]
l+=1
res=max(res,r-l+1)
r+=1
return res
print(Solution().maxFrequency(nums,k))
#28 Target Combination Sum IV - Dynamic Programming - Leetcode 377 - Python #answer is very simple
nums = [1,2,3]
target = 4
Output= 7
class Solution:
def combinationSum4(self, nums: List[int], target: int) -> int:
dp={0:1}
for total in range(1, target +1):
dp[total]=0
for n in nums:
dp[total]+=dp.get(total-n,0)
return dp[total]
print(Solution().combinationSum4(nums,target))
#29 Check Warmer Daily Temperatures - Monotonic Stack - Leetcode 739 - Python
temperatures = [73,74,75,71,69,72,76,73]
Output= [1,1,4,2,1,1,0,0]
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res=[0]*len(temperatures)
stack=[]
for i,t in enumerate(temperatures):
while stack and t>stack[-1][0]:
stackT, stackInd=stack.pop()
res[stackInd]=(i-stackInd)
stack.append([t,i])
return res
print(Solution().dailyTemperatures(temperatures))
#35 Get remove numbers Maximum Number of Removable Characters - Binary Search - Leetcode 1898 - Python
s = "abcacb"
p = "ab"
removable = [3,1,0]
Output=2
class Solution:
def removeChar(self, s:str, p:str,removable:List[int])->int:
def isSubseq(s, subseq):
i1,i2=0,0
while i1<len(s) and i2<len(subseq):
if i1 in removed or s[i1]!=subseq[i2]:
i1+=1
continue
i1+=1
i2+=1
return i2==len(subseq)
res=0
l,r=0,len(removable)-1
while l<=r:
m=(l+r)//2
removed=set(removable[:m+1])
print(s,p)
if isSubseq(s,p):
res=max(res,m+1)
l=m+1
else:
r=m-1
return res
print(Solution().removeChar(s,p,removable))
"""
Q1
Given two arguments (current working directory and directory to change to), implement the cd (change directory) command on Unix as a string processing function, which synthesize the output (path) as string.
| cwd | cd (arg) | output
| -------- | -------------- | ------
| / | foo | /foo
| /foo/bar | ../../../../.. | /
| /x/y | ../p/../q | /x/q
| /x/y | /p/./q | /p/q
/, cd foo, /foo
Note
1. all inputs are valid no empty\
2. you can find all the folders exist, /foo/foo/foo infinitly
3. input only contains /, letters, .. (goes back to the parent directory), . (stays at the current directory)
"""
def cd(cwd, cd_arg):
if cd_arg.startswith('/'):
abspath = cd_arg
else:
abspath = cwd + '/' + cd_arg if cwd != '/' else '/' + cd_arg
components = abspath.split('/')
print(components)
stack = []
for component in components:
if component == '' or component == '.': #不理会
continue
elif component == '..': # 退一层
if stack:
stack.pop()
else: # 进一层
stack.append(component)
print('st:',stack)
result = '/' + '/'.join(stack)
print(result)
return result if result != '' else '/'
matrix=[['/' ,'foo' ,'/foo'],
[ '/foo/bar' , '../../../../..', '/'],
[ '/x/y ' , '../p/../q ' , '/x/q'],
[ '/x/y ' , '/p/./q ' , '/p/q']]
def test(matrix):
for i in matrix:
print(cd(i[0],i[1]))
print('res',i[2])
a=cd(i[0],i[1]).strip()
assert( a==i[2])
test(matrix)
"""
Q2:
Given an input string where all spaces have been removed, and an English dictionary, insert spaces back into the string so that it contains all valid words.
Let me give you some examples
Example: Input: s = "cathat", wordDict = ["cat","hat"] Output: "cat hat"
Input: s = "applepenapple", wordDict = ["apple","pen"] Output: "apple pen apple".
Input: s = "catshat", wordDict = ["cat","hat"] Output: ""
cathat (input) -> "cat hat"
Note:
1. you will need to write this one in a recursive manner
2. you will need to travese all the possible solutions but just need to return one at the end.
"""
s='hongqizhanghat'
wordDict=["hat","zhang","hongqi"]
def wordBreak(s, wordDict):
def helper(s, words, start):
if start == len(s): #结束条件，若 start 到终点
return ""
for end in range(start + 1, len(s) + 1): #右指针后移循环
prefix = s[start:end] #取一单词
if prefix in words: #是否在字典中
rest = helper(s, words, end) #进行下一个词
if rest is not None: #若取到放到结果加空
return prefix + (" " + rest if rest else "")
return None
words = set(wordDict)
result = helper(s, words, 0) #从开始调用
return result if result is not None else ""
print(wordBreak(s,wordDict))
def helper(s, words, start):
if start == len(s): #结束条件，若 start 到终点
return ""
for end in range(start + 1, len(s) + 1): #右指针后移循环
prefix = s[start:end] #取一单词
if prefix in words: #是否在字典中
rest = helper(s, words, end) #进行下一个词
if rest is not None: #若取到放到结果加空
return prefix + (" " + rest if rest else "")
return None
print(helper(s, set(wordDict), 0) )
amount = 100
coins = [1,5,10,25]
#Output: 4
def change(amount:int,coins:List[int])->int:
dp = [0]*(amount+1)
dp[0] = 1
for coin in coins:
print(coin)
for way in range(coin,amount+1):
print(way-coin)
dp[way] += dp[way-coin]
print(dp)
return dp[amount]
print(change(amount,coins))