Two Sum
解説見ながら解きました。
合計がtargetになるようにlistから２つ数字を取って、それらの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
解説見ながら解きました。
単方向リストをそれぞれ足していき、足した結果が１０を超える場合は繰り上げする問題です。
この方の記事わかりやすいです
解法
carry: int (繰り上げ)
val1: int （l1の値）
val2: int （l2の値）
- while文でl1、l2、carryがなくなるまで回す
- val1、val2に値をそれぞれ代入する（l１、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
解法１ 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])
- rightは文字列sの長さを超えずに、Sliding Windowの範囲を拡大する
- Sliding Windowの範囲に何回その文字が出現したか、カウントするために、文字列sのright番目の文字rをcharsに追加する
- 文字列sのright番目の文字s[right]を文字rに代入
- 文字rをcharsに登録する
- もし文字rの出現回数が1回以上だったら、Sliding Windowの範囲を狭める
- 文字列sのleft番目の文字s[left]を文字lに代入
- Sliding Windowの範囲を狭めたので、出現回数をカウントしているcharsから狭めた文字のカウントを１減らす
- leftを１つスライドさせる
- 現在のSliding Windowの範囲に重複する文字は無くなったので、Sliding Windowの範囲の最大値を求める
- rightを１つスライドさせる
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])
- jは文字列sの長さnを超えずに、Sliding Windowの範囲を拡大する
- もしs[j]が既に出現されていたら、sliding windowの範囲を重複しない範囲に狭める
- iを重複した文字s[j]の前回のindex+1と現在のiを比較し、iを文字列が重複しないようにスライドさせる
- 現在のSliding Windowの範囲に重複する文字は無くなったので、Sliding Windowの範囲の最大値を求める
- mpにkey: 文字s[j], value: 文字s[j]の現在のindex+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