491. Non-decreasing Subsequences （Medium）
Given an integer array nums, return all the different possible non-decreasing subsequences of the given array with at least two elements. You may return the answer in any order.
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = set()
def bt(start, tmp):
if len(tmp)>1:
res.add(tuple(tmp))
for i in range(start,len(nums)):
if i-1>= start and nums[i]==nums[i-1]: continue
if not tmp or nums[i]>=tmp[-1]:
tmp.append(nums[i])
bt(i+1,tmp)
tmp.pop()
bt(0,[])
return list(res)
#ANSWER
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
res = set()
def bt(start, tmp):
if start==len(nums):
if len(tmp)>1:
res.add(tuple(tmp))
return
#add num[i]
if not tmp or nums[start]>=tmp[-1]:
tmp.append(nums[start])
bt(start+1,tmp)
tmp.pop()
#not add num[i]
bt(start+1,tmp)
bt(0,[])
return list(res)
#BIT MASK 方法
class Solution:
def findSubsequences(self, nums: List[int]) -> List[List[int]]:
n=len(nums)
res = set()
for mask in range(1, 1<<n):
tmp = [nums[i] for i in range(n) if (mask>>i)&1 ]
if len(tmp)>=2 and all([tmp[i]<=tmp[i+1] for i in range(len(tmp)-1)]):
res.add(tuple(tmp))
return res
感觉是个backtracking问题， debug了一会解决了。。答案更好
492. Construct the Rectangle （Easy）
A web developer needs to know how to design a web page's size. So, given a specific rectangular web page’s area, your job by now is to design a rectangular web page, whose length L and width W satisfy the following requirements:
The area of the rectangular web page you designed must equal to the given target area.
The width W should not be larger than the length L, which means L >= W.
The difference between length L and width W should be as small as possible.
Return an array [L, W] where L and W are the length and width of the web page you designed in sequence.
class Solution:
def constructRectangle(self, area: int) -> List[int]:
# L*W=area
# L>=W
# min(abs(L-W))
L=res_L=area
W=res_W=1
while L>=W:
W+=1
L=area//W
if L>=W and L*W==area:
res_L=L
res_W=W
return res_L,res_W
#ANSWER
class Solution:
def constructRectangle(self, area: int) -> List[int]:
# L*W=area
# L>=W
# min(abs(L-W))
W=int(math.sqrt(area))
while area%W!=0:
W-=1
return area//W, W
#ANSWER
class Solution:
def constructRectangle(self, area: int) -> List[int]:
middle=int(sqrt(area))
for i in range(middle,0,-1):
if area%i==0:
return[int(area/i),i]
493. Reverse Pairs (Hard)
Given an integer array nums, return the number of reverse pairs in the array.
A reverse pair is a pair (i, j) where:
0 <= i < j < nums.length and
nums[i] > 2 * nums[j].
class Solution:
def reversePairs(self, nums: List[int]) -> int:
# i<j
# nums[i]> 2*nums[j]
class BIT:
def __init__(self,n):
self.n = n
self.bits = [0]*(n+1)
def insert(self,idx):
idx+=1
while idx>0:
self.bits[idx]+=1
idx-=idx&-idx
def query(self,idx):
idx+=1
res = 0
while idx<=self.n:
res+=self.bits[idx]
idx+=idx&-idx
return res
bit = BIT(len(nums))
tmp = nums[:]
tmp.sort()
res =0
for n in nums:
#n是nums[j]要找到有多少nums[i]>2nums[j]
#query 2n+1 ~ end
#由于bit一般是从0还是，加到idx，反向需要把insert 和 query反向
idx = bisect.bisect_left(tmp,2*n+1)
res+= bit.query(idx)
idx = bisect.bisect_left(tmp,n)
bit.insert(idx)
return res
#ANSWER 2 Merge SORT
class Solution:
def reversePairs(self, nums: List[int]) -> int:
def ms(l,r):
if l>=r: return 0
m = (l+r)//2
count = ms(l,m)+ms(m+1,r)
j=m+1
for i in range(l,m+1):
while j<=r and nums[i]>2*nums[j]:
j+=1
count+=(j-1)-m
nums[l:r+1] = sorted(nums[l:r+1])
return count
return ms(0,len(nums)-1)
初看像用stack做 但是做不出来。。。答案用了BIT。。。。但是不是通常意义的BIT。反了insert 和update function。
For our case, the running total is simply the number of elements encountered during the traversal process. If we stick to the convention above, the running total will be the number of elements smaller than the one at the given index, since the copy array is sorted in ascending order. However, we'd actually like to find the number of elements greater than some value (i.e., twice of the element being scanned), therefore we need to flip the convention. This is what you see inside the search and insert functions: the former traversing towards the end of the bit while the latter towards the root.
MergeSort方法二 。。。
494. Target Sum (Medium)
You are given an integer array nums and an integer target.
You want to build an expression out of nums by adding one of the symbols '+' and '-' before each integer in nums and then concatenate all the integers.
For example, if nums = [2, 1], you can add a '+' before 2 and a '-' before 1 and concatenate them to build the expression "+2-1".
Return the number of different expressions that you can build, which evaluates to target.
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
@lru_cache(None)
def bt(start,target):
if start==len(nums) and target==0: return 1
if start>=len(nums): return 0
# +
res1 = bt(start+1,target-nums[start])
# -
res2 = bt(start+1,target+nums[start])
return res1+res2
return bt(0,target)
#ANSWER
def findTargetSumWays(self, nums, S):
if not nums:
return 0
dic = {nums[0]: 1, -nums[0]: 1} if nums[0] != 0 else {0: 2}
for i in range(1, len(nums)):
tdic = {}
for d in dic:
tdic[d + nums[i]] = tdic.get(d + nums[i], 0) + dic.get(d, 0)
tdic[d - nums[i]] = tdic.get(d - nums[i], 0) + dic.get(d, 0)
dic = tdic
return dic.get(S, 0)
#ANSWER
class Solution:
def findTargetSumWays(self, nums: List[int], target: int) -> int:
# dp[i][t] using upto ith number of target t
total=sum(nums)
if abs(target)>total:return 0
dp=[ [0]*(2*total+1) for _ in range(len(nums))]
dp[0][nums[0]+total] = 1
dp[0][-nums[0]+total] +=1
for i in range(1,len(nums)):
for sum_ in range(-total,total+1):
if dp[i-1][sum_+total]>0:
dp[i][sum_+nums[i]+total]+=dp[i-1][sum_+total]
dp[i][sum_-nums[i]+total]+=dp[i-1][sum_+total]
return dp[len(nums)-1][target+total]
DP。 因为数字和在-sum到sum之间，offset到0开始需要+sum。
495. Teemo Attacking （Easy）
Our hero Teemo is attacking an enemy Ashe with poison attacks! When Teemo attacks Ashe, Ashe gets poisoned for a exactly duration seconds. More formally, an attack at second t will mean Ashe is poisoned during the inclusive time interval [t, t + duration - 1]. If Teemo attacks again before the poison effect ends, the timer for it is reset, and the poison effect will end duration seconds after the new attack.
You are given a non-decreasing integer array timeSeries, where timeSeries[i] denotes that Teemo attacks Ashe at second timeSeries[i], and an integer duration.
Return the total number of seconds that Ashe is poisoned.
class Solution:
def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
# input:[1,2] 2
# 1 2
# start end
# start2 new_end3
start = timeSeries[0]
end = start+duration-1
res = end-start+1
for t in timeSeries[1:]:
new_end = t+duration-1
if new_end>end:
start = end+1 if t<=end else t
end = new_end
res+=end-start+1
return res
#MY ANSWER
class Solution:
def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
res = 0
right = 0
for i,t in enumerate(timeSeries):
if t >= right:
res+= min(duration, timeSeries[i+1]-t) if i+1<len(timeSeries) else duration
right = min(t+duration-1, timeSeries[i+1] ) if i+1<len(timeSeries) else t+duration-1
return res
#ANSER ORZ indeed EZ
class Solution:
def findPoisonedDuration(self, timeSeries: List[int], duration: int) -> int:
n = len(timeSeries)
if n == 0:
return 0
total = 0
for i in range(n - 1):
total += min(timeSeries[i + 1] - timeSeries[i], duration)
return total + duration
496. Next Greater Element I (Easy)
The next greater element of some element x in an array is the first greater element that is to the right of x in the same array.
You are given two distinct 0-indexed integer arrays nums1 and nums2, where nums1 is a subset of nums2.
For each 0 <= i < nums1.length, find the index j such that nums1[i] == nums2[j] and determine the next greater element of nums2[j] in nums2. If there is no next greater element, then the answer for this query is -1.
Return an array ans of length nums1.length such that ans[i] is the next greater element as described above.
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
minheap=[ ]
dic= dict()
for n in nums2:
while minheap and minheap[0]<n:
dic[heappop(minheap)] = n
heappush(minheap,n)
return [dic.get(n,-1) for n in nums1]
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
dic = dict()
stack = []
while nums2:
cur = nums2.pop(0)
if not stack:
stack.append(cur)
else:
while stack and cur>stack[-1]:
dic[stack[-1]] = cur
stack.pop()
stack.append(cur)
return [dic.get(e,-1) for e in nums1]
#MY ANSWER
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
dic = dict()
stack = []
for n in nums2:
if not stack or stack and n<stack[-1]:
stack.append(n)
else:
while stack and n>stack[-1]:
dic[stack.pop()] = n
stack.append(n)
return [dic.get(n,-1) for n in nums1]
用不着用minheap 直接用stack就好，因为插入时候顺序已经是从左到右满足条件了。
497. Random Point in Non-overlapping Rectangles （Medium）
You are given an array of non-overlapping axis-aligned rectangles rects where rects[i] = [ai, bi, xi, yi] indicates that (ai, bi) is the bottom-left corner point of the ith rectangle and (xi, yi) is the top-right corner point of the ith rectangle. Design an algorithm to pick a random integer point inside the space covered by one of the given rectangles. A point on the perimeter of a rectangle is included in the space covered by the rectangle.
Any integer point inside the space covered by one of the given rectangles should be equally likely to be returned.
Note that an integer point is a point that has integer coordinates.
Implement the Solution class:
Solution(int[][] rects) Initializes the object with the given rectangles rects.
int[] pick() Returns a random integer point [u, v] inside the space covered by one of the given rectangles.
class Solution:
def __init__(self, rects: List[List[int]]):
self.rects = rects
self.area = [ (p[2]-p[0]+1)*(p[3]-p[1]+1) for p in self.rects]
def pick(self) -> List[int]:
#pick rect based on area
pick_rect = random.random()*sum(self.area)
now = 0
ind = -1
while now<pick_rect:
ind+=1
now+=self.area[ind]
rect = self.rects[ind]
return [random.randint(rect[0], rect[2]),random.randint(rect[1], rect[3])]
这题有个tricky地方，area为0的rect也是有点包含在里面的，要想包含边上的点需要 （width+1）*（height+1）
498. Diagonal Traverse （Medium）
iven an m x n matrix mat, return an array of all the elements of the array in a diagonal order.
#TLE
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
m=len(mat)
n=len(mat[0])
res = []
ij_sum=0
for level in range(m+n-1):
tmp=[]
for i in range(level+1):
j = ij_sum-i
if i>=0 and i<m and j>=0 and j<n:
tmp.append(mat[i][j])
if level%2==0:
tmp=tmp[::-1]
res.extend(tmp)
ij_sum+=1
return res
class Solution:
def findDiagonalOrder(self, mat: List[List[int]]) -> List[int]:
dic = defaultdict(list)
res = []
for i in range(len(mat)):
for j in range(len(mat[0])):
key=i+j
dic[key].append(mat[i][j])
for key in range(len(mat)-1+len(mat[0])):
if key%2==0:
res.extend(dic[key][::-1])
else:
res.extend(dic[key])
return res
#ANSWER
class Solution:
def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
# Check for empty matrices
if not matrix or not matrix[0]:
return []
# Variables to track the size of the matrix
N, M = len(matrix), len(matrix[0])
# The two arrays as explained in the algorithm
result, intermediate = [], []
# We have to go over all the elements in the first
# row and the last column to cover all possible diagonals
for d in range(N + M - 1):
# Clear the intermediate array everytime we start
# to process another diagonal
intermediate.clear()
# We need to figure out the "head" of this diagonal
# The elements in the first row and the last column
# are the respective heads.
r, c = 0 if d < M else d - M + 1, d if d < M else M - 1
# Iterate until one of the indices goes out of scope
# Take note of the index math to go down the diagonal
while r < N and c > -1:
intermediate.append(matrix[r][c])
r += 1
c -= 1
# Reverse even numbered diagonals. The
# article says we have to reverse odd
# numbered articles but here, the numbering
# is starting from 0 :P
if d % 2 == 0:
result.extend(intermediate[::-1])
else:
result.extend(intermediate)
return result
初次尝试TLE，用dic后满足条件。。。
499. The Maze III （Hard）
There is a ball in a maze with empty spaces (represented as 0) and walls (represented as 1). The ball can go through the empty spaces by rolling up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction. There is also a hole in this maze. The ball will drop into the hole if it rolls onto the hole.
Given the m x n maze, the ball's position ball and the hole's position hole, where ball = [ballrow, ballcol] and hole = [holerow, holecol], return a string instructions of all the instructions that the ball should follow to drop in the hole with the shortest distance possible. If there are multiple valid instructions, return the lexicographically minimum one. If the ball can't drop in the hole, return "impossible".
If there is a way for the ball to drop in the hole, the answer instructions should contain the characters 'u' (i.e., up), 'd' (i.e., down), 'l' (i.e., left), and 'r' (i.e., right).
The distance is the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included).
You may assume that the borders of the maze are all walls
#ANSWER
class Solution:
def findShortestWay(self, maze, ball, hole):
m, n, q, stopped = len(maze), len(maze[0]), [(0, "", ball[0], ball[1])], {(ball[0], ball[1]): [0, ""]}
while q:
dist, pattern, x, y = heapq.heappop(q)
if [x, y] == hole:
return pattern
for i, j, p in ((-1, 0, "u"), (1, 0, "d"), (0, -1, "l"), (0, 1, "r")):
newX, newY, d = x, y, 0
while 0 <= newX + i < m and 0 <= newY + j < n and maze[newX + i][newY + j] != 1:
newX += i
newY += j
d += 1
if [newX, newY] == hole:
break
if (newX, newY) not in stopped or [dist + d, pattern + p] < stopped[(newX, newY)]:
stopped[(newX, newY)] = [dist + d, pattern + p]
heapq.heappush(q, (dist + d, pattern + p, newX, newY))
return "impossible"
BFS 写了答案能过60/64 个test case。。。不知道哪里还有BUG。看答案。难点在，循环queue时候，这个queue不是普通的queue，是minheap。 这样就能取出距离最小的而且lexcially最小的next node做计算。
500. Keyboard Row （Easy）
Given an array of strings words, return the words that can be typed using letters of the alphabet on only one row of American keyboard like the image below.
In the American keyboard:
the first row consists of the characters "qwertyuiop",
the second row consists of the characters "asdfghjkl", and
the third row consists of the characters "zxcvbnm"
class Solution:
def findWords(self, words: List[str]) -> List[str]:
s1 = set("qwertyuiopQWERTYUIOP")
s2=set("asdfghjklASDFGHJKL")
s3=set("zxcvbnmZXCVBNM")
return [w for w in words if any(set(w)&s==set(w) for s in [s1,s2,s3] ) ]