Open29

# LeetCode 記録

eidm

### 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]
}
}
}
}
``````

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

eidm

### 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]
``````
eidm

### 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

``````
eidm

``````index out of range
``````

となっていたが、

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

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

eidm

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

eidm

#### 配列のアンパック

``````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):

``````('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ではなかったら(つまり文字が一致しなかったら)

eidm

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

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

eidm

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

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

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

#### 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]
``````

ほんまや！

eidm

### 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

``````
eidm

#### 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
``````
eidm

## 解けたけど

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

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

``````
eidm

#### 206. Reverse Linked List

``````    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

``````
eidm

#### 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

``````
eidm

#### 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

``````
eidm

#### 58. Length of Last Word

`````` 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

``````
eidm

#### 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)
``````
eidm

#### 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
``````
eidm

#### 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]

``````
eidm

#### 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

``````
eidm

``````if prices[buypPoint] < prices[sellPoint]:
``````

eidm

#### 169. Majority Element

``````
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]

``````
eidm

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

``````def reverseVowels(self, s: str) -> str:

stack = []
i = 0
for k in s:
stack.append(k)

while stack:
s[i] = stack.pop()
i += 1
``````
eidm

``````    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
``````

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

eidm

283.move-zeroes.py

いやー激闘でした..完全にハマりましたね..笑

``````
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

``````