emmmm、私の先延ばし症は治らない、ついでに今週は Kotlin に夢中になっていて、この問題解決は本来月曜日に書き終えるべきだったのに、今まで引き延ばしてしまった、= = しかし今週は二週間ごとのコンテストで、また二つの問題解決を書かなければならない。。。
1351. ソートされた行列内の負の数を数える#
問題文：
行と列の両方が非増加順にソートされた m * n 行列 grid が与えられます。
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 メソッドを提供し、ユーザーが最後の K 個の数の積を求める getProduct メソッドを提供します。この問題は特に言うことはなく、単純に暴力的に書き、間にキャッシュとしての 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 に終わります。
あなたは startTimei <= d <= endTimei の任意の日 d にイベント i に参加できます。注意：任意の日 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 とします。
- 0 <= i < target.size となるようなインデックス i を選び、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] そして現在の数字はもはや配列内の最大の数字ではなくなりますので、次の配列内の最大の数字を見つけるために繰り返しを開始します。
ここで、配列内の最大数字の最初のバージョンの値は、現在の数字と他の数字の合計の剰余であることがわかります。したがって、このように繰り返し続ければ大丈夫です。
さて、コードを書きましょう。
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