emmmm，我的拖延症沒救了，順便加上這周沉迷 Kotlin ，這篇本應該周一就寫完的題解拖到現在，= = 然而這周雙周賽，，我又得寫兩篇題解了。。。
1351. Count Negative Numbers in a Sorted Matrix#
題面：
Given a m * n matrix grid which is sorted in non-increasing order both row-wise and column-wise.
Return the number of negative numbers in grid.
示例：
Input: grid = [[4,3,2,-1],[3,2,1,-1],[1,1,-1,-2],[-1,-1,-2,-3]]
Output: 8
Explanation: There are 8 negatives number in the matrix.
題面很簡單，給定一個矩陣，矩陣橫 / 縱向都是遞減的，求這個矩陣中負數的個數，這個題，因為橫 / 縱向的數據規模都是小於 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. Product of the Last K Numbers#
題面:
Implement the class ProductOfNumbers that supports two methods:
1. add(int num)
Adds the number num to the back of the current list of numbers.
2. getProduct(int k)
Returns the product of the last k numbers in the current list.
You can assume that always the current list has at least k numbers.
At any time, the product of any contiguous sequence of numbers will fit into a single 32-bit integer without overflowing.
示例
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); // return 20. The product of the last 2 numbers is 5 * 4 = 20
productOfNumbers.getProduct(3); // return 40. The product of the last 3 numbers is 2 * 5 * 4 = 40
productOfNumbers.getProduct(4); // return 0. The product of the last 4 numbers is 0 * 2 * 5 * 4 = 0
productOfNumbers.add(8); // [3,0,2,5,4,8]
productOfNumbers.getProduct(2); // return 32. The product of the last 2 numbers is 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. Maximum Number of Events That Can Be Attended#
題面：
Given an array of events where events[i] = [startDayi, endDayi]. Every event i starts at startDayi and ends at endDayi.
You can attend an event i at any day d where startTimei <= d <= endTimei. Notice that you can only attend one event at any time d.
Return the maximum number of events you can attend.
示例
Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 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. Construct Target Array With Multiple Sums#
題面
Given an array of integers target. From a starting array, A consisting of all 1's, you may perform the following procedure :
- let x be the sum of all elements currently in your array.
- choose index i, such that 0 <= i < target.size and set the value of A at index i to x.
- You may repeat this procedure as many times as needed.
Return True if it is possible to construct the target array from A otherwise return False.
示例：
Input: target = [9,3,5]
Output: true
Explanation: Start with [1, 1, 1]
[1, 1, 1], sum = 3 choose index 1
[1, 3, 1], sum = 5 choose index 2
[1, 3, 5], sum = 9 choose index 0
[9, 3, 5] Done
這題算是一個數學題吧，我們首先知道數組中所有的元素的和一定大於數組中每個元素（這不是廢話），然後我們假定有這樣一個數組 [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