Leetcodeを進める：easyのみ(4)

easyの問題を中心に、pythonに限らず複数の言語で解いていく方針に。

今日はpythonに偏ってしまったのでC++、goなども増やしたいです.

コード：GitHub - Y-kyoto/leetcode

他の問題：leetcode カテゴリーの記事一覧 - めも

Problem461

概要：二つの自然数を二進数で表現した時のハミング距離を求めたい.

Python3

bin で二進数にしたのち、先頭の 0b を切り取り、

str.zfill(0) で短い方の文字列を0で埋めて桁数を同じにしてから、

sum(...) で二つが一致しない箇所を数えあげて結果としました.

class Solution:
    def hammingDistance(self, x: int, y: int) -> int:
        bx, by = bin(x)[2:], bin(y)[2:]
        ndigit = len(bx) if x>=y else len(by)
        bx, by = bx.zfill(ndigit), by.zfill(ndigit)
        return sum([xi!=yi for xi, yi in zip(bx, by)])

submission detail

Problem561

概要：問題参照, 最良の場合はソートした数列の偶数インデックスのみを選択して総和を取るのがベストと判断した.

Python3

class Solution:
    def arrayPairSum(self, nums: List[int]) -> int:
        nums.sort()
        return sum([ni for i, ni in enumerate(nums) if i%2==0])

Problem617

概要：二つの二分木をマージする、ノードが存在する箇所はそのノードの数値の和を新しいノードにする.

Python3

最も単純には再帰的にマージを行う. Solutionではスタックを使用することでO(n)の時間・空間複雑さで計算を終える方法が紹介されている.

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    def mergeTrees(self, t1: TreeNode, t2: TreeNode) -> TreeNode:

        def mergetree(node1, node2):
            if node1 is None:
                return node2
            elif node2 is None:
                return node1
            else:
                node = node1
                node.val = node1.val + node2.val
                node.left = mergetree(node1.left, node2.left)
                node.right = mergetree(node1.right, node2.right)
                return node

        return mergetree(t1, t2)

Problem627

概要：salary テーブルの sex 属性について、updateのみで性別を逆にしたい.

MySQL

IF で性別を逆に置き換える. おそらく全く同じ回答にしている人が多数存在する.

MySQL :: MySQL 5.6 リファレンスマニュアル :: 12.4 制御フロー関数

# Write your MySQL query statement below
UPDATE salary SET sex = IF(sex='f', 'm', 'f');

submission detail

UPDATE文の中でCASEを使う事もできるので, 性別よりもさらに多数の値を取りうる属性で同様の処理をしたいときは

UPDATE salary
SET
    colA = CASE
        WHEN colA=='xxx' THEN ...
        WHEN colA=='yyy' THEN ...
        ELSE ...
    END;

のようなSQLになる.

Problem852

概要：リストの中の最大値のインデックス.

Python3

A[0]にこれまでに見た最大値を保存しておく.

問題文に 3 <= A.length <= 10000の条件があるので、二分木で探索するのもあり. かと思ったが, [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,...1,2,1] の場合などが難しいので結局前から順番に見るしかないと判断.

class Solution:
    def peakIndexInMountainArray(self, A: List[int]) -> int:
        for i, ai in enumerate(A):
            if A[0]<=ai:A[0]=ai
            else:return i-1

Runtime: 88 ms

submission detail

一行で終わらせる場合,

class Solution:
    def peakIndexInMountainArray(self, A: List[int]) -> int:
        return A.index(max(A))

Runtime: 92 ms, faster than 59.37% of Python3 online submissions for Peak Index in a Mountain Array.

Problem942

概要：DIDI...と行った形式でDとIのリストが渡されるので、それに従ってD（減少）・I（増加）する数列を返す。ただし、リストは[０, DI列の長さ]の範囲の数値しか含まず、重複する自然数は含まれてはいけない. [問題文]

Python3

これまでのリストに出現した値の最小・最大を持つ変数 nmin, nmaxを用意.

D/I に従ってとりあえず0から順番に数字が重複しないように nmin, nmax を参照しながら数字を並べる. 最後に nmin だけ足して全て０以上の自然数にして結果を作成する.

class Solution:
    def diStringMatch(self, S: str) -> List[int]:
        nmin, nmax = -1, 1
        res = [0]
        
        for IorD in S:
            if IorD=="D":
                res.append(nmin)
                nmin -= 1
            else:
                res.append(nmax)
                nmax += 1
            
        return [n-nmin-1 for n in res]

Runtime: 72 ms, faster than 90.56% of Python3 online submissions for DI String Match. Memory Usage: 14.9 MB, less than 5.00% of Python3 online submissions for DI String Match.

submission detail

Problem944

概要：文字列のリストが渡される(A[i][j]にa~zが1文字入っている行列を想定すればいい). この中から, a->z順に並んでいない列がいくつ存在するかを返す.

問題文がわかりにくいというコメントがかなり多い.

Python3

愚直に列ごとに調べる. 不等号に等号を含んでしまい, Wrong Answerを記録. 次回から気をつけたい.

class Solution:
    def minDeletionSize(self, A: List[str]) -> int:
        res = 0
        lenA = len(A)

        for i in range(len(A[0])):
            for j in range(lenA-1):
                if A[j][i]>A[j+1][i]:
                    res += 1
                    break
        return res

submission detail