# 亞麻OA 校招
### Searching in a 2D matrix
```java
class Point {
int x;
int y;
}
Point isInMatrix(int[][] matrix, int target){
int row = matrix.length;
int column = matrix[0].length;
int r = 0;
int c = column - 1;
while (r < row && c >= 0){
if (matrix[r][c] == target){
return new Point(r,c);
}
if (matrix[r][c] > target){
c--;
} else {
r++;
}
}
return new Point(-1,-1);
}
```
### Critical connections
```python
class Solution:
def criticalConnections(self, n: int, connections: List[List[int]]) -> List[List[int]]:
graph = collections.defaultdict(list)
for i, j in connections:
graph[i].append(j)
graph[j].append(i)
ans = []
states = [-1] * n
#Start from 0, if we find the step is smaller or equal to the minimum step, it means ring exist.
def dfs(curr, parents, steps):
states[curr] = steps + 1 #Min step now
for child in graph[curr]:
if child == parents: continue #go back and forth
elif states[child] == -1: #haven't vistied
states[curr] = min(states[curr], dfs(child, curr, steps + 1))
else: #if we find smaller step, update it
states[curr] = min(states[curr], states[child])
#Check if the step changes, but 0 which is the starting point should be excluded
if states[curr] == steps + 1 and curr != 0:
ans.append([parents, curr])
return states[curr]
dfs(0, -1, 0)
return ans
```
### Copy List with Random Pointer
```python
class Node:
def __init__(self, x: int, next: 'Node' = None, random: 'Node' = None):
self.val = int(x)
self.next = next
self.random = random
class Solution:
def copyRandomList(self, head: 'Node') -> 'Node':
dummy = Node(0)
nodeDict = {}
newHead, curr = dummy, head
while curr:
node = Node(curr.val)
nodeDict[curr] = node
newHead.next = node
newHead = newHead.next
curr = curr.next
curr = head
while curr:
if curr.random:
nodeDict[curr].random = nodeDict[curr.random]
curr = curr.next
return dummy.next
```
### Jenny(題目沒看到只記得有個人叫Jenny)
```python
from collections import defaultdict, deque
N, M, K = map(int, input().split())
graph = defaultdict(list)
v, max, cost, ans = [False] * (N + 1), 0, 0, 0
def BFS(start, ok = False):
if v[start]:
return
global max, cost, ans
v[start], nr, edges = True, 1, set()
queue = deque([start])
while queue:
node = queue.popleft()
for next_node in graph[node]:
if not v[next_node]:
nr += 1
v[next_node] = True
queue.append(next_node)
if not (node, next_node) in edges and not (next_node, node) in edges:
edges.add((node, next_node))
ans += nr * (nr - 1) // 2 - len(edges)
if ok:
if (nr > max):
max = nr
else:
global nr_without_water
ans += nr_without_water * nr
cost += nr_without_water * nr
nr_without_water += nr
while M:
M -= 1
x, y = map(int, input().split())
graph[x].append(y)
graph[y].append(x)
for water_point in map(int, input().split()): # 1
BFS(water_point, True)
nr_without_water = 0 # 2
for i in range(1, N + 1):
BFS(i)
ans += max * nr_without_water # 3
cost += max * nr_without_water
print(ans, cost) # 4
```
### Connecting city with minimum cost
```python
def minimumCost(self, N: int, connections: List[List[int]]) -> int:
parents = [x for x in range(N)]
ranks = [1] * N
def find(u):
while u != parents[u]:
parents[u] = parents[parents[u]]
u = parents[u]
return u
def union(u, v):
root_u, root_v = find(u), find(v)
if root_u == root_v: return False
if ranks[root_v] > ranks[root_u]:
root_u, root_v = root_v, root_u
parents[root_v] = root_u
ranks[root_u] += ranks[root_v]
return True
connections.sort(key = lambda x: x[2])
ans = 0
for u, v, val in connections:
if union(u-1, v-1): ans += val
groups = len({find(x) for x in parents})
return ans if groups == 1 else -1
```
### Subtree with Maximum Average
```python
class TreeNode:
def __init__(self, val, children):
self.val = val
self.children = children
class Solution:
def maxAverage(self, root):
if not root or not root.children:
return None
# self.res = [max average, tree node of the max average]
self.res = [float('-inf'), root)]
self.dfs(root)
return self.res[1]
def dfs(self, root):
if not root.children:
return [root.val, 1]
cur_val, cur_count = root.val, 1
for node in root.children:
child_val, child_count = self.dfs(node)
cur_val += child_val
cur_count += child_count
cur_average = cur_val / float(cur_count)
if cur_average > self.res[0]:
self.res = [cur_average, root]
return [cur_val, cur_count]
```
```python
def maximumAverageSubtree(self, root):
self.res = 0
def helper(root):
if not root: return [0, 0.0]
n1, s1 = helper(root.left)
n2, s2 = helper(root.right)
n = n1 + n2 + 1
s = s1 + s2 + root.val
self.res = max(self.res, s / n)
return [n, s]
helper(root)
return self.res
```
### Battle Ship
```python
S = "1B 2C,2D 4D"
T = "2B 2D 3D 4D 4A"
tothit, totsunk = 0,0
def noPos(i):
no = ''
pos = ''
for j in i:
if(0 <= ord(j) - ord('0') <=9):
no+=j
else:
pos+=j
no = int(no)
pos = ord(pos)-ord('A')
return[no, pos]
target = []
S = S.split(',')
T = T.split()
for i in T:
target.append(noPos(i))
for i in S:
i = i.split()
hit, sunk, count = 0,0,0
rlow, rhigh, clow, chigh =0,0,0,0
cc= 0
for k in i :
if(cc == 0):
rlow, clow = noPos(k)
cc+=1
else:
rhigh, chigh = noPos(k)
for r in range(rlow, rhigh+1):
for c in range(clow, chigh+1):
count+=1
if([r, c] in target):
hit+=1
if hit == count:
totsunk+=1
elif(0<hit<count):
tothit+=1
print("total ships hit are ", tothit, " and total sunk are ", totsunk)
```
### Robot throw, robotic challenge
```python
class Solution(object):
def calPoints(self, ops):
# Time: O(n)
# Space: O(n)
history = []
for op in ops:
if op == 'C':
history.pop()
elif op == 'D':
history.append(history[-1] * 2)
elif op == '+':
history.append(history[-1] + history[-2])
else:
history.append(int(op))
return sum(history)
```
### Distance Between Nodes in BST
```python
class TreeNode(object):
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def insert(root, val):
if root == None:
return TreeNode(val=val)
if val < root.val:
root.left = insert(root.left, val)
else:
root.right = insert(root.right, val)
return root
bst = []
def preorder(root):
if root == None:
bst.append(None)
return
bst.append(root.val)
preorder(root.left)
preorder(root.right)
def lowestCommonAncestor(root, p, q):
"""
:type root: TreeNode
:type p: int
:type q: int
:rtype: TreeNode
"""
parent_val = root.val
if p < parent_val and q < parent_val:
return lowestCommonAncestor(root.left, p, q)
if p > parent_val and q > parent_val:
return lowestCommonAncestor(root.right, p, q)
return root
def height(root, val):
if root.val == val:
return 0
if val < root.val:
return (height(root.left, val) + 1)
else:
return (height(root.right, val) + 1)
l = [4, 2, 7, 1, 3, 5]
p = 1
q = 2
root = None
for val in l:
root = insert(root, val)
preorder(root)
print bst
lca = lowestCommonAncestor(root, p, q)
print lca.val
h1 = height(lca, p)
h2 = height(lca, q)
print h1, h2
print h1 + h2
```
### Treasure Island
```python
def solution(m):
if len(m) == 0 or len(m[0]) == 0:
return -1 # impossible
matrix = [row[:] for row in m]
nrow, ncol = len(matrix), len(matrix[0])
q = deque([((0, 0), 0)]) # ((x, y), step)
matrix[0][0] = "D"
while q:
(x, y), step = q.popleft()
for dx, dy in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
if 0 <= x+dx < nrow and 0 <= y+dy < ncol:
if matrix[x+dx][y+dy] == "X":
return step+1
elif matrix[x+dx][y+dy] == "O":
# mark visited
matrix[x + dx][y + dy] = "D"
q.append(((x+dx, y+dy), step+1))
return -1
```
### Valid Parentheses
```python
class Solution:
def isValid(self, s: str) -> bool:
stack = []
d = {"[": "]", "{":"}", "(":")"}
for i in s:a
if i in d:
stack.append(i)
else:
if not stack or d[stack.pop()] != i : return False
return True if not stack else False
```
### Longest Palindromic Substring
```python
class Solution:
def longestPalindrome(self, s: str) -> str:
n = len(s)
def getLen(s, l, r):
while l >= 0 and r < n and s[l] == s[r]:
l -= 1
r += 1
return r - l -1
start, length, end = 0, 0, 0
for i in range(n):
curr = max(getLen(s, i, i), getLen(s, i, i+1))
if curr < length: continue
length = curr
start = i - (length-1) // 2
end = start + length
return s[start: end]
```
### Search Suggestions System , Keyword Suggestions
```python
def suggestedProducts(self, A, word):
A.sort()
res, prefix, i = [], '', 0
for c in word:
prefix += c
i = bisect.bisect_left(A, prefix, i)
res.append([w for w in A[i:i + 3] if w.startswith(prefix)])
return res
```
### Count teams
```python
import math
def solution(num, skills, minAssociates, minLevel, maxLevel):
satis = 0
for skill in skills:
if minLevel <= skill <= maxLevel:
satis+=1
ans = 0
for i in range(minAssociates, satis+1):
ans += math.factorial(satis) / math.factorial(i) * math.factorial(satis - i)
return ans
```
### Fetch Item to display
```java
public class Main {
public static List<String> fetchItemsToDisplay(int numOfItems, HashMap<String, Pair<Integer, Integer>> items, int sortParameter, int sortOrder, int itemsPerPage, int pageNumber) {
if(items.size() == 0)
return Collections.EMPTY_LIST;
SortedSet<Map.Entry<String, Pair<Integer, Integer>>> set = new TreeSet<>(new Comparator<Map.Entry<String, Pair<Integer, Integer>>>() {
@Override
public int compare(Map.Entry<String, Pair<Integer, Integer>> entry1, Map.Entry<String, Pair<Integer, Integer>> entry2) {
if(sortParameter == 0) {
if(sortOrder == 0)
return entry1.getKey().compareTo(entry2.getKey());
return entry2.getKey().compareTo(entry1.getKey());
}
if(sortParameter == 1) {
if(sortOrder == 0)
return (int) entry1.getValue().getKey() - (int) entry2.getValue().getKey();
return (int) entry2.getValue().getKey() - (int) entry1.getValue().getKey();
}
if(sortParameter == 2) {
if(sortOrder == 0)
return (int) entry1.getValue().getValue() - (int) entry2.getValue().getValue();
return (int) entry2.getValue().getValue() - (int) entry1.getValue().getValue();
}
return 0;
}
});
set.addAll(items.entrySet());
List<String> result = new ArrayList<>();
for(Map.Entry<String,Pair<Integer, Integer>> entry : set)
result.add(entry.getKey());
int start = pageNumber * itemsPerPage;
int end = (start + itemsPerPage) > result.size() ? result.size() : start + itemsPerPage;
return result.subList(start, end);
}
public static void main(String[] args) {
int numOfItems = 3;
HashMap<String, Pair<Integer, Integer>> items = new HashMap<>();
items.put("item1", new Pair<Integer, Integer>(10, 15));
items.put("item2", new Pair<Integer, Integer>(3, 4));
items.put("item3", new Pair<Integer, Integer>(17, 8));
int sortParameter = 1;
int sortOrder = 0;
int itemsPerPage = 2;
int pageNumber = 1;
System.out.println(fetchItemsToDisplay(numOfItems, items, sortParameter, sortOrder, itemsPerPage, pageNumber));
}
}
```
### Find the highest profit
```python
suppliers = [3, 5]
order = 6
import heapq
max_heap = []
for product in suppliers:
heapq.heappush(max_heap, -product)
profit = 0
while max_heap and order > 0:
product = heapq.heappop(max_heap)
product_profit = -product
profit += product_profit
if product_profit > 0:
product_profit -= 1
heapq.heappush(max_heap, -product_profit)
```
### Break a Palindrome
```python
def breakPalindrome(self, S):
for i in xrange(len(S) / 2):
if S[i] != 'a':
return S[:i] + 'a' + S[i + 1:]
return S[:-1] + 'b' if S[:-1] else ''
```
### Fill The Truck
```python
import heapq
def fillTheTruck(num, boxes, unitSize, unitsPerBox, truckSize):
pq = []
for i in range(len(boxes)):
for j in range(boxes[i]):
heapq.heappush(pq, -unitsPerBox[i])
ans = 0
while truckSize > 0 and pq:
ans += - heapq.heappop(pq)
truckSize -= 1
return ans
```
### Optimal Utilization
```python
class Solution:
def findPairs(self, a, b, target):
a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
l, r = 0, len(b) - 1
ans = []
curDiff = float('inf')
while l < len(a) and r >= 0:
id1, i = a[l]
id2, j = b[r]
if (target - i - j == curDiff):
ans.append([id1, id2])
elif (i + j <= target and target - i - j < curDiff):
ans.clear()
ans.append([id1, id2])
curDiff = target - i - j
if (target > i + j):
l += 1
else:
r -= 1
return ans
```
### Cut off Rank
```python
def GetRanks(cutOffRank, numScores, scores):
scores.sort()
rank = []
if cutOffRank == numScores:
return numScores
rank.append(1)
for i in reversed(range(1, len(scores))):
if scores[i] == scores[i-1]:
rank.append(i-1)
else:
rank.append(i)
ans = 0
for j in range(len(rank)):
if rank[j] <= cutOffRank:
ans += 1
return ans
```
### Min Cost to Connect Rope
```python
def minCost(ropes: List[int]) -> int:
if not ropes: return 0
if len(ropes) == 1: return ropes[0]
heapify(ropes)
cost = 0
while len(ropes) > 1:
a, b = heappop(ropes), heappop(ropes)
cost += a+b
if ropes:
heappush(ropes, a+b)
return cost
```
### Amazon Fresh Promotion
```python
secret_code = [['apple', 'apple'], ['banana', WILD_CARD, 'banana']]
user_purchase = ['apple', 'apple', 'apple', 'banana']
expected 0
secret_code = [['apple', 'apple']]
user_purchase = ['apple', 'apple', 'apple', 'banana']
expected 1
secret_code = []
user_purchase = ['apple', 'apple', 'apple', 'banana']
expected 1
WILD_CARD = 'anything'
# Time complexity is O( n + m )
def is_winner(secret_code, shopping_cart):
if not secret_code:
return True
shopping_cart_length = len(shopping_cart)
shopping_cart_index = 0 # Moving index to scan through shopping cart
secret_index = 0 # Moving index to scan through each secret
start_cart_index = 0 # to be able to reset search if partial secret was found
previous_scan_index = 0 # If one secret was found, we want to offset the search by the last index in the shopping cart
for i in range(len(secret_code)):
secret = secret_code[i] # Current secret we are looking for
secret_l = len(secret) # Length of current secret we are looking for
secret_index = 0
matched_secret = 0
while matched_secret != secret_l:
if (start_cart_index + shopping_cart_index) >= shopping_cart_length:
return 0
item = shopping_cart[start_cart_index+shopping_cart_index]
if item == secret[secret_index] or secret[secret_index] == WILD _CARD:
secret_index += 1
matched_secret += 1
shopping_cart_index += 1
else:
shopping_cart_index = previous_scan_index
start_cart_index += 1
if secret_index != 0:
secret_index = 0
matched_secret = 0
previous_scan_index = shopping_cart_index
if secret_index == len(secret_code[-1]):
return 1
return 0
```
```python
def isWinner(secret, shoppingCart):
def isMatch(source, target):
return target == "anything" or target == source
index = 0
secretIndex = 0
newIndex = index
secretWordIndex = 0
while secretIndex < len(secret) and newIndex < len(shoppingCart):
if isMatch(shoppingCart[newIndex], secret[secretIndex][secretWordIndex]):
newIndex+=1
secretWordIndex+=1
if secretWordIndex==len(secret[secretIndex]):
index+=1
index=newIndex
secretWordIndex=0
else:
index+=1
newIndex=index
secretWordIndex=0
return 1 if secretIndex == len(secret) else 0
```
### Items in Containers
```python
def numberOfItems(s, startIndicies, endIndicies):
n = len(s)
preSum = [0] * n
leftCompIdx =[0] * n
rightCompIdx = [0] * n
sum = 0
result = [0] * len(startIndicies)
for i in range(n):
if s[i] =="*":
sum += 1
preSum[i] = sum
seen = -1
for i in range(n):
if s[i] =="|":
seen = i
leftCompIdx[i] = seen
seen = -1
for i in range(n-1, -1, -1):
if s[i] =="|":
seen = i
rightCompIdx[i] = seen
k = 0
while k < len(startIndicies):
start = startIndicies[k] - 1
end = endIndicies[k] - 1
if rightCompIdx[start] != -1 and leftCompIdx[end] != -1:
result[k] = preSum[leftCompIdx[end]]- preSum[rightCompIdx[start]]
k+=1
return result
```
### Largest Item Association
```python
from collections import deque, defaultdict
def largest_item_association(item_association):
item_map = defaultdict(set)
for item_pair in item_association:
item_map[item_pair[0]].add(item_pair[1])
item_map[item_pair[1]].add(item_pair[0])
largest_group = []
visited = set()
for key in item_map.keys():
if key not in visited:
curr_group = []
q = deque()
q.append(key)
while q:
curr = q.popleft()
visited.add(curr)
curr_group.append(curr)
for neighbor in item_map[curr]:
if neighbor not in visited:
q.append(neighbor)
if len(curr_group) > len(largest_group):
largest_group = curr_group
elif len(curr_group) == len(largest_group):
if largest_group > curr_group:
largest_group = curr_group
largest_group.sort()
return largest_group
```
### Turnstile
```python
def turnstile(time, direction):
en, ex = [], []
res = [0] * len(time)
for i, t in enumerate(time):
if direction[i] == 1:
ex.append([time[i], i])
else:
en.append([time[i], i])
timeCounter, lastTurn = 0, -1 # time is 0 at the beginning and -1
# indicates nothing happened at prior time
while ex or en:
# Process the exit queue if and only if following conditions are satisfied
# If exit queue is not empty and the person at the front of the queue can go out based on his time stamp
# and ( Nothing happened at last time stamp i.e. nobody moved in or out so lastTurn will be -1 in this case
# or, somebody moved out at last time stamp, in this case lastTurn will be 1
# or, nobody is there in the entrance queue
# or, at last time stamp somebody got in but the person at the front of the queue can't go in due to their timestamp
if ex and ex[0][0] <= timeCounter and \
(lastTurn == -1 or lastTurn == 1 or not en or (lastTurn == 0 and en[0][0] > timeCounter)):
res[ex[0][1]] = timeCounter
lastTurn = 1
ex.pop(0)
elif en and en[0][0] <= timeCounter:
res[en[0][1]] = timeCounter
lastTurn = 0
en.pop(0)
else:
lastTurn = -1
timeCounter += 1
return res
```
### Five Star Sellers
```python
def fiveStartReviews(productRatings, ratingsThreshold):
count = 0
tempList = productRatings.copy()
while(getRating(tempList) < ratingsThreshold / 100):
distinctList = []
for productRating in tempList:
distinct = ((productRating[0] + 1) / (productRating[1] + 1)
) - ((productRating[0]) / (productRating[1]))
distinctList.append(distinct)
index = distinctList.index(max(distinctList))
tempList[index][0] = tempList[index][0] + 1
tempList[index][1] = tempList[index][1] + 1
count = count + 1
return count
def getRating(productRatings):
sum = 0
for i in productRatings:
sum = i[0]/i[1] + sum
return sum / len(productRatings)
```
### Minimum Difficulty of a Job Schedule/Best Beta
```python
def minDifficulty(self, A, d):
n, inf = len(A), float('inf')
if n < d: return -1
dp = [inf] * n + [0]
for d in range(1, d + 1):
for i in range(n - d + 1):
maxd, dp[i] = 0, inf
for j in range(i, n - d + 1):
maxd = max(maxd, A[j])
dp[i] = min(dp[i], maxd + dp[j + 1])
return dp[0]
```
### Autoscale Policy
```python
def autoScale(ins, A):
lim_l, lim_h, th_l, th_h, idle = 1, int(1e8), 25, 60, 10
i, n, ans = 0, len(A), ins
while i < n:
print(f'{i}-th second, utility is {A[i]}, instance number before action is {ans}')
if A[i] < th_l and ans > lim_l:
ans, i = (ans + 1) // 2, i + idle
elif A[i] > th_h and ans <= lim_h:
ans, i = ans * 2, i + idle
i += 1
return ans
```
### Top K Frequently Mentioned Keywords
```python
import collections
import heapq
import string
def topMentioned(keywords, reviews, k):
def preprocess(word):
result = ""
for c in word:
if c not in string.punctuation:
result += c.lower()
return result
count = collections.Counter()
kw = set([w.lower() for w in keywords])
for review in reviews:
seen = set()
words = review.split(" ")
for word in words:
w = preprocess(word)
if w in kw and w not in seen:
count[w] += 1
seen.add(w)
pq = []
for key, val in count.items():
heapq.heappush(pq, (-val, key))
return [heapq.heappop(pq)[1] for _ in range(k)]
```
### Transaction Logs
```python
import heapq
import collections
def getFrauds(logs, threshold):
count = collections.Counter()
for log in logs:
log = log.split(" ")
user1 = log[0]
user2 = log[1]
count[user1] += 1
count[user2] += 1
pq = []
for k, v in count.items():
heapq.heappush(pq, (-int(k), v, k))
ans = []
for _ in range(len(pq)):
_, freq, id = heapq.heappop(pq)
if freq >= threshold:
ans.append(id)
return ans
getFrauds(logs, threshold)
```
### Substrings of size K with K distinct chars
```python
def substringk(s, k):
if not s or k == 0:
return []
letter, res = {}, set()
start = 0
for i in range(len(s)):
if s[i] in letter and letter[s[i]] >= start:
start = letter[s[i]]+1
letter[s[i]] = i
if i-start+1 == k:
res.add(s[start:i+1])
start += 1
return list(res)
```
### Substrings of size K with K distinct chars
```python
import collections
def substringk(s, k):
if not s or k == 0:
return []
ch = collections.Counter()
ans = set()
l, r = 0, 0
while l <= r and r < len(s):
ch[s[r]] += 1
while ch[s[r]] > 1:
ch[s[l]] -= 1
l += 1
if r - l + 1 == k:
ans.add(s[l:r+1])
ch[s[l]] -= 1
l += 1
r += 1
return list(ans)
```
### Number of islands
```python
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
m = len(grid)
if m < 1:
return 0
n = len(grid[0])
def dfs(i,j):
grid[i][j] = "0"
if i + 1 < m and grid[i+1][j] == "1":
dfs(i+1, j)
if i - 1 >= 0 and grid[i-1][j] == "1":
dfs(i-1, j)
if j + 1 < n and grid[i][j+1] == "1":
dfs(i, j+1)
if j - 1 >= 0 and grid[i][j-1] == "1":
dfs(i, j-1)
ans = 0
for i in range(m):
for j in range(n):
if grid[i][j] == "1":
dfs(i,j)
ans += 1
return ans
```
### Most common words
```python
class Solution:
def mostCommonWord(self, paragraph: str, banned: List[str]) -> str:
bannedSet = set(banned)
words = re.findall(r'\w+', paragraph.lower())
counts = collections.Counter(w for w in words if w not in bannedSet)
return max(counts, key=counts.get)
```
### K closest points to origin
```python
def kClosest(self, points, K):
"""
:type points: List[List[int]]
:type K: int
:rtype: List[List[int]]
"""
def quickSelect(arr, left, right, k):
p = left
l, r = left, right
while l < r:
while l < r and arr[r][0] >= arr[p][0]:
r -= 1
while l < r and arr[l][0] < arr[p][0]:
l += 1
arr[l], arr[r] = arr[r], arr[l]
arr[p], arr[l] = arr[l], arr[p]
if l + 1 == k:
return arr[:l+1]
elif l + 1 < k:
return quickSelect(arr, l + 1, right, k)
else:
return quickSelect(arr, left, l - 1, k)
_index = {(points[i][0]**2 + points[i][1]**2): i for i in range(len(points))}
arr = [((y**2 + x**2), [y,x]) for y, x in points]
kClosest = quickSelect(arr, 0, len(arr)-1, K)
return [kClosest[i][1] for i in range(K)]
```
### Friend circle
```python
class Solution:
def findCircleNum(self, M: List[List[int]]) -> int:
ans, n = 0, len(M)
for i in range(n):
if M[i][i] == 1:
self.dfs(M, i, n)
ans += 1
return ans
def dfs(self, M, curr, n):
for i in range(n):
if M[curr][i] == 1:
M[curr][i] = M[i][curr] = 0
self.dfs(M, i, n)
```
### Partition label
```python
class Solution:
def partitionLabels(self, S: str) -> List[int]:
rightmost = {c: i for i,c in enumerate(S)}
l, r = 0, 0
ans = []
for i, c in enumerate(S):
# The rightmost position of the letter in the interval we visited so far
r = max(r, rightmost[c])
if i == r:
ans.append(r - l + 1)
l = i + 1
return ans
```
### wildcard matching
```python
class Solution:
def isMatch(self, s, p):
length = len(s)
#patter太長，字串太短
if len(p) - p.count("*") > length: return False
dp = [True] + [False] * length
for i in p:
if i != "*":
for j in reversed(range(length)):
dp[j+1] = dp[j] and (i == "?" or i == s[j])
else:
for j in range(1, length + 1):
dp[j] = dp[j-1] or dp[j]
dp[0] = dp[0] and i == "*"
return dp[-1]
```
### Recorder Data in log files
```python
class Solution:
def reorderLogFiles(self, logs: List[str]) -> List[str]:
def order(s):
id_, payload = s.split(' ', 1)
if payload[0].isalpha():
return (0, payload, id_)
else:
return (1, None, None)
return sorted(logs ,key=order)
```
### Shopping pattern
```python
import collections
def shoppingPattern(numOfProducts, products_from , products_to):
map = collections.defaultdict(set)
for i in range(len(products_from)):
map[products_from[i]].add(products_to[i])
map[products_to[i]].add(products_from[i])
count = float('inf')
for i in range(1, numOfProducts - 2):
if len(map[i]) < 2: continue
for j in range(i+1, numOfProducts - 1):
for k in range(j+1, numOfProducts):
if j in map[i] and k in map[j] and i in map[k]:
p = (len(map[i]) + len(map[j]) + len(map[k])) - 6
count = min(count, p)
return -1 if count == 0 else count
```
### Maximum Product of Splitted Binary Tree
```python
def maxProduct(self, root):
self.res = total = 0
def s(root):
if not root: return 0
left, right = s(root.left), s(root.right)
self.res = max(self.res, left * (total - left), right * (total - right))
return left + right + root.val
total = s(root)
s(root)
return self.res % (10**9 + 7)
```
### Design a Stack With Increment Operation
```python
def __init__(self, maxSize):
self.n = maxSize
self.stack = []
self.inc = []
def push(self, x):
if len(self.inc) < self.n:
self.stack.append(x)
self.inc.append(0)
def pop(self):
if not self.inc: return -1
if len(self.inc) > 1:
self.inc[-2] += self.inc[-1]
return self.stack.pop() + self.inc.pop()
def increment(self, k, val):
if self.inc:
self.inc[min(k, len(self.inc)) - 1] += val
```
### Third Maximum Number
```python
class Solution:
def thirdMax(self, nums: List[int]) -> int:
max1 = -2**32
max2 = -2**32
max3 = -2**32
for x in nums:
if x == max1 or x == max2 or x == max3: continue
if x > max1:
max3 = max2
max2 = max1
max1 = x
elif x > max2:
max3 = max2
max2 = x
elif x > max3:
max3 = x
return max1 if max3 == -2**32 else max3
```
### Sliding Window maximum
```python
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = collections.deque()
ans = []
for i in range(len(nums)):
while q and nums[i] > q[-1]:
q.pop()
q.append(nums[i])
#窗口的第一個>＝0
if i - k + 1 >= 0:
ans.append(q[0])
if nums[i - k + 1] == q[0]:
q.popleft()
return ans
```
### Longest Substring with At Most K Distinct Characters
```python
class Solution(object):
def lengthOfLongestSubstringKDistinct(self, s, k):
# Use dictionary d to keep track of (character, location) pair,
# where location is the rightmost location that the character appears at
d = {}
low, ret = 0, 0
for i, c in enumerate(s):
d[c] = i
while len(d) > k:
tmp = low
low = min(d.values())
print(tmp, low)
del d[s[low]]
low += 1
ret = max(i - low + 1, ret)
return ret
```
### Split Array Largest Sum
```python
class Solution:
def splitArray(self, nums: List[int], m: int) -> int:
l, r = max(nums), sum(nums) + 1
def minSum(nums, limit):
total = 0
groups = 1
for num in nums:
if total + num > limit:
total = num
groups += 1
else:
total += num
return groups
while l < r:
limit = (r - l) // 2 + l
if minSum(nums, limit) > m:
l = limit + 1
else:
r = limit
return l
```
### Label System
```python
k = 2
s = sorted(s)
length = len(s)
flag = 0
remains = list()
alike = s[-1]
for i in range(len(s)-1,-1,-1):
toset = list()
if s[i] == alike and i == 0 :
flag+=1
toset = s[i+k : flag]
del s[i+k : flag]
elif s[i] == alike :
flag += 1
continue
elif s[i] != alike :
if flag > k :
j = i
toset = s[i+1 : i+1+flag-k]
del s[i+1 : i+1+flag-k]
while toset and j >= 0 :
if len(toset)<k :
while toset :
s.insert(j,toset[0])
toset.pop(0)
else:
p = 0
while p < k :
s.insert(j,toset[0])
toset.pop(0)
p+=1
j-=1
flag = 1
alike = s[i]
if toset :
remains.append(toset)
for i in range(len(remains)):
j = 0
while remains[i] and j < len(s)-1 :
if s[j] != remains[i][0] and s[j+1] != remains[i][0] :
if len(remains[i]) > k :
p = 0
while p < k :
s.insert(j+1,remains[i][0])
remains[i].pop(0)
p+=1
else :
while remains[i] :
s.insert(j+1,remains[i][0])
remains[i].pop(0)
elif s[j] == remains[i][0] and s[max(0,j-1)] != remains[i][0]:
if s[j:j+k+1].count(remains[i][0]) < k :
rem = k - s[j:j+k+1].count(remains[i][0])
while rem and remains[i] :
s.insert(j,remains[i][0])
remains[i].pop(0)
rem-=1
elif s[j+1] != remains[i][0] and j+1 == len(s)-1:
p = 0
while remains[i] and p < k :
s.append(remains[i][0])
remains[i].pop(0)
p+=1
j += 1
result = ''.join([i for i in s[::-1]])
print(result)
```
### Labelling System
```python
def newLabel(s, limit):
n = len(s)
charset = [0] * 128
def nextAvailableChar(charset, start):
for i in range(start - 1,-1,-1):
if charset[i] > 0:
charset[i] -= 1
return chr(i)
return None
for i in range(n):
charset[ord(s[i])] += 1
ans = ""
for i in range(len(charset) - 1, -1, -1):
count = 0
while charset[i] > 0:
ans += chr(i)
charset[i] -= 1
count += 1
if charset[i] > 0 and count == limit:
next = nextAvailableChar(charset, i)
if not next:
return ans
ans += next
count = 0
return ans
```
### Merge two sorted list
```python
class Solution:
def mergeTwoLists(self, l1: ListNode, l2: ListNode) -> ListNode:
dummy = ListNode(0)
curr = dummy
while l1 and l2:
if l1.val > l2.val:
l1, l2 = l2, l1
curr.next = l1
l1 = curr.next.next
curr = curr.next
curr.next = l1 or l2
return dummy.next
```
### subtree of another tree
```python
class Solution:
def isSubtree(self, s: TreeNode, t: TreeNode) -> bool:
if not s and not t: return True
if not s or not t: return False
return self.sameTree(s, t) or self.isSubtree(s.left, t) or self.isSubtree(s.right, t)
def sameTree(self, s, t):
if not s and not t : return True
if not s or not t: return False
return s.val == t.val and self.sameTree(s.left, t.left) and self.sameTree(s.right, t.right)
```
### Maximal Square
```python
class Solution:
def maximalSquare(self, matrix: List[List[str]]) -> int:
if len(matrix) == 0: return 0
m, n = len(matrix), len(matrix[0])
dp = [[0] * (n+1) for _ in range(m+1)]
dp[1][1] = 1
for i in range(1, m+1):
for j in range(1, n+1):
if matrix[i-1][j-1] == "1":
dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1
else:
dp[i][j] = 0
return max(map(max, dp)) ** 2
```
### throttling gateway
```python
import collections
def droppedRequests(requestTime):
# Write your code here
Q1 = []
Q20 = []
Q60 = []
count = 0
for v in requestTime:
while len(Q1) > 0 and v - Q1[0] >= 1:
Q1.pop(0)
while len(Q20) > 0 and v - Q20[0] >= 10:
Q20.pop(0)
while len(Q60) > 0 and v - Q60[0] >= 60:
Q60.pop(0)
drop = 0
if len(Q1) < 3:
Q1.append(v)
else:
drop = 1
if len(Q1) > 0:
Q1.pop(0)
Q1.append(v)
if len(Q20) < 20:
Q20.append(v)
else:
drop = 1
if len(Q20) > 0:
Q20.pop(0)
Q20.append(v)
if len(Q60) < 60:
Q60.append(v)
else:
drop = 1
if len(Q60) > 0:
Q60.pop(0)
Q60.append(v)
count += drop
# print(Q1, Q20, Q60)
return count
```
### Unique Device Name
```python
import collections
def getUniqueNames(num, devices):
seen = collections.Counter()
for i in range(len(devices)):
name = devices[i]
if devices[i] in seen:
name = devices[i] + str(seen[devices[i]])
seen[devices[i]] += 1
devices[i] = name
return devices
```
### Slow key press
```python
class Solution:
def slowestKey(self, releaseTimes: List[int], keysPressed: str) -> str:
maximum, ans = releaseTimes[0], keysPressed[0]
for i in range(1, len(releaseTimes)):
diff = releaseTimes[i] - releaseTimes[i-1]
word = keysPressed[i]
if diff > maximum:
maximum, ans = diff, word
elif diff == maximum and word > ans:
ans = word
return ans
```
### Unique pairs
```python
def uniqueTwoSum(nums, target):
ans = set()
for n in nums:
c = target-n
if c in nums and c >= n:
ans.add((n, c))
return len(ans)
```
### Amazon music pair
```python
class Solution:
def numPairsDivisibleBy60(self, time: List[int]) -> int:
cache = [0] * 60
ans = 0
for t in time:
ans += cache[t%60]
cache[-t%60] += 1
return ans
```
Sign in with Wallet
Connect another wallet