Zenn
Open29

LeetCode 記録

Python
#
tech
LeetCode
eidmeidm

9. Palindrome Number

    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        x = str(x)
        length = len(x)
        mid = length / 2
        for i in range(mid + 1):
            if x[i] != x[-(i + 1)]:
                return False
        return True 


mid = math.floor(length / 2)

# TypeError: range() integer end argument expected, got float.

参考
上位の人の回答を覗くとスライスをうまく使っている人が多い

return str(x) == str(x)[::-1]
eidmeidm

13. Roman to Integer

hashMap長いな...。

こういうのもう少し綺麗に書きたい。

    def romanToInt(self, s: str) -> int:
        
        sumOfValue = 0
        hashMap = {
                 'IV': 4,
                 'IX': 9,
                 'XL': 40,
                 'XC': 90,
                 'CM': 900,
                 'CD': 400,
                 "I":1,
                 "V":5,
                 "X":10,
                 "L":50,
                 "C":100,
                 "D":500,
                 "M":1000,
             }

        for i in hashMap:
            count = s.count(i)
            sumOfValue += hashMap[i] * count
            s = s.replace(i, '')
            
        return sumOfValue

参考

    def romanToInt(self, s: str) -> int:
        translations = {
            "I": 1,
            "V": 5,
            "X": 10,
            "L": 50,
            "C": 100,
            "D": 500,
            "M": 1000
        }
        number = 0
        s = s.replace("IV", "IIII").replace("IX", "VIIII")
        s = s.replace("XL", "XXXX").replace("XC", "LXXXX")
        s = s.replace("CD", "CCCC").replace("CM", "DCCCC")
        for char in s:
            number += translations[char]
        return number
eidmeidm

一番最後の要素に来た時

index out of range

となっていたが、

return sumOfValue + hashMap[s[len(s) - 1]]

で最後の要素だけ加算して返すのも一つの解

eidmeidm

14.Longest Common Prefix

いやー解けませんでした笑
これは研究
https://leetcode.com/problems/longest-common-prefix/solutions/323909/python-simple-solution-implementing-vertical-scanning/?languageTags=python3

eidmeidm

何をやっているのか読み解いてみる。
基本的な挙動確認

配列のアンパック

strs = ["flower","xlow","flowers"]
print(*strs) # flower xlow flowers

zip の挙動

for i in zip("flower","xlow","flowers"):
    print(i)
#('f', 'x', 'f')
#('l', 'l', 'l')
#('o', 'o', 'o')
#('w', 'w', 'w')

zip に関しては配列で使うことが多いので文字列だとこんな挙動になるんだと勉強なりました。
挙動がわかったところでコードを見てみる

result = []
for s in zip(*strs):
    if len(set(s)) != 1:
        break
        result.append(s[0])
return "".join(result)

for s in zip(*strs):

文字列 格納の配列をアンパックして文字列をzipに渡している。

('f', 'x', 'f')
('l', 'l', 'l')
('o', 'o', 'o')
('w', 'w', 'w')

コメントで

 # Create one iterator per string using zip, it will stop at the shortest string

と書いてくれているのでzipの性質上最小文字数基準になる。

if len(set(s)) != 1

ここで重複したものを削除した長さが1ではなかったら(つまり文字が一致しなかったら)
処理を抜ける。それ以外はリストにいれてjoin でreturn

eidmeidm

Happy Number

function isHappy(n: number): boolean {

    if (n === 0) return false;

    while (n != 1 && n != 4) {

        let sumOfNumber: number = 0
        let dividedNum: number = n

        // 割り続けたらdividedNum は 最終的に0
        while (dividedNum > 0) {

            sumOfNumber += (dividedNum % 10) * (dividedNum % 10);
            dividedNum = Math.floor(dividedNum / 10)
        }
        n = sumOfNumber
    }
    return n == 1
};

(n != 1 && n != 4)　思いっきりハードコーディング！

おしかったけどダメですね.....

公式の回答があったので読んでみる
https://leetcode.com/problems/happy-number/solutions/421162/happy-number/

eidmeidm

Intersection of Two Arrays

class Solution:
    def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:

        hashmap = {}
        sortedList = []

        # create hash
        for i in nums1:
            if i in hashmap: hashmap[i] += 1
            else:hashmap[i] = 1
        
        for j in nums2:
            if j in hashmap and hashmap[j] > 0: 
                hashmap[j] -= 1
                sortedList.append(j)

        return set(sortedList)

