81. Search in Rotated Sorted Array II (Medium)
There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length) such that the resulting array is [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed). For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
Given the array nums after the rotation and an integer target, return true if target is in nums, or false if it is not in nums.
You must decrease the overall operation steps as much as possible.
class Solution:
def search(self, nums: List[int], target: int) -> bool:
#still binary search
l=0
r=len(nums)-1
while l<=r:
m=(l+r)//2
if target==nums[m]:return True
while nums[l]==nums[r] and l<r:
if nums[l]==target:
return True
l+=1
r-=1
if nums[m] >= nums[l]:
#left increase
if nums[m]>=target>=nums[l]:
r=m-1
else:
l=m+1
else:
#right increase
if nums[r]>=target>=nums[m]:
l=m+1
else:
r=m-1
return False
需要注意特别处理 nums[l]==nums[r] 情况 而且要确保 l小于r 也就是aba情形。 这样才能l+1 ， r-1。
82. Remove Duplicates from Sorted List II （Medium）
Given the head of a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list. Return the linked list sorted as well.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummyhead = ListNode(val='NULL',next=head)
pre = dummyhead
cur = head
while cur and cur.next:
if cur.val==cur.next.val:
#find dup, do while loop til end, update pre and cur
while cur and cur.next and cur.val==cur.next.val:
cur = cur.next
pre.next = cur.next if cur.next else None
cur = cur.next if cur.next else None
else:
#normal update
pre=cur
cur=cur.next
return dummyhead.next
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
# a b c c d d e
# P C
# P C
# a a c c d
# P means previous C means current
dummyhead = ListNode(val='NULL',next=head)
pre=dummyhead
cur = head
while cur and cur.next:
#print(cur.val)
if cur.next and cur.next.val!=cur.val:
pre = cur
cur = cur.next
elif cur.next and cur.next.val==cur.val:
while cur.next and cur.next.val==cur.val:
cur = cur.next
cur = cur.next
if pre:
pre.next = cur
return dummyhead.next
83. Remove Duplicates from Sorted List （Easy）
Given the head of a sorted linked list, delete all duplicates such that each element appears only once. Return the linked list sorted as well.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummyhead = ListNode(val='NULL',next=head)
pre=dummyhead
cur=head
while cur:
if pre.val==cur.val:
#find dup
while cur and pre.val==cur.val:
cur=cur.next
pre.next=cur
else:
#normal update
pre=cur
cur=cur.next
return dummyhead.next
#answer way of writting
class Solution:
def deleteDuplicates(self, head: ListNode) -> ListNode:
cur=head
while cur and cur.next:
if cur.val==cur.next.val:
cur.next=cur.next.next
else:
cur=cur.next
return head
答案写法更优雅。。。
84. Largest Rectangle in Histogram （Hard）
重点记忆，遇到当前小于等于栈顶元素确定了右边界。开始计算，高度是stack.pop（）左边界是stack【-1】，注意起始stack = 【-1】
Given an array of integers heights representing the histogram's bar height where the width of each bar is 1, return the area of the largest rectangle in the histogram.
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack=[-1]
res=0
for i in range(len(heights)):
while stack[-1]!=-1 and heights[stack[-1]]>=heights[i]:
res=max(res, heights[stack.pop()]*(i-stack[-1]-1)
stack.append(i)
while stack[-1]!=-1 and stack:
res=max(res,heights[stack.pop()]*(len(heights)-stack[-1]-1))
return res
没思路， 似乎是用stack 。。。但如何知道哪块板是需要的？
思路: 如果当前高度小于等于栈顶，说明找到了栈顶的右边界，开始计算。pop栈顶元素的高度为高度，宽度为目前位置到已经pop过的栈顶位置减一。 过完一遍后，如果栈里还有元素， 开始计算， pop栈顶元素的高度为高度， 宽度为目前位置（已经是len（heights）了）到已经pop过的栈顶位置减一。注意初始栈为-1， 方便计算面积公式再edge case 下成立。
85. Maximal Rectangle （Hard）
Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
# 似乎能转化成上一题，板子面积最大问题。
def maxarea(nums):
res = 0
stack = [-1]
for i, n in enumerate(nums):
while stack[-1]!=-1 and nums[stack[-1]] >= n:
#calculate
res = max(res, nums[stack.pop()]*(i-stack[-1]-1))
stack.append(i)
while stack and stack[-1]!=-1:
res = max(res, nums[stack.pop()]*(len(nums)-stack[-1]-1))
return res
res = 0
for rowid in range(len(matrix)):
if rowid==0:
row = [int(e) for e in matrix[0]]
#print(row)
res = max(res,maxarea(row[:]))
else:
currow = [int(e) for e in matrix[rowid]]
row = [ cr+cr*r for (cr,r) in zip(currow,row)]
#print(row)
res = max(res,maxarea(row[:]))
return res
直接用了上一题求解。。。。
86. Partition List (Medium)
Given the head of a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
smallhead = ListNode(val='NULL')
largehead = ListNode(val='NULL')
small = smallhead
large = largehead
while head:
if head.val<x:
small.next = head
small = small.next
else:
large.next = head
large = large.next
head = head.next
#makde ends clean
if small:
small.next = None
if large:
large.next = None
small.next = largehead.next
return smallhead.next
class Solution:
def partition(self, head: Optional[ListNode], x: int) -> Optional[ListNode]:
dummyheadA = ListNode(val='NULL')
dummyheadB = ListNode(val='NULL')
curA = dummyheadA
curB = dummyheadB
while head:
headnext = head.next
if head.val<x:
curA.next = head
curA = curA.next
curA.next = None
else:
curB.next = head
curB = curB.next
curB.next = None
head = headnext
#print(dummyheadA.next)
#print(dummyheadB.next)
curA.next = dummyheadB.next
return dummyheadA.next
87. Scramble String (Hard)
We can scramble a string s to get a string t using the following algorithm:
If the length of the string is 1, stop.
If the length of the string is > 1, do the following:
Split the string into two non-empty substrings at a random index, i.e., if the string is s, divide it to x and y where s = x + y.
Randomly decide to swap the two substrings or to keep them in the same order. i.e., after this step, s may become s = x + y or s = y + x.
Apply step 1 recursively on each of the two substrings x and y.
Given two strings s1 and s2 of the same length, return true if s2 is a scrambled string of s1, otherwise, return false.
# mem limit exceeded
class Solution:
def isScramble(self, s1: str, s2: str) -> bool:
@lru_cache(None)
def scr(s):
if len(s)==1: return [s]
res = set()
for i in range(1,len(s)):
x =s[:i]
y =s[i:]
for left in scr(x):
for right in scr(y):
res.add(left+right)
res.add(right+left)
res.add(s)
return list(res)
return s2 in scr(s1)
class Solution:
@lru_cache(None)
def isScramble(self, s1: str, s2: str) -> bool:
m =len(s1)
n=len(s2)
if m!=n or sorted(s1)!=sorted(s2): return False
if m<=3 or s1==s2: return True
f = self.isScramble
for i in range(1,len(s1)):
if f(s1[:i],s2[:i]) and f(s1[i:],s2[i:]) or f(s1[:i],s2[-i:]) and f(s1[i:],s2[:-i]):
return True
return False
backtraking MLE TLE，重新想办法。。
答案很优雅，用了递归和mem
88. Merge Sorted Array （Easy）
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
# fill nums1 from end pos to head pos
cur=len(nums1)-1
while m>0 and n>0:
if nums1[m-1]>nums2[n-1]:
nums1[cur]=nums1[m-1]
m-=1
else:
nums1[cur]=nums2[n-1]
n-=1
cur-=1
while m>0:
nums1[cur]=nums1[m-1]
m-=1
cur-=1
while n>0:
nums1[cur]=nums2[n-1]
n-=1
cur-=1
从后向前覆盖，避免overwrite。
89. Gray Code （Medium）
class Solution:
def grayCode(self, n: int) -> List[int]:
# 0 0
# 1 [0 1]
# 2 [00 01 11 10]
level = [0,1]
if n==1: return level
for i in range(n-1):
level_res = []
mask1 = 1<<(i+1)
mask0 = 0
for n in level:
level_res.append(n|mask0)
for n in level[::-1]:
level_res.append(n|mask1)
level=level_res
return level
在每个level下，用0/1 mask遍历前一个level的结果就行了，注意mask1时候reverse遍历顺序。
90. Subsets II （Medium）
Given an integer array nums that may contain duplicates, return all possible subsets (the power set).
The solution set must not contain duplicate subsets. Return the solution in any order.
class Solution:
def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:
res = []
def bt(temp,start):
res.append(temp[:])
for i in range(start,len(nums)):
if i>start and nums[i]==nums[i-1]: continue
temp.append(nums[i])
bt(temp,i+1)
temp.pop()
nums.sort()
bt([],0)
return res
已经在backtrakcing总结篇写过，注意2点，去重，下一次bt起始位置为i+1，不look back。