class Solution:
def arraySign(self, nums: List[int]) -> int:
if 0 in nums:
return 0
len_n = 0
for n in nums:
if n < 0:
len_n = len_n +1
return -1 if len_n % 2 else 1'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 2215. Find the Difference of Two Arrays (0) | 2023.05.03 |
|---|---|
| [Leetcode] 1491. Average Salary Excluding the Minimum and Maximum Salary (0) | 2023.05.02 |
| [Leetcode] 121. Best Time to Buy and Sell Stock (0) | 2023.05.02 |
| [Leetcode 334] 334. Increasing Triplet Subsequence (0) | 2023.05.02 |
| [Leetcode] 162. Find Peak Element (0) | 2023.05.02 |
Time Complexity: O(N)
Space Complexity: O(N) (Worst -> len(maxlist) = n/2
class Solution:
def maxProfit(self, prices: List[int]) -> int:
if len(prices) < 2:
return 0
n1, n2 = 0, 1
minlist = []
for i in range(len(prices) - 1):
if prices[i] < prices[n1]:
if prices[n2] - prices[n1] > 0:
minlist.append(prices[n2] - prices[n1])
n1 = i
n2 = i + 1
elif prices[i+1] > prices[n2]:
n2 = i + 1
if prices[n2] - prices[n1] > 0:
minlist.append(prices[n2] - prices[n1])
return max(minlist) if minlist else 0'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 1491. Average Salary Excluding the Minimum and Maximum Salary (0) | 2023.05.02 |
|---|---|
| [Leetcode] 1822. Sign of the Product of an Array (0) | 2023.05.02 |
| [Leetcode 334] 334. Increasing Triplet Subsequence (0) | 2023.05.02 |
| [Leetcode] 162. Find Peak Element (0) | 2023.05.02 |
| [Leetcode] 153. Find Minimum in Rotated Sorted Array (0) | 2023.05.02 |
class Solution:
def increasingTriplet(self, nums: List[int]) -> bool:
n1 = n2 = float('inf')
for n in nums:
if n < n1:
n1 = n
elif n1 < n < n2:
n2 = n
elif n1 < n2 < n:
return True
return False'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 1822. Sign of the Product of an Array (0) | 2023.05.02 |
|---|---|
| [Leetcode] 121. Best Time to Buy and Sell Stock (0) | 2023.05.02 |
| [Leetcode] 162. Find Peak Element (0) | 2023.05.02 |
| [Leetcode] 153. Find Minimum in Rotated Sorted Array (0) | 2023.05.02 |
| [Leetcode] 74. Search a 2D Matrix (0) | 2023.05.01 |
정렬이 되어 있지 않은 배열의 이분 탐색
옆으로 한칸씩만 이동하면 마지막 mid가 업데이트 되지 않는다.
class Solution:
def findPeakElement(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
while left < right:
mid = left + (right - left)//2
if nums[mid] > nums[mid + 1]:
right = mid
else:
left = mid + 1
return left'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 121. Best Time to Buy and Sell Stock (0) | 2023.05.02 |
|---|---|
| [Leetcode 334] 334. Increasing Triplet Subsequence (0) | 2023.05.02 |
| [Leetcode] 153. Find Minimum in Rotated Sorted Array (0) | 2023.05.02 |
| [Leetcode] 74. Search a 2D Matrix (0) | 2023.05.01 |
| [Leetcode] 33. Search in Rotated Sorted Array (0) | 2023.05.01 |
class Solution:
def findMin(self, nums: List[int]) -> int:
left, right = 0, len(nums) - 1
mid = -1
while left < right:
mid = left + (right - left) // 2
if nums[mid] < nums[right]:
right = mid
elif nums[mid] < nums[left]:
left = mid
else:
while mid < right:
prev = mid
mid = mid + 1
if nums[prev] > nums[mid]:
return nums[mid]
return nums[mid]'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode 334] 334. Increasing Triplet Subsequence (0) | 2023.05.02 |
|---|---|
| [Leetcode] 162. Find Peak Element (0) | 2023.05.02 |
| [Leetcode] 74. Search a 2D Matrix (0) | 2023.05.01 |
| [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 |
class Solution:
def searchMatrix(self, matrix: List[List[int]], target: int) -> bool:
for line in matrix:
left, right = 0, len(line) - 1
while left <= right:
mid = left + (right - left) // 2
if line[mid] == target:
return True
if target < line[mid]:
right = mid - 1
else:
left = mid + 1
return Falsewhile left < right: 인 경우
원소가 하나인 경우를 탐색하지 못한다.
'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 162. Find Peak Element (0) | 2023.05.02 |
|---|---|
| [Leetcode] 153. Find Minimum in Rotated Sorted Array (0) | 2023.05.02 |
| [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] 17. Letter Combinations of a Phone Number (0) | 2023.05.01 |
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 |