LoginSignup
0

More than 1 year has passed since last update.

Leetcode日記

Last updated at Posted at 2022-08-17

Two Sum

解説見ながら解きました。
合計がtargetになるようにlistから2つ数字を取って、それらのindexを返す問題です。

解法

cur: int (現在の数字)
x: int (xとcurの合計がtargetになるような数字)
d: dict (key: nums[i], value: i)

  • for文でnumsを回す
  • curとxを求める
  • もし、xがdにあったら、
    • i: numsに含まれる、現在の数字(cur)のindex番号
    • d.get(x): numsに含まれる、xのindex番号
  • dに要素を追加
    • key: nums[i]
    • value: i
class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        # cur + x = target
        # x = target - cur
        d = {}
        # key : nums[i] 
        # value : i
        for i in range(len(nums)):
            cur = nums[i]
            x = target - cur
            if x in d:
                return [i, d.get(x)]
            d[nums[i]] = i

Add Two Numbers

解説見ながら解きました。
単方向リストをそれぞれ足していき、足した結果が10を超える場合は繰り上げする問題です。
この方の記事わかりやすいです

解法

carry: int (繰り上げ)
val1: int (l1の値)
val2: int (l2の値)

  • while文でl1、l2、carryがなくなるまで回す
  • val1、val2に値をそれぞれ代入する(l1、l2に値がない場合は0)
  • 合計 sum = val1 + val2 + carry
  • carry = (val1 + val2 + carry) / 10
  • sumの10で割ったあまりの値を持つ新しいノードを作成し、カレントノードのnextに設定し、カレントノードをnextに進める
  • l1、l2を次の値に進める
# 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: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
        # plus 1 to next digit 
        carry = 0
        dummy_head = ListNode(0)
        current = dummy_head

        while l1 or l2 or carry:
            val1 = l1.val if l1 else 0
            val2 = l2.val if l2 else 0
            current.next = ListNode((val1 + val2 + carry) % 10)
            current = current.next
            
            if (val1 + val2 + carry) >= 10:
                carry = 1
            else:
                carry = 0
            
            l1 = l1.next if l1 else None
            l2 = l2.next if l2 else None

        return dummy_head.next

Longest Substring Without Repeating Characters

解法1 Brute Force

TLEになります

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        result = 0
        for i in range(len(s)):
            for j in range(i,len(s)):
                # インデックスがi番目からj番目までの文字列sが、重複していない場合
                if self.check(s, i, j):
                    # 今までの最大値resultと、インデックスがi番目からj番目までの文字数(j-i+1)を比較し、大きい方をresultに代入
                    result = max(result, j - i + 1)
        return result
        
    # インデックスがstart番目からend番目までの文字列sが、重複していないかどうか?
    # "abc" -> True
    # "aab" -> False
    def check(self, s: str, start: int, end: int):
        list_s = []
        for i in range(start, end+1):
            if s[i] not in list_s:
                list_s.append(s[i])
            else:
                return False
        return True

解法2 Sliding Window

文字列sが与えられた時、重複を許さない、かつ連続した文字列の数の最大値を求める問題です

chars: Conter(Sliding Window内で何回その文字が出現したか、カウントする)
left: int(Sliding Windowの範囲を狭める)
right: int(Sliding Windowの範囲を拡大する)
res: int(重複を許さない、連続した文字列の数の最大値)
r: str(文字列sのright番目の文字s[right])
l: str(文字列sのleft番目の文字s[left])

  1. rightは文字列sの長さを超えずに、Sliding Windowの範囲を拡大する
  2. Sliding Windowの範囲に何回その文字が出現したか、カウントするために、文字列sのright番目の文字rをcharsに追加する
    • 文字列sのright番目の文字s[right]を文字rに代入
    • 文字rをcharsに登録する
  3. もし文字rの出現回数が1回以上だったら、Sliding Windowの範囲を狭める
    • 文字列sのleft番目の文字s[left]を文字lに代入
    • Sliding Windowの範囲を狭めたので、出現回数をカウントしているcharsから狭めた文字のカウントを1減らす
    • leftを1つスライドさせる
  4. 現在のSliding Windowの範囲に重複する文字は無くなったので、Sliding Windowの範囲の最大値を求める
  5. rightを1つスライドさせる
from collections import Counter
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        # we need to declare a direct access table to record how many times each character appears in the sliding window
        # So we declare the table as an int array, 
        # and all the characters can be encoded into integers
        
        chars = Counter()
        #left :contract the window
        #right :expand the window
        left = 0
        right = 0
        
        res = 0
        # slide the window
        while right < len(s):
        
            # obtain the character at the right boundary
            # we can add one more time for this character's occurence
            # we can keep extending the window
            r = s[right]
            chars[r] += 1

            # Before extending the window, we shold firstly consider contracting the window
            # So if the character at the right boundary appears more than once,
            # we need to keep contracting the window
            # To contract the window, we should get the character at the left boundary,
            # and to reduce it's occurrence
            # Then move forward the left pointer
            while chars[r] > 1:
                l = s[left]
                chars[l] -=1
                left += 1
        
            # after contracting the window
            # we can make sure that there is no duplicate character in the current window
            res = max(res, right - left + 1)
            right += 1

        return res

解法3 Sliding Window Optimized

文字列sが与えられた時、重複を許さない、かつ連続した文字列の数の最大値を求める問題です

mp: dict(key: 文字、 value: 文字の現在のindex+1)
i: int(Sliding Windowの範囲を狭める)
j: int(Sliding Windowの範囲を拡大する)
res: int(重複を許さない、連続した文字列の数の最大値)
n: int(文字列sの長さ)

r: str(文字列sのright番目の文字s[right])
l: str(文字列sのleft番目の文字s[left])

  1. jは文字列sの長さnを超えずに、Sliding Windowの範囲を拡大する
  2. もしs[j]が既に出現されていたら、sliding windowの範囲を重複しない範囲に狭める
    • iを重複した文字s[j]の前回のindex+1と現在のiを比較し、iを文字列が重複しないようにスライドさせる
  3. 現在のSliding Windowの範囲に重複する文字は無くなったので、Sliding Windowの範囲の最大値を求める
  4. mpにkey: 文字s[j], value: 文字s[j]の現在のindex+1を登録
    • +1する理由---> 次に文字s[j]が重複した際に、iをmp[s[j]]に移動することで、重複しないようにsliding windowの範囲を狭めることができる
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        n = len(s)
        res = 0
        # mp stores the current index + 1 
        # key : 文字
        # value : 文字の現在のindex + 1
        mp = {}
        # i: contract the window
        # j: extend the window
        i = 0
        for j in range(n):
            # s[j]が既に出現されていたら
            if s[j] in mp:
                # sliding window の幅を狭める
                # iをmp[s[j]]と現在のiを比較し、大きい方にiをスライドさせる
                # mp[s[j]] : 重複した文字s[j]の前回のindex+1
                # +1する理由は重複しないように、重複した文字s[j]の次の文字を指すindexを指定するため
                i = max(mp[s[j]], i)
            res = max(res, j - i + 1)
            # mp に
                # key: 文字s[j], value: 文字s[j]の現在のindex + 1
            # を登録
            mp[s[j]] = j + 1
        return res

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
0