201. Bitwise AND of Numbers Range （Medium）
Given two integers left and right that represent the range [left, right], return the bitwise AND of all numbers in this range, inclusive.
class Solution:
def rangeBitwiseAnd(self, left: int, right: int) -> int:
if left==right: return left
res = 0
for pos in range(32):
res |= 1 << pos
for n in range(left,right+1):
if (n & 1<<pos) >> pos ==0:
res ^= 1 << pos
break
return res
#answer way of writing
class Solution:
def rangeBitwiseAnd(self, m: int, n: int) -> int:
shift = 0
# find the common 1-bits
while m < n:
m = m >> 1
n = n >> 1
shift += 1
return m << shift
#
class Solution:
def rangeBitwiseAnd(self, m: int, n: int) -> int:
while m < n:
# turn off rightmost 1-bit
n = n & (n - 1)
return m & n
初次尝试，time limit exceeded， 32位过一次，一旦发现在pos位上为0，就break。 还是速度慢， after the AND operation on all the numbers, the remaining part of bit strings is the common prefix of all these bit strings.As a result, we then can reformulate the problem as "given two integer numbers, we are asked to find the common prefix of their binary strings." 思路： shift 直到m n相等，然后再 shift back。 这样就找到了common prefix。另一解法，思路：关闭右侧最后是1的位，然后和左侧求&。
When we do AND bit operation between number and number-1, the rightmost bit of one in the original number would be turned off (from one to zero).
202. Happy Number （Easy）
Write an algorithm to determine if a number n is happy.
Input: n = 19
Output: true
Explanation:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
class Solution:
def isHappy(self, n: int) -> bool:
visited =set()
while n!=1:
if n in visited: return False
visited.add(n)
new_n =0
while n:
lastdig = n%10
new_n += lastdig*lastdig
n //= 10
n=new_n
return True
#MY ANSWER
class Solution:
def isHappy(self, n: int) -> bool:
s =set()
def helper(n):
if n==1: return True
res = 0
while n:
lastdig = n%10
n = n//10
res+=lastdig**2
if res in s:return False
s.add(res)
return helper(res)
return helper(n)
203. Remove Linked List Elements （Easy）
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: Optional[ListNode], val: int) -> Optional[ListNode]:
if not head: return head
dummyhead = ListNode(val='NULL',next=head)
cur=dummyhead
while cur and cur.next:
while cur.next and cur.next.val==val:
cur.next=cur.next.next
cur=cur.next
return dummyhead.next
204. Count Primes (Medium)
class Solution:
def countPrimes(self, n: int) -> int:
if n <=2:
return 0
primes = [True] * n
primes[0] = primes[1] = False
for i in range(2, int(n ** 0.5) + 1):
if primes[i]:
primes[i * i: n: i] = [False] * len(primes[i * i: n: i])
#如果i是pime 比如i=2 那么 i的倍数肯定不是prime 从i**2 开始。
return sum(primes)
直接用判断是否位质数方法会time limit exceeded。 思路：如果i是pime 比如i=2 那么 i的倍数肯定不是prime 从i**2 开始。
def isP(num):
for i in range(2,num//2+1):
if num%i==0:
return False
return True
205. Isomorphic Strings （Easy）
Given two strings s and t, determine if they are isomorphic.
Two strings s and t are isomorphic if the characters in s can be replaced to get t.
class Solution:
def isIsomorphic(self, s: str, t: str) -> bool:
if len(s)!=len(t): return False
l=len(s)
dic1 = dict()
dic2 = dict()
for i in range(l):
a = s[i]
b = t[i]
if a in dic1:
if dic1[a]!=b:
return False
if b in dic2:
if dic2[b]!=a:
return False
dic1[a] = b
dic2[b] = a
return True
206. Reverse Linked List (Easy)
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
pre = None
while head:
headnext=head.next
head.next = pre
pre = head
head=headnext
return pre
207. Course Schedule (Medium)
class Solution:
class Node:
def __init__(self,val=None):
self.val = val
self.nei = []
self.ind = 0 #indegree
self.status = -1 # -1 not visited, 0 visiting, 1 visited
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# DAG 判断
#
# 建立graph
nodes = [self.Node(val=i) for i in range(numCourses)]
for row in prerequisites:
a,b = row
nodes[b].nei.append(nodes[a])
nodes[a].ind+=1
#DFS 法
def dfs(node):
# return True 无环 False 有环
node.status=0
for nei in node.nei:
if nei.status==-1:
if not dfs(nei):
return False
elif nei.status == 0:
return False
node.status=1
return True
for node in nodes:
if node.status==-1:
if not dfs(node):
return False
return True
# upper DFS lower BFS
class Solution:
class Node:
def __init__(self,val=None):
self.val = val
self.nei = []
self.ind = 0 #indegree
self.status = -1 # -1 not visited, 0 visiting, 1 visited
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
# DAG 判断
#
# 建立graph
nodes = [self.Node(val=i) for i in range(numCourses)]
for row in prerequisites:
a,b = row
nodes[b].nei.append(nodes[a])
nodes[a].ind+=1
#bfs 法
queue=[]
cnt=0
for node in nodes:
if node.ind==0:
queue.append(node)
while queue:
v=queue.pop(0)
cnt+=1
for nei in v.nei:
nei.ind-=1
if nei.ind==0:
queue.append(nei)
return cnt==numCourses
#MY ANSWER
class Solution:
def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
indegree = {i:0 for i in range(numCourses)}
b2a = collections.defaultdict(set)
# a<-b
# c<-d
# a<-b
# \| |\
# c->d
for row in prerequisites:
a,b = row
b2a[b].add(a)
indegree[a]+=1
queue = []
tobedel = set()
for key in indegree:
if indegree[key] == 0:
queue.append(key)
tobedel.add(key)
for key in tobedel:
del indegree[key]
while queue:
for _ in range(len(queue)):
b = queue.pop(0)
#need b->a map
for a in b2a[b]:
indegree[a]-=1
if indegree[a] == 0:
queue.append(a)
del indegree[a]
return not indegree
感觉是图的算法，判断是否为DAG。BFS找入度为0的。 DFS时候，如果正在搜索某V，但又回到了V。证明有环路。注意需要3个状态来表示node状态， 【visited，visiting，not visited】
需要补充拓扑排序算法解决变种题。
# TopoSort sudo
queue = []
for 图中每个顶点V:
if indegree(V)==0:
queue.append(V)
while queue:
V=queue.pop(0)
输出V，记录V的输出序号cnt++
for V的每个邻居 W:
indegree(W) -= 1
if indegree(W)==0:
queue.append(W)
if cnt!=|V|:
ERROR(图中有回路)
208. Implement Trie (Prefix Tree)
class Trie:
def __init__(self):
self.next= dict()
self.isword=False
def insert(self, word: str) -> None:
if word:
char = word[0]
rest = word[1:]
if char not in self.next:
self.next[char] = Trie()
self.next[char].insert(rest)
else:
self.isword=True
def search(self, word: str) -> bool:
if not word:
return self.isword
char = word[0]
rest = word[1:]
if char in self.next:
if not self.next[char].search(rest):
return False
else:
return False
return True
def startsWith(self, prefix: str) -> bool:
if not prefix:
return True
char=prefix[0]
rest=prefix[1:]
if char in self.next:
if not self.next[char].startsWith(rest):
return False
else:
return False
return True
#MY ANSWER
class Trie:
def __init__(self):
self.data = collections.defaultdict(Trie)
self.isword = False
def insert(self, word: str) -> None:
if not word:
self.isword = True
return
head=word[0]
rest = word[1:]
if head not in self.data:
self.data[head] = Trie()
self.data[head].insert(rest)
def search(self, word: str) -> bool:
if not word:
if self.isword:
return True
else:
return False
head = word[0]
rest = word[1:]
if head not in self.data: return False
return self.data[head].search(rest)
def startsWith(self, prefix: str) -> bool:
if not prefix: return True
head = prefix[0]
rest = prefix[1:]
if head not in self.data: return False
return self.data[head].startsWith(rest)
209. Minimum Size Subarray Sum (Medium)
# answer way of writting
class Solution:
def minSubArrayLen(self, target: int, nums: List[int]) -> int:
# two pointer
l=len(nums)
res=float('inf')
left=0
sum_=0
for i,n in enumerate(nums):
sum_+=n
while sum_>=target:
res=min(res,i-left+1)
sum_-=nums[left]
left+=1
return res if res!= float('inf') else 0
果然是two pointer, 学习answer写法，很清晰。
210. Course Schedule II （Medium）
class Solution:
class Node:
def __init__(self,val=None):
self.val=val
self.nei = []
self.indegree = 0
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
# dag
nodes = [self.Node(val=i) for i in range(numCourses)]
for a,b in prerequisites:
nodes[b].nei.append(nodes[a])
nodes[a].indegree+=1
queue = []
for node in nodes:
if node.indegree==0:
queue.append(node)
res = []
while queue:
cur=queue.pop(0)
res.append(cur.val)
for w in cur.nei:
w.indegree-=1
if w.indegree==0:
queue.append(w)
return res if len(res)==numCourses else []
###
class Solution:
def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
indegree = {i:0 for i in range(numCourses)}
b2a = collections.defaultdict(set)
queue = deque()
for row in prerequisites:
a,b = row
# a<-b
indegree[a]+=1
b2a[b].add(a)
res = []
tobedel= []
for key in indegree:
if indegree[key]==0:
res.append(key)
tobedel.append(key)
queue.append(key)
for key in tobedel:
del indegree[key]
while queue:
for _ in range(len(queue)):
b = queue.popleft()
for a in b2a[b]:
indegree[a]-=1
if indegree[a]==0:
del indegree[a]
queue.append(a)
res.append(a)
return res if not indegree else []
BFS 拓扑排序，找出indegree==0的node output。