class Solution:
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
mid = left + (right - left) // 2
if nums[mid] == target:
return mid
# right order from mid to right
if nums[mid] < nums[right]:
if nums[mid] < target <= nums[right]:
left = mid + 1
else:
right = mid - 1
# right order from left to mid
else:
if nums[left] <= target < nums[mid]:
right = mid - 1
else:
left = mid + 1
return -1mid = left + (right - left) // 2
mid = (left + right) // 2 과 동일하되, 오버플로우 문제 회피 위함. 파이썬의 경우 비교적 자유로움.
'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 153. Find Minimum in Rotated Sorted Array (0) | 2023.05.02 |
|---|---|
| [Leetcode] 74. Search a 2D Matrix (0) | 2023.05.01 |
| [Leetcode] 34. Find First and Last Position of Element in Sorted Array (0) | 2023.05.01 |
| [Leetcode] 17. Letter Combinations of a Phone Number (0) | 2023.05.01 |
| [Leetcode] 16. 3Sum Closest (0) | 2023.05.01 |
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
left, right = 0, len(nums) - 1
answer = [-1, -1]
while left <= right:
if answer[0] != -1 and answer[1] != -1:
break
if target > nums[left]:
left += 1
elif target == nums[left]:
answer[0] = left
if target < nums[right]:
right -=1
elif target == nums[right]:
answer[1] = right
return answer'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 74. Search a 2D Matrix (0) | 2023.05.01 |
|---|---|
| [Leetcode] 33. Search in Rotated Sorted Array (0) | 2023.05.01 |
| [Leetcode] 17. Letter Combinations of a Phone Number (0) | 2023.05.01 |
| [Leetcode] 16. 3Sum Closest (0) | 2023.05.01 |
| [Leetcode] 15. 3Sum (0) | 2023.05.01 |
Solution 1. product
from itertools import product
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
phone = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
values = [phone[d] for d in digits]
comb = [''.join(val) for val in product(*values)]
return comb if len(comb) != 1 else []Solution 2. BFS
class Solution:
def letterCombinations(self, n: str) -> List[str]:
if n == '':
return []
options = ["", "", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"]
queue = deque([""])
for digit in n:
digit = int(digit)
for _ in range(len(queue)):
curr = queue.popleft()
for letter in options[digit]:
queue.append(curr + letter)
return queueSolution 3. Backtracking
class Solution:
def letterCombinations(self, digits: str) -> List[str]:
phone = {
"2": "abc",
"3": "def",
"4": "ghi",
"5": "jkl",
"6": "mno",
"7": "pqrs",
"8": "tuv",
"9": "wxyz"
}
result = set()
def backtrack(index, chosen):
if index >= len(digits):
if chosen:
result.add(chosen)
return
for s in phone[digits[index]]:
backtrack(index+1, chosen + s)
backtrack(0, "")
return sorted(result)'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 33. Search in Rotated Sorted Array (0) | 2023.05.01 |
|---|---|
| [Leetcode] 34. Find First and Last Position of Element in Sorted Array (0) | 2023.05.01 |
| [Leetcode] 16. 3Sum Closest (0) | 2023.05.01 |
| [Leetcode] 15. 3Sum (0) | 2023.05.01 |
| [Leetcode] 1. Two Sum (0) | 2023.05.01 |
15. 3Sum 과 유사
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
n = len(nums)
diff = float('inf')
res = 0
for i in range(n - 2):
left = i + 1
right = n - 1
while left < right:
s = nums[left] + nums[right] + nums[i]
if abs(target - s) < diff:
diff = abs(target - s)
res = s
if s < target:
left += 1
else:
right -= 1
return res'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 34. Find First and Last Position of Element in Sorted Array (0) | 2023.05.01 |
|---|---|
| [Leetcode] 17. Letter Combinations of a Phone Number (0) | 2023.05.01 |
| [Leetcode] 15. 3Sum (0) | 2023.05.01 |
| [Leetcode] 1. Two Sum (0) | 2023.05.01 |
| [Leetcode] 12. Integer to Roman (0) | 2023.05.01 |
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
answer = set()
n, p, z = [], [], []
for num in nums:
if num > 0:
p.append(num)
elif num < 0:
n.append(num)
else:
z.append(num)
N, P = set(n), set(p)
if z:
for num in P:
if -1 * num in N:
answer.add(( -1 *num, 0, num ))
if len(z) >= 3:
answer.add((0, 0, 0))
for i in range(len(n)):
for j in range(i+1, len(n)):
target = -1 * (n[i] + n[j])
if target in P:
answer.add(tuple(sorted([n[i], n[j], target])))
for i in range(len(p)):
for j in range(i+1, len(p)):
target = -1 * (p[i] + p[j])
if target in N:
answer.add(tuple(sorted([target, p[i], p[j]])))
return answer'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 17. Letter Combinations of a Phone Number (0) | 2023.05.01 |
|---|---|
| [Leetcode] 16. 3Sum Closest (0) | 2023.05.01 |
| [Leetcode] 1. Two Sum (0) | 2023.05.01 |
| [Leetcode] 12. Integer to Roman (0) | 2023.05.01 |
| [Leetcode] 202. Happy Number (0) | 2023.04.27 |
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
complements = {}
for i, x in enumerate(nums):
c = target - x
if x in complements:
return [complements[x], i]
complements[c] = i
return [-1, -1]'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 16. 3Sum Closest (0) | 2023.05.01 |
|---|---|
| [Leetcode] 15. 3Sum (0) | 2023.05.01 |
| [Leetcode] 12. Integer to Roman (0) | 2023.05.01 |
| [Leetcode] 202. Happy Number (0) | 2023.04.27 |
| [Leetcode] 55. Jump Game (0) | 2023.04.27 |
class Solution:
def intToRoman(self, num: int) -> str:
answer = ""
ones = ["M", "C", "X", "I"]
fives = ["D", "L", "V"]
# Handle thousands
thou = num // 1000
i = 0
while i < thou:
answer += "M"
i = i + 1
# Remove thousands
num %= 1000
num = str(num)
# Padding to fill 3 digits
while len(num) != 3:
num = "0" + num
# Iterate num from left to right
for i, x in enumerate(num):
x = int(x)
if x == 5:
answer += fives[i]
elif x == 9:
answer += ones[i + 1]
answer += ones[i]
elif x == 4 :
answer += ones[i + 1]
answer += fives[i]
elif x < 5:
answer += (x * ones[i+1])
elif x > 5:
answer += fives[i]
answer += ((x - 5) * ones[i+1])
return answer'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 15. 3Sum (0) | 2023.05.01 |
|---|---|
| [Leetcode] 1. Two Sum (0) | 2023.05.01 |
| [Leetcode] 202. Happy Number (0) | 2023.04.27 |
| [Leetcode] 55. Jump Game (0) | 2023.04.27 |
| [Leetcode] 11. Container With Most Water (0) | 2023.04.27 |
class Solution:
def isHappy(self, n: int) -> bool:
hashmap = {}
while n > 1:
nums = [int(x) for x in str(n)]
n = 0
for num in nums:
n += (num ** 2)
if hashmap.get(n, False):
return False
hashmap[n] = 1
return True'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 15. 3Sum (0) | 2023.05.01 |
|---|---|
| [Leetcode] 1. Two Sum (0) | 2023.05.01 |
| [Leetcode] 12. Integer to Roman (0) | 2023.05.01 |
| [Leetcode] 55. Jump Game (0) | 2023.04.27 |
| [Leetcode] 11. Container With Most Water (0) | 2023.04.27 |