Open2023/01/21にコメント追加29

LeetCode 記録

ピン留めされたアイテム

https://leetcode.com/E-dmp/
https://visualgo.net/en

2.Two Sum

function twoSum (nums: number[], target: number): number[] {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] == target) {
        return [i, j]
      }
    }
  }
}

2重ループを卒業したい

ハッシュを学んで解き直す

参考

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]

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

一番最後の要素に来た時

index out of range

となっていたが、

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

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

14.Longest Common Prefix

いやー解けませんでした笑
これは研究

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

配列のアンパック

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

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)　思いっきりハードコーディング！

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

公式の回答があったので読んでみる

set を使ってる

Python しか回答がなかったけど、set型でソートしてる

seen = set()
seen.add(1)
seen.add(2)
seen.add(3)
seen.add(2)

print(seen)   # {1,2,3}

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]

ほんまや！

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

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

83.remove-duplicates-from-sorted-list

解けたけど

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

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

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

Clean Code アジャイルソフトウェア達人の技

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

  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

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

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

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

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

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)

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

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]

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

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

if prices[buypPoint] < prices[sellPoint]:

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

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]

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

参考

    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

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

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