emmmm，我的拖延症沒救了，順便加上這周沉迷 Kotlin ，這篇本應該周一就寫完的題解拖到現在，= = 然而這周雙周賽，，我又得寫兩篇題解了。。。
1351. 計算排序矩陣中的負數個數#
題面：
給定一個 m * n 矩陣 grid，該矩陣按行和列的非遞增順序排序。
返回矩陣中負數的個數。
示例：
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: 矩陣中有 8 個負數。
題面很簡單，給定一個矩陣，矩陣橫 / 縱向都是遞減的，求這個矩陣中負數的個數，這個題，因為橫 / 縱向的數據規模都是小於 100 的，那就沒啥說的了，，直接暴力，橫向遍歷，然後遇到負數就停止遍歷
from typing import List
class Solution:
def countNegatives(self, grid: List[List[int]]) -> int:
if not grid:
return 0
n_length = len(grid[0])
result = 0
for item in grid:
for i in range(n_length):
if item[i] < 0:
result += n_length - i
break
return result
1352. 最後 K 個數的乘積#
題面:
實現類 ProductOfNumbers，支持兩個方法：
1. add(int num)
將數字 num 添加到當前數字列表的末尾。
2. getProduct(int k)
返回當前列表中最後 k 個數的乘積。
你可以假設當前列表始終至少有 k 個數。
在任何時候，任何連續數字序列的乘積都將適合單個 32 位整數而不會溢出。
示例
Input
["ProductOfNumbers","add","add","add","add","add","getProduct","getProduct","getProduct","add","getProduct"]
[[],[3],[0],[2],[5],[4],[2],[3],[4],[8],[2]]
Output
[null,null,null,null,null,null,20,40,0,null,32]
Explanation
ProductOfNumbers productOfNumbers = new ProductOfNumbers();
productOfNumbers.add(3); // [3]
productOfNumbers.add(0); // [3,0]
productOfNumbers.add(2); // [3,0,2]
productOfNumbers.add(5); // [3,0,2,5]
productOfNumbers.add(4); // [3,0,2,5,4]
productOfNumbers.getProduct(2); // 返回 20。最後 2 個數的乘積是 5 * 4 = 20
productOfNumbers.getProduct(3); // 返回 40。最後 3 個數的乘積是 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // 返回 0。最後 4 個數的乘積是 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8); // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // 返回 32。最後 2 個數的乘積是 4 * 8 = 32
題面很簡單，設計一個數據結構，提供一個 add 方法，讓用戶能夠往裡面添加數字，提供一個 getProduct 方法，讓用戶能求倒數 K 個數的乘積，這題沒啥好說的，直接暴力寫，中間加個 hashmap 作為緩存
from typing import List, Dict
import bisect
from operator import mul
from functools import reduce
class ProductOfNumbers:
_value: List[int]
_cache_result: Dict[int, int]
_cache_index: List[int]
def __init__(self):
self._value = []
self._cache_result = {}
self._cache_index = []
def add(self, num: int) -> None:
self._value.append(num)
self._cache_index.clear()
self._cache_result.clear()
def getProduct(self, k: int) -> int:
if k in self._cache_result:
return self._cache_result[k]
cache_index = bisect.bisect(self._cache_index, k) - 1
if cache_index >= 0:
last_k = self._cache_index[cache_index]
result = self._cache_result[last_k]
for i in range(1, cache_index + 1):
temp_last_k = last_k + i
if temp_last_k >= len(self._value):
break
result *= self._value[-last_k]
else:
temp_value = (
self._value[-1 : -k - 1 : -1] if k <= len(self._value) else self._value
)
result = reduce(mul, temp_value, 1)
bisect.bisect_left(self._cache_index, k)
self._cache_result[k] = result
return result
1353. 可以參加的最大活動數#
題面：
給定一個活動數組，其中 events [i] = [startDayi, endDayi]。每個活動 i 在 startDayi 開始並在 endDayi 結束。
你可以在任何一天 d 參加活動 i，滿足 startTimei <= d <= endTimei。注意你在任何時間 d 只能參加一個活動。
返回你可以參加的最大活動數。
示例
Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: 你可以參加所有三個活動。
參加所有活動的一種方法如下。
在第 1 天參加第一個活動。
在第 2 天參加第二個活動。
在第 3 天參加第三個活動。
給定一個數組，數組中每個元素 x 代表一個活動，x [0], x [i] 代表該活動的起始與結束時間，一個用戶一天只能參加一個活動，求用戶最多能參加多少個活動。經典的貪心題目，首先對活動列表以結束時間進行排序，然後依次遍歷每個時間，確認具體哪一天可以參加，整體時間複雜度為 O (max (nlogn,n*m))
from typing import List, Dict
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
if not events:
return 0
events_size = len(events)
if events_size == 1:
return 1
events = sorted(events)
_day_map: Dict[str, bool] = {}
_event_map: Dict[int, bool] = {}
count = 0
for i in range(events_size):
for j in range(events[i][0], events[i][1]+1):
temp = "{}".format(j)
if temp not in _day_map and i not in _event_map:
count += 1
_day_map[temp] = True
_event_map[i] = True
return count
1354. 用多次求和構造目標數組#
題面
給定一個整數數組 target。從一個由所有 1 組成的起始數組 A 開始，你可以執行以下過程：
- 讓 x 成為當前數組中所有元素的和。
- 選擇索引 i，使得 0 <= i < target.size，並將 A 中索引 i 的值設置為 x。
- 你可以重複這個過程任意次。
如果可以從 A 構造目標數組，則返回 True，否則返回 False。
示例：
Input: target = [9,3,5]
Output: true
Explanation: 從 [1, 1, 1] 開始
[1, 1, 1], sum = 3 選擇索引 1
[1, 3, 1], sum = 5 選擇索引 2
[1, 3, 5], sum = 9 選擇索引 0
[9, 3, 5] 完成
這題算是一個數學題吧，我們首先知道數組中所有的元素的和一定大於數組中每個元素（這不是廢話），然後我們假定有這樣一個數組 [1,1,9,17,63] ，我們可以往回迭代上個數組結構是 [1,1,9.17,33] ，然後我們還可以向前迭代一次 [1,1,9,17,5] 然後當前的數字已經不再是數組中最大的數字，因此我們開始尋找下一個數組中最大的數字進行迭代
這裡我們也可以發現，數組中最大數字的最原始版本的值是當前數字對其餘數字的和的模，因此我們就這樣一直迭代就 OK 了
好了，上碼
import heapq
from typing import List
class Solution:
def isPossible(self, target: List[int]) -> bool:
if not target:
return False
total = sum(target)
target = sorted([-x for x in target])
heapq.heapify(target)
while True:
a = -heapq.heappop(target)
total -= a
if a == 1 or total == 1:
return True
if a < total or total == 0 or a % total == 0:
return False
a %= total
total += a
heapq.heappush(target, -a)
總結#
這次的題還是周賽的常規水平，然而我刷題實在是太少了 QAQ