Closed13
LeetCode
えみ投稿フォーマット
- 問題：
### 自分の解答
```python
```
### 良いと思った解答
```python
```
### 勉強になった記事
自分の解答
文字列に変換して、最初と最後の値を比較
class Solution:
def isPalindrome(self, x: int) -> bool:
x = str(x)
lengs = len(x)
if lengs == 1:
return True
for i in range(lengs):
if lengs/2 >= i+1:
if x[lengs-i-1] != x[i]:
return False
else:
return True
良いと思った解答
元の数値を半分入れたxと逆向きの数値を半分入れたreversedHalfを比較する。
奇数の場合はreversedHalfの値から一桁減らして比較する。
class Solution:
def isPalindrome(self, x: int) -> bool:
if x == 0:
return True
if x < 0 or x % 10 == 0:
return False
reversedHalf = 0
while x > reversedHalf:
reversedHalf = reversedHalf*10 + x%10
x//=10
return ((x == reversedHalf) or (x == reversedHalf//10))
短いコード
スライスで数値を逆向きの文字列に変換する
class Solution(object):
def isPalindrome(self, x):
original = str(x)
reversed = original[::-1]
return original == reversed
勉強になった記事
えみ自分の解答
辞書を用いて左と右の数値の大小を比べる。
左の数値が小さければ、右の数値から引いて足す
class Solution:
def romanToInt(self, s: str) -> int:
total = 0
dic = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
a = 0
if len(s) == 1:
return dic[s]
for i in range(1, len(s)):
if a == 0:
if dic[s[i-1]] >= dic[s[i]]:
total += dic[s[i-1]]
else:
total += dic[s[i]] - dic[s[i-1]]
a = 1
else:
a = 0
if i == len(s) - 1 and a == 0:
total += dic[s[i]]
# print(total)
return total
良いと思った解答
私が書いたコードは、前の値との比較を行ったが、次の値との比較を行うことで最後の値も問題なく足すことができ、一文字の場合にも対応できる
わざわざ正しい数値にしてから計算するのではなく、加減算の判別をするだけでよかった
class Solution:
def romanToInt(self, s: str) -> int:
total = 0
dic = {'I':1, 'V':5, 'X':10, 'L':50, 'C':100, 'D':500, 'M':1000}
for i in range(0, len(s)-1):
if dic[s[i]] < dic[s[i+1]]:
total -= dic[s[i]]
else:
total += dic[s[i]]
return total + dic[s[-1]]
勉強になった記事
えみ自分の解答
二つずつ比較していき残ったものを出力する
一致している個数をカウントし、最後に0からカウント数までの文字列を出力する
class Solution:
def longestCommonPrefix(self, strs: List[str]) -> str:
s = copy.deepcopy(strs[0])
count = 0
for i in range(1, len(strs)):
if s == "":
break
for j in range(len(s)):
if j == len(strs[i]):
break
elif strs[i][j] == s[j]:
count += 1
else:
break
s = copy.deepcopy(s[0:count])
count = 0
return s
良いと思った解答
勉強になった記事
えみ自分の解答
閉じ括弧を探してそれに対応する開き括弧があるかどうかを判断した
class Solution:
def isValid(self, s: str) -> bool:
dec = {')':'(', '}':'{', ']':'['}
count = 0
if len(s) == 2:
if s[1] in dec.keys():
return s[0] == dec[s[1]]
return False
while len(s) > count:
if s[count] in dec.keys():
if count == 0:
return False
elif s[count-1] not in dec[s[count]]:
return False
elif count == 1:
s = s[2:]
count -= 2
else:
s = s[:count-1] + s[count+1:]
count -= 2
count += 1
if s == "":
return True
return False
良いと思った解答
スタックを利用して、閉じ括弧があればスタックと比較して該当する開き括弧があるかどうかを判断する
class Solution:
def isValid(self, s: str) -> bool:
if len(s)%2 == 1:
return False
stack = []
dec = {')':'(', '}':'{', ']':'['}
for i in s:
if i in '([{':
stack.append(i)
elif i in ')]}':
if not stack or dec[i] != stack.pop():
return False
return not stack
勉強になった記事
えみ良いと思った解答
今回はListNodeを用いる問題で自分で解くことができなかった。
headに追加するリストを選択し、リストの中すべてを追加していく。
追加したリストの値は消しておく。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
# 両方のリストが空の場合、空のリストを返す
if not list1 and not list2:
return None
# 一方のリストが空の場合、もう一方のリストを返す
elif not list1:
return list2
elif not list2:
return list1
# リストのヘッドを決定
if list1.val < list2.val:
head = list1
list1 = list1.next
else:
head = list2
list2 = list2.next
# 現在のノードをヘッドに設定
current_node = head
# どちらかのリストが空になるまでループ
while list1 and list2:
print(head)
if list1.val < list2.val:
current_node.next = list1
list1 = list1.next
else:
current_node.next = list2
list2 = list2.next
current_node = current_node.next
# どちらかのリストがまだ要素を持っている場合、それを追加
current_node.next = list1 if list1 else list2
return head
別解
headを指定せずに追加していく
最後に次の値からを指定してreturnする。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
ask = ListNode()
curr = ask
while list1 and list2:
if list1.val < list2.val:
curr.next = list1
list1 = list1.next
else:
curr.next = list2
list2 = list2.next
curr = curr.next
if list1:
curr.next = list1
elif list2:
curr.next = list2
return ask.next
勉強になった記事
えみ自分の解答
pythonのsetを用いてlistの重複を削除した。
しかし、元のnumsが変更されないために重複が削除されていない値が出てしまう。
間違い
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
nums = copy.deepcopy(list(set(nums)))
print(len(nums))
return len(nums)
ask = set(nums)
print(len(ask))
a = len(ask)
return a
良いと思った解答
class Solution:
def removeDuplicates(self, nums: List[int]) -> int:
k = 0
for x in nums:
if k == 0 or x != nums[k - 1]:
nums[k] = x
k += 1
print(nums)
return k
勉強になった記事
えみ自分の解答
さっきの問題同様、上書きで値を修正していく
class Solution:
def removeElement(self, nums: List[int], val: int) -> int:
k = 0
for i in nums:
if i != val:
nums[k] = i
k += 1
return k
自分の解答
一致しなければ-1
一致する部分を探すにはpythonの位置取得: re.search()を利用した。
re.search()で位置の最初と最後まで取得可能
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
if needle not in haystack:
return -1
return re.search(needle, haystack).start()
別解
find()メソッドで文字列中の特定の文字列の位置を取得できる
class Solution:
def strStr(self, haystack: str, needle: str) -> int:
return haystack.find(needle)
勉強になった記事
えみ自分の解答
index()でtargetが含まれている場合のインデックスを取得する
含まれていない場合は、最初と最後に入る場合のみ先に判定し、そのほかは地道に探索する
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
if target in nums:
return nums.index(target)
if target < nums[0]:
return 0
elif nums[-1] < target:
return len(nums)
for i in range(1, len(nums)):
if nums[i] > target:
return i
良いと思った解答
targetが含まれていない時の探索を半分ずつ行うことで探索する量が減る
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
l = 0
r = len(nums)
if target in nums:
return nums.index(target)
while l < r:
m = (l + r) // 2
if nums[m] < target:
l = m + 1
else:
r = m
return l
勉強になった記事****
えみ自分の解答
スペースがない場合は、文字列の長さを返す
スペースがある場合は、文字列の後ろから見ていきスペースが現れるまでの文字の個数をカウントしていく
class Solution:
def lengthOfLastWord(self, s: str) -> int:
a = ''
count = 0
if ' ' not in s:
return len(s)
for i in range(1, len(s)+1):
a = s[-i]
if a!= ' ':
count += 1
elif a == ' ' and count != 0:
return count
return count
良いと思った解答
文字列を後ろから見ていきポインタを移動させていく
class Solution:
def lengthOfLastWord(self, s: str) -> int:
length = 0
n = len(s)
while n > 0 and s[n-1] == ' ':
n -= 1
while n > 0 and s[n-1] != ' ':
length += 1
n -= 1
return length
勉強になった記事
えみ自分の解答
末尾が9の時はリストからint型に変換し、＋1してからもう一度リスト型に戻す
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
ask = []
a = 0
if digits[-1] != 9:
digits[-1] += 1
return digits
else:
for i in digits:
a *= 10
a += i
a += 1
ask = [int(x) for x in list(str(a))]
return ask
良いと思った解答
末尾が9の場合は0にし、9でなくなったら＋1をして出力する
[9,9]のような場合は、[1]と[0]×len([9,9])で出力する
class Solution:
def plusOne(self, digits: List[int]) -> List[int]:
for i in range(len(digits)):
if digits[~i] < 9:
digits[~i] += 1
return digits
digits[~i] = 0
return [1] + [0] * len(digits)
勉強になった記事
このスクラップは3ヶ月前にクローズされました