LeetCodeに挑戦：Weekly Contest 172
Weekly Contest 172 に挑戦しました。
https://leetcode.com/contest/weekly-contest-172
今回の出題は、以下の通りでした。
1323. Maximum 69 Number（Difficulty: Easy）
1324. Print Words Vertically（Difficulty: Medium）
1325. Delete Leaves With a Given Value（Difficulty: Medium）
1326. Minimum Number of Taps to Open to Water a Garden（Difficulty: Hard）
以下に問題の概要と、解答例を紹介します。
1323. Maximum 69 Number
（問題）6 と 9 のみで構成される、正の整数 ( num ) が与えられる。最大1桁の変更で、得られる最大値を返せ。
（例）Input: num = 9669
Output: 9969
（考え方） とにかく大きな数字になれば良いので、桁が上のところから探索して、6 があれば 9に変更すれば良い。
（コーディング）私は、forループを使って地道に検索して、6を探しましたが、Discuss内で見つけたエレガントなコードを以下に記述します。
def maximum69Number(self, num):
return int(str(num).replace('6', '9', 1))replace( ) を使えば、3つ目の引数を 1 として与えれば、上から1つ目だけ置換できるんですね。。
1324. Print Words Vertically
（問題）ある文字列 (s) が与えられる。文字列内のすべての単語を、s に現れるのと同じ順序で垂直に返しなさい。また、単語は文字列のリストとして返され、必要に応じてスペースが追加されます。ただし、末尾のスペースは使用できません。各単語は1つの列にのみ配置され、1つの列には1つの単語しかありません。
（例）Input: s = “TO BE OR NOT TO BE”
Output: [“TBONTB”,”OEROOE”,” T”]
（コーディング）各単語の長さが違う事がキモで、短い単語はスペースで保管をしなくてはなりません。さらに、末尾にスペースがあってはいけないという制約があるので、そこにも処理が必要です。こちらも、Discuss内で見つけた、きれいなコードを参考に以下に記述します。
def printVertically(self, s):
words = s.split() #文字列 s を単語単位でリストwordsに格納
maxlen = max(len(w) for w in words) #単語の中の最長の長さを取得
res = [""] * maxlen #答えを格納するリストの初期化（最長の単語の長さと同じ要素数になる）
for i in range(maxlen):
for w in words:
res[i] += ' ' if i >= len(w) else w[i] #最長のものより短い単語の場合はスペースで保管
res[i] = res[i].rstrip() #関数rstrip( ) で右側のスペースを除去
return res1325. Delete Leaves With a Given Value
（問題）2分木(root) と ある整数(target)が与えられる。root の リーフが targetである場合、そのリーフを削除した root を返せ。ただし、リーフを削除した結果、親ノードがリーフになった場合、そのリーフが targetであれば削除しなくてはならない。（問題）2分木(root) と ある整数(target)が与えられる。root の リーフが targetである場合、そのリーフを削除した root を返せ。ただし、リーフを削除した結果、親ノードがリーフになった場合、そのリーフが targetであれば削除しなくてはならない。
（コーデイング）深さ優先探索で解ける問題です。
class Solution:
def removeLeafNodes(self, root: TreeNode, target: int) -> TreeNode:
self.dfs(root, target, cnt)
if root.val == target and not(root.left or root.right):
return None
return root
def dfs(self, root, target, cnt):
#もうnodeはない
if not root:
return False
#左側のリーフの探索
is_left = self.dfs(root.left, target, cnt)
if is_left:
root.left = None
#右側のリーフの探索
is_right = self.dfs(root.right, target, cnt)
if is_right:
root.right = None
#リーフの値がtargetだった場合
if root.val == target and not(root.left or root.right):
return True
else:
return False1326. Minimum Number of Taps to Open to Water a Garden
（問題）0から始まり n で終わる 1次元の庭がり、庭のポイント [0, 1, …, n] に合計 n + 1 個のタップがある。整数 nと、長さn + 1の整数の配列 ranges が与えられ、ranges[ i ] は、i 番目のタップが領域 [ i – range [ i ]、i + range [ i ] ]の範囲に散水できることを意味する。庭全体に水をまくために必要なタップの最小数を返せ。庭に水をまくことができない場合は、-1を返せ。
（コーデイング）(1) 各要素が1回で到達できる最も遠いインデックスを表すように、ranges を変更します。 (2) 到達するために必要な最小限の個数を見つけます。
class Solution:
def minTaps(self, n: int, ranges: List[int]) -> int:
# (1)
for i,r in enumerate(ranges): # i はindex, r はranges[i]
l = max(0,i-r)
ranges[l] = max(i+r, ranges[l])
# (2)
res = lo = hi = 0
while hi < n:
lo, hi = hi, max(ranges[lo:hi+1])
if hi == lo: return -1
res += 1
return res 最後に、今回私は1323, 1324の2つをAcceptedにできました。その結果 rating は 1417 –> 1427 と +10となりました。。