参考

def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]: 
a1=set(nums1) a2=set(nums2) 
return list(a1 & a2)

return list(a1 & a2)

↑の部分ですね。そんな書き方あるんだ！って感じ

試してみる

    a = set([1,2,3])
    b = set([1,2,4])

    print(list(a & b))  #[1, 2]

ほんまや！

eidmeidm

First Unique Character in a String

これはすんなり解けた。


    def firstUniqChar(self, s: str) -> int:
        
        """
        :type s: string
        :rtype: int
        """

        hashmap = {}

        # create hashmap
        for i in range(0,len(s)):
            if s[i] not in hashmap:
                hashmap[s[i]] = 1
            else: hashmap[s[i]] += 1

        for i,j in enumerate(hashmap):
            if hashmap[j] == 1: return list(s).index(j)
        return -1
eidmeidm

141. Linked List Cycle

問題の意味と入力値がなんなのか理解するまで非常に時間がかかった💦
けど連結リストにも慣れて来た

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:

        slowPointer = head
        fastPointer = head

        while fastPointer is not None:

            if fastPointer.next != None:
                fastPointer = fastPointer.next.next
            else: 
                return False    

            slowPointer = slowPointer.next

            if fastPointer == slowPointer:
                return True

        return False
eidmeidm

83.remove-duplicates-from-sorted-list

解けたけど

反省点しかない問題でした。

1...コードがわかりにくい
2...計算量多い
3. コードがわかりにくい
4. コードがry

新たに配列を登場させてしまいました。
学びとしてはwhile文の条件設定が苦手だとわかったこと。
唯一成長したと思うところはlengthの長さが0と1のケースを考えられたことくらい。

Clean Code アジャイルソフトウェア達人の技
https://www.amazon.co.jp/Clean-Code-アジャイルソフトウェア達人の技-Robert-C-Martin/dp/4048930591

読んでみようと思っているもののそもそも解き方の工夫ができればもう少し見やすくなるのでは？って感じなので今買うか悩み中

  def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:

     """
     this solution is accepted but not clean code...
     """
        
     iterator = head
     arr = []

     # walk ListNode
     while iterator is not None:

         if iterator.val not in arr:
             arr.append(iterator.val)
         iterator = iterator.next

     length = len(arr)

     if length == 0: return head
     elif length == 1 : length += 1

     # create newNodeList
     newNodehead = ListNode(arr[0])
     currentNode = newNodehead

     for i in range(1,len(arr)):
         node = ListNode(arr[i])
         currentNode.next = node
         currentNode = node

     return newNodehead
eidmeidm

206. Reverse Linked List

解けませんでした！すごい悔しい...

https://youtu.be/G0_I-ZF0S38

    def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:

        prev, curr = None,head

        while curr:

            nextNode = curr.next
            curr.next = prev
            prev = curr
            curr = nextNode

        return prev
eidmeidm

20. valid-parentheses.py

206は解けなかったけどこれは解けました。同じeasyなのに...


    def isValid(self, s: str) -> bool:
       
       stack = []
        
        for i in range(0,len(s)):
            if s[i] == "{" or s[i] == "(" or s[i] == "[" :
                 stack.append(s[i])
            elif s[i] == "}" and len(stack) > 0 and stack[len(stack) - 1] == "{":
                 stack.pop(len(stack) - 1)
            elif s[i] == ")" and len(stack) > 0 and stack[len(stack) - 1] == "(": 
                stack.pop(len(stack) - 1)
            elif s[i] == "]" and len(stack) > 0 and stack[len(stack) - 1] == "[": 
                stack.pop(len(stack) - 1)
            else:
                return False
                
        return len(stack) == 0
eidmeidm

21.merge-two-sorted-lists.py

これはRecusionCS で似たような問題を解いたことがあったのでいい復習になりました。
dummyNode を作るところは最初思いつかなかった

    def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:

        iterator1 = list1
        iterator2 = list2
        dummyNode = ListNode()
        edge = dummyNode

        while iterator1 and iterator2:

            if iterator1.val < iterator2.val: 
                edge.next = iterator1
                iterator1 = iterator1.next
            else:
                 edge.next = iterator2
                 iterator2 = iterator2.next

            edge = edge.next

        if iterator1 is not None: edge.next = iterator1    
        if iterator2 is not None: edge.next = iterator2   
        
        return dummyNode.next
