# RN x LULU
## 494. Target Sum
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
Example 1:
Input: nums = [1,1,1,1,1], target = 3
Output: 5
Explanation: There are 5 ways to assign symbols to make the sum of nums be target 3.
-1 + 1 + 1 + 1 + 1 = 3
+1 - 1 + 1 + 1 + 1 = 3
+1 + 1 - 1 + 1 + 1 = 3
+1 + 1 + 1 - 1 + 1 = 3
+1 + 1 + 1 + 1 - 1 = 3
Example 2:
Input: nums = [1], target = 1
Output: 1
if target not reachable return 0
Sol1. backtracking
all_sum = sum(nums)
back-tracking -> pick idx as neg -> all_sum -= 2 * num
if all_sum < target -> skip
if all_sum = target -> res += 1
if all_sum > target -> dfs next idx
```python
def get_all_combinations(nums, target):
all_sum = sum(nums) # target
res = [0]
visited = set()
def dfs(idx, all_sum, bismask):
if all_sum < target or idx >= len(nums):
return
if all_sum == target and bismask not in visited:
res[0] += 1
visited.add(bismask)
# treat idx as neg
dfs(idx + 1, all_sum - 2* nums[idx], bismask | (1<<idx))
# treat idx as positive
dfs(idx + 1, all_sum, bismask)
dfs(0, all_sum, 0)
return res[0]
# time: O(2 ** N) # len(num)
# space: O(2 ** N)
```
```python
def target_sum(nums, target):
def dfs(index, remain):
if (index, remain) in dp:
return dp[(index, remain)]
if index == len(nums) :
if remain != 0:
return 0
else:
return 1
ways = 0
# select +1
ways += dfs(index + 1, remain - nums[index])
# select -1
ways += dfs(index + 1, remain + nums[index])
dp[(index, remain)] = ways
return ways
return dfs(0, target)
```
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.
Example 1:
Input: nums = [1,2,3,4]
Output: false
Explanation: There is no 132 pattern in the sequence.
Example 2:
Input: nums = [3,1,4,2]
Output: true
Explanation: There is a 132 pattern in the sequence: [1, 4, 2].
Example 3:
Input: nums = [-1,3,2,0]
Output: true
Explanation: There are three 132 patterns in the sequence: [-1, 3, 2], [-1, 3, 0] and [-1, 2, 0].
i < j < k
nums[i] < nums[k] < nums[j]
for x :
find prev_larger y, smallest before y as z
x > z
y > x, comapre x > z ? => z < x < y
monotone decresing
[3,1,4,2]
[3]
[3, 1]
[4]
[4, 2], 2 : 4 is pre_larger 2, min before 4 is 1
becasue 2 > 1 => 132 pattern
[4, 3, 1,2]
[(6, _), (5, _)] <- pop increase upper bound lower bound
```python
def find_pattern(nums):
if len(nums) <= 2:
return Fasle
if nums[1] > nums[2]:
stack = [(nums[1], nums[0])] # monotone decreasing stack
else :
stack = []
min_before = min(nums[1], nums[0])
for num in nums[2:] :
while not stack and num >= stack[-1]:
tmp = stack.pop()
if stack and num > stack[-1][1]:
return True
stack.append((num, min_before))
min_before = min(min_before, num)
return False
```
## 334. Increasing Triplet Subsequence
1 <= nums.length <= 5 * 105
-2^31 <= nums[i] <= 2^31 - 1
Example 1:
Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.
Example 2:
Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.
Example 3:
Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.
[2,1,5,0,4,6]
[6] (5, 1)
[(2, 0)]
[(2, 0), (1, 0)]
[(5, 1)]
[(5, 1), (0, 0)]
[(5, 1), (4, 1)]
[(6, 2)] (5, 1), (4, 1)
^ = max(poped_item_count) + 1
val >= 2 -> 123 pattern exits
[54321]
[1523] -> can't
- sol1, 3N
[1523]
[1, 1, 1, 1] # from start min val
[5, 5, 3, 3] # from end max val
[1, 5, 2, 3]
^
- sol2, one pass, segment tree nlog n xxx
[1, 5, 2, 3]
^
? element <= 3
- sol3
[1, 5, 2, 3]
main a minimum queue with size two
[1, 5]
^
[1, 2]
-> true
```python
from heapq import heappush, heappop
def check_ott_pattern(nums):
min_queue = []
for i in nums:
if not min_queue:
min_queue.append(i)
else:
min_queue.append(min(min_queue[-1], i))
max_queue = []
for i in nums[::-1]:
if not max_queue:
max_queue.append(i)
else:
max_queue.append(max(max_queue[-1], i))
for i, min_, max_ in zip(nums, min_queue, max_queue[::-1]):
if i > min_ and i < max_:
return True
return False
```
https://leetcode.cn/problems/increasing-triplet-subsequence/solution/c-xian-xing-shi-jian-fu-za-du-xiang-xi-jie-xi-da-b/
```python=
def increasingTriplet(self, nums: List[int]) -> bool:
if len(nums) <= 2:
return False
small = nums[0]
mid = float("inf")
for num in nums[1:]:
if num > mid :
#print("{}, {}, {}".format(small, mid, num))
return True
elif num > small : # small < num <= mid
mid = num
elif num <= small: # num <= small
small = num
return False
```
fine LCA of start node & dest node
find path of LCA to start & dest node
result 1 = reverse (LCA to start)
result 2 = LCA to dest node
result = result_1 + result_2
if LCA == start => result_2
if LCA == dest => result_1
```python
def find_step(root, startValue, destValue):
def findLCA(root, p, q):
if root is None :
return None
if p == root.val or q == root.val :
return root
left = self.findLCA(root.left, p, q)
right = self.findLCA(root.right, p, q)
if left is None and right is None:
return None
if left is None:
return right
if right is None:
return left
return root
lca = findLCA(root, startValue, destValue)
# find path of lca to startNode
def dfs(root, direction, target):
if root is None :
return
if root.val == target:
result[0] = cur_path.copy()
return
cur_path.append(direction)
dfs(root.left, "L")
dfs(root.right, "R")
cur_path.pop()
return
result_lca_to_start = []
cur_path = []
dfs(lca, None, startValue)
result_lca_to_end = []
cur_path = []
dfs(lca, None, endValue)
result_up = "U"*len(result_lca_to_start[1:])
result_down = "".join(result_lca_to_end[1:])
if lca.val == startValue:
return result_down
elif lca.val == destValue:
return result_up
else :
return result_down + result_up
```
Constraints:
1 <= s.length <= 100
s contains only digits and may contain leading zero(s).
sol1. backtracking
226
^
^
res +=1
< O(2 ** N)
sol2. dp + backtracking
f(22665555) = f(22) * f(66) * f(55) * f(55)
^
f(123412341234) = f(1) * f(23412341234) + f(12) * (3412341234)
f(23412341234) = f(2) * f(3412341234) <-
f(idx) = f(idx + 1) + f(idx + 2)
f(idx+1) = f(idx + 2) + f(idx + 3)
f(idx+2) = f(idx + 3) + f(idx + 4)
N len of string
time: O(N)
space: O(N)
```python
def decodeways(s):
valid_strings = set(str(i) for i in range(10, 27))
@cache
def f(idx):
if s[idx] == 0:
return 0
else:
if idx + 1 < len(s):
res = f(idx+1)
else:
res = 1
if idx + 2 < len(s) and s[idx:idx+2] in valid_strings:
res += f(idx+2)
return res
return f(0)
```
## 2007. Find Original Array From Doubled Array
An integer array original is transformed into a doubled array changed by appending twice the value of every element in original, and then randomly shuffling the resulting array.
Given an array changed, return original if changed is a doubled array. If changed is not a doubled array, return an empty array. The elements in original may be returned in any order.
Example 1:
Input: changed = [1,3,4,2,6,8]
Output: [1,3,4]
Explanation: One possible original array could be [1,3,4]:
- Twice the value of 1 is 1 * 2 = 2.
- Twice the value of 3 is 3 * 2 = 6.
- Twice the value of 4 is 4 * 2 = 8.
Other original arrays could be [4,3,1] or [3,1,4].
Example 2:
Input: changed = [6,3,0,1]
Output: []
Explanation: changed is not a doubled array.
Example 3:
Input: changed = [1]
Output: []
Explanation: changed is not a doubled array.
x = [a, b, c]
-> intput [b, a, 2*a, 2*b, 2*c, c]
-> output original x
[1,1,1,2,2,2]
[1,3,4,2,6,8]
sol :
result = []
trace 1st ; put in set
trace 2nd ;
[6,2,2,1,1,3]
result = [1,1,3]
sol1:
sort ; increasing;
[1,1,2,2,2,2,3,6]
[4,4, 2, 2]
result = []
[1,1,3]
dict = {1 : 2 }
time : o(nlogn)
space : o(n)
```python
def find_ori(nums):
if len(nums) % 2 :
return []
counter = collections.Counter(nums)
# {1 : 2, 2 : 3, 4 : 1}
unique_values = list(counter.keys())
unique_values.sort()
result = []
for key in unique_values:
count = counter[key]
result = result + [key] * count
if key * 2 not in counter :
return []
counter[key * 2] -= count
if counter[key * 2] < 0 :
return False
return result
Counter(nums)
# 1, 1, 2, 2, 2
# [1,1,2]
# 1:2, 2:3, 4:0
# 2:1 4:0
nums.sort()
count = {}
result = []
for num in nums:
if num not in count :
result.append(num)
count[num] += 1
if num % 2 :
if num not in count :
count[num] = 1
else:
count[num] += 1
result.append(num)
else:
half = num // 2
if half not in count :
result.append(num)
count[half] += 1
else:
```
2,2,4,4,6,12
## 802. Find Eventual Safe States
802. Find Eventual Safe States
A node is a terminal node if there are no outgoing edges. A node is a safe node if every possible path starting from that node leads to a terminal node (or another safe node).
Return an array containing all the safe nodes of the graph. The answer should be sorted in ascending order.
f(0) = f(1) & f(2)
f(1) = f(2) & f(3)
f(2) = f(5)
f
- with circle -> False
- all(f(path) for path in paths)
f(0) -> return f(1) & f(2)
```python
def eventualSafeNodes(self, paths: List[List[int]]) -> List[int]:
visited = set()
dp = {}
for idx, path in enumerate(paths):
if not path:
dp[idx] = True
def check_safe(node, visited):
if node in dp:
return dp[node]
for path in paths[node]:
if visited & 1 << path or not check_safe(path, visited | 1 << path):
dp[node] = False
dp[path] = False
return False
dp[node] = True
return True
res = []
for i in range(len(paths)):
visited = 0
if check_safe(i, visited << i):
res.append(i)
return res
```
1 -> < i + 3
[1,0, 0, 0, 999]
[1,0, 0, 0, 999]
^ ^
1 1 1
[1, 2, 5]
[3, 2, 1]
0 +1
3 -1
1 +2
3 -2
2 +5
3 -1
(0, +1), (1, +2), (2, +5), (3, -1), (3, -3), (3, -1)
max apples
day 0 : (0, 1) -> eat -> (0, 0)
day 1 : (1, 2) -> eat -> (1, 1)
day 2 : (2, 7) -> eat
[6,4]
[2,2]
day 0 : (0, 6) -> eat -> (0, 5)
day 1 : (0, 9) -> eat -> (0, 8)
day 2 : ()
[6, 4]
[2, 2]
[(2, 6), (3, 4)]
0 -> eat smallest
[(2, 5), (3, 4)]
1 -> eat smallest
[(2, 4), (3, 4)]
2 ->eat smallest
[(3, 3)]
3 -> xx
[1, 2, 5] appls
[3, 3, 4] days
every day 1
[4]
[3]
(3, 1)
(2, 2)
(1, 5)
sortedDict logn ->
for i in sorted_dict:
pass
## 337. House Robber III
5
/
1
/
2
/
7
val2 = f(root, should_skip=True)
= f(root.left, should_skip=False) + f(root.right, should_skip=False)
val1 = f(root, should_skip=False)
= max(f(root.left, should_skip=False) + f(root.right, should_skip=False)
, root.val + f(root.left, should_skip=True) + f(root.right, should_skip=True) )
return f(root, should_skip=False)
```python
def get_score(root, should_skip):
if root is None:
return 0
if should_skip:
if hasattr(root, 'skip_val'):
return root.skip_val
res = get_score(root.left, should_skip=False) + f(root.right, should_skip=False)
root.skip_val = res
return root.skip_val
else:
if hasattr(root, 'not_skip_val'):
return root.not_skip_val
val1 = get_score(root.left, should_skip=False) + f(root.right, should_skip=False)
val2 = root.val + get_score(root.left, should_skip=True) + f(root.right, should_skip=True)
root.not_skip_val = max(val1, val2)
return max(val1, val2)
return get_score(root, should_skip=False)
```
score('abc') = count_start('a') + count_start('ab') + count_start('abc')
Input: words = ["abc","ab","bc","b"]
Output: [5,4,3,2]
score('abc') = count_start('a') +
count_start('ab') +
count_start('abc')
sol :-1:
```python
def count_appearence(words):
counter = collections.defaultdict(int)
for word in words:
for i in len(word):
sub_word = word[:(i+1)]
counter[sub_word] += 1
momo = {}
result = []
for word in words:
if word in memo :
result.append(momo[word])
else:
score_word = 0
for i in len(word):
score += counter[word[:(i+1)]]
momo[word] = score
result.append(score)
return result
memo = {}
result = []
for word in words:
if word in memo:
memo[word]
for i in len(word):
score('abc') = count_start('a') +
count_start('ab') +
count_start('abc')
memo[word] = socre
n * s (max length of word)
```
## 1268. Search Suggestions System
Example 1:
Input:
products = ["mobile","mouse","moneypot","monitor","mousepad"], searchWord = "mouse"
Output:
[["mobile","moneypot","monitor"],
["mobile","moneypot","monitor"],
["mouse","mousepad"],
["mouse","mousepad"],
["mouse","mousepad"]]
Explanation: products sorted lexicographically = ["mobile","moneypot","monitor","mouse","mousepad"].
After typing m and mo all products match and we show user ["mobile","moneypot","monitor"].
After typing mou, mous and mouse the system suggests ["mouse","mousepad"].
Example 2:
Input:
products = ["havana"],
searchWord = "havana"
Output:
[["havana"],["havana"],["havana"],["havana"],["havana"],["havana"]]
Explanation: The only word "havana" will be always suggested while typing the search word.
m -> [m, m, m]
mou -> [mo, mo, mo]
mouse -> [mouse ... ]
m -> products -> O(n)
mo -> products -> O(2n)
mouse -> proudcts -> O(kn) n (k) * (k+1)
Trie
m -> {'recomends': []}
len(searchWord) = k
n * k * logn
k
```python
root = {'m': {
'o': {
l:{
'recs': ["mobile"]
}
'recs': ["mobile"]
},
'recs': ["mobile"]}
}
```
```python
class Trie():
def __init__(self, root):
self.root = {}
def insert(self, word):
root = self.root
for s in word:
if s not in root:
root[s] = {}
root = root[s]
```
```python!
from heapq import heappushpop
class Trie():
def __init__(self, root, k):
self.root = {}
self.k = k
def insert(self, word):
root = self.root
for s in word[:self.k]:
if s not in root:
root[s] = {}
if len(root[s]['recs']) >= 3:
heappushpop(root[s]['recs'], word)
root = root[s]
def lookup(self, word):
root = self.root
for s in word:
if s in root:
root = root[s]
else:
return []
return root['recs']
trie = Trie()
for word in words:
trie.insert(word)
res = []
stop = False
for k in range(len(search_word)):
out = trie.lookup(k)
if out and not stop:
res.append(out)
else:
stop = True
res.append([])
return res
```
```python
def suggestedProducts(self, products: List[str], searchWord: str) -> List[List[str]]:
res = []
products.sort()
print(products)
l, r = 0, len(products) - 1
for i in range(len(searchWord)):
c = searchWord[i]
# 當 i = 2 時(index= 0, 1, 2), 表示product字長至少要 3個字, 少於等於兩個字都刪除
while l <= r and (len(products[l]) <= i or products[l][i] != c):
l += 1
while l <= r and (len(products[r]) <= i or products[r][i] != c):
r -= 1
res.append([])
remain = r - l + 1
for j in range(min(3, remain)):
res[-1].append(products[l + j])
return res
```
```python!
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, val=0, left=None, right=None):
# self.val = val
# self.left = left
# self.right = right
def insert_node(root, val);
def dfs(root):
if root is None:
return TreeNode(val)
if val > root.val:
root.right = dfs(root.right)
else :
root.left = dfs(root.left)
return root
return dfs(root)
```
## 1110. Delete Nodes And Return Forest
Given the root of a binary tree, each node in the tree has a distinct value.
After deleting all nodes with a value in to_delete, we are left with a forest (a disjoint union of trees).
Return the roots of the trees in the remaining forest. You may return the result in any order.
```python
def del_values(root, to_delete):
res = []
dele = set(to_delete)
if not dele:
return root
def dfs(root):
if not root:
return None
if (root.val in dele):
node = dfs(root.left)
if node is not None:
res.append(node)
node = dfs(root.right)
if node is not None:
res.append(node)
root.left = None
root.right = None
return None
else:
dfs(root.left)
dfs(root.right)
return root
dfs(root)
if root.val not in dele:
res.append(root)
retrun res
```e
## 809
Input: s = "heeellooo", words = ["hello", "hi", "helo"]
Output: 1
Explanation:
We can extend "e" and "o" in the word "hello" to get "heeellooo".
We can't extend "helo" to get "heeellooo" because the group "ll" is not size 3 or more.
s = "heeellooo",
words = ["hello", "hi", "helo"]
s => [(h:1), (e:3), (l : 2), (o:3)] => stack
"hello" => [(h:1), (e:1), (l: 2), (o:1)] => stack
compare same index
if char are diff => return False
if diff_count == 1=> return Fasle
return True
```python=
def check_extend(s, words):
def char_count(s):
stack = []
for c in s :
if not stack :
stack.append([c, 1])
else:
if stack[-1][0] == c:
stack[-1][1] += 1
else:
stack.append([c, 1])
return stack
result = 0
stack_s = char_count(s)
for word in words:
stack_word = char_count(word)
if len(stack_s) != len(stack_word):
continue
flag = True
for i in range(len(stack_s)):
if stack_s[i][0] != stack_word[i][0] or \
stack_s[i][1] - stack_word[i][1] == 1:
flag = False
break
if not flag:
continue
result += 1
return result
```
counter(word) =>
1. different chars
2.
heeellooo
hello
eeee
eee
count() - count() == 1 => (x)
eeeeeeeeee
e
s => [(h:1), (e:3), (l : 2), (o:3)]
"hello" => [(h:1), (e:1), (l: 2), (o:1)]
e = 5
e = 2
eeeee
ee---
eeeee => e : 5
eee => e : 3
s = "ooo"
word = "oo"
## 1834. Single-Threaded CPU
Example 1:
Input: tasks = [[1,2],[2,4],[3,2],[4,1]]
Output: [0,2,3,1]
Explanation: The events go as follows:
- At time = 1, task 0 is available to process. Available tasks = {0}.
- Also at time = 1, the idle CPU starts processing task 0. Available tasks = {}.
- At time = 2, task 1 is available to process. Available tasks = {1}.
- At time = 3, task 2 is available to process. Available tasks = {1, 2}.
- Also at time = 3, the CPU finishes task 0 and starts processing task 2 as it is the shortest. Available tasks = {1}.
- At time = 4, task 3 is available to process. Available tasks = {1, 3}.
- At time = 5, the CPU finishes task 2 and starts processing task 3 as it is the shortest. Available tasks = {1}.
- At time = 6, the CPU finishes task 3 and starts processing task 1. Available tasks = {}.
- At time = 10, the CPU finishes task 1 and becomes idle.
Example 2:
Input: tasks = [[7,10],[7,12],[7,5],[7,4],[7,2]]
Output: [4,3,2,0,1]
Explanation: The events go as follows:
- At time = 7, all the tasks become available. Available tasks = {0,1,2,3,4}.
- Also at time = 7, the idle CPU starts processing task 4. Available tasks = {0,1,2,3}.
- At time = 9, the CPU finishes task 4 and starts processing task 3. Available tasks = {0,1,2}.
- At time = 13, the CPU finishes task 3 and starts processing task 2. Available tasks = {0,1}.
- At time = 18, the CPU finishes task 2 and starts processing task 0. Available tasks = {1}.
- At time = 28, the CPU finishes task 0 and starts processing task 1. Available tasks = {}.
- At time = 40, the CPU finishes task 1 and becomes idle.
sol1
priority queue
[(1,2), (2, 4), (3, 2) , ..]
1 + 2 -> 3
while queue[0][1] <= current_time
-> pop, .... pick minimum nlog
-> push back others nlog
n^2 * logn
sol2
[(1,2), (2, 4), (3, 2) , ..]
^
available_queue = []
while queue[0][1] <= current_time:
-> push back available_queue
if not available_queue:
jump to next idx
elif available_queue[0] >= current_time and idx the end:
jump to next idx
else:
O(nlogn)
O(n)
```python!
import heapq import heappush, heappop
from collections import dequeue
def get_the_execute_order(tasks):
tasks = dequeue(sorted(((start, end), idx) for idx, (start, end) in enumerate(tasks)))
current_time = -float(inf)
available_queue = []
res = []
while tasks or available_queue:
if tasks and tasks[0][1] <= current_time:
idx, (start, period) = tasks.popleft()
heappush(available_queue, (period, idx))
elif available_queue:
period, idx = heappop(available_queue)
current_time += period
res.append(idx)
else:
idx, (start, period) = tasks.popleft()
current_time = start + period
res.append(idx)
return res
```
```python=
def getOrder(self, tasks: List[List[int]]) -> List[int]:
for i, t in enumerate(tasks):
t.append(i)
tasks.sort(key = lambda t : t[0])
#print('tasks : {}'.format(tasks))
minheap = []
i = 0
cur_time = 0
result = []
# minheap 裡面有東西 或 所有課程都還沒放入heap中時都要繼續看
while minheap or i < len(tasks):
#print(minheap)
# minheap 裡面沒東西, 直接拉快時間到第一個可以處理的時間
if not minheap :
# 有時候, heap之前有東西, 剛被pop出來處理完,
# cur time反而比當前第一個task可進入queue的時間大(可能前依task處理太久)
# 所以需要兩著取最大值
cur_time = max(cur_time, tasks[i][0])
# 把目前可以處理的任務加入;
# 多加上 i < len(task) 確保後面index不會出問題
# 如果已經都加入 heap過那就不用再加了
while i < len(tasks) and cur_time >= tasks[i][0]:
heapq.heappush(minheap, [tasks[i][1], tasks[i][2]])
i += 1
process_time, index = heapq.heappop(minheap)
cur_time += process_time
result.append(index)
return result
```
## 1310 RN
Input: arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
Output: [2,7,14,8]
Explanation:
The binary representation of the elements in the array are:
1 = 0001
3 = 0011
4 = 0100
8 = 1000
The XOR values for queries are:
[0,1] = 1 xor 3 = 2
[1,2] = 3 xor 4 = 7
[0,3] = 1 xor 3 xor 4 xor 8 = 14
[3,3] = 8
xor => 1, 1 => 0
1, 0 => 1
0, 1 => 1
0, 0 => 0
[0, 3] =>
1, 3, 4, 8
[0, 1] = > 2
0 xor 1
3, 4, 8
1 xor 3 xor 4 xor 8
range [i, j] = (0 xor ... xor j) xor (0 xor 1 xor .. xor (i -1))
dict = {index : xor(0~index)}
range [i, j] = dict[j] xor dict[i-1]
```python=
def xor_query(arr, queries):
map_index_xorsum = {}
xor_sum = 0
for i, num in enumerate(arr):
xor_sum ^= num
map_index_xorsum[i] = xor_sum
result = []
for query in queries
if query[0] == 0:
result.append(map_index_xorsum[query[1]])
else:
result.append(map_index_xorsum[query[1]] ^ map_index_xorsum[query[0]-1])
return result
```
## 698. Partition to K Equal Sum Subsets
Given an integer array nums and an integer k, return true if it is possible to divide this array into k non-empty subsets whose sums are all equal.
Example 1:
Input: nums = [4,3,2,3,5,2,1], k = 4
Output: true
Explanation: It is possible to divide it into 4 subsets (5), (1, 4), (2,3), (2,3) with equal sums.
Example 2:
Input: nums = [1,2,3,4], k = 3
Output: false
Constraints:
1 <= k <= nums.length <= 16
1 <= nums[i] <= 104
The frequency of each element is in the range [1, 4].
num_sum = sum([4,3,2,3,5,2,1])
num_sum % k != 0 -> false
elemnts = num_sum / k
k -> len(partitions) = k
nums= sorted(nums, reverse=True)
def dp(partitions, idx):
pass
(0, 0, 0, 0), 0
(4, 0, 0, 0), 1
4,3,2,3,5
(4, 5, 5, 3), 5
limit -> each partition <= 5 -> put elements
stop -> (x, x, x, x) == x
O(K ** N)
N * 2 ** N
```python!
num_sum = sum(nums)
if num_sum % k != 0:
return False
else:
goal = num_sum // k
if max(num_sum) > goal:
return False
@cache
def dfs(partitions, idx):
if all(j == goal for j in partitions):
return True
if idx >= len(nums):
return False
next_ = list(partitions)
for i in range(k):
if next_[i] + nums[idx] <= goal:
next_[i] += nums[idx]
next_ = tuple(sorted(next_))
if dfs(next_, idx+1):
return True
next_[i] -= nums[k]
return False
return dfs(tuple([0] * k), 0)
```
https://leetcode.cn/problems/partition-to-k-equal-sum-subsets/solution/hua-fen-wei-kge-xiang-deng-de-zi-ji-by-l-v66o/
(k ** N) * (klogk + N)
## RN 2178
2 + 4 + 6 + ... + ? <= final_sum
final_sum = 1000
2 + 4 + .. + k-2 + k = 996
4 / 2 = 2 =>
k => k+2
k-2 => k
ex : final_sum = 16
2 + 4 + 6 = 12
2 + 4 + 10 = 16
2 + 4 + ... + 2k <= finalSum
(2 + 2k) * (k) / 2 = (1+k) * k <= finalSum
find max k
binay search =>
l = 1
r = finalSum
```python=
def max_split_even(finalSum):
if finalSum % 2 : return []
def get_sum(k):
return (1+k) * k
# find max k
l = 1
r = finalSum
max_k = l
while l <= r :
mid = (l + r) // 2
if get_sum(mid) <= finalSum:
max_k = max(max_k, mid)
l = mid + 1
else :
r = mid - 1
# 2 + 4 + ... + 2k <= finalSum
result = [2*x for x in range(1, mak_k+1)]
diff = finalSum - sum(result)
result[-1] += diff
return result
```
##
Constraints:
n == grid.length
n == grid[i].length
1 <= n <= 50
0 <= grid[i][j] < n2
Each value grid[i][j] is unique.
dp[i, j] = min(dp[i + i_diff, j + j_diff] for i_diff, j_diff in 4 direction)
bfs
dp[i, j] = min(dp[i, j], current_time)
dij
bfs -> (v, i, j)
nearest path to (i, j) until visit (n-1, n-1)
n * n * 3
- > 4 step
n ** 2 * 3 <-
(0, 0) -> (1, 1), (0, 2), (1,1) -> ()
```python
from heapq import heappush, heappop
# until meet n-1, n-1 -> return current_max
def get_max_wait_time(grids):
init_value = grids[0][0]
queue = [(grids[0][0], 0, 0)]
n = len(grids)
visited = set()
def bfs():
curren_max = None
while queue:
current_val, i, j = heappop(queue)
if curren_max is None or current_val > curren_max:
curren_max = current_val
if i == n-1 and j == n-1:
return current_max - init_value
for i_diff, j_diff in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
i_next = i + i_diff
j_next = j + j_diff
if i_next >= n or i_next < 0:
continue
if j_next >= n or j_next < 0:
continue
if i_next, j_next not in visited:
heappush((grids[i_next][j_next], i_next, j_next), queue)
visited.add((i_next, j_next))
return bfs()
```
## 990 RN
a==b
{a : [b, 1]}
{b : [a, 1]}
{b : [a, 0]}
{a : [b, 0]}
a != c
{c : }
{a : [c, 0]}
c == a
a == b => {a : [set(b), set(),
b : [set(a), set(),}
b != a =>
{a : [set(b), set(),
b : [set(a), set(),}
{a : [set(b), set(),
b : [set(a), set(),}
a == b
c == a
c != b
{a : [set(b, c), set(),
b : [set(a), set(),
c : [set(a), set(),}
== => x, y is same => y par is x
== => x, z is same => z par is x
y. z is same ? => union(y, z) is true.
same_set = set()
for equa in equalation:
if union(x, y) :
same_set.add(x)
same_set.add(y)
def find_par():
return
def union(v1, v2):
union(a, b)
set(a, b, c)
time :o(n)
space o()
{a : [set(), set()]}
1
https://leetcode.com/contest/weekly-contest-312/problems/number-of-good-paths/
## 713. Subarray Product Less Than K
Given an array of integers nums and an integer k, return the number of contiguous subarrays where the product of all the elements in the subarray is strictly less than k.
Example 1:
Input: nums = [10,5,2,6], k = 100
Output: 8
Explanation: The 8 subarrays that have product less than 100 are:
[10], [5], [2], [6], [10, 5], [5, 2], [2, 6], [5, 2, 6]
Note that [10, 5, 2] is not included as the product of 100 is not strictly less than k.
Example 2:
Input: nums = [1,2,3], k = 0
Output: 0
Constraints:
1 <= nums.length <= 3 * 10^4
1 <= nums[i] <= 1000
0 <= k <= 10^6
[10,5,2,6], k = 100
^ ^
l r
l r
l-r
each l -> find first r such that prod() < 100
n^2
[10, 5, 2, 6]
queue = [],
[10, 5] -> 10, [10, 5] res += 2
^
[5, 2, 6], 5, [5,2] [526], 2, [26], 6 res+= 6
^
if current >= k:
res += len(queue)
queue.pop(0)
if right == len(n) - 1:
res += (n * n+ 1) / 2
return res
```python
def get_valid_subarrays(nums, k):
if k <= 1:
return 0
queue = []
current_val = 1
left = 0
res = 0
for right, num in enumerate(nums):
queue.append(num)
# current_val *= num
# [10, 5, 2]
# 0 1 2
if current_val * num >= k:
res += (right - left)
current_val *= num
while current_val >= k:
out = queue.pop(0)
current_val /= out
left += 1
n_ = len(queue)
res += n_ * (n_ + 1) / 2
return res
[10, 5, 2, 6]
left, right, queue, current_val, res
0 , 0 , 10, 10
0 , 1 , 10-5, 50
0 , 2, , 10-5-2, 100, 2
1 , 2, , 5-2, 10, 2
1 , 3, , 5-2-6, 60, 2
2 + 3 * 4 / 2 = 8
```
https://leetcode.cn/problems/subarray-product-less-than-k/solution/by-programmercoding-hqm4/
## 1395 RN
Example 1:
Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1).
[2,5,3,4,1] => [2,3,4]
123 pattern =>
smaller <= 5 => larger; exist => count : count(smaller) * cont(larger)
larger
[2,5,3,4,1] => count of larget at right =>
=> count of larget at left =>
=> count of larget at right
```python=
def count_pattern(nums):
'''
# count larger at right
larger_right = []
for i in range(len(nums)):
count = 0
for j in range(i+1, len(nums)):
if nums[j] > nums[i]:
count +=1
larger_left.append(count)
# count smaller at left
smaller_left = []
for i in range(len(nums)):
count = 0
for j in range(i-1):
if nums[j] < nums[i]:
count += 1
smaller_left.append(count)
'''
def count_fun(direction, compare):
result = []
for i in range(len(nums)):
count = 0
if compare == "larger":
for j in range(i+1, len(nums)):
if direction == "right"
if nums[j] > nums[i]:
count +=1
else:
if nums[j] < nums[i]:
count += 1
elif compare == "smaller":
if direction == "right"
if nums[j] > nums[i]:
count +=1
else:
if nums[j] < nums[i]:
count += 1
result.append(count)
return result
larger_right = count_fun("right", "larger")
larger_left = count_fun("left", "larger")
smaller_right = count_fun("right", "smaller")
smaller_left = count_fun("left", "smaller")
result = 0
for i in range(1, len(nums)-1) :
result += (larger_right[i] * smaller_left[i] + larger_left[i] * smaller_right[i])
return result
```
## google
1,2,3,2,1,1, k = 1
^
O(n)
```python
def get_len(nums, k):
max_len = 0
res = 0
for num in nums:
if num != k:
res = 0
else:
res += 1
max_len = max(max_len, res)
return max_len
```
k = 1
num, res, max_len,
1, 1, 1
2, 0, 1,
3, 0, 1,
2, 0, 1
1, 1, 1,
1, 2, 2
return max_len -> 2
1,2,3,2,1,1, every_likes
valid_nums <- [k1, k2, ... kn]
```python
def get_len(nums, every_likes):
prev = None
res = defaultdict(int)
valid_nums = set(every_likes)
# 1| 2|3|2|1,1| 2,2| 3
# ^
for num in nums:
if prev is None or num != prev:
current_len = 1
prev = num
else:
current_len += 1
if num in valid_nums:
res[num] = max(res[num], current_len)
return [res[i] for i in every_likes]
```
1,2,3,2,1,1
every_like = [1,2,3,4]
prev = None
res = {}
num, current_len, prev, res
1, 1, 1, {1: 1}
2, 1, 2, {1:1, 2:1},
3, 1, 3, {1:1, 2:1, 3:1},
2, 1, 2, {1:1, 2:1, 3:1},
1, 1, 1, {1:1, 2:1, 3:1},
1, 2, 1, {1:2, 2:1, 3:1},
{1:2, 2:1, 3:1}
return [2, 1, 1, 0]
Sign in with Wallet
Connect another wallet