391. Perfect Rectangle （Hard）
Given an array rectangles where rectangles[i] = [xi, yi, ai, bi] represents an axis-aligned rectangle. The bottom-left point of the rectangle is (xi, yi) and the top-right point of it is (ai, bi).
Return true if all the rectangles together form an exact cover of a rectangular region.
class Solution:
def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
x1 = float('inf')
y1 = float('inf')
x2 = float('-inf')
y2 = float('-inf')
_set = set()
area = 0
for rect in rectangles:
x1 = min(x1, rect[0])
y1 = min(y1, rect[1])
x2 = max(x2, rect[2])
y2 = max(y2, rect[3])
area += (rect[2] - rect[0]) * (rect[3] - rect[1])
for x, y in [(rect[0],rect[1]),(rect[0],rect[3]),(rect[2],rect[3]),(rect[2],rect[1])]:
if (x, y) in _set:
_set.remove((x, y))
else:
_set.add((x, y))
return all((x, y) in _set for x, y in [(x1,y1),(x2,y2),(x1,y2),(x2,y1)]) and len(_set) == 4 and area == (x2 - x1) * (y2 - y1)
#MY ANSWER
class Solution:
def isRectangleCover(self, rectangles: List[List[int]]) -> bool:
dic = dict()
minx = miny = float('inf')
maxx = maxy = float('-inf')
area = 0
for x,y, a,b in rectangles:
area+= (a-x) * (b-y)
def add(x,y):
if (x,y) not in dic:
dic[(x,y)] =1
else:
dic[(x,y)] -=1
if dic[(x,y)]==0:
del dic[(x,y)]
add(x,y)
add(x,b)
add(a,b)
add(a,y)
minx=min(minx,x)
miny=min(miny,y)
maxx=max(maxx,a)
maxy=max(maxy,b)
return set(dic.keys()) == {(minx,miny),(minx,maxy),(maxx,miny),(maxx,maxy)} and area== (maxx-minx)*(maxy-miny)
要是exact cover of rectangular region 1）大的rectangle面积是所有小rectangle面积和 2） 所有的图中的点应该是偶数个，除了边界的4个点。
392. Is Subsequence (Easy)
Given two strings s and t, return true if s is a subsequence of t, or false otherwise.
A subsequence of a string is a new string that is formed from the original string by deleting some (can be none) of the characters without disturbing the relative positions of the remaining characters. (i.e., "ace" is a subsequence of "abcde" while "aec" is not).
#ANSWER
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if not s: return True
p1=0
p2=0
while p1<len(s) and p2<len(t):
if s[p1]==t[p2]:
p1+=1
p2+=1
if p1==len(s):
return True
return False
#My ANSWER
class Solution:
def isSubsequence(self, s: str, t: str) -> bool:
if not s: return True
start = 0
for i, n in enumerate(t):
if start<len(s) and s[start]==n:
start+=1
return start == len(s)
这题竟然卡了，用了two pointer。。 答案写的更好。 只有相等时候s的pointer才跳，t的pointer一直跳，判断s的pointer到头就可以了。
393. UTF-8 Validation （Medium）
Given an integer array data representing the data, return whether it is a valid UTF-8 encoding.
A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:
For a 1-byte character, the first bit is a 0, followed by its Unicode code.
For an n-bytes character, the first n bits are all one's, the n + 1 bit is 0, followed by n - 1 bytes with the most significant 2 bits being 10.
This is how the UTF-8 encoding would work:
Char. number range | UTF-8 octet sequence
(hexadecimal) | (binary)
--------------------+---------------------------------------------
0000 0000-0000 007F | 0xxxxxxx
0000 0080-0000 07FF | 110xxxxx 10xxxxxx
0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data.
class Solution:
def validUtf8(self, data: List[int]) -> bool:
# Number of bytes in the current UTF-8 character
n_bytes = 0
# For each integer in the data array.
for num in data:
# Get the binary representation. We only need the least significant 8 bits
# for any given number.
bin_rep = format(num, '#010b')[-8:]
# If this is the case then we are to start processing a new UTF-8 character.
if n_bytes == 0:
# Get the number of 1s in the beginning of the string.
for bit in bin_rep:
if bit == '0': break
n_bytes += 1
# 1 byte characters
if n_bytes == 0:
continue
# Invalid scenarios according to the rules of the problem.
if n_bytes == 1 or n_bytes > 4:
return False
else:
# Else, we are processing integers which represent bytes which are a part of
# a UTF-8 character. So, they must adhere to the pattern `10xxxxxx`.
if not (bin_rep[0] == '1' and bin_rep[1] == '0'):
return False
# We reduce the number of bytes to process by 1 after each integer.
n_bytes -= 1
# This is for the case where we might not have the complete data for
# a particular UTF-8 character.
return n_bytes == 0
#ANSWER BIT Manipulation
class Solution:
def validUtf8(self, data):
"""
:type data: List[int]
:rtype: bool
"""
# Number of bytes in the current UTF-8 character
n_bytes = 0
# Mask to check if the most significant bit (8th bit from the left) is set or not
mask1 = 1 << 7
# Mask to check if the second most significant bit is set or not
mask2 = 1 << 6
for num in data:
# Get the number of set most significant bits in the byte if
# this is the starting byte of an UTF-8 character.
mask = 1 << 7
if n_bytes == 0:
while mask & num:
n_bytes += 1
mask = mask >> 1
# 1 byte characters
if n_bytes == 0:
continue
# Invalid scenarios according to the rules of the problem.
if n_bytes == 1 or n_bytes > 4:
return False
else:
# If this byte is a part of an existing UTF-8 character, then we
# simply have to look at the two most significant bits and we make
# use of the masks we defined before.
if not (num & mask1 and not (num & mask2)):
return False
n_bytes -= 1
return n_bytes == 0
看答案了，down vote比较多不是什么好题
394. Decode String （Medium）
Given an encoded string, return its decoded string.
The encoding rule is: k[encoded_string], where the encoded_string inside the square brackets is being repeated exactly k times. Note that k is guaranteed to be a positive integer.
You may assume that the input string is always valid; there are no extra white spaces, square brackets are well-formed, etc.
Furthermore, you may assume that the original data does not contain any digits and that digits are only for those repeat numbers, k. For example, there will not be input like 3a or 2[4].
class Solution:
def decodeString(self, s: str) -> str:
# 3[a2[c]]
#
# stack=[]
# [3]
# [3 [ a 2 [ c ]
#
dig=''
stack=[]
for char in s:
if char.isdigit():
dig+=char
elif char=='[':
if dig:
stack.append(int(dig))
stack.append('[')
dig=''
elif char==']':
string=[]
while stack[-1]!='[':
string.append(stack.pop())
string=''.join(string[::-1])
stack.pop() #pop掉【
if type(stack[-1])==int:
string=stack.pop()*string
stack.append(string)
else:
stack.append(char)
return ''.join(stack)
#3年前的答案估计是看的别人的一样的思路
class Solution(object):
def decodeString(self, s):
"""
:type s: str
:rtype: str
"""
num='0123456789'
s=[e for e in s]
stack=[]
while s:
cur=s.pop(0)
if cur in num:
stack.append(int(cur))
elif cur=='[':
stack.append(cur)
elif cur==']':
temp=[]
while stack and stack[-1]!='[':
me=stack.pop()
temp.append(me)
stack.pop()
temp=''.join(temp[::-1])
number=0
time=1
while stack and type(stack[-1])==int:
number+=stack.pop()*time
time*=10
stack.append(temp*number)
else:
stack.append(cur)
return ''.join(stack)
#MY ANSWER
class Solution:
def decodeString(self, s: str) -> str:
# 3 [ a2[c] ]
#
stack = []
i=0
while i<len(s):
if s[i].isdigit():
val = s[i]
while i+1<len(s) and s[i+1].isdigit():
i+=1
val+=s[i]
stack.append(int(val))
elif s[i] == '[':
stack.append(s[i])
elif s[i] == ']':
#do calculation
tmp = []
while stack[-1]!='[':
tmp.append(stack.pop())
tmp = ''.join(tmp[::-1]) #rev order due to stack
#pop [
stack.pop()
if type(stack[-1])==int:
tmp = tmp*stack.pop()
stack.append(tmp)
elif s[i].isalpha():
tmp =s[i]
while i+1<len(s) and s[i+1].isalpha():
i+=1
tmp+=s[i]
stack.append(tmp)
i+=1
return ''.join(stack)
感觉是用stack的确写出来了~~
395. Longest Substring with At Least K Repeating Characters （Medium）
Given a string s and an integer k, return the length of the longest substring of s such that the frequency of each character in this substring is greater than or equal to k.
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
def helper(start,end):
if end<k:return 0
countMap=[0]*26
for i in range(start,end):
countMap[ord(s[i])-ord('a')]+=1
for mid in range(start,end):
if countMap[ord(s[mid])-ord('a')]>=k: continue
midnext=mid+1
while midnext<end and countMap[ord(s[midnext])-ord('a')]<k:
midnext+=1
return max(helper(start,mid),helper(midnext,end))
return end-start
return helper(0,len(s))
#Perfect ANSWER
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
for c in set(s):
if s.count(c) < k:
return max(self.longestSubstring(t, k) for t in s.split(c))
return len(s)
#Sliding WIndow
class Solution:
def longestSubstring(self, s: str, k: int) -> int:
maxunique=len(set(s))
res=0
for cur_unique in range(1,maxunique+1):
countmap=[0]*26
start=end=unique=idx=countAtLeasetK=0
while end <len(s):
#expanding sliding window
if unique<=cur_unique:
idx=ord(s[end])-ord('a')
if countmap[idx]==0:
unique+=1
countmap[idx]+=1
if countmap[idx]==k:
countAtLeasetK+=1
end+=1
else:
#shrink sliding window
idx=ord(s[start])-ord('a')
if countmap[idx]==k:
countAtLeasetK-=1
countmap[idx]-=1
if countmap[idx]==0:
unique-=1
start+=1
if unique==cur_unique and unique==countAtLeasetK:
res=max(res,end-start)
return res
答案的分治法很好，
的确是tow pointer啊，但写不出来。。。思路：第一层for loop 用来扫 cur_unique 。 while end 小于len(s)； 当unique小于cur_unique而且不到s末尾时， expand。记录unique he countAtLeastK大小，否则当unique大于cur_unique就收缩， 更新countAtLeastK和unique。 如果unique等于cur_unique 而且unique等于countAtLeastK，更新结果。
最简单的是方法2解法，如果count（char)小于K就用char作为分界char，recursive call function。
396. Rotate Function （Medium）
You are given an integer array nums of length n.
Assume arrk to be an array obtained by rotating nums by k positions clock-wise. We define the rotation function F on nums as follow:
F(k) = 0 * arrk[0] + 1 * arrk[1] + ... + (n - 1) * arrk[n - 1].
Return the maximum value of F(0), F(1), ..., F(n-1).
class Solution:
def maxRotateFunction(self, nums: List[int]) -> int:
#nums = [4,3,2,6]
#F(0) = (0 * 4) + (1 * 3) + (2 * 2) + (3 * 6) = 0 + 3 + 4 + 18 = 25
#F(1) = (0 * 6) + (1 * 4) + (2 * 3) + (3 * 2) = 0 + 4 + 6 + 6 = 16
# = F[0]+sum-4*6
#F(2) = (0 * 2) + (1 * 6) + (2 * 4) + (3 * 3) = 0 + 6 + 8 + 9 = 23
# = F[1]+sum-4*2
#F(3) = (0 * 3) + (1 * 2) + (2 * 6) + (3 * 4) = 0 + 2 + 12 + 12 = 26
# = F[2]+sum-4*3
f0=0
sum_=0
for i,n in enumerate(nums):
f0+=i*n
sum_+=n
res=f0
for j in range(len(nums)-1,0,-1):
f1=f0+sum_-len(nums)*nums[j]
res=max(res,f1)
f0=f1
return res
397. Integer Replacement (Medium)
Given a positive integer n, you can apply one of the following operations:
If n is even, replace n with n / 2.
If n is odd, replace n with either n + 1 or n - 1.
Return the minimum number of operations needed for n to become 1.
#MY ANSWER
class Solution:
@lru_cache(None)
def integerReplacement(self, n: int) -> int:
if n==1: return 0
if n%2==0:
return 1+self.integerReplacement(n//2)
else:
return 1+min(self.integerReplacement(n+1),self.integerReplacement(n-1))
398. Random Pick Index （Medium）
Given an integer array nums with possible duplicates, randomly output the index of a given target number. You can assume that the given target number must exist in the array.
Implement the Solution class:
Solution(int[] nums) Initializes the object with the array nums.
int pick(int target) Picks a random index i from nums where nums[i] == target. If there are multiple valid i's, then each index should have an equal probability of returning.
class Solution:
def __init__(self, nums: List[int]):
self.dic=collections.defaultdict(list)
for i,n in enumerate(nums):
self.dic[n].append(i)
def pick(self, target: int) -> int:
return random.choice(self.dic[target])
399. Evaluate Division (Medium)
ou are given an array of variable pairs equations and an array of real numbers values, where equations[i] = [Ai, Bi] and values[i] represent the equation Ai / Bi = values[i]. Each Ai or Bi is a string that represents a single variable.
You are also given some queries, where queries[j] = [Cj, Dj] represents the jth query where you must find the answer for Cj / Dj = ?.
Return the answers to all queries. If a single answer cannot be determined, return -1.0.
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
# a-val->b--val->c
graph = defaultdict(defaultdict)
def backtrack_evaluate(curr_node, target_node, acc_product, visited):
visited.add(curr_node)
ret = -1.0
neighbors = graph[curr_node]
if target_node in neighbors:
ret = acc_product * neighbors[target_node]
else:
for neighbor, value in neighbors.items():
if neighbor in visited:
continue
ret = backtrack_evaluate(
neighbor, target_node, acc_product * value, visited)
if ret != -1.0:
break
visited.remove(curr_node)
return ret
# Step 1). build the graph from the equations
for (dividend, divisor), value in zip(equations, values):
# add nodes and two edges into the graph
graph[dividend][divisor] = value
graph[divisor][dividend] = 1 / value
# Step 2). Evaluate each query via backtracking (DFS)
# by verifying if there exists a path from dividend to divisor
results = []
for dividend, divisor in queries:
if dividend not in graph or divisor not in graph:
# case 1): either node does not exist
ret = -1.0
elif dividend == divisor:
# case 2): origin and destination are the same node
ret = 1.0
else:
visited = set()
ret = backtrack_evaluate(dividend, divisor, 1, visited)
results.append(ret)
return results
###UNIONFIND 变种
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
gid_weight = {}
def find(node_id):
if node_id not in gid_weight:
gid_weight[node_id] = (node_id, 1)
group_id, node_weight = gid_weight[node_id]
# The above statements are equivalent to the following one
#group_id, node_weight = gid_weight.setdefault(node_id, (node_id, 1))
if group_id != node_id:
# found inconsistency, trigger chain update
new_group_id, group_weight = find(group_id)
gid_weight[node_id] = (new_group_id, node_weight * group_weight)
return gid_weight[node_id]
def union(dividend, divisor, value):
dividend_gid, dividend_weight = find(dividend)
divisor_gid, divisor_weight = find(divisor)
if dividend_gid != divisor_gid:
# merge the two groups together,
# by attaching the dividend group to the one of divisor
gid_weight[dividend_gid] = (divisor_gid, divisor_weight * value / dividend_weight)
# Step 1). build the union groups
for (dividend, divisor), value in zip(equations, values):
union(dividend, divisor, value)
results = []
# Step 2). run the evaluation, with "lazy" updates in find() function
for (dividend, divisor) in queries:
if dividend not in gid_weight or divisor not in gid_weight:
# case 1). at least one variable did not appear before
results.append(-1.0)
else:
dividend_gid, dividend_weight = find(dividend)
divisor_gid, divisor_weight = find(divisor)
if dividend_gid != divisor_gid:
# case 2). the variables do not belong to the same chain/group
results.append(-1.0)
else:
# case 3). there is a chain/path between the variables
results.append(dividend_weight / divisor_weight)
return results
#MY SOLUTION
class Solution:
def calcEquation(self, equations: List[List[str]], values: List[float], queries: List[List[str]]) -> List[float]:
# a/b = 2 b/c =3
# 2 3
# a--->b--->c
# <--- <---
# 0.5 1/3
#graph problem
neis = defaultdict(set)
ew = dict() #edge_weights = dict()
for [a,b], v in zip(equations,values):
neis[a].add(b)
neis[b].add(a)
key = '-'.join([a,b])
ew[key] = v
key = '-'.join([b,a])
ew[key] = 1.0/v
res = []
def dfs(a,b, visited =set(),val=1):
key = '-'.join([a,b])
if key in ew:
return True,val*ew[key]
else:
for c in neis[a]:
if c not in visited:
visited.add(c)
key_ac = '-'.join([a,c])
tmp = dfs(c,b, visited,val*ew[key_ac])
visited.remove(c)
if tmp[0]:
return tmp
return False, -1.0
for a, b in queries:
if a==b and a in neis:
res.append(1.0)
elif a not in neis or b not in neis:
res.append(-1.0)
else:
res.append(dfs(a,b)[1])
return res
看提示，是graph问题， 一开始就偏了。。。若是graph问题，则a-val-》b-val-》c，
那么a-》c就是val1*val2，如果是c-》a找不到，就找a-c然后1/结果. 如果node不在里面就return -1，如果是自己-》自己return1
还是第一种方法graph比较标准用DFS。
400. Nth Digit （Medium）
Given an integer n, return the nth digit of the infinite integer sequence [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, ...].
class Solution:
def findNthDigit(self, n: int) -> int:
#1 ~ 9 include 9 one digit number;
#10 ~ 99 include 90 two digits number;
#100 ~ 999 include 900 three digits number;
#1000 ~ 9999 include 9000 four digits number;
#...
#length is how many digits:1 or 2 or 3 ..., range is 9 or 90 or 900 ...
length = 1
num = 1
range_ = 9
while n > length * range_:
n -= length * range_
length+=1
range_ *= 10
num *= 10
num += (n - 1) // length
return str(num)[ (n-1)%length]
知道思路，写时候卡。。。