class Solution:
def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
#candidates = [1,2]
#target = 4
ret = []
def get_comb(candidates, cand, target):
if target == 0:
ret.append(cand)
return
for i in range(len(candidates)):
if target-candidates[i] >=0:
get_comb(candidates[i:], cand + [candidates[i]], target-candidates[i])
get_comb(candidates, [], target)
return ret
1353 https://leetcode.com/problems/maximum-number-of-events-that-can-be-attended/
모든 이벤트들을 시작일 기준으로, 그다음엔 끝나는 날 기준으로 정렬한 후에 시작일을 하나하나 돌아가면서 같은 시작일일 경우 그 이벤트들의 끝나는 날짜를 최소 힙에 저장해둔다. 그다음 최소 힙에서 pop하면 '같은 시작일이면서 빨리 끝나는 이벤트' 순으로 pop이 될것이므로 이것을 이용해서 최대한 많은 이벤트를 참석할수 있도록 조율한다.
from heapq import *
class Solution:
def maxEvents(self, events: List[List[int]]) -> int:
#events= [[1,2],[1,2],[1,6],[1,2],[1,2]]
events.sort(key=lambda x:(x[0], x[1])) # 이벤트들을 시작일 기준으로, 그다음엔 끝나는 일 기준으로 정렬한다.
end_day = max([e[1] for e in events]) # 모든게 끝나는 날짜
heap = []
ret = 0
cur_day = -1
i = 0
while cur_day <= end_day:
if cur_day == -1: # cur_day를 초기화해준다.
cur_day = events[i][0] # cur_day는 현재 존재하는 가장 빨리 시작하는 이벤트의 시작일.
while i < len(events) and events[i][0] == cur_day: # 시작일이 같은 이벤트들을 먼저 처리하기 위해 힙에 저장해둔다.
heappush(heap, events[i][1]) # 시작일이 같은 이벤트들의 끝나는 날짜만 힙에 저장해둔다. 빨리 끝나는거부터 처리하기 위함
i += 1
# [[1,2],[1,2],[1,6],[1,2],[1,2]] 같은 예외케이스를 처리하기 위함.
# 이벤트의 끝나는 날이 이미 지나갔으면(cur_day보다 작으면) 참석 못하는거니 그냥 버린다.
while heap and heap[0] < cur_day:
heappop(heap)
if heap: # 참석할 이벤트가 있으면 참석한다.
ret += 1
heappop(heap)
cur_day += 1
return ret
128 https://leetcode.com/problems/longest-consecutive-sequence/
[-1, -1, 0, 1, 3, 4, 5, 6, 7, 8, 9] 와 같은 리스트가 있다고 할 경우 증가하는 부분집합들은 (-1, 0, 1), (3,4,5,6,7,8,9) 가 있다. 이것들을 찾으려면 two pointer로 앞점과 뒷점을 만든 후, 앞점 + 1 == 뒷점인 경우 한칸씩 뒤로 증가시켜주면서 길이를 늘려주되, 앞점 + 1 != 뒷점이면 길이를 다시 1로 초기화해주면 된다.
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
#nums = [9,1,4,7,3,-1,0,5,8,-1,6]
if not nums:
return 0
nums.sort() # 오름차순 정렬
ret = -1
i = 0
while i < len(nums): # 모든 경우에 대해서 계산
_len = 1
_prev, _next = i, i+1 # _prev는 two pointer의 앞점, _next는 뒷점이 될 예정
while _next < len(nums):
while _next < len(nums)-1 and nums[_prev] == nums[_next]: # lcs의 뒷점이 앞점과 같으면 다른곳까지 가라고 늘려준다.
_next += 1
if nums[_prev] + 1 == nums[_next]: # 앞점과 뒷점이 1 차이이면 길이를 1 늘려준다.
_len += 1
else: # 앞점과 뒷점의 차이가 1 초과면 길이를 초기화해준다.
_len = 1
ret = max(ret, _len)
_prev = _next # 앞점을 이전 뒷점으로,
_next += 1 # 뒷점을 1 증가신후 다시 판별
i = _prev + 1
return ret
class Solution:
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
#nums = [5,9,18,54,108,540,90,180,360,720]
nums.sort()
ret = [[n] for n in nums]
for i in range(len(nums)):
for j in range(i):
if nums[i] % nums[j] == 0 and len(ret[i]) < len(ret[j])+1:
ret[i] = ret[j] + [nums[i]]
return sorted(ret, key=lambda x: -len(x))[0]
class Solution:
def lengthOfLIS(self, nums: List[int]) -> int:
#nums = [10,9,2,5,3,7,101,18]
ret = [1]*len(nums)
for i in range(len(nums)):
for j in range(i):
if nums[i] > nums[j] and ret[i] < ret[j] + 1:
ret[i] = ret[j] + 1
return max(ret)