이것도 이전에 풀어놓은건데 오늘 한번에 보따리를 풀어 봄.
Self 모의고사 문제
- Letter Combinations of a Phone Number
https://leetcode.com/problems/letter-combinations-of-a-phone-number/
Computational Thinkking 문제: Recursion을 구현할 수 있는가 테스트
hashMap = {
'2': 'abc',
'3': 'def',
'4': 'ghi',
'5': 'jkl',
'6': 'mno',
'7': 'pqrs',
'8': 'tuv',
'9': 'wxyz'
}
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
ans = []
if digits == '':
return ans
def comb_track(_digits, _ans):
if _digits == '':
ans.append(_ans)
return
for c in hashMap[_digits[0]]:
comb_track(_digits[1:], _ans + c)
comb_track(digits, '')
return ans
- Find First and Last Position of Element in Sorted Array
https://leetcode.com/problems/find-first-and-last-position-of-element-in-sorted-array/
Binary Search의 변형인 Bisect 구현 능력 테스트
from bisect import bisect_left, bisect_right
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
if not nums: return [-1, -1]
_s = bisect_left(nums, target)
if _s == len(nums) or nums[_s] != target:
return [-1, -1]
_e = bisect_right(nums, target, _s, len(nums))
return [_s, _e - 1]직접 구현하면 다음과 같이 구현한다.
bisect는 어떤 target 값을 집어 넣을 index를 찾는것임을 생각하면 된다.
bisect_right(0, len(nums)) 가 되는 이유는 최대 len(nums) 위치에 index를 집어넣어야 할 수 있기 때문에 다음과 같은 범위로 탐색을 해야함. 또한, 이와 관련해서 주목할 점이 nums[mid] > target 일때 mid 까지도 포함 시켜야 된다.
from bisect import bisect_right
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def bisect_left(s, e):
while s < e:
mid = (s + e) // 2
if nums[mid] < target:
s = mid + 1
else:
e = mid
return s
def bisect_right(s, e):
"""Find the insertion point to right most. """
while s < e:
mid = (s + e) // 2
if nums[mid] > target:
e = mid
else:
s = mid + 1
return s
left, right = bisect_left(0, len(nums) - 1), bisect_right(0, len(nums)) - 1
# print(left, right)
return [
left if left < len(nums) and nums[left] == target else -1,
right if 0 <= right < len(nums) and nums[right] == target else -1
]