Recently, I haven't been solving problems for a long time due to illness. This morning, I started a Leetcode weekly contest and decided to write a solution. I was in decent shape this morning. By the way, I will participate in the weekly contests every week and strive to write solutions.
Leetcode 1341. The K Weakest Rows in a Matrix#
Description:
Given a m * n matrix mat of ones (representing soldiers) and zeros (representing civilians), return the indexes of the k weakest rows in the matrix ordered from the weakest to the strongest.
A row i is weaker than row j, if the number of soldiers in row i is less than the number of soldiers in row j, or they have the same number of soldiers but i is less than j. Soldiers are always stand in the frontier of a row, that is, always ones may appear first and then zeros.
Example 1:
Input: mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
Output: [2,0,3]
Explanation:
The number of soldiers for each row is:
row 0 -> 2
row 1 -> 4
row 2 -> 1
row 3 -> 2
row 4 -> 5
Rows ordered from the weakest to the strongest are [2,0,3,1,4]
The problem is quite simple; in fact, this problem is about binary processing, and in Python, brute force works wonders.
from typing import List
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
if not mat:
return []
number = []
for i in range(len(mat)):
number.append((int("".join([str(x) for x in mat[i]]), 2), i))
number.sort()
return [x for _, x in number[0:k]]
1342. Reduce Array Size to The Half#
Description:
Given an array arr. You can choose a set of integers and remove all the occurrences of these integers in the array.
Return the minimum size of the set so that at least half of the integers of the array are removed.
Input: arr = [3,3,3,3,5,5,5,2,2,7]
Output: 2
Explanation: Choosing {3,7} will make the new array [5,5,5,2,2] which has size 5 (i.e equal to half of the size of the old array).
Possible sets of size 2 are {3,5},{3,2},{5,2}.
Choosing set {2,7} is not possible as it will make the new array [3,3,3,3,5,5,5] which has size greater than half of the size of the old array.
This problem is also quite simple. Given an array, choose a set of numbers to remove, such that the size of the remaining array is less than or equal to half of the original size. The goal is to find the minimum number of numbers to select to achieve this.
Using a hash table, the O(N) approach is as follows:
from typing import List
class Solution:
def minSetSize(self, arr: List[int]) -> int:
if not arr:
return 0
counter = {}
for i in arr:
counter[i] = counter.setdefault(i, 0) + 1
counter = {k: v for k, v in sorted(counter.items(), key=lambda item: item[1], reverse=True)}
total_count = 0
result_count = 0
for i, count in counter.items():
total_count += count
result_count += 1
if total_count >= len(arr) / 2:
break
return result_count
1343. Maximum Product of Splitted Binary Tree#
Description:
Given a binary tree root. Split the binary tree into two subtrees by removing 1 edge such that the product of the sums of the subtrees are maximized.
Since the answer may be too large, return it modulo 10^9 + 7.
Example 1:
Input: root = [1,2,3,4,5,6]
Output: 110
Explanation: Remove the red edge and get 2 binary trees with sum 11 and 10. Their product is 110 (11*10)
This problem is also quite simple. Given a binary tree with values, remove an edge to split it into two new binary trees, and find the maximum product of the sums of the two trees.
Initially, many people might be intimidated by this problem, but in reality, it is just a traversal of a binary tree. Regardless of whether it's pre-order, in-order, or post-order traversal, first traverse the binary tree to calculate the total sum of the node values, as well as the sum of the left subtree left_sum and the sum of the right subtree right_sum.
Then traverse again, result=max((total_sum-left_sum)*left_sum),(total_sum-right_sum)*right_sum),result) to find the solution.
class TreeNode:
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class Solution:
def maxProduct(self, root: TreeNode) -> int:
total_sum = self.sum_node(root)
result = 0
stack = []
node = root
while node or stack:
while node:
stack.append(node)
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
node = node.left
node = stack.pop()
node = node.right
if node:
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
return result % (10 ** 9 + 7)
def sum_node(self, root: TreeNode) -> int:
if not root:
return 0
left_sum = self.sum_node(root.left)
right_sum = self.sum_node(root.right)
root.left_sum = left_sum
root.right_sum = right_sum
return left_sum + right_sum + root.val
By the way, the type hinting in this code is somewhat problematic; I modified it after the competition.
from typing import Optional, Tuple, List
class TreeNode:
val: int
left: Optional["TreeNode"]
right: Optional["TreeNode"]
def __init__(self, x):
self.val = x
self.left = None
self.right = None
class TreeNodeWithSum:
val: int
left: Optional["TreeNodeWithSum"]
right: Optional["TreeNodeWithSum"]
left_sum: int
right_sum: int
def __init__(
self,
x: int,
left: Optional["TreeNodeWithSum"],
right: Optional["TreeNodeWithSum"],
left_sum: int,
right_sum: int,
):
self.val = x
self.left = left
self.right = right
self.left_sum = left_sum
self.right_sum = right_sum
class Solution:
def maxProduct(self, root: TreeNode) -> int:
total_sum,new_root = self.sum_node(root)
result = 0
stack:List[TreeNodeWithSum] = []
node = new_root
while node or stack:
while node:
stack.append(node)
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
node = node.left
node = stack.pop()
node = node.right
if node:
result = max(result, ((total_sum - node.right_sum) * node.right_sum))
result = max(result, ((total_sum - node.left_sum) * node.left_sum))
return result % (10 ** 9 + 7)
def sum_node(
self, root: Optional[TreeNode]
) -> Tuple[int, Optional[TreeNodeWithSum]]:
if not root:
return 0, None
left_sum, new_left_node = self.sum_node(root.left)
right_sum, new_right_node = self.sum_node(root.right)
return (
left_sum + right_sum + root.val,
TreeNodeWithSum(
root.val, new_left_node, new_right_node, left_sum, right_sum
),
)
By the way, this problem requires taking modulo 10^9+7 due to large data, and I forgot to take the modulo, resulting in two wrong answers and penalties. I really need to improve...
1344. Jump Game V#
Description:
Given an array of integers arr and an integer d. In one step you can jump from index i to index:
i + x where: i + x < arr.length and 0 < x <= d.
i - x where: i - x >= 0 and 0 < x <= d.
In addition, you can only jump from index i to index j if arr[i] > arr[j] and arr[i] > arr[k] for all indices k between i and j (More formally min(i, j) < k < max(i, j)).
You can choose any index of the array and start jumping. Return the maximum number of indices you can visit.
Notice that you cannot jump outside of the array at any time.
Input: arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
Output: 4
Explanation: You can start at index 10. You can jump 10 --> 8 --> 6 --> 7 as shown.
Note that if you start at index 6 you can only jump to index 7. You cannot jump to index 5 because 13 > 9. You cannot jump to index 4 because index 5 is between index 4 and 6 and 13 > 9.
Similarly, you cannot jump from index 3 to index 2 or index 1.
The problem states that you have an array with several values, and you can start jumping from any position. You can only jump one step at a time, and you need to satisfy certain conditions. Assuming you jump from index i, the conditions are:
-
i+x < arr.length and 0<x<=d
-
i-x >=0 and 0<x<=d
At the same time, if you jump from i to j, you need to ensure that arr[i]>arr[j] and every element between i and j satisfies arr[j]<x<arr[i]. The goal is to find the maximum number of elements you can jump.
Initially, I thought this problem was a two-headed DP problem, and I was too lazy to write it. However, later in the competition, I realized that this problem can actually be solved with a single DP because we can only jump from high to low. Therefore, we can sort the elements first and iterate through them. The formula can be derived as dp[i]=max(dp[i]+dp[j]+1) where j is the index value that can be reached from i. The complexity of the DP part is O(DN), but since sorting is required beforehand, the overall time complexity is O(logN+DN).
from typing import List
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
length = len(arr)
dp = [1] * length
for a, i in sorted([a, i] for i, a in enumerate(arr)):
for di in [-1, 1]:
for j in range(i + di, i + d * di + di, di):
if not (0 <= j < length and arr[j] < arr[i]):
break
dp[i] = max(dp[i], dp[j] + 1)
return max(dp)
Summary#
I haven't solved problems for a long time, so I'm a bit rusty. I spent time on the first few sign-in problems and made some basic mistakes, so I must stick to solving problems in the future. By the way, I feel that the problems in this week's contest are quite simple, as if they were backup problems found after a leak. That's it for now; I will continue to rest in bed and recover from my illness.