🗓️ Daily LeetCoding Challenge May, Day 8
class Solution:
def diagonalSum(self, mat: List[List[int]]) -> int:
n = len(mat)
answer = 0
for i in range(n):
answer += mat[i][i] + mat[i][n - i - 1]
if n % 2 != 0:
answer -= mat[n // 2][n // 2]
return answer'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 34. Find First and Last Position of Element in Sorted Array (0) | 2023.05.09 |
|---|---|
| [Leetcode] 1498. Number of Subsequences That Satisfy the Given Sum Condition (1) | 2023.05.06 |
| [Leetcode] 1456. Maximum Number of Vowels in a Substring of Given Length (0) | 2023.05.06 |
| [Leetcode] 649. Dota2 Senate (0) | 2023.05.05 |
| [Leetcode] 986. Interval List Intersections (0) | 2023.05.05 |
import bisect
class Solution:
def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:
lis = []
result = []
for obstacle in obstacles:
idx = bisect.bisect_right(lis, obstacle)
if idx == len(lis):
lis.append(obstacle)
else:
lis[idx] = obstacle
print(idx, lis, obstacle)
result.append(idx+1)
return result'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 1572. Matrix Diagonal Sum (0) | 2023.05.09 |
|---|---|
| [Leetcode] 1498. Number of Subsequences That Satisfy the Given Sum Condition (1) | 2023.05.06 |
| [Leetcode] 1456. Maximum Number of Vowels in a Substring of Given Length (0) | 2023.05.06 |
| [Leetcode] 649. Dota2 Senate (0) | 2023.05.05 |
| [Leetcode] 986. Interval List Intersections (0) | 2023.05.05 |
[Leetcode] 1498. Number of Subsequences That Satisfy the Given Sum Condition
|2023. 5. 6. 13:16
class Solution:
def numSubseq(self, nums: List[int], target: int) -> int:
answer = 0
nums.sort() # O(NlogN)
left, right = 0, len(nums) - 1
while left <= right: # O(N)
if nums[left] + nums[right] <= target:
if (left - right) in [0, 1]:
answer += 1
else:
answer += pow(2, right - left)
left += 1
else:
right -= 1
return answer % (10**9 + 7)'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 1572. Matrix Diagonal Sum (0) | 2023.05.09 |
|---|---|
| [Leetcode] 34. Find First and Last Position of Element in Sorted Array (0) | 2023.05.09 |
| [Leetcode] 1456. Maximum Number of Vowels in a Substring of Given Length (0) | 2023.05.06 |
| [Leetcode] 649. Dota2 Senate (0) | 2023.05.05 |
| [Leetcode] 986. Interval List Intersections (0) | 2023.05.05 |
class Solution:
def maxVowels(self, s: str, k: int) -> int:
q = collections.deque(s[:k])
vowel = ['a', 'e', 'i', 'o', 'u']
count = 0
max_count = 0
for v in vowel:
count += s[:k].count(v)
max_count = max(max_count, count)
i = k
while i < len(s):
if q.popleft() in vowel:
count -= 1
x = s[i]
q.append(x)
if x in vowel:
count += 1
max_count = max(max_count, count)
if count == k:
return k
i = i + 1
return max_count'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 34. Find First and Last Position of Element in Sorted Array (0) | 2023.05.09 |
|---|---|
| [Leetcode] 1498. Number of Subsequences That Satisfy the Given Sum Condition (1) | 2023.05.06 |
| [Leetcode] 649. Dota2 Senate (0) | 2023.05.05 |
| [Leetcode] 986. Interval List Intersections (0) | 2023.05.05 |
| [Leetcode] 844. Backspace String Compare (0) | 2023.05.05 |
class Solution:
def predictPartyVictory(self, senate: str) -> str:
A = collections.deque()
people = [0, 0]
bans = [0, 0]
for person in senate:
x = person == 'R'
people[x] += 1
A.append(x)
while all(people):
x = A.popleft()
people[x] -= 1
if bans[x]:
bans[x] -= 1
else:
people[x] +=1
bans[x^1] += 1
A.append(x)
return 'Radiant' if people[1] else 'Dire''CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 1498. Number of Subsequences That Satisfy the Given Sum Condition (1) | 2023.05.06 |
|---|---|
| [Leetcode] 1456. Maximum Number of Vowels in a Substring of Given Length (0) | 2023.05.06 |
| [Leetcode] 986. Interval List Intersections (0) | 2023.05.05 |
| [Leetcode] 844. Backspace String Compare (0) | 2023.05.05 |
| [Leetcode] 82. Remove Duplicates from Sorted List II (0) | 2023.05.04 |
class Solution:
def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> List[List[int]]:
answer = []
i, j = 0, 0
if len(firstList) == 0 or len(secondList) == 0:
return []
while i < len(firstList) and j < len(secondList):
if firstList[i][1] < secondList[j][0]:
i += 1
elif secondList[j][1] < firstList[i][0]:
j += 1
else:
intersection_start = max(firstList[i][0], secondList[j][0])
intersection_end = min(firstList[i][1], secondList[j][1])
answer.append([intersection_start, intersection_end])
if firstList[i][1] < secondList[j][1]:
i += 1
else:
j += 1
return answer
더 간단한 접근
class Solution:
def intervalIntersection(self, A, B):
i, j, ans = 0, 0, []
while i < len(A) and j < len(B):
curr = [max(A[i][0], B[j][0]), min(A[i][1], B[j][1])]
if curr[0] <= curr[1]:
ans.append(curr)
if A[i][1] <= B[j][1]:
i += 1
else:
j += 1
return ans'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 1456. Maximum Number of Vowels in a Substring of Given Length (0) | 2023.05.06 |
|---|---|
| [Leetcode] 649. Dota2 Senate (0) | 2023.05.05 |
| [Leetcode] 844. Backspace String Compare (0) | 2023.05.05 |
| [Leetcode] 82. Remove Duplicates from Sorted List II (0) | 2023.05.04 |
| [Leetcode] 2215. Find the Difference of Two Arrays (0) | 2023.05.03 |
class Solution:
def backspaceCompare(self, s: str, t: str) -> bool:
def check(string):
lst = []
for s in string:
if s != "#":
lst.append(s)
else:
if lst:
lst.pop()
return lst
return check(s) == check(t)'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 649. Dota2 Senate (0) | 2023.05.05 |
|---|---|
| [Leetcode] 986. Interval List Intersections (0) | 2023.05.05 |
| [Leetcode] 82. Remove Duplicates from Sorted List II (0) | 2023.05.04 |
| [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 |
Solution 1. memoization
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
memo = {}
newhead = ListNode(0)
cur = newhead
while head:
if head.val not in memo:
memo[head.val] = 1
cur.next = ListNode(head.val)
cur = cur.next
else:
memo[head.val] += 1
head = head.next
lst = [k for k, v in memo.items() if v == 1]
newhead = ListNode(0)
cur = newhead
for i in lst:
cur.next = ListNode(i)
cur = cur.next
return newhead.nextSolution 2. Two Pointer (플로이드 사이클 알고리즘 응용)
class Solution:
def deleteDuplicates(self, head: Optional[ListNode]) -> Optional[ListNode]:
dummy = ListNode(0)
dummy.next = head
fast, slow = head, dummy
# slow는 기록이 완료된 노드
# fast는 탐색을 진행하는 노드
while fast:
while fast.next and fast.val == fast.next.val:
fast = fast.next
if slow.next == fast:
slow = slow.next
fast = fast.next
else:
slow.next = fast.next
fast = fast.next
return dummy.next'CS > 알고리즘' 카테고리의 다른 글
| [Leetcode] 986. Interval List Intersections (0) | 2023.05.05 |
|---|---|
| [Leetcode] 844. Backspace String Compare (0) | 2023.05.05 |
| [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] 1822. Sign of the Product of an Array (0) | 2023.05.02 |