411. Minimum Unique Word Abbreviation （Hard）
A string can be abbreviated by replacing any number of non-adjacent substrings with their lengths. For example, a string such as "substitution" could be abbreviated as (but not limited to):
"s10n" ("s ubstitutio n")
"sub4u4" ("sub stit u tion")
"12" ("substitution")
"su3i1u2on" ("su bst i t u ti on")
"substitution" (no substrings replaced)
Note that "s55n" ("s ubsti tutio n") is not a valid abbreviation of "substitution" because the replaced substrings are adjacent.
The length of an abbreviation is the number of letters that were not replaced plus the number of substrings that were replaced. For example, the abbreviation "s10n" has a length of 3 (2 letters + 1 substring) and "su3i1u2on" has a length of 9 (6 letters + 3 substrings).
Given a target string target and an array of strings dictionary, return an abbreviation of target with the shortest possible length such that it is not an abbreviation of any string in dictionary. If there are multiple shortest abbreviations, return any of them.
#TLE 暴力解法
class Solution:
def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
def abbr(w):
if not w: return []
if len(w)==1:
return [(1,w),(1,"1")]
res = set()
for p in range(1,len(w)):
head = w[:p]
tail = w[p:]
for l in abbr(head):
for r in abbr(tail):
lw1 = l[0]
lw2 = r[0]
w1 = l[1]
w2 = r[1]
if w1[-1].isdigit() and w2[0].isdigit():
i=-1
while -i<len(w1) and w1[i].isdigit():
i-=1
j=0
while j<len(w2) and w2[j].isdigit():
j+=1
word = w1[:i+1]+ str(int(w1[i+1:])+int(w2[:j]))+ w2[j:]
lword = lw1+lw2 -1
else:
word = w1+w2
lword = lw1+lw2
res.add((lword,word))
res.add( (1,str(len(w)) ))
return list(res)
fobidden = { r for w in dictionary for r in abbr(w)}
for res in sorted(abbr(target)):
if res not in fobidden:
return res[1]
#ANSWER
class Solution:
def minAbbreviation(self, target: str, dictionary: List[str]) -> str:
masks = []
for word in dictionary:
if len(word)==len(target):
#mask is bit representation of word-target char differ
#mask bit set true will hold that char
mask = 0
i = len(word)
for a,b in zip(word, target):
i-=1
if a!=b:
#bit diff
mask |= 1 <<i
masks.append(mask)
if not masks:
# no len word== len target:
return str(len(target))
res = []
for val in range(2**len(target)):
if all([val & mask for mask in masks]):
# val 's binary is potential valid abbr
count = 0
tmp = []
length = 0
for bit, ch in zip(bin(val)[2:].zfill(len(target)), target):
if bit=='1':
if count:
tmp.append(str(count))
length+=1
count = 0
tmp.append(ch)
length+=1
else:
count+=1
if count:
tmp.append(str(count))
length+=1
res.append( (length,''.join(tmp)))
return sorted(res)[0][1]
思路是bit manipulation。 1）找出在字典里同长度但字符和target不同的bit。 然后所有的encoding是0到2^m， 所以 all（encoding&dif for dif in diffs） encoding的bit能和所有dif bits有交集则是个可能的候选，把 encoding bit转换为string然后加入到abbrs中，最后找出长度最小的abbrs就可以了。
412. Fizz Buzz （Easy）
Given an integer n, return a string array answer (1-indexed) where:
answer[i] == "FizzBuzz" if i is divisible by 3 and 5.
answer[i] == "Fizz" if i is divisible by 3.
answer[i] == "Buzz" if i is divisible by 5.
answer[i] == i (as a string) if none of the above conditions are true.
class Solution:
def fizzBuzz(self, n: int) -> List[str]:
def helper(n):
if n%3==0 and n%5==0:
return 'FizzBuzz'
elif n%3==0:
return 'Fizz'
elif n%5==0:
return 'Buzz'
else:
return str(n)
return [helper(i) for i in range(1,n+1)]
413. Arithmetic Slices (Medium)
An integer array is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.
For example, [1,3,5,7,9], [7,7,7,7], and [3,-1,-5,-9] are arithmetic sequences.
Given an integer array nums, return the number of arithmetic subarrays of nums.
A subarray is a contiguous subsequence of the array.
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
# [1,3,5,7,9]
# dp 0 0 1
# 2
# 3
# dp is the number of subarays ending in ith
if len(nums)<3: return 0
dp=[0]*len(nums)
if nums[0]-nums[1]==nums[1]-nums[2]:
dp[2]=1
if len(nums)==3: return dp[2]
for i in range(3,len(nums)):
if nums[i]-nums[i-1]==nums[i-1]-nums[i-2]:
dp[i]=1+dp[i-1]
return sum(dp)
#ANSWER
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
dp=0
res=0
for i in range(2,len(nums)):
if nums[i]-nums[i-1]==nums[i-1]-nums[i-2]:
dp=1+dp
res+=dp
else:
dp=0
return res
#MY ANSWER
class Solution:
def numberOfArithmeticSlices(self, nums: List[int]) -> int:
#calculate diff
# 1 2 3 6 7 8 9 10
# 1 1 3 1 1 1 1
# 0 1 0 0 1 2 3
diffs = []
for i in range(1,len(nums)):
diff = nums[i]-nums[i-1]
diffs.append(diff)
res = 0
c=0
pre =None
for cur in diffs:
if pre is not None and cur!=pre:
c =0
elif cur==pre:
c+=1
res+=c
pre = cur
return res
思路和答案一致，DP解决。自己思路是用diff rence重新组成的数组计算， 和dp异曲同工。
414. Third Maximum Number （Easy）
Given an integer array nums, return the third distinct maximum number in this array. If the third maximum does not exist, return the maximum number.
class Solution:
def thirdMax(self, nums: List[int]) -> int:
if len(set(nums))<3: return max(nums)
if len(set(nums))==3: return sorted(set(nums))[0]
res=[]
for n in set(nums):
heapq.heappush(res,-n)
heapq.heappop(res)
heapq.heappop(res)
return -heapq.heappop(res)
#
class Solution:
def thirdMax(self, nums: List[int]) -> int:
maximums = set()
for num in nums:
maximums.add(num)
if len(maximums) > 3:
maximums.remove(min(maximums))
if len(maximums) == 3:
return min(maximums)
return max(maximums)
#
class Solution:
def thirdMax(self, nums: List[int]) -> int:
min_heap = []
for num in nums:
if num in min_heap:
continue
if len(min_heap) < 3:
heapq.heappush(min_heap, num)
elif len(min_heap) == 3:
heapq.heappushpop(min_heap, num)
if len(min_heap) == 3:
return heapq.heappop(min_heap)
else:
while min_heap:
result = heapq.heappop(min_heap)
return result
#3pointer...
class Solution:
def thirdMax(self, nums: List[int]) -> int:
max=float('-inf')
max2=float('-inf')
max3=float('-inf')
s=set()
for n in nums:
if n in s: continue
if n>max:
max3=max2
max2=max
max=n
elif n>max2:
max3=max2
max2=n
elif n>max3:
max3=n
s.add(n)
return max3 if len(s)>=3 else max
#MY ANSWER 最优O（n） quick select
class Solution:
def thirdMax(self, nums: List[int]) -> int:
#remove dup
res = []
s =set()
for n in nums:
if n not in s:
res.append(n)
s.add(n)
nums = res
#conercase
if len(nums)<=2: return max(nums)
def partition(idx, left,right):
pval = nums[idx]
#swap idx right
nums[idx],nums[right] = nums[right],nums[idx]
stored_idx = left
for i in range(left,right):
if nums[i]<pval:
nums[i],nums[stored_idx] = nums[stored_idx],nums[i]
stored_idx+=1
nums[right],nums[stored_idx] = nums[stored_idx],nums[right]
return stored_idx
def select(left,right, k):
if left==right:
return nums[left]
p_idx = random.randint(left,right)
p_idx = partition(p_idx,left,right)
if p_idx == k:
return nums[p_idx]
elif p_idx>k:
return select(left,p_idx-1,k)
else:
return select(p_idx+1,right,k)
#quick select
return select(0,len(nums)-1,len(nums)-3)
415. Add Strings (Easy)
Given two non-negative integers, num1 and num2 represented as string, return the sum of num1 and num2 as a string.
You must solve the problem without using any built-in library for handling large integers (such as BigInteger). You must also not convert the inputs to integers directly.
class Solution:
def addStrings(self, num1: str, num2: str) -> str:
n1=[int(e) for e in num1]
n2=[int(e) for e in num2]
res=[]
carry=0
while n1 or n2:
a=n1.pop() if n1 else 0
b=n2.pop() if n2 else 0
val=(a+b+carry)%10
carry=(a+b+carry)//10
res.append(val)
if carry:
res.append(carry)
return ''.join(map(str,res[::-1]))
416. Partition Equal Subset Sum (Medium)
Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.
class Solution:
def canPartition(self, nums: List[int]) -> bool:
@lru_cache(None)
def dfs(n,subset_sum):
if subset_sum==0:
return True
if n==0 or subset_sum<0:
return False
result = dfs(n-1,subset_sum-nums[n-1]) or dfs(n-1,subset_sum)
return result
total_sum=sum(nums)
if total_sum%2==1: return False
subset_sum=total_sum//2
n=len(nums)
return dfs(n,subset_sum)
###DP
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# find sum of array elements
total_sum = sum(nums)
# if total_sum is odd, it cannot be partitioned into equal sum subsets
if total_sum % 2 != 0:
return False
subset_sum = total_sum // 2
n = len(nums)
# construct a dp table of size (n+1) x (subset_sum + 1)
# dp[n][subsetsum] up to nth num can sum to subsetsum
dp = [[False] * (subset_sum + 1) for _ in range(n + 1)]
dp[0][0] = True
for i in range(1, n + 1):
curr = nums[i - 1]
for j in range(subset_sum + 1):
if j < curr:
# subset_sum< nums[i-1] so, subsetsum not include nums[i-1]
dp[i][j] = dp[i - 1][j]
else:
# could not include or include nums[i-1]
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - curr]
return dp[n][subset_sum]
#DP
class Solution:
def canPartition(self, nums: List[int]) -> bool:
# find sum of array elements
total_sum = sum(nums)
# if total_sum is odd, it cannot be partitioned into equal sum subsets
if total_sum % 2 != 0:
return False
subset_sum = total_sum // 2
# construct a dp table of size (subset_sum + 1)
dp = [False] * (subset_sum + 1)
dp[0] = True
for curr in nums:
for j in range(subset_sum,curr-1,-1):
dp[j] = dp[j] or dp[j - curr]
return dp[subset_sum]
#MY ANSWER
class Solution:
def canPartition(self, nums: List[int]) -> bool:
if sum(nums)%2==1: return False
target=sum(nums)//2
#find subset sum is target
@functools.lru_cache(None)
def dfs(i,remaining):
if i>=len(nums) or remaining<0: return False
if remaining==0: return True
res = False
#select i
res = res or dfs(i+1,remaining-nums[i])
#skip i
res =res or dfs(i+1,remaining)
return res
return dfs(0, target)
有两种情况，1) num in subset_sum 2) num not in subset_sum 所以dfs
417. Pacific Atlantic Water Flow （Medium）
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
m , n = len(heights), len(heights[0])
def bfs(q,visited):
for i,j in q:
visited.add((i,j))
while q:
l=len(q)
for _ in range(l):
i,j =q.pop(0)
for x,y in [(i+1,j),(i,j+1),(i-1,j),(i,j-1)]:
if m>x>=0 and n>y>=0 and (x,y) not in visited and heights[i][j]<=heights[x][y]:
visited.add((x,y))
q.append([x,y])
return visited
#pacifit
q = []
for i in range(n):
q.append([0,i])
for j in range(1,m):
q.append([j,0])
visited_pacifit = bfs(q,set())
#atalantic
q = []
for i in range(n):
q.append([m-1,i])
for j in range(m-1):
q.append([j,n-1])
visited_atalantic = bfs(q,set())
res = visited_pacifit & visited_atalantic
return [list(e) for e in res]
思路，从边界处做两次BFS，相交地方就是结果。
418. Sentence Screen Fitting （Medium）
Given a rows x cols screen and a sentence represented as a list of strings, return the number of times the given sentence can be fitted on the screen.
The order of words in the sentence must remain unchanged, and a word cannot be split into two lines. A single space must separate two consecutive words in a line.
#TIME LIMIT EXCEEDED
class Solution:
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
i = 0
l = len(sentence)
counter = 0
row = 0
col = 0
while row<rows:
cur = 0
while cur<=cols:
cur+=len(sentence[i])+1
if cur>cols:
if cur-1==cols:
if i==l-1:counter+=1
#next i
i = (i+1)%l
else:
#i is next going to place ,stay the same
break
else:
if i==l-1:counter+=1
#next i
i = (i+1)%l
row+=1
return counter
#ANSWER
#case 1: sentence_ptr at the end of the screen falls on space in the sentence. Go to the next letter sentence_ptr+1 in the next row of the screen.
#case 2: sentence_ptr at the end of the screen falls on the last letter of a word. We skip the space in the sentence as the last letter coincides with the screen end: sentence_ptr+2
#case 3: sentence_ptr points in the middle of a word at the end of the screen: roll back sentence_ptr till there's a space in the sentence. his corresponds to starting to fill the word in the next row, as it does not fit into the current. sentence_ptr > 0 is needed for the case when a word is longer than cols; sentence_ptr will be < len(s)
#Code with the comments and the variable change:
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
s = ' '.join(sentence) + ' '
sentence_ptr = 0
for i in range(rows):
sentence_ptr += cols - 1
# case 1: sentence_ptr at the end of screen falls exactly on the space
if s[sentence_ptr % len(s)] == ' ':
sentence_ptr += 1
# case 2: sentence_ptr at the end of screen coincides with the last letter of a word (next is space)
elif s[(sentence_ptr + 1) % len(s)] == ' ':
sentence_ptr += 2
else:
# case 3: sentence_ptr at the end of screen falls in the middle of a word; roll back
while sentence_ptr > 0 and s[(sentence_ptr - 1) % len(s)] != ' ':
sentence_ptr -= 1
return sentence_ptr // len(s)
####
class Solution:
def wordsTyping(self, sentence: List[str], rows: int, cols: int) -> int:
s = ' '.join(sentence)+' '
p = 0
for _ in range(rows):
p += cols-1
#1) p at end of column is space
if s[p%len(s)]==' ':
p+=1
#2)p is last letter of word, next is space
elif s[(p+1)%len(s)] == ' ':
p+=2
#3): p is in the middle of word need shrink
else:
while p>0 and s[(p - 1) % len(s)] != ' ':
p-=1
return p//len(s)
初次尝试是TLE。。。 直接暴力解即使考虑全了cornercase也还是过不了。
答案思路，先组成一个句子 s=‘ ‘.join（sentence）+’‘。 定义sentence_ptr 每过一行，sentence_ptr+= cols-1 这时候分3种情况， 1） 如果恰巧sentence_ptr落的位置是空格，senternce_ptr+1 2)如果 sentence_ptr+1位置是空格，sentence_ptr+=2 3)sentence_ptr落在字符上，那么sentence_ptr得往回缩直到遇到空格。
419. Battleships in a Board （Medium）
Given an m x n matrix board where each cell is a battleship 'X' or empty '.', return the number of the battleships on board.
Battleships can only be placed horizontally or vertically on board. In other words, they can only be made of the shape 1 x k (1 row, k columns) or k x 1 (k rows, 1 column), where k can be of any size. At least one horizontal or vertical cell separates between two battleships (i.e., there are no adjacent battleships).
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
m,n = len(board),len(board[0])
visited = set()
res = 0
def dfs(i,j):
if m>i>=0 and n>j>=0 and board[i][j]=='X' and (i,j) not in visited:
visited.add((i,j))
dfs(i+1,j)
dfs(i-1,j)
dfs(i,j+1)
dfs(i,j-1)
for i in range(m):
for j in range(n):
if board[i][j]=='X' and (i,j) not in visited:
res+=1
dfs(i,j)
return res
#ANSWER
class Solution:
def countBattleships(self, board: List[List[str]]) -> int:
total = 0
for i in range(len(board)):
for j in range(len(board[0])):
if board[i][j] == 'X':
flag = 1
if j > 0 and board[i][j-1] == 'X': flag = 0
if i > 0 and board[i-1][j] == 'X': flag = 0
total += flag
return total
答案没用DFS or BFS 但是很完美的解决了，因为只有横的竖的是叫做Battleships，所以如果不是左上角的X就不是一个qualified battlesships。
420. Strong Password Checker （Hard）
A password is considered strong if the below conditions are all met:
It has at least 6 characters and at most 20 characters.
It contains at least one lowercase letter, at least one uppercase letter, and at least one digit.
It does not contain three repeating characters in a row (i.e., "...aaa..." is weak, but "...aa...a..." is strong, assuming other conditions are met).
Given a string password, return the minimum number of steps required to make password strong. if password is already strong, return 0.
In one step, you can:
Insert one character to password,
Delete one character from password, or
Replace one character of password with another character.
class Solution:
def strongPasswordChecker(self, s: str) -> int:
missingtype = 3
if any([ 'z'>=ch>='a' for ch in s]): missingtype-=1
if any([ 'Z'>=ch>='A' for ch in s]): missingtype-=1
if any([ ch.isdigit() for ch in s]): missingtype-=1
change = 0
one = two = 0 #deleting one/two in aaa ... for change
p=2
while p<len(s):
if s[p-1]==s[p-2]==s[p]:
length = 2
while p<len(s) and s[p]==s[p-1]:
p+=1
length+=1
change+= length//3
if length%3==0: one+=1
#we need to make len/3 replacements and we can reduce the number of replacements len/3 by one by deleting one character
# aaa aaa
elif length%3==1: two+=1
#we can reduce one replacement by deleting two characters.
# aaaa
else:
p+=1
if len(s)<6:
return max(6-len(s), missingtype)
elif len(s)<=20:
return max(change, missingtype) #max because both change and missing type condition must statifsy
else:
delete = len(s)-20
change -= min(delete, one)
# one delete can reduce one change, but one can not exeeds delete
change -= min(two*2, max(delete-one,0))//2
# two delete can reduce one change, the upper bond of two delete is delete-one
change -= max(delete-one-two*2, 0)//3
# 3 delete can reduce one change
return delete + max(missingtype,change) # missing type and change condition must both satisifed.
看到这题就头疼~，直接看答案了。
当有20+chars，必须delete=len（s）-20.但是我们能用这些delete中的一部分来处理3char rule violation。
1） aaa ... 这种violation可以del最后一个a。所以， 需要从change里减去这些del。change -= min(delete, one)
2）aaaa ... 这种violation可以del最后2个a。因为已经用了1）中的deletions，所以需要调整, min(max(delete - one, 0), two * 2) // 2 意思是，如果残留 max(delete - one, 0) 个dels，那么，用这些dels来处理case2的violation。 因为必须del 2 chars to resolve each violation, 所以只能用 dels // 2
3）aaaaa ...这种 violation可以del最后3个a。 max(delete - one - 2 * two, 0) // 3