めも

メモ.

Leetcodeを進める:easyのみ(5)

コード:GitHub - Y-kyoto/leetcode

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

Problem344

概要:リストの逆順を返す.

Python3

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        for i in range(len(s)//2):s[i], s[-1-i] = s[-1-i], s[i]
        return s

submission detail

Runtime: 228 ms, faster than 82.70% of Python3 online submissions for Reverse String. Memory Usage: 17.8 MB, less than 15.12% of Python3 online submissions for Reverse String.

.reverse()を使えば反転できる.

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        s.reverse()
        return s

Runtime: 248 ms, faster than 14.49% of Python3 online submissions for Reverse String. Memory Usage: 18 MB, less than 5.81% of Python3 online submissions for Reverse String.

Problem509

概要:フィボナッチ数を返す.

フィボナッチ数に記憶しておく必要があるデータ数は F(n-1) と F(n-2) のみなので,

fibsにはこの二つの値のみを保存する. リストの末尾に計算結果を繋げ(fibs.append(sum(fibs[-2:])))、先頭を削除(fibs.pop(0))することを繰り返した.

Python3

class Solution:
    def fib(self, N: int) -> int:
        fibs = [0, 1]
        
        if N==0:
            return 0
        elif N<=2:
            return 1
        else:
            for i in range(N-2):
                fibs.append(sum(fibs[-2:]))
                fibs.pop(0)
            return sum(fibs[-2:])

Runtime: 28 ms, faster than 98.07% of Python3 online submissions for Fibonacci Number. Memory Usage: 13.9 MB, less than 5.80% of Python3 online submissions for Fibonacci Number.

submission detail

Problem811

概要:Webページのurlごとの閲覧回数のリストが文字列で渡されるので、ドメインごとに何回出現したかをカウントする. [問題文]

Python3

はじめにナイーブに一ウェブサイトごとにドットで区切って処理.

  • 1000 blog.hatena.ne.jp
  • 1000, ["blog.hatena.ne.jp", "hatena.ne.jp", "ne.jp", "jp"] -{"blog.hatena.ne.jp":1000, "hatena.ne.jp":1000, "ne.jp":1000, "jp":1000}

のように処理.

class Solution:
    def subdomainVisits(self, cpdomains: List[str]) -> List[str]:
        res = {}

        # website domainごとに
        for cpdomain in cpdomains:
            countStr, domainsStr = cpdomain.split(" ")
            count = int(countStr)

            # 「.」で区切ったドメインのリスト
            domainsDotSplitted = [domainsStr]
            for i, si in enumerate(domainsStr):
                if si is ".":
                    # 「.」以降には必ず文字が存在する想定でいる
                    domainsDotSplitted.append(domainsStr[i+1:])

            # 集計
            for domain in domainsDotSplitted:
                if not domain in res:
                    res.update({domain:count})
                else:
                    res[domain] += count

        # 集計結果を出力のフォーマットに合わせる
        return [ "%s %s"%(v, k) for k, v in res.items()]

Runtime: 84 ms, faster than 5.42% of Python3 online submissions for Subdomain Visit Count. Memory Usage: 13.8 MB, less than 8.33% of Python3 online submissions for Subdomain Visit Count.

submission detail

速くするために修正したい。

Problem929

概要:gmailのようなメールのリストが与えられるので、その中に含まれるユニークなメールアドレス(届け先が異なるアドレス数)を返す. ドットは無視し、 +~@の文字列も無視されることに注意する. [問題文]

Python3

[email.split("@") for email in emails]でメールアドレスを@前後で分割したリストを作り,

local.replace(".", "").split("+")[0] = ローカルのドットを除去し、+より手前の文字列だけ残す.

set(local_domain)でユニークな要素のみを残し、その要素数を答えとして返す.

class Solution:
    def numUniqueEmails(self, emails: List[str]) -> int:
        local_domain = [email.split("@") for email in emails]
        local_domain = [(local.replace(".", "").split("+")[0], domain) for local, domain in local_domain]
        return len(set(local_domain))

submission detail

Problem1122

概要:arr1の数値をarr2に指定された順番に並び替える. arr2に含まれない数字は結果の末尾にソート済みの状態で連結させる.

Python3

notInArr2arr2に含まれない数値を繋げて、最後にソートする. arr1には arr2のインデックスを入れて、最後にインデックスをソートしてから元の数値に戻す. arr2に含まれなかった数値は -1 にしておき無視する. およそ以下のように処理した. arr1の中身は再利用しないので、arr1 に答えを上書きしていく.

  • arr1: [ 100, 200, 300, 400, ], arr2: [400, 200, 300]
  • arr1: [-1, 1, 2, 0], arr2: [500, 100]
  • arr1: [-1, 0, 1, 2], arr2: [500, 100]
  • arr1: [400, 200, 300], arr2: 100, 500
class Solution:
    def relativeSortArray(self, arr1: List[int], arr2: List[int]) -> List[int]:
        notInArr2 = []

        for i, ni in enumerate(arr1):
            if not ni in arr2:
                notInArr2.append(ni)
                arr1[i] = -1
            else:
                arr1[i] = arr2.index(ni)

        arr1.sort()
        notInArr2.sort()
        return [arr2[n] for n in arr1 if n>=0] + notInArr2

submission datail

Runtime: 48 ms, faster than 47.82% of Python3 online submissions for Relative Sort Array. Memory Usage: 14 MB, less than 100.00% of Python3 online submissions for Relative Sort Array.

Problem1200

概要:数値のリストから差が最小になる数値のペアのリストを返す.

Python3

ソートしてから隣同士の差分を見る. 最小のものを見つけたら結果をクリア(res.clear())して新しい答えを繋げる.

class Solution:
    def minimumAbsDifference(self, arr: List[int]) -> List[List[int]]:
        arr.sort()
        res = []
        mindiff = 10**6
        for i in range(len(arr)-1):
            diff = abs(arr[i+1]-arr[i])
            if diff<mindiff:
                mindiff = diff
                res.clear()
                res.append([arr[i], arr[i+1]])
            elif diff==mindiff:
                res.append([arr[i], arr[i+1]])
        return res

Runtime: 384 ms, faster than 99.60% of Python3 online submissions for Minimum Absolute Difference. Memory Usage: 27.8 MB, less than 100.00% of Python3 online submissions for Minimum Absolute Difference.

submission detail