eidmeidm

58. Length of Last Word

今まで解いて来たLeetCodeの問題で学んだことを使えたので直ぐに解けました😃

 def lengthOfLastWord(self, s: str) -> int:

        """
        :type s: str
        :rtype: int
        """
        lastWordLength = 0
        
        # 最後の文字以降の空白があれば削除
        # 文字列逆転
        for i in range(1,len(s)):
            if s[len(s) - i] != ' ':
                s = s[:(len(s) - i + 1)][::-1]
                break

        for j in s:
            if j == ' ': break
            else: lastWordLength += 1

        return lastWordLength
eidmeidm

35.search-insert-position

😃

def searchInsert(self, nums: List[int], target: int) -> int:
    if target in nums:
        return nums.index(target)
    else:
        nums.append(target)
        return sorted(nums).index(target)
eidmeidm

136.single-number

きっと一行で解いている人がいるんだろうと思ったら案の定いたw

    def singleNumber(self, nums: List[int]) -> int:
        
        hashmap = {}

        for i in range(0,len(nums)):
            if nums[i] in hashmap: hashmap[nums[i]] += 1
            else: hashmap[nums[i]] = 1

        for key in hashmap.keys():
            if hashmap[key] == 1: return key
eidmeidm

66 plus-one.py

2時間くらい考えてようやく解けました..ただ解けただけでコードはひどいw

    def plusOne(self, digits: List[int]) -> List[int]:

        i = -1
        counter = 0
        length = len(digits)
   
        if digits[-1] != 9:
            return digits[:-1] + [digits[-1] + 1]

        while length != 0:
            if digits[i] != 9:
                break
            i -= 1
            counter += 1
            length -= 1 

        """
        Listが9だけで構成されていた場合
        [9,8,9]のように9以外の要素がある場合
        """
        if counter == len(digits):
             return [1] + counter * [0]
        else: 
            return digits[:-(counter + 1)] + [digits[-(counter + 1)] + 1] + counter * [0]
eidmeidm

121.best-time-to-buy-and-sell-stock

解けませんでした。。今までで一番悔しい💦
下記動画を参考にして回答。悔しい！


    def maxProfit(self, prices: List[int]) -> int:

        buypPoint,sellPoint = 0,1

        maxProift = 0

        while sellPoint < len(prices):

            if prices[buypPoint] < prices[sellPoint]:
                profit = prices[sellPoint] - prices[buypPoint]
                maxProift = max(maxProift,profit)
            else:
                buypPoint = sellPoint

            sellPoint += 1

        return maxProift
eidmeidm

最小値ってどこで更新してるのか気づけなかった.

if prices[buypPoint] < prices[sellPoint]:

普通にここで更新してたw

eidmeidm

169. Majority Element

解き方自体は簡単でしたが、lamdaのsortは挙動がイマイチだったので記事を参考に。


  def majorityElement(self, nums: List[int]) -> int:

    hashMap = {}

    for i in range(0,len(nums)):
        if nums[i] not in hashMap: hashMap[nums[i]] = 1
        else: hashMap[nums[i]] += 1

    sortedMap = sorted(hashMap.items(), key = lambda i: i[1], reverse=True)
    return sortedMap[0][0]
eidmeidm

345.reverse-vowels-of-a-string.py

少し間が開きましたがLeetCode再開！とりあえず1発目は解けました〜

def reverseVowels(self, s: str) -> str:
        
    stack = []
    i = 0
    for k in s:
        stack.append(k)
            
    while stack:
        s[i] = stack.pop()
        i += 1
eidmeidm

参考

    def reverseString(self, s: List[str]) -> None:
        a=int(len(s)/2)
        b=len(s)-1
        for i in range(0,a):
            s[i],s[b]=s[b],s[i]
            b-=1

なるほど..外側から順に入れ替えるのか

eidmeidm

283.move-zeroes.py

いやー激闘でした..完全にハマりましたね..笑
解けた時はカフェで声出そうでしたw

新しい配列を作らないところが条件で、特にelse以下が思いつかなかった


    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """

        i = 0
        length = len(nums)

        while length > 0:

            if nums[i] == 0:
                nums.append(nums[i])
                nums.pop(i) 
                length -= 1
            else:
                i += 1
                length -= 1