Leetcodeを進める：問1〜問7

Leetcode

leetcode.com

実際に企業で出題された（とされる）技術テストを解くことができる。問題の解説あり、難易度別にタグ付けなどがされている。全部で1000+α題。

解答サブミット時に、全体のサブミットでだいたいどれくらいの解答であるかを知ることができる（ランタイムトップXX％でした、メモリ使用トップXX％でした、など）。ただ、サブミットのたびに同じコードでも上下する時もあり、参考程度。

ぐぐらずとも、submissionsのタブから他の人の良い解答を見ることができ、解法の解説も詳しく書いてありためにある。いろんな言語をためしたい。

他の方の解答例

自分の初挑戦時の回答

自戒のために初回時（解答・他の人のサブミッションを見ていない状態で書いた）コードをめも。

Problem1(Easy)

• 入力：整数値のリストと整数値（ターゲット）
• 目的：リストの中から二つ選んで足したらターゲットになるような整数二つのインデックスを返す
• 仮定：解答は必ず1組だけ存在する

gist.github.com

• Runtime: 52 ms
• Memory Usage: 13.4 MB

Submission Detail

Problem2(Medium)

• 入力：(2 -> 4 -> 3)のような連結リストが二つ
• 目的：二つの連結リストの和を同様の連結リストのフォーマットで返す
• 例

  Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)

  Output: 7 -> 0 -> 8

  Explanation: 342 + 465 = 807.

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        ans = 0

        # calc l1 + l2
        for temp in [l1, l2]:
            counter = 0
            while True:
                ans += 10**counter*temp.val
                if not temp.next is None:
                    counter += 1
                    temp = temp.next
                else:
                    break
            
        # answer, 逆順に入れる
        l1 = l2 = ListNode(0)
        for ci in str(ans)[::-1]:
            l2.next = ListNode(int(ci))
            l2 = l2.next
            
        return l1.next

Problem3(Medium)

• 入力：文字列
• 目的：文字が重複しないような部分列のうち、最大の長さの部分列の長さを返す

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # 最大の部分列長、現在保持してる部分列
        result, sub = 0, ""
        for char in s:
            if char not in sub:
                # 部分列に含まれないcharならば追加
                sub += char
                result = max(result, len(sub))
            else:
                # 部分列の中で最初に見つかるcharの箇所まで切り落とす
                sub = sub[sub.index(char)+1:] + char
        return result

Submission Detail

Problem4(Hard)

pythonだとリストのソートを簡単に(ソートなどのアルゴリズムの中身を理解せずに)行えるので Hard ではない感じでした。

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        # リストをソート
        nums1_nums2 = nums1 + nums2
        nums1_nums2.sort()
        med_index = len(nums1_nums2)/2
        
        # 長さが偶数奇数で場合分け
        if med_index.is_integer():
            return (nums1_nums2[int(med_index-.5)]+nums1_nums2[int(med_index+.5)])/2.0
        else:
            return nums1_nums2[int(med_index)]

Runtime: 40 ms, faster than 99.99% of Python3 online submissions for Median of Two Sorted Arrays.

Memory Usage: 13.5 MB, less than 15.49% of Python3 online submissions for Median of Two Sorted Arrays.

Submission Detail

Problem5(Mediam)

• 入力：文字列
• 目的：文字列に含まれる最長の回文(palindrome)を見つけ、その文字列を返す

Manacherのアルゴリズム

回文については有名なアルゴリズムがありました。計算時間はO(n)です。

元論文：A New Linear-Time ``On-Line'' Algorithm for Finding the Smallest Initial Palindrome of a String

Problem6(Medium)

• 入力：任意長の文字列と０以上の整数
• 出力：文字列をジグザグに配置した時の各行を連結したもの（要問題参照）

よく見るとj行に入る文字は 2*numRows を元にして求めることができる。また、numRowsが２以下の時は入力のテキストをそのまま返せばいい。

class Solution(object):
    def convert(self, s, numRows):
        # ジグザグにならないのでそのまま返す
        if numRows <= 1:
            return s
        
        n = len(s)
        if n <= 1:
            return s
        
        # 各行の文字列を連結する
        index = 2*numRows - 2
        res = ''
        for i in range(numRows):
            for j in range(i, n, index):
                res += s[j]
                if i==0:
                    continue
                elif i!=numRows-1 and j+index-i*2<n:
                    res += s[j+index-i*2]
        return res

Problem7(Easy)

• 入力：整数値
• 目的：整数値の順番を反転させて、反転させた整数値が |反転させた整数値| <= 2**31 ならば反転させた整数値を、そうでないならば０を返す

class Solution:
    def reverse(self, x: int) -> int:
        if x >= 0:
            x = int(str(x)[::-1])
        else:
            x = -1*int(str(x)[::-1][:-1])
            
        return (-2147483649<x<2147483649)*x

Runtime: 32 ms, faster than 97.16% of Python3 online submissions for Reverse Integer.

Memory Usage: 13.1 MB, less than 94.50% of Python3 online submissions for Reverse Integer.