LeetCodeをPython3で何問か解いてみた

GAFAの面接で使用されるとかされないとかの噂(確度は高い)のLeetCodeをやり始めたので、解法を共有します。たまに(?)汚いコードがありますが、ご容赦ください。

Leetcode Problemsの画面

始めて3日ですが、今のところ7問解きました。ゆっくり適当に解いています。

Problems

1. Two Sum

リストとtarget(数値)の合計2つのinputが与えられます。足してtargetになるようにリストから2つの数字を取り出すとき、どのindexかを出力します。(indexの意味が分からない方は調べてみれください)

今見ると汚いコードですが、許してください。。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i+1, len(nums)):
                ans = nums[i] + nums[j]
                if ans == target:
                    return [i, j]

2. Add Two Numbers

この問題、Pythonで解きづらい問題でしたね。最初から書いてある、上から5行目までのコメントアウトされている部分が結構重要です。ListNodeという独自のクラスを設定していて、それを使わないといけません。変わっていて面白いですが、実務には使わなそうな問題でした。(個人の感想です)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        dummy = ListNode()
        cur = dummy
        
        carry = 0
        while l1 or l2 or carry:
            v1 = l1.val if l1 else 0
            v2 = l2.val if l2 else 0
            
            # new digit
            val = v1 + v2 + carry
            # 15
            carry = val // 10  # 10の位が出る
            val = val % 10  # 10で割った余り
            cur.next = ListNode(val)
            
            # update ptrs
            cur = cur.next
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None
            
        return dummy.next

3. Longest Substring Without Repeating Characters

繰り返しのない、最も長いsubstring、つまり部分文字列の長さを出力します。なんとなく競プロっぽい問題。

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # Base condition
        if s == "":
            return 0

        start = 0
        end = 0
        maxLength = 0
        # Set to store unique characters
        unique_characters = set()
        # Loop for each character in the string
        while end < len(s):
            if s[end] not in unique_characters:
                unique_characters.add(s[end])
                end += 1
                maxLength = max(maxLength, len(unique_characters))
            else:  # unique_charactersにs[end]があった場合
                unique_characters.remove(s[start])
                start += 1
        return maxLength

4. Median of Two Sorted Array

2つのリストを連結して、中央値を求める問題。

import numpy as np

class Solution:
    def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
        nums = nums1 + nums2
        return np.median(nums)

なんか面倒だったのでnumpyを使うという楽な道を選んでしまいました。(Pythonを使った実務ではむしろnumpyをこのように適切に素早く使えるスキルの方が重要だったりしますが、使うのと使わないのと”両方”できるのがベストです)

5. Longest Palindromic Substring

与えられた文字列の中から、回文となる部分文字列の中で最も長いものを出力する問題。とてもシンプルです。

class Solution:
    def longestPalindrome(self, s: str) -> str:
        if s == s[::-1]:
            return s
        
        maxLength = 0
        
        for i in range(1, len(s)):
            n = len(s) - i  # substringの長さ
            for j in range(i+1):
                substring = s[j:j+n]
                if substring == substring[::-1]:
                    return substring

7. Reverse Integer

与えられた整数のマイナスより後ろの部分を文字列的に逆にして出力するだけの問題。絶対値が2の31乗より大きい場合は0を返せという問題になっていて、それに気づかず3回もWrong Answerとしてしまった。低評価が多いのはそのせいなんですかね。

class Solution:
    def reverse(self, x: int) -> int:
        s = str(x)
        if len(s) == 1:
            return x
        
        if s[0] == '-':
            s_int = s[1:][::-1]
            s_int = self.remove_zero(s_int)
            s = '-' + s_int
        else:
            s = s[::-1]
            s = self.remove_zero(s)
        
        x = int(s)
        
        if x < -2**31 or 2**31 - 1 < x:
            return 0
        else:
            return x
    
    def remove_zero(self, s):
        while s[0] == '0':
            s = s[1:]
        return s

9. Palindrome Number

9問目です。与えられた整数が回文かどうかを判定する問題。とても簡単でした。

class Solution:
    def isPalindrome(self, x: int) -> bool:
        s = str(x)
        if s == s[::-1]:
            return True
        else:
            return False

とりあえず今のところは以上です。引き続き遊んでみます。

タイトルとURLをコピーしました