笔记仓库

正常人的正常笔记集

LeetCode Weekly Contest 174

https://leetcode.com/contest/weekly-contest-174/

一人血书一下个破比赛的时间规划对我们东部时区的人来说实在太不友好了,结束了差不多就可以直接睡觉了(好不容易调整好的作息),真的没心思再详细写题解了,所以以后不要指望我稳定产出了,我也好累啊。

weekly contest在每周周六9.30 p.m. biweekly contest在每两周周六9.30 a.m.,我真没那么多时间再来刷这些没什么意思的题了,反正也找不到工作(当然有任何intern机会还请联系我……我真的现在看现在的就业情况好焦虑啊)

简单写一下题吧。

The K Weakest Rows in a Matrix

https://leetcode.com/contest/weekly-contest-174/problems/the-k-weakest-rows-in-a-matrix/

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:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
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]

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
Input: mat =
[[1,0,0,0],
[1,1,1,1],
[1,0,0,0],
[1,0,0,0]],
k = 2
Output: [0,2]
Explanation:
The number of soldiers for each row is:
row 0 -> 1
row 1 -> 4
row 2 -> 1
row 3 -> 1
Rows ordered from the weakest to the strongest are [0,2,3,1]

Constraints:

  1. m == mat.length
  2. n == mat[i].length
  3. 2 <= n, m <= 100
  4. 1 <= k <= m
  5. matrix[i][j] is either 0 or 1.

简单排序,直接写:

1
2
3
4
class Solution:
def kWeakestRows(self, mat: List[List[int]], k: int) -> List[int]:
rank = sorted(list(range(len(mat))), key=lambda i: (sum(mat[i]), i))
return rank[:k]

Reduce Array Size to The Half

https://leetcode.com/contest/weekly-contest-174/problems/reduce-array-size-to-the-half/

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.

Example 1:

1
2
3
4
5
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.

Example 2:

1
2
3
Input: arr = [7,7,7,7,7,7]
Output: 1
Explanation: The only possible set you can choose is {7}. This will make the new array empty.

Example 3:

1
2
Input: arr = [1,9]
Output: 1

Example 4:

1
2
Input: arr = [1000,1000,3,7]
Output: 1

Example 5:

1
2
Input: arr = [1,2,3,4,5,6,7,8,9,10]
Output: 5

Constraints:

  1. 1 <= arr.length <= 10^5
  2. arr.length is even.
  3. 1 <= arr[i] <= 10^5

找出现频数高的元素依次去除,看去到第几个可以去掉超过半数。xjb写就行

1
2
3
4
5
6
7
8
9
10
11
12
13
from collections import Counter


class Solution:
def minSetSize(self, arr: List[int]) -> int:
cnt = Counter(arr)
res = 0
qual = 0
for _, i in cnt.most_common():
res += 1
qual += i
if qual >= len(arr) / 2:
return res

Maximum Product of Splitted Binary Tree

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:

1
2
3
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)

Example 2:

1
2
3
Input: root = [1,null,2,3,4,null,null,5,6]
Output: 90
Explanation: Remove the red edge and get 2 binary trees with sum 15 and 6.Their product is 90 (15*6)

Example 3:

1
2
Input: root = [2,3,9,10,7,8,6,5,4,11,1]
Output: 1025

Example 4:

1
2
Input: root = [1,1]
Output: 1

Constraints:

  1. Each tree has at most 50000 nodes and at least 2 nodes.
  2. Each node’s value is between [1, 10000].

首先做一次后序遍历,计算以每个结点作为根结点时该子树的所有结点和,并记录在这个结点。假设整个树的值的和记录在根结点为root_sum

假设去掉一条边生成的子树的根结点上现在的和值为node_sum,那么剩下的部分也就是以原来的根结点的树,和值也就是去掉上面那个子树和值后的值root_sum-node_sum,众所周知根据基本不等式或二次曲线,node_sum*(root_sum-node_sum)node_sum在越接近root_sum/2时值越大,找到这个结点即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None


class Solution:
def maxProduct(self, root: TreeNode) -> int:
self.node_sum = []

def sum_tree(root):
if not root:
return 0
left_sum = sum_tree(root.left)
right_sum = sum_tree(root.right)
root.val += left_sum + right_sum
self.node_sum.append(root.val)
return root.val
root_sum = sum_tree(root)
sub_root = min(self.node_sum, key=lambda x: abs(x - root_sum / 2))
return (root_sum - sub_root) * sub_root % (10**9 + 7)

Jump Game V

https://leetcode.com/contest/weekly-contest-174/problems/jump-game-v/

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 can not jump outside of the array at any time.

Example 1:

1
2
3
4
5
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.

Example 2:

1
2
3
Input: arr = [3,3,3,3,3], d = 3
Output: 1
Explanation: You can start at any index. You always cannot jump to any index.

Example 3:

1
2
3
Input: arr = [7,6,5,4,3,2,1], d = 1
Output: 7
Explanation: Start at index 0. You can visit all the indicies.

Example 4:

1
2
Input: arr = [7,1,7,1,7,1], d = 2
Output: 2

Example 5:

1
2
Input: arr = [66], d = 1
Output: 1

Constraints:

  1. 1 <= arr.length <= 1000
  2. 1 <= arr[i] <= 10^5
  3. 1 <= d <= arr.length

这题没卡时间,我就用最粗暴的办法写了,其实优化空间很大,有兴趣的可以改一下。

跳转关系是单向的,从i坐标跳到j坐标后无法再跳回,每一步的跳转范围不受上一步限制,i->j关系可以组成拓扑图。假设以i为起点,找所有能跳转到的j,即在距离d以内,且包括j在内所有的元素都小于(体现在图上是低于)arr[i],把这些j记录到lower[i]。遍历一次所有坐标得到一个lower

如果lower[i]里面没有任何j那么以i为起点不能继续跳转,所有能经过1个坐标。如果lower[i]有多个j可以跳转,那么找到路径最长的j作为下一步就是最长的以i为起点的路径了。这个后序遍历的递归写法你可以按照top-down或者bottom-up的思路去写,反正只要再配合一个辅助数组作为memo,时间限制肯定够用。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution:
def maxJumps(self, arr: List[int], d: int) -> int:
lower = [[] for _ in range(len(arr))]
self.path = {}
for i, n in enumerate(arr):
for step in range(1, d + 1):
if 0 <= i - step:
if arr[i - step] < arr[i]:
lower[i].append(i - step)
else:
break
for step in range(1, d + 1):
if i + step < len(arr):
if arr[i + step] < arr[i]:
lower[i].append(i + step)
else:
break

def path_len(i):
if i in self.path:
return self.path[i]
if not lower[i]:
self.path[i] = 1
return self.path[i]
else:
paths = [path_len(x) for x in lower[i]]
self.path[i] = 1 + max(paths)
return self.path[i]
paths = [path_len(i) for i in range(len(arr))]
return max(paths)

终于写完了,太晚了我也要去睡了。祝大家新年愉快,近期注意安全卫生少出门,保持身体健康!