281. Zigzag Iterator （Medium）
Given two vectors of integers v1 and v2, implement an iterator to return their elements alternately.
class ZigzagIterator:
def __init__(self, v1: List[int], v2: List[int]):
self.up = True
self.v1=v1
self.v2=v2
def next(self) -> int:
if not self.v1:
return self.v2.pop(0)
if not self.v2:
return self.v1.pop(0)
self.up = not self.up
if self.up:
return self.v2.pop(0)
else:
return self.v1.pop(0)
def hasNext(self) -> bool:
return len(self.v1)>0 or len(self.v2)>0
# Your ZigzagIterator object will be instantiated and called as such:
# i, v = ZigzagIterator(v1, v2), []
# while i.hasNext(): v.append(i.next())
282. Expression Add Operators (Hard)
Given a string num that contains only digits and an integer target, return all possibilities to insert the binary operators '+', '-', and/or '*' between the digits of num so that the resultant expression evaluates to the target value.Note that operands in the returned expressions should not contain leading zeros.
#MY ANSWER
class Solution:
def addOperators(self, num: str, target: int) -> List[str]:
if not num: return []
res = []
def bt(tmp,num):
if not num:
res.append(tmp)
else:
for i in range(1,len(num)+1):
head = num[:i]
rest = num[i:]
if len(head)>1 and head[0]=='0': continue
if rest:
for op in '+-*':
bt( tmp+head+op ,rest)
else:
bt(tmp+head,rest)
bt('',num)
#print(res)
return [r for r in res if eval(r)==target]
class Solution:
def addOperators(self, num: 'str', target: 'int') -> 'List[str]':
N = len(num)
answers = []
def recurse(index, prev_operand, current_operand, value, string):
# Done processing all the digits in num
if index == N:
# If the final value == target expected AND
# no operand is left unprocessed
if value == target and current_operand == 0:
answers.append("".join(string[1:]))
return
# Extending the current operand by one digit
current_operand = current_operand*10 + int(num[index])
str_op = str(current_operand)
# To avoid cases where we have 1 + 05 or 1 * 05 since 05 won't be a
# valid operand. Hence this check
if current_operand > 0:
# NO OP recursion
recurse(index + 1, prev_operand, current_operand, value, string)
# ADDITION
string.append('+'); string.append(str_op)
recurse(index + 1, current_operand, 0, value + current_operand, string)
string.pop();string.pop()
# Can subtract or multiply only if there are some previous operands
if string:
# SUBTRACTION
string.append('-'); string.append(str_op)
recurse(index + 1, -current_operand, 0, value - current_operand, string)
string.pop();string.pop()
# MULTIPLICATION
string.append('*'); string.append(str_op)
recurse(index + 1, current_operand * prev_operand, 0, value - prev_operand + (current_operand * prev_operand), string)
string.pop();string.pop()
recurse(0, 0, 0, 0, [])
return answers
第一眼感觉是用backtracking，写出了第一版，但是没考虑1） number 可以是1位可以是2位，3位 etc， 2）乘法的优先级高于加减，所以需要tracking operator是什么。 3）不可以backtracking到最后eval结果，太费时间。 直接看答案了。。。答案： 关键在于除了加减乘以外，增加一个不操作operator， 12-->123 是 12乘以10+3 extending 当前值12 by one digit， 12乘以10。 看了答案还是懵逼。细节太多但都符合逻辑。
283. Move Zeroes （Easy）
Given an integer array nums, move all 0's to the end of it while maintaining the relative order of the non-zero elements.
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
pos=0
for i,n in enumerate(nums):
if n!=0:
nums[pos]=n
pos+=1
while pos<len(nums):
nums[pos]=0
pos+=1
#SWAP is a better solution
class Solution:
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
pos=0
for i,n in enumerate(nums):
if n!=0:
nums[pos],nums[i] = nums[i],nums[pos]
pos+=1
284. Peeking Iterator (Medium)
# Below is the interface for Iterator, which is already defined for you.
#
# class Iterator:
# def __init__(self, nums):
# """
# Initializes an iterator object to the beginning of a list.
# :type nums: List[int]
# """
#
# def hasNext(self):
# """
# Returns true if the iteration has more elements.
# :rtype: bool
# """
#
# def next(self):
# """
# Returns the next element in the iteration.
# :rtype: int
# """
class PeekingIterator:
def __init__(self, iterator):
"""
Initialize your data structure here.
:type iterator: Iterator
"""
self.iterator=iterator
self.peekval=None
def peek(self):
"""
Returns the next element in the iteration without advancing the iterator.
:rtype: int
"""
if self.peekval:
return self.peekval
else:
self.peekval=self.iterator.next()
return self.peekval
def next(self):
"""
:rtype: int
"""
if self.peekval is not None:
peekval=self.peekval
self.peekval=None
return peekval
else:
return self.iterator.next()
def hasNext(self):
"""
:rtype: bool
"""
return self.iterator.hasNext() or self.peekval is not None
# Your PeekingIterator object will be instantiated and called as such:
# iter = PeekingIterator(Iterator(nums))
# while iter.hasNext():
# val = iter.peek() # Get the next element but not advance the iterator.
# iter.next() # Should return the same value as [val].
#MY ANSWER
class PeekingIterator:
def __init__(self, iterator):
"""
Initialize your data structure here.
:type iterator: Iterator
"""
self.iter = iterator
self.val = None
def peek(self):
"""
Returns the next element in the iteration without advancing the iterator.
:rtype: int
"""
if self.val is None:
if self.iter.hasNext():
self.val = self.iter.next()
return self.val
def next(self):
"""
:rtype: int
"""
if self.val is None:
self.peek()
val = self.val
self.val=None
return val
def hasNext(self):
"""
:rtype: bool
"""
return self.val is not None or self.iter.hasNext()
285. Inorder Successor in BST (Medium)
Given the root of a binary search tree and a node p in it, return the in-order successor of that node in the BST. If the given node has no in-order successor in the tree, return null.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'Optional[TreeNode]':
stack = []
while root and root.val!=p.val:
stack.append(root)
if p.val<root.val:
root=root.left
else:
root=root.right
if p.right:
node=p.right
while node.left:
node=node.left
return node
else:
while stack:
node=stack.pop()
if node.val>p.val:
return node
return None
#ANSWER
class Solution:
def inorderSuccessor(self, root: 'TreeNode', p: 'TreeNode') -> 'TreeNode':
successor = None
while root:
if p.val >= root.val:
root = root.right
else:
successor = root
root = root.left
return successor
#MY ANSWER
class Solution:
def inorderSuccessor(self, root: TreeNode, p: TreeNode) -> Optional[TreeNode]:
stack = []
pre = None
while root or stack:
while root:
stack.append(root)
root=root.left
root =stack.pop()
if pre==p:
return root
pre = root
root = root.right
答案更巧妙。
286. Walls and Gates （Medium）
You are given an m x n grid rooms initialized with these three possible values.
-1 A wall or an obstacle.
0 A gate.
INF Infinity means an empty room. We use the value 231 - 1 = 2147483647 to represent INF as you may assume that the distance to a gate is less than 2147483647.
Fill each empty room with the distance to its nearest gate. If it is impossible to reach a gate, it should be filled with INF.
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
from collections import deque
m=len(rooms)
n=len(rooms[0])
INF=2**31-1
q = deque()
for i in range(m):
for j in range(n):
if rooms[i][j]==0:
q.append((i,j))
level=0
visited = set()
while q:
level+=1
for _ in range(len(q)):
i,j = q.popleft()
visited.add((i,j))
for ii,jj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
if ii>=0 and ii<m and jj>=0 and jj<n and (ii,jj) not in visited:
if rooms[ii][jj]!=0 and rooms[ii][jj]!=-1:
rooms[ii][jj] = level
q.append((ii,jj))
visited.add((ii,jj))
#ANSWER
class Solution:
def wallsAndGates(self, rooms: List[List[int]]) -> None:
"""
Do not return anything, modify rooms in-place instead.
"""
from collections import deque
m=len(rooms)
n=len(rooms[0])
INF=2**31-1
q = deque()
for i in range(m):
for j in range(n):
if rooms[i][j]==0:
q.append((i,j))
level=0
while q:
for _ in range(len(q)):
i,j = q.popleft()
for ii,jj in [(i+1,j),(i-1,j),(i,j+1),(i,j-1)]:
if ii>=0 and ii<m and jj>=0 and jj<n and rooms[ii][jj]==INF :
rooms[ii][jj] = rooms[i][j]+1
q.append((ii,jj))
第一眼感觉用bfs做，从gates 处扫不是墙和gate的rooms距离。 差点忘了bfs 要for _ in range(len(queue)) ..... 答案不用visited level 解决， 因为BFS所以只要INF 变成距离就是最短距离， 从什么地方变得距离？就是rooms[ii][jj] = rooms[i][j]+1
287. Find the Duplicate Number （Medium）
Given an array of integers nums containing n + 1 integers where each integer is in the range [1, n] inclusive.
There is only one repeated number in nums, return this repeated number.
You must solve the problem without modifying the array nums and uses only constant extra space.
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
for num in nums:
cur = abs(num)
if nums[cur] < 0:
duplicate = cur
break
nums[cur] = -nums[cur]
# Restore numbers
for i in range(len(nums)):
nums[i] = abs(nums[i])
return duplicate
#ANSWER
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
duplicate = 0
n = len(nums)
bits = n.bit_length()
for bit in range(bits):
mask = 1 << bit
base_count = 0
nums_count = 0
for i in range(n):
# If bit is set in number (i) then add 1 to base_count
if i & mask:
base_count += 1
# If bit is set in nums[i] then add 1 to nums_count
if nums[i] & mask:
nums_count += 1
# If the current bit is more frequently set in nums than it is in
# the range [1, 2, ..., n] then it must also be set in the duplicate number.
if nums_count - base_count > 0:
duplicate |= mask
return duplicate
#ANSWER
class Solution:
def findDuplicate(self, nums: 'List[int]') -> 'int':
low = 1
high = len(nums)-1
while low < high:
mid = low+(high-low)//2
count = 0
for i in nums:
if i <= mid:
count+=1
if count <= mid:
low = mid+1
else:
high = mid
return low
#ANSWER
class Solution:
def findDuplicate(self, nums: List[int]) -> int:
#who can think it as cycled two pointer problem?
slow = nums[0]
fast = nums[0]
while True:
slow = nums[slow]
fast = nums[nums[fast]]
if slow==fast:
break
fast = nums[0]
while slow!=fast:
slow=nums[slow]
fast=nums[fast]
return slow
一堆double数中找single容易，用xor就可以， 但一堆single中找double。。。 答案思路： 思路1）标负。符号所在位置表示数出现过没。 nums[cur]小于0表示 cur这个数出现过。 2）bitmask 3）binary search 4）Cycle Detection，这个方法最妙。
288. Unique Word Abbreviation （Medium）
The abbreviation of a word is a concatenation of its first letter, the number of characters between the first and last letter, and its last letter. If a word has only two characters, then it is an abbreviation of itself.
class ValidWordAbbr:
def __init__(self, dictionary: List[str]):
import collections
self.dic= collections.defaultdict(set)
for w in dictionary:
key=self.sort(w)
self.dic[key].add(w)
#print(self.dic)
def sort(self,w):
if len(w)<=2:
key=w
else:
key=w[0]+str(len(w[1:-1])) +w[-1]
return key
def isUnique(self, word: str) -> bool:
key=self.sort(word)
if key not in self.dic or (len(self.dic[key])==1 and list(self.dic[key])[0]==word):
return True
return False
# Your ValidWordAbbr object will be instantiated and called as such:
# obj = ValidWordAbbr(dictionary)
# param_1 = obj.isUnique(word)
#Better solution
class ValidWordAbbr(object):
def getkey(self,word):
if len(word)<=2:
return word
else:
return word[0]+str(len(word[1:-1]))+word[-1]
def __init__(self, dictionary):
"""
:type dictionary: List[str]
"""
self.dic=dict()
for word in dictionary:
key=self.getkey(word)
if key in self.dic and word!=self.dic[key]:
self.dic[key]='#'
else:
self.dic[key]=word
def isUnique(self, word):
"""
:type word: str
:rtype: bool
"""
key=self.getkey(word)
if key in self.dic and self.dic[key]==word:
return True
elif key not in self.dic:
return True
return False
289. Game of Life (Medium)
class Solution:
def gameOfLife(self, board: List[List[int]]) -> None:
"""
Do not return anything, modify board in-place instead.
"""
m=len(board)
n=len(board[0])
#solve it in-place
#rule
# live cell =1
# #nei <2 die
# #nei 2 or 3 live
# #nei >3 die
# dead cell = 0
# #nei 3 live
#
# save live die in next round with (X//10)%2 if live save as 10+old
# if die save as 20+old
# when get old value old = old%10
for i in range(m):
for j in range(n):
live=0
old=board[i][j]%10
if old==1:
livecell=True
else:
livecell=False
for nei in [(i+1,j),(i-1,j),(i,j+1),(i,j-1),(i+1,j+1),(i+1,j-1),(i-1,j+1),(i-1,j-1)]:
ii,jj=nei
if ii<m and ii>=0 and jj<n and jj>=0:
live+=board[ii][jj]%10
if livecell:
if live==2 or live==3:
board[i][j]= 10+old
else:
board[i][j]= 20+old
else:
if live==3:
board[i][j] = 10+old
for i in range(m):
for j in range(n):
board[i][j] = (board[i][j]//10)%2
#INF CASE
def gameOfLifeInfinite(self, live):
ctr = collections.Counter((I, J)
for i, j in live
for I in range(i-1, i+2)
for J in range(j-1, j+2)
if I != i or J != j)
return {ij
for ij in ctr
if ctr[ij] == 3 or ctr[ij] == 2 and ij in live}
def gameOfLife(self, board):
live = {(i, j) for i, row in enumerate(board) for j, live in enumerate(row) if live}
live = self.gameOfLifeInfinite(live)
for i, row in enumerate(board):
for j in range(len(row)):
row[j] = int((i, j) in live)
290. Word Pattern （Easy）
class Solution:
def wordPattern(self, pattern: str, s: str) -> bool:
dic1=dict()
dic2=dict()
if len(pattern)!=len(s.split()): return False
for k,v in zip(s.split(),pattern):
if k not in dic1:
dic1[k]=v
else:
if dic1[k]!=v:
return False
if v not in dic2:
dic2[v]=k
else:
if dic2[v]!=k:
return False
return True
注意是一一映射，所以需要2个dict检查， 注意corner case。