151. Reverse Words in a String （Medium）
Given an input string s, reverse the order of the words.
class Solution:
def reverseWords(self, s: str) -> str:
if not s: return s
#trim space
tmp=''
while s:
if s[0]!=' ':
tmp+=s[0]
else:
if tmp and tmp[-1]!=' ' :
tmp+=' '
s=s[1:]
while tmp and tmp[-1]==' ':
tmp=tmp[:-1]
s = [e for e in tmp]
print(s)
def rev(s,i,j):
while i<=j:
s[i],s[j]=s[j],s[i]
i+=1
j-=1
return s
#rev all
s = rev(s,0,len(s)-1)
start=0
for i in range(len(s)):
if s[i]==' ':
s = rev(s,start,i-1)
start=i+1
s=rev(s,start,len(s)-1)
return ''.join(s)
#quick way using python function
class Solution:
def reverseWords(self, s: str) -> str:
def rev(e):
w=[i for i in e]
return ''.join(w[::-1])
s=rev(s)
res=[]
for e in s.strip().split():
res.append(rev(e))
return ' '.join(res)
152. Maximum Product Subarray (Medium)
Given an integer array nums, find a contiguous non-empty subarray within the array that has the largest product, and return the product.
class Solution:
def maxProduct(self, nums: List[int]) -> int:
# dp[i][j] is max subarry product till nums[i].. nums[j]
# dp[i][i] = nums[i]
# -2 -3 -4 -5 -6
# -3 -4 -5 -6
# max_dp[i][j] = max(min_dp[i][j-1]*nums[j], max_dp[i][j-1]*nums[j], nums[j])
# min_dp[i][j] = min(max_dp[i][j-1]*nums[j], min_dp[i][j-1]*nums[j], nums[j])
# j>=i
#
l=len(nums)
if l==1: return nums[0]
res = float('-inf')
max_dp = [[float('-inf')]*l for i in range(l)]
min_dp = [[float('inf')]*l for i in range(l)]
for i in range(l):
max_dp[i][i] = nums[i]
min_dp[i][i] = nums[i]
res = max(res,max_dp[i][i])
for i in range(l):
for j in range(l):
if i>=j:continue
max_dp[i][j] = max(min_dp[i][j-1]*nums[j], max_dp[i][j-1]*nums[j], nums[j])
min_dp[i][j] = min(max_dp[i][j-1]*nums[j], min_dp[i][j-1]*nums[j], nums[j])
res=max(res,max_dp[i][j])
#for row in max_dp:
# print(row)
#for col in min_dp:
# print(col)
return res
# 搞定 O（n）解法
class Solution:
def maxProduct(self, nums: List[int]) -> int:
# max_dp[i] = maxProduct up to nums[0] ... nums[i]
# min_dp[i] = minProduct up to nums[0] ... nums[i]
res = float('-inf')
l=len(nums)
max_dp = [float('-inf')]*l
min_dp = [float('inf')]*l
for i in range(l):
max_dp[i] = max(nums[i],max_dp[i-1]*nums[i],min_dp[i-1]*nums[i]) if i!=0 else nums[i]
res = max(res,max_dp[i])
min_dp[i] = min(nums[i],min_dp[i-1]*nums[i],max_dp[i-1]*nums[i]) if i!=0 else nums[i]
#print(max_dp)
#print(min_dp)
return res
想了个dp 但是O(n*n)的 time limit exceeded， 所以应该有O（n）的dp解法。
思路： 由于nums的正负符号来回变化，所以需要追踪最大乘积和最小乘积。令max_dp[i] 表示用nums【0】到nums【i】所能得到的最大乘积。 min_dp[i]表示用nums【0】到nums【i】所能得到的最大乘积。 则 max_dp[i] = max(nums[i],max_dp[i-1]*nums[i],min_dp[i-1]*nums[i]) min_dp[i] = min(nums[i],min_dp[i-1]*nums[i],max_dp[i-1]*nums[i]) 由于dp【i】只与dp【i-1】有关，所以甚至能简化为O（1）space的解。
153. Find Minimum in Rotated Sorted Array (Medium)
Suppose an array of length n sorted in ascending order is rotated between 1 and n times. For example, the array nums = [0,1,2,4,5,6,7] might become:
[4,5,6,7,0,1,2] if it was rotated 4 times.
[0,1,2,4,5,6,7] if it was rotated 7 times.
Notice that rotating an array [a[0], a[1], a[2], ..., a[n-1]] 1 time results in the array [a[n-1], a[0], a[1], a[2], ..., a[n-2]].
Given the sorted rotated array nums of unique elements, return the minimum element of this array.
You must write an algorithm that runs in O(log n) time.
class Solution:
def findMin(self, nums: List[int]) -> int:
if nums[0]>nums[-1]:
#rotated
l=0
r=len(nums)-1
while l <= r:
m=(l+r)//2
if nums[m] > nums[m+1]:
return nums[m+1]
if nums[m-1] > nums[m]:
return nums[m]
if nums[m] > nums[l]:
l =m+1
else:
r = m-1
else:
return nums[0]
#MY ANSWER
class Solution:
def findMin(self, nums: List[int]) -> int:
if nums[0]<nums[-1]: return nums[0]
l = 0
r = len(nums)-1
min_ = nums[0]
while l<=r:
m = (l+r)//2
if nums[l]<=nums[m]:
#left increase
min_ = min(min_,nums[l])
l=m+1
else:
#right incrase
min_=min(min_,nums[m])
r=m-1
return min_
不应该做不出来，首先判断是不是rotated 用head，tail大小判断， 其次， 要是再中间遇到下一个或者上一个小于那就能确定最小值了， 最后如果 nums[l] < nums[m] 是左面递增的，所以l=m+1.
154. Find Minimum in Rotated Sorted Array II （Hard）
Given the sorted rotated array nums that may contain duplicates, return the minimum element of this array.
class Solution:
def findMin(self, nums: List[int]) -> int:
l=0
r=len(nums)-1
res = float('inf')
while l<=r:
m=(l+r)//2
while l<r and nums[l]==nums[r]:
res = min(res,nums[l])
l+=1
r-=1
if nums[l]<=nums[m]:
#left incresase
res = min(res,nums[l])
l=m+1
else:
#right increase
res = min(res,nums[m])
r=m-1
res = min(res,nums[l]) if len(nums)>l>=0 else res
return res
#MY ANSWER
class Solution:
def findMin(self, nums: List[int]) -> int:
min_ = nums[0]
l=0
r=len(nums)-1
while l<=r:
while l<r and nums[l]==nums[r]:
min_=min(min_,nums[l])
l+=1
r-=1
m = (l+r)//2
if nums[l]<=nums[m]:
#left increase
min_=min(min_,nums[l])
l=m+1
else:
#right incraese
min_=min(min_,nums[m])
r=m-1
return min_
在之前思路上多加一行判断，while left==rgiht， left+=1 right-=1. 这样在大部分case下是lg（n）最坏情况是O（n）。 有数字duplicated时候要nums[l]<=nums[m] 去重判断要l小于r
155. Min Stack （Easy）
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack:
self.min_stack.append(val)
else:
self.min_stack.append(min(self.min_stack[-1],val))
def pop(self) -> None:
self.stack.pop()
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1] if self.stack else None
def getMin(self) -> int:
return self.min_stack[-1] if self.min_stack else None
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
156. Binary Tree Upside Down (Medium)
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
class Solution:
def upsideDownBinaryTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
# 层序遍历
if not root: return root
res = []
queue = [root]
while queue:
l=len(queue)
level = []
for i in range(l):
cur=queue.pop(0)
level.append(cur)
if cur.left:
queue.append(cur.left)
cur.left=None
if cur.right:
queue.append(cur.right)
cur.right=None
res.append(level)
result=res[-1][0]
for j,row in enumerate(res):
for i,node in enumerate(row):
if j+1<len(res) and i*2<len(res[j+1]):
res[j+1][i*2].right=node
res[j+1][i*2].left = res[j+1][i*2+1] if i*2+1 <len(res[j+1]) else None
return result
#ANSWER
def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
def recurse(node=root, parent=None, right=None):
if not node:
return parent
res = recurse(node.left, node, node.right)
node.right = parent
node.left = right
return res
return recurse()
# ANSWER
class Solution:
def upsideDownBinaryTree(self, root: TreeNode) -> TreeNode:
if not root or not root.left: return root
node = root.left
ans = self.upsideDownBinaryTree(node)
node.left = root.right
node.right = root
root.left = root.right = None
return ans
思路：层序遍历，然后strip left&right=None光剩下node。 然后重新组建链接关系。
递归去写没写出来。。。一定是postorder。
157. Read N Characters Given Read4 （Easy）
Given a file and assume that you can only read the file using a given method read4, implement a method to read n characters.
"""
The read4 API is already defined for you.
@param buf4, a list of characters
@return an integer
def read4(buf4):
# Below is an example of how the read4 API can be called.
file = File("abcdefghijk") # File is "abcdefghijk", initially file pointer (fp) points to 'a'
buf4 = [' '] * 4 # Create buffer with enough space to store characters
read4(buf4) # read4 returns 4. Now buf = ['a','b','c','d'], fp points to 'e'
read4(buf4) # read4 returns 4. Now buf = ['e','f','g','h'], fp points to 'i'
read4(buf4) # read4 returns 3. Now buf = ['i','j','k',...], fp points to end of file
"""
class Solution:
def read(self, buf, n):
"""
:type buf: Destination buffer (List[str])
:type n: Number of characters to read (int)
:rtype: The number of actual characters read (int)
"""
buf4 =[' ' for _ in range(4)]
c=0
start=0
while c<n:
val=read4(buf4)
c+=val
if c<=n:
buf[start:start+val]=buf4
else:
buf[start:n]=buf4[:n-start]
return n
start=start+val
if val==0:
break
return c
class Solution:
def read(self, buf: List[str], n: int) -> int:
copied_chars = 0
read_chars = 4
buf4 = [''] * 4
while copied_chars < n and read_chars == 4:
read_chars = read4(buf4)
for i in range(read_chars):
if copied_chars == n:
return copied_chars
buf[copied_chars] = buf4[i]
copied_chars += 1
return copied_chars
158. Read N Characters Given read4 II - Call Multiple Times (Hard)
Given a file and assume that you can only read the file using a given method read4, implement a method read to read n characters. Your method read may be called multiple times.
# The read4 API is already defined for you.
# def read4(buf4: List[str]) -> int:
class Solution:
buf4_rem = [' ']*4
n_rem=0
def read(self, buf: List[str], n: int) -> int:
start=0
buf4=[' ']*4
c=0
while c<n:
if self.n_rem>0:
#have remain
if c+self.n_rem<n:
buf[start:start+self.n_rem] = self.buf4_rem[:self.n_rem]
start+=self.n_rem
c+=self.n_rem
self.n_rem=0
else:
#c+n_rem>=n
# char needed = n-c
buf[start:n] = self.buf4_rem[:n-c]
self.n_rem = self.n_rem - (n-c)
if self.n_rem>0:
self.buf4_rem = self.buf4_rem[n-c:]+[' ']*(4-(n-c))
return n
else:
#n_rem==0
nread = read4(buf4)
if nread==0:break
if c+nread<n:
#overwrite nead chars
buf[start:start+nread] = buf4[:nread]
start+=nread
c+=nread
else:
#char needed n-c
buf[start:n]= buf4[:n-c]
self.buf4_rem = buf4[n-c:] + [' ']*(4-(n-c))
self.n_rem = nread-(n-c)
return n
return c
#ANSWER
class Solution:
def __init__(self):
self.deq = deque()
def read(self, buf, n):
while n > len(self.deq):
a_buf = [""] * 4
read4(a_buf)
self.deq.extend(a_buf)
if not self.deq[-1]: break
k = 0
while self.deq and self.deq[0] and k < n:
buf[k] = self.deq.popleft()
k += 1
return k
尼玛，这hard题目，完全是考细心不是考算法，垃圾题目。答案很简单。。。
159. Longest Substring with At Most Two Distinct Characters （Medium）
Given a string s, return the length of the longest substring that contains at most two distinct characters.
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
# e c e b a
# e c e b a
map_2pos = dict()
res=1
start=0
for i,char in enumerate(s):
if (char not in map_2pos) and len(map_2pos)==2:
#do calculation
small_k=None
small_v=float('inf')
for k,v in map_2pos.items():
if v<small_v:
small_v=v
small_k=k
del map_2pos[small_k]
start=small_v+1
res=max(res,i-start+1)
elif char in map_2pos and len(map_2pos)==2:
res=max(res,i-start+1)
elif len(map_2pos)<2:
res=max(res,i-start+1)
map_2pos[char]=i
return res
#ANSWER
class Solution:
def lengthOfLongestSubstringTwoDistinct(self, s: str) -> int:
if not s: return 0
dic = dict()
start = 0
res =0
for i,n in enumerate(s):
if (n not in dic and len(dic)==2):
candi =None
for key in dic.keys():
if dic[key]==min(dic.values()):
candi = key
candi_val = dic[candi]
del dic[candi]
start = candi_val +1
res=max(res,i-start+1)
dic[n] = i
return res
思路： sliding window， 用dic保存char最近一次出现位置，dic保持2个元素内。 情况1： 当dic已经有2个元素，要加入不同元素，需要pop位置最小那个。然后计算。 情况2：还是在dic中相同char，只做长度更新。 情况3：dic中元素不到2，只做长度更新。
160. Intersection of Two Linked Lists （Easy）
Given the heads of two singly linked-lists headA and headB, return the node at which the two lists intersect. If the two linked lists have no intersection at all, return null.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
def length(node):
c=0
while node:
c+=1
node=node.next
return c
la=length(headA)
lb=length(headB)
if la<lb:
la,lb=lb,la
headA,headB=headB,headA
# A always > B
diff = la-lb
for i in range(diff):
headA = headA.next
while headA and headB:
if headA==headB:
return headA
headA=headA.next
headB=headB.next
return None
#ANSWER
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
pA = headA
pB = headB
while pA != pB:
pA = headB if pA is None else pA.next
pB = headA if pB is None else pB.next
return pA