久しぶりに週末コンテストをやったので、簡単に解答を書いてみます。
2224. 時間を変換するための最小操作数#
問題文：
現在の時間と正しい時間を表す2つの文字列 current と correct が与えられます。
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 を試合で打ち負かしたことを示します。
敗北していないプレイヤーのリスト answer[0] と、ちょうど1回敗北したプレイヤーのリスト answer[1] を含むサイズ2のリストを返します。
2つのリストの値は昇順で返されるべきです。
注意:
少なくとも1回試合をしたプレイヤーのみを考慮する必要があります。
テストケースは、同じ結果を持つ試合がないように生成されます。
例：
例 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 人の子供に配分される最大キャンディ#
この問題の番号は本当に面白いですね、尊敬します。。。
問題文：
0-indexed の整数配列 candies が与えられます。配列の各要素はサイズ 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-indexed の文字列を暗号化または復号化できるデータ構造を実装する必要があります。
文字列は次のプロセスで暗号化されます：
文字列内の各文字 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]