451. Sort Characters By Frequency （Medium）
Given a string s, sort it in decreasing order based on the frequency of the characters. The frequency of a character is the number of times it appears in the string.
Return the sorted string. If there are multiple answers, return any of them
class Solution:
def frequencySort(self, s: str) -> str:
d=Counter(s)
res=''
for k in sorted(d,key=lambda x: d[x],reverse=True):
res+=k*d[k]
return res
#O(n) bucket sort
class Solution:
def frequencySort(self, s: str) -> str:
if not s: return s
counts=collections.Counter(s)
max_freq=max(counts.values())
buckets=[[] for _ in range(max_freq+1)]
for c,i in counts.items():
buckets[i].append(c)
string_builder=[]
for i in range(len(buckets)-1,0,-1):
for c in buckets[i]:
string_builder.append(c*i)
return ''.join(string_builder)
答案的On解法好。bucketsort
452. Minimum Number of Arrows to Burst Balloons (Medium)
There are some spherical balloons taped onto a flat wall that represents the XY-plane. The balloons are represented as a 2D integer array points where points[i] = [xstart, xend] denotes a balloon whose horizontal diameter stretches between xstart and xend. You do not know the exact y-coordinates of the balloons.
Arrows can be shot up directly vertically (in the positive y-direction) from different points along the x-axis. A balloon with xstart and xend is burst by an arrow shot at x if xstart <= x <= xend. There is no limit to the number of arrows that can be shot. A shot arrow keeps traveling up infinitely, bursting any balloons in its path.
Given the array points, return the minimum number of arrows that must be shot to burst all balloons.
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
#merge range by min range calculate len
points.sort()
res = []
for a,b in points:
# a b
# res a' b'
if res and a<=res[-1][1] :
res[-1][1] = min(res[-1][1],b)
else:
res.append([a,b])
return len(res)
#ANSWER WAY OF WRITTING
class Solution:
def findMinArrowShots(self, points: List[List[int]]) -> int:
if not points:
return 0
# sort by x_end
points.sort(key = lambda x : x[1])
arrows = 1
first_end = points[0][1]
for x_start, x_end in points:
# if the current balloon starts after the end of another one,
# one needs one more arrow
if first_end < x_start:
arrows += 1
first_end = x_end
return arrows
我的思路是找到相交的区间，看总共多少个就行。。。答案思路是track球右边位置，让碰到新气球左边大于cur end位置+1，更新end位置的greedy算法。
453. Minimum Moves to Equal Array Elements （Medium）
Given an integer array nums of size n, return the minimum number of moves required to make all array elements equal.
In one move, you can increment n - 1 elements of the array by 1.
#TLE naive solution
class Solution:
def minMoves(self, nums: List[int]) -> int:
c=0
while len(set(nums))!=1:
ind = nums.index(max(nums))
for i in range(len(nums)):
if i!=ind:
nums[i]+=1
#print(nums)
c+=1
return c
#ANSWER
class Solution:
def minMoves(self, nums: List[int]) -> int:
nums.sort()
c=0
for i in range(len(nums)-1,0,-1):
c+=nums[i]-nums[0]
return c
#ANSWER
class Solution:
def minMoves(self, nums: List[int]) -> int:
moves=0
min_=float('inf')
for i in range(len(nums)):
moves+=nums[i]
min_=min(min_,nums[i])
return moves-min_*len(nums)
#MY ANSWER
class Solution:
# 除了一个位置，其余位置同时加1。 等效于这个位置减去1。
def minMoves(self, nums: List[int]) -> int:
me=min(nums)
res = 0
for n in nums:
res+= n-me
return res
答案很巧妙，如果是答案1） 思路先sort，那么每次需要move是nums【i】-nums【0】，这样move后nums【i】和nums【0】相等，然后其余数字都加上了move次，再次move时候，求nums【i-1】-nums【0】，这样nums【0】就和nums【i-1】相等，自然也和nums【i】相等。 以此类推，可求出总共move数目。 如果是答案2）所有加1除了1个不加，和只有一个减去1是等效的。 所以就是减多少次能使所有数平衡，sum（all）-min（all）乘n。
454. 4Sum II （Medium）
Given four integer arrays nums1, nums2, nums3, and nums4 all of length n, return the number of tuples (i, j, k, l) such that:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
dic2sum=collections.defaultdict(int)
for i in nums1:
for j in nums2:
dic2sum[i+j]+=1
res=0
for k in nums3:
for l in nums4:
if -k-l in dic2sum:
res+=dic2sum[-k-l]
return res
#
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
d1 = collections.defaultdict(int)
d2 = collections.defaultdict(int)
for a in nums1:
for b in nums2:
d1[a+b]+=1
for c in nums3:
for d in nums4:
d2[c+d]+=1
res = 0
for k1,v1 in d1.items():
for k2,v2 in d2.items():
if k1+k2==0:
res+=v1*v2
return res
#ANSWER GENERALIZED
class Solution:
def fourSumCount(self, A: List[int], B: List[int], C: List[int], D: List[int]) -> int:
m = collections.defaultdict(int)
lists = [A, B, C, D]
def nSumCount() -> int:
addToHash(0, 0)
return countComplements(len(lists) // 2, 0)
def addToHash(i: int, total: int) -> None:
if i == len(lists) // 2:
m[total] = m[total] + 1
else:
for a in lists[i]:
addToHash(i + 1, total + a)
def countComplements(i: int, complement: int) -> int:
if i == len(lists):
return m[complement]
cnt = 0
for a in lists[i]:
cnt += countComplements(i + 1, complement - a)
return cnt
return nSumCount()
455. Assign Cookies (Easy)
Assume you are an awesome parent and want to give your children some cookies. But, you should give each child at most one cookie.
Each child i has a greed factor g[i], which is the minimum size of a cookie that the child will be content with; and each cookie j has a size s[j]. If s[j] >= g[i], we can assign the cookie j to the child i, and the child i will be content. Your goal is to maximize the number of your content children and output the maximum number.
class Solution:
def findContentChildren(self, g: List[int], s: List[int]) -> int:
g.sort()
s.sort()
res = 0
while g:
need = g.pop(0)
while s and s[0]<need:
s.pop(0)
if s:
s.pop(0)
res+=1
return res
#
# 先对g, s两个数组进行排序
# 贪心算法
# 贪心思想1 优先满足需求因子较小的孩子。因为如果较小需求的孩子无法被满足，则之后的较大的需求更不可能能被满足了。
#贪心思想2 尽量用较小的糖果去优先满足孩子。
class Solution:
def findContentChildren(self, g, s):
"""
:type g: List[int]
:type s: List[int]
:rtype: int
"""
g.sort() # 对需求因子进行排序，从小到大
s.sort() # 对糖果数组进行排序，从小到大
child = 0 # 记录可以被满足孩子数
cookie = 0 # 记录可以满足的糖果数
while child <len(g) and cookie < len(s):
if g[child] <= s[cookie]:
child += 1
cookie += 1
return child
456. 132 Pattern （Medium）
Given an array of n integers nums, a 132 pattern is a subsequence of three integers nums[i], nums[j] and nums[k] such that i < j < k and nums[i] < nums[k] < nums[j].
Return true if there is a 132 pattern in nums, otherwise, return false.
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
if len(nums) < 3:
return False
stack=[]
min_array = [-1] * len(nums)
min_array[0] = nums[0]
for i in range(1, len(nums)):
min_array[i] = min(min_array[i - 1], nums[i])
for j in range(len(nums) - 1, -1, -1):
if nums[j] <= min_array[j]:
continue
while stack and stack[-1] <= min_array[j]:
stack.pop()
#到此 确保了stack[-1] 大于 min_array[j]，只需要确保下一步了
if stack and stack[-1] < nums[j]:
return True
stack.append(nums[j])
return False
估计是用stack但是。。。看答案思路：从前往后算minarry，从后往前用stack。
457. Circular Array Loop （Medium）
You are playing a game involving a circular array of non-zero integers nums. Each nums[i] denotes the number of indices forward/backward you must move if you are located at index i:
If nums[i] is positive, move nums[i] steps forward, and
If nums[i] is negative, move nums[i] steps backward.
Since the array is circular, you may assume that moving forward from the last element puts you on the first element, and moving backwards from the first element puts you on the last element.
A cycle in the array consists of a sequence of indices seq of length k where:
Following the movement rules above results in the repeating index sequence seq[0] -> seq[1] -> ... -> seq[k - 1] -> seq[0] -> ...
Every nums[seq[j]] is either all positive or all negative.
k > 1
Return true if there is a cycle in nums, or false otherwise.
class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
#two pointer
n=len(nums)
#check every start location
for start in range(n):
if nums[start]==0: continue
slow=start
fast=(slow+nums[slow])%n
#if sign of fast and fast.next is the same we do the while loop
while nums[start]*nums[fast]>0 and nums[start] * nums[(fast+nums[fast])%n] > 0:
if slow == fast:
if slow == (slow+nums[slow])%n:
break # 1-element loop
return True
slow = (slow+nums[slow])%n
fast = (fast+nums[fast])%n
fast = (fast+nums[fast])%n
#we are here know start from start have no loop so mark visited as 0
slow = start
sgn = nums[start]
while sgn * nums[slow] > 0:
nxt = (slow+nums[slow])%n
nums[slow] = 0
slow = nxt
return False
#MY ANSWER DFS
class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
n = len(nums)
visited = set()
self.res =False
def dfs(i,visited):
if i in visited:
if (i+nums[i])%n!=i :
#no self loop
start = i
sign = [ ]
while (start+nums[start])%n!=i:
sign.append(nums[start]>0)
start = (start+nums[start])%n
sign.append(nums[start]>0)
if len(sign)>1 and (all(sign) or not any(sign)):
self.res = True
return
visited.add(i)
dfs( (i+nums[i])%n, visited)
for i in range(n):
dfs(i,set())
return self.res
#ANSWER PYTHONIC
class Solution:
def circularArrayLoop(self, nums: List[int]) -> bool:
t = {i: (i + v) % len(nums) for i, v in enumerate(nums)}
inc = {k: v for k, v in t.items() if k != v}
while inc:
if any(k == v for k, v in inc.items()): return True
inc = {k: t[v] for k, v in inc.items() if nums[k] * nums[v] > 0 and v in inc}
return False
two pointer, but tricky ....if we meet element with different directions, then the search fail, we set all elements along the way to 0. Because 0 is fail for sure so when later search meet 0 we know the search will fail.
458. Poor Pigs (Hard)
There are buckets buckets of liquid, where exactly one of the buckets is poisonous. To figure out which one is poisonous, you feed some number of (poor) pigs the liquid to see whether they will die or not. Unfortunately, you only have minutesToTest minutes to determine which bucket is poisonous.
You can feed the pigs according to these steps:
Choose some live pigs to feed.
For each pig, choose which buckets to feed it. The pig will consume all the chosen buckets simultaneously and will take no time.
Wait for minutesToDie minutes. You may not feed any other pigs during this time.
After minutesToDie minutes have passed, any pigs that have been fed the poisonous bucket will die, and all others will survive.
Repeat this process until you run out of time.
Given buckets, minutesToDie, and minutesToTest, return the minimum number of pigs needed to figure out which bucket is poisonous within the allotted time.
class Solution:
def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
return int(math.ceil(math.log(buckets, 2) / math.log(minutesToTest / minutesToDie + 1, 2)))
#MY ANSWER
class Solution:
def poorPigs(self, buckets: int, minutesToDie: int, minutesToTest: int) -> int:
if buckets == 1: return 0
round = minutesToTest//minutesToDie
# 1pig is 1 bit has 2 state only when round == 1
# 2**pig >= buckets
round = minutesToTest//minutesToDie
states = round+1
l=1
r = buckets
while l<=r:
m = (l+r)//2
if states**m<buckets:
#pig too small
l=m+1
else:
#pig too large
r=m-1
return l
good to knwo but not algorithm..
459. Repeated Substring Pattern （Easy）
Given a string s, check if it can be constructed by taking a substring of it and appending multiple copies of the substring together.
class Solution:
def repeatedSubstringPattern(self, s: str) -> bool:
for i in range(1,len(s)//2+1):
if s[:i]*(len(s)//i)==s:
return True
return False
#ANSWER
def repeatedSubstringPattern(self, str):
"""
:type str: str
:rtype: bool
"""
if not str:
return False
ss = (str + str)[1:-1]
return ss.find(str) != -1
#ANSWER
def repeatedSubstringPattern(self, str):
return s in (s+s)[1:-1]
答案思路很好， If the string S has repeated block, it could be described in terms of pattern.
S = SpSp (For example, S has two repeatable block at most)
If we repeat the string, then SS=SpSpSpSp.
Destroying first and the last pattern by removing each character, we generate a new S2=SxSpSpSy.
460. LFU Cache （Hard）
Design and implement a data structure for a Least Frequently Used (LFU) cache.
Implement the LFUCache class:
LFUCache(int capacity) Initializes the object with the capacity of the data structure.
int get(int key) Gets the value of the key if the key exists in the cache. Otherwise, returns -1.
void put(int key, int value) Update the value of the key if present, or inserts the key if not already present. When the cache reaches its capacity, it should invalidate and remove the least frequently used key before inserting a new item. For this problem, when there is a tie (i.e., two or more keys with the same frequency), the least recently used key would be invalidated.
To determine the least frequently used key, a use counter is maintained for each key in the cache. The key with the smallest use counter is the least frequently used key.
When a key is first inserted into the cache, its use counter is set to 1 (due to the put operation). The use counter for a key in the cache is incremented either a get or put operation is called on it.
The functions get and put must each run in O(1) average time complexity.
class Node:
def __init__(self,key,val):
self.key = key
self.val = val
self.freq = 1
self.pre = None
self.next = None
class DLL:
def __init__(self):
self.head = Node('H','H')
self.tail = Node('T','T')
self.head.next =self.tail
self.tail.pre = self.head
self.size = 0
def append(self,node):
self.tail.pre.next = node
node.pre = self.tail.pre
node.next =self.tail
self.tail.pre = node
self.size+=1
def pop(self, node=None):
#pop from head
if self.size == 0: return None
if not node:
node = self.head.next
node.pre.next =node.next
node.next.pre = node.pre
self.size-=1
return node
def __len__(self):
return self.size
def __repr__(self):
res = []
cur = self.head
while cur:
res.append( '-'.join(map(str,[cur.freq,cur.key,cur.val])) )
cur = cur.next
return ','.join(res)
class LFUCache:
#
# freq1 freq2 .
# H 1 2 T H 3 4 T
def __init__(self, capacity: int):
self.size = 0
self.cap = capacity
self.key2node = dict()
self.freq2dll = defaultdict(DLL)
self.minfreq = 0
def debug(self,flag=False):
if flag:
print('#'*10)
for f, dll in self.freq2dll.items():
print(f)
print(dll)
print('#'*10)
def _update(self,node):
freq = node.freq
self.freq2dll[freq].pop(node)
if self.minfreq==freq and len(self.freq2dll[freq])==0:
self.minfreq+=1
node.freq+=1
freq = node.freq
self.freq2dll[freq].append(node)
def get(self, key: int) -> int:
#print('get',key)
if key not in self.key2node: return -1
node = self.key2node[key]
self._update(node)
self.debug()
return node.val
def put(self, key: int, value: int) -> None:
if self.cap == 0: return
if key in self.key2node:
node = self.key2node[key]
self._update(node)
node.val = value
else:
if self.size==self.cap:
node = self.freq2dll[self.minfreq].pop()
del self.key2node[node.key]
self.size-=1
#if not len(self.freq2dll[self.minfreq]):
# self.minfreq+=1
node = Node(key,value)
self.key2node[key] = node
self.freq2dll[1].append(node)
self.minfreq = 1
self.size+=1
self.debug()
# Your LFUCache object will be instantiated and called as such:
# obj = LFUCache(capacity)
# param_1 = obj.get(key)
# obj.put(key,value)
Each key is mapping to the corresponding node (self._node), where we can retrieve the node in O(1) time.
Each frequency freq is mapped to a Doubly Linked List (self._freq), where all nodes in the DLinkedList have the same frequency, freq. Moreover, each node will be always inserted in the head (indicating most recently used).
A minimum frequency self._minfreq is maintained to keep track of the minimum frequency of across all nodes in this cache, such that the DLinkedList with the min frequency can always be retrieved in O(1) time.
Here is how the algorithm works
get(key)
query the node by calling self._node[key]
find the frequency by checking node.freq, assigned as f, and query the DLinkedList that this node is in, through calling self._freq[f]
pop this node
update node's frequence, append the node to the new DLinkedList with frequency f+1
if the DLinkedList is empty and self._minfreq == f, update self._minfreq to f+1.
return node.val
put(key, value)
If key is already in cache, do the same thing as get(key), and update node.val as value
Otherwise:
if the cache is full, pop the least frequenly used element (*)
add new node to self._node
add new node to self._freq[1]
reset self._minfreq to 1
(*) The least frequently used element is the tail element in the DLinkedList with frequency self._minfreq
#MY ANSWER
# freq1 freq 2 freq3
# H 1 T H 2 T H 3 T
debug_flag = False
class Node:
def __init__(self,key,value):
self.key = key
self.val = value
self.pre = None
self.next = None
class DLL:
def __init__(self):
self.size = 0
self.head = Node('H','H')
self.tail = Node('T','T')
self.head.next = self.tail
self.tail.pre = self.head
self.key2node = dict()
def append(self,node):
key = node.key
self.key2node[key] = node
self.size+=1
#append before tail
self.tail.pre.next = node
node.pre =self.tail.pre
node.next = self.tail
self.tail.pre = node
def pop0(self, node = None):
if not node:
node = self.head.next
self.size-=1
key = node.key
node = self.key2node[key]
del self.key2node[key]
#remove node
node.pre.next = node.next
node.next.pre = node.pre
return node
def get_node(self,key):
if key in self.key2node:
return self.key2node[key]
return None
def __len__(self):
return self.size
def __repr__(self):
res = []
cur = self.head
while cur:
res.append('-'.join([str(cur.key),str(cur.val)]))
cur =cur.next
return ','.join(res)
class LFUCache:
def __init__(self, capacity: int):
self.cap = capacity
self.c = 0
self.freq2dll = collections.defaultdict(DLL)
self.key2freq = collections.defaultdict(int)
self.minfreq = None
self.debugcounter = -1
def debug(self):
if debug_flag:
print('#'*10)
for f in sorted(self.freq2dll):
dll = self.freq2dll[f]
print(f)
print(dll)
print('#'*10)
def get(self, key: int) -> int:
self.debugcounter+=1
if debug_flag:print(self.debugcounter , 'get',key)
if key not in self.key2freq: return -1
old_freq = self.key2freq[key]
new_freq = self.key2freq[key]+1
self.key2freq[key] = new_freq
node = self.freq2dll[old_freq].get_node(key)
self.freq2dll[old_freq].pop0(node)
if old_freq==self.minfreq and not self.freq2dll[old_freq]:
del self.freq2dll[old_freq]
self.minfreq = new_freq
if new_freq not in self.freq2dll:
self.freq2dll[new_freq] = DLL()
self.freq2dll[new_freq].append(node)
self.debug()
return node.val
def put(self, key: int, value: int) -> None:
self.debugcounter+=1
if debug_flag:print(self.debugcounter,'put',key,value)
if key not in self.key2freq:
self.c+=1
if self.c>self.cap:
#remove least frequent
node = self.freq2dll[self.minfreq].pop0()
del self.key2freq[node.key]
if not self.freq2dll[self.minfreq]:
del self.freq2dll[self.minfreq]
self.c-=1
self.key2freq[key] = 1
if 1 not in self.freq2dll:
self.freq2dll[1] = DLL()
node = Node(key,value)
self.freq2dll[1].append(node)
self.minfreq = 1
else:
#key in key2freq
self.key2freq[key] += 1
old_freq = self.key2freq[key]-1
new_freq = self.key2freq[key]
#update old_freq dll
node = self.freq2dll[old_freq].get_node(key)
self.freq2dll[old_freq].pop0(node)
if not self.freq2dll[old_freq]:
del self.freq2dll[old_freq]
node.val = value
# update minfreq
if old_freq == self.minfreq and not self.freq2dll[old_freq]:
self.minfreq = new_freq
#node ready to insert to new_freq dll
if new_freq not in self.freq2dll:
self.freq2dll[new_freq] = DLL()
self.freq2dll[new_freq].append(node)
self.debug()
要特别注意 update minfreq，
if old_freq == self.minfreq and not self.freq2dll[old_freq]:
self.minfreq = new_freq