久しぶりに週末コンテストをやったので、簡単に解答を書いてみます。
2224. 時間を変換するための最小操作数#
問題文：
current と correct の 2 つの文字列が与えられ、2 つの 24 時間形式の時間を表します。
24 時間形式は "HH:MM" の形式で、HH は 00 から 23 の間、MM は 00 から 59 の間です。最も早い 24 時間形式は 00:00 で、最も遅いのは 23:59 です。
1 回の操作で、current の時間を 1、5、15、または 60 分増やすことができます。この操作は任意の回数行うことができます。
current を correct に変換するために必要な最小操作数を返します。
例：
例 1:
入力: current = "02:30", correct = "04:35"
出力: 3
説明:
次のように 3 回の操作で current を correct に変換できます：
- current に 60 分を加えます。current は "03:30" になります。
- current に 60 分を加えます。current は "04:30" になります。
- current に 5 分を加えます。current は "04:35" になります。
3 回未満の操作で current を correct に変換することは不可能であることが証明できます。
例 2:
入力: current = "11:00", correct = "11:01"
出力: 1
説明: current に 1 分を加えるだけで済むので、必要な最小操作数は 1 です。
この問題は特に言うことはないですね、単純に時間を計算して書けばいいです。
class Solution:
def convertTime(self, current: str, correct: str) -> int:
correct_time = correct.split(':')
current_time = current.split(':')
minutes = int(correct_time[1]) - int(current_time[1])
hours = int(correct_time[0]) - int(current_time[0])
if correct_time[1] < current_time[1]:
minutes += 60
hours -= 1
results = hours
flag = [15, 5, 1]
for i in flag:
if minutes >= i:
results += (minutes // i)
minutes = minutes % i
return results
2225. ゼロまたは 1 回の敗北のプレイヤーを見つける#
問題文：
matches という整数配列が与えられ、matches[i] = [winneri, loseri] はプレイヤー winneri がプレイヤー loseri を試合で打ち負かしたことを示します。
次の 2 つのサイズのリスト answer を返します：
answer[0] は試合に負けたことがないすべてのプレイヤーのリストです。
answer[1] はちょうど 1 回だけ試合に負けたすべてのプレイヤーのリストです。
2 つのリストの値は昇順で返されるべきです。
注意:
少なくとも 1 回は試合を行ったプレイヤーのみを考慮する必要があります。
テストケースは、2 つの試合が同じ結果を持たないように生成されます。
例：
例 1:
入力: matches = [[1,3],[2,3],[3,6],[5,6],[5,7],[4,5],[4,8],[4,9],[10,4],[10,9]]
出力: [[1,2,10],[4,5,7,8]]
説明:
プレイヤー 1、2、および 10 は試合に負けたことがありません。
プレイヤー 4、5、7、および 8 はそれぞれ 1 回の試合に負けています。
プレイヤー 3、6、および 9 はそれぞれ 2 回の試合に負けています。
したがって、answer[0] = [1,2,10] および answer[1] = [4,5,7,8] です。
例 2:
入力: matches = [[2,3],[1,3],[5,4],[6,4]]
出力: [[1,2,5,6],[]]
説明:
プレイヤー 1、2、5、および 6 は試合に負けたことがありません。
プレイヤー 3 および 4 はそれぞれ 2 回の試合に負けています。
したがって、answer[0] = [1,2,5,6] および answer[1] = [] です。
この問題は実際には単に遍歴して集計すればよいので、時間計算量は O (N)、空間計算量は O (N) です。
from collections import defaultdict
from typing import List
class Solution:
def findWinners(self, matches: List[List[int]]) -> List[List[int]]:
index = defaultdict(lambda: [0, 0])
for winner, loser in matches:
index[winner][0] += 1
index[loser][1] += 1
return [
sorted([k for k, v in index.items() if v[0] > 0 and v[1] == 0]),
sorted([k for k, v in index.items() if v[1] == 1]),
]
2226. K 人の子供に配分される最大キャンディ数#
この問題の番号は本当に面白いですね、尊敬します。。。
問題文：
candies という 0 インデックスの整数配列が与えられます。配列の各要素は candies[i] のサイズのキャンディの山を示します。各山を任意の数のサブ山に分割できますが、2 つの山を一緒にマージすることはできません。
また、整数 k が与えられます。k 人の子供にキャンディの山を配分する必要があります。各子供は同じ数のキャンディを受け取る必要があります。各子供は最大 1 つのキャンディの山を受け取ることができ、一部のキャンディの山は未使用のままになる可能性があります。
各子供が受け取ることができる最大のキャンディの数を返します。
例：
例 1:
入力: candies = [5,8,6], k = 3
出力: 5
説明: candies[1] をサイズ 5 と 3 の 2 つの山に分割し、candies[2] をサイズ 5 と 1 の 2 つの山に分割できます。現在、サイズ 5、5、3、5、および 1 の 5 つのキャンディの山があります。サイズ 5 の 3 つの山を 3 人の子供に配分できます。各子供が 5 個以上のキャンディを受け取ることはできないことが証明できます。
例 2:
入力: candies = [2,5], k = 11
出力: 0
説明: 11 人の子供がいますが、合計で 7 個のキャンディしかないため、各子供が少なくとも 1 個のキャンディを受け取ることを保証することは不可能です。したがって、各子供はキャンディを受け取らず、答えは 0 です。
この問題は実際には最初は考えがまとまらなかったのですが、後でよく考えたら、実際には二分探索の問題です。
まず、すべてのキャンディの合計を y と仮定し、k で割った値を z と仮定します（これは最大の整数分割可能な数を意味します）。したがって、子供たちが得られる最大のキャンディの数の値域は [0,z] である必要があります。
この区間は単調性を持っているため（単調増加）、二分探索の条件を満たします。では、二分探索の問題は何でしょうか？中間値を mid と仮定し、各キャンディを mid に分けていくつの部分に分けられるかを計算し、その合計を求めます。もし合計が k より小さければ、値が目標値より大きいことを意味し、そうでなければ目標値より小さいことを意味します。これを繰り返して近づいていきます。
from typing import List
class Solution:
def maximumCandies(self, candies: List[int], k: int) -> int:
left, right = 0, sum(candies) // k
while left < right:
mid = (left + right + 1) // 2
if k > sum(candy // mid for candy in candies):
right = mid - 1
else:
left = mid
return left
2227. 文字列の暗号化と復号化#
この問題は実際には 3 番目の問題より簡単です。
問題文：
ユニークな文字を含む文字配列 keys と、長さ 2 の文字列を含む文字配列 values が与えられます。また、復号化後のすべての許可された元の文字列を含む文字列配列 dictionary も与えられます。0 インデックスの文字列を暗号化または復号化できるデータ構造を実装する必要があります。
文字列は次のプロセスで暗号化されます：
文字列内の各文字 c に対して、keys[i] == c を満たす i を見つけます。
文字列内の c を values[i] に置き換えます。
文字列は次のプロセスで復号化されます：
文字列内の偶数インデックスに出現する長さ 2 の各部分文字列 s に対して、values[i] == s を満たす i を見つけます。有効な i が複数ある場合は、そのうちのいずれかを選択します。これは、文字列が復号化できる可能性のある複数の文字列を持つことを意味します。
文字列内の s を keys[i] に置き換えます。
Encrypter クラスを実装します：
Encrypter(char[] keys, String[] values, String[] dictionary) は、keys、values、および dictionary で Encrypter クラスを初期化します。
String encrypt(String word1) は、上記の暗号化プロセスで word1 を暗号化し、暗号化された文字列を返します。
int decrypt(String word2) は、word2 が復号化できる可能性のある文字列の数を返します。これらの文字列は dictionary にも存在します。
例：
入力
["Encrypter", "encrypt", "decrypt"]
[[['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]], ["abcd"], ["eizfeiam"]]
出力
[null, "eizfeiam", 2]
説明
Encrypter encrypter = new Encrypter([['a', 'b', 'c', 'd'], ["ei", "zf", "ei", "am"], ["abcd", "acbd", "adbc", "badc", "dacb", "cadb", "cbda", "abad"]);
encrypter.encrypt("abcd"); // "eizfeiam" を返します。
// 'a' は "ei" にマッピングされ、'b' は "zf" にマッピングされ、'c' は "ei" にマッピングされ、'd' は "am" にマッピングされます。
encrypter.decrypt("eizfeiam"); // 2 を返します。
// "ei" は 'a' または 'c' にマッピングでき、"zf" は 'b' にマッピングされ、"am" は 'd' にマッピングされます。
// 従って、復号化後の可能な文字列は "abad"、"cbad"、"abcd"、および "cbcd" です。
// そのうちの 2 つの文字列、"abad" と "abcd" は dictionary に存在するので、答えは 2 です。
この問題の暗号化部分は実際にはルールに従って書くだけで済み、復号化部分は事前に辞書内の値を計算しておくことで O (1) で計算できます。
from collections import Counter
from typing import List
class Encrypter:
def __init__(self, keys: List[str], values: List[str], dictionary: List[str]):
self.index = {k: v for k, v in zip(keys, values)}
self.counter = Counter(self.encrypt(item) for item in dictionary)
def encrypt(self, word1: str) -> str:
return "".join(self.index.get(letter, " ") for letter in word1)
def decrypt(self, word2: str) -> int:
return self.counter[word2]