941. Valid Mountain Array
Given an array of integers arr, return true if and only if it is a valid mountain array.
Recall that arr is a mountain array if and only if:
- arr.length >= 3
- There exists some i with 0 < i < arr.length - 1 such that:
arr[0] < arr[1] < ... < arr[i - 1] < arr[i]
arr[i] > arr[i + 1] > ... > arr[arr.length - 1]
My Answer 1: Accepted (Runtime: 192 ms - 94.49% / Memory Usage: 15.5 MB - 60.06%)
class Solution:
def validMountainArray(self, arr: List[int]) -> bool:
if len(arr) < 3:
return False
idx = 0
for i in range(1, len(arr)):
if arr[idx] < arr[i]:
idx = i
elif arr[idx] == arr[i]:
return False
else:
break
if idx == 0 or idx == len(arr)-1:
return False
for i in range(idx+1, len(arr)):
if arr[idx] > arr[i]:
idx = i
elif arr[idx] <= arr[i]:
return False
return True상승세 -> 하락세 전환 시점의 idx 를 찾아서 유효한지 검사
같은 값이 있거나 계속 상승세, 계속 하락세이면 return False
939. Minimum Area Rectangle
Given a set of points in the xy-plane, determine the minimum area of a rectangle formed from these points, with sides parallel to the x and y axes.
If there isn't any rectangle, return 0.
이건 아예 못풀었네요..^^
Solution 1: Accepted (Runtime: 1196 ms - 59.81% / Memory Usage: 14.8 MB - 29.55%)
class Solution:
def minAreaRect(self, points: List[List[int]]) -> int:
seen = set()
res = float('inf')
for x1, y1 in points:
for x2, y2 in seen:
if (x1, y2) in seen and (x2, y1) in seen:
area = abs(x1 - x2) * abs(y1 - y2)
if area and area < res:
res = area
seen.add((x1, y1))
return res if res < float('inf') else 0이미 봤던 좌표들과 새로 보는 좌표들을 비교해서
(x1, y2) & (x2, y1) 를 이미 봤으면 사각형 완성
=> 넓이 구해서 작은 값으로 update
아무것도 없었으면 return 0
731. My Calendar II
You are implementing a program to use as your calendar. We can add a new event if adding the event will not cause a triple booking.
A triple booking happens when three events have some non-empty intersection (i.e., some moment is common to all the three events.).
The event can be represented as a pair of integers start and end that represents a booking on the half-open interval [start, end), the range of real numbers x such that start <= x < end.
Implement the MyCalendarTwo class:
- MyCalendarTwo() Initializes the calendar object.
- boolean book(int start, int end) Returns true if the event can be added to the calendar successfully without causing a triple booking. Otherwise, return false and do not add the event to the calendar.
My Answer 1: Wrong Answer (10 / 97 test cases passed.)
class MyCalendarTwo:
def __init__(self):
self.intervals = []
self.count = []
def book(self, start: int, end: int) -> bool:
if len(self.intervals) == 0:
self.intervals.append([start, end])
self.count.append(1)
return True
double = 0
for i in range(len(self.intervals)):
# start 만
if self.intervals[i][0] <= start < self.intervals[i][1] and self.intervals[i][1] < end:
if self.count[i] >= 2:
return False
if self.intervals[i][0] != start:
self.intervals.append([start, self.intervals[i][0]])
self.count.append(1)
self.intervals[i][0] = start
self.count[i] += 1
self.intervals.append([self.intervals[i][1], end])
self.count.append(1)
double = 1
break
# end 만
elif self.intervals[i][0] < end < self.intervals[i][1] and self.intervals[i][0] > start:
if self.count[i] >= 2:
return False
self.intervals.append([start, self.intervals[i][0]])
self.count.append(1)
self.intervals.append([end, self.intervals[i][1]])
self.count.append(1)
self.intervals[i][1] = end
self.count[i] += 1
double = 1
break
# 둘다 in
elif self.intervals[i][0] < start < self.intervals[i][1] and end <= self.intervals[i][1]:
if self.count[i] >= 2:
return False
self.intervals.append([self.intervals[i][0], start])
self.intervals.append([end, self.intervals[i][1]])
self.count.append(1)
self.count.append(1)
self.intervals[i][0] = start
self.intervals[i][1] = end
self.count[i] += 1
double = 1
break
# 둘다 out
elif start < self.intervals[i][0] and self.intervals[i][1] < end:
if self.count[i] >= 2:
return False
self.count[i] += 1
self.intervals.append([start, self.intervals[i][0]])
self.intervals.append([self.intervals[i][1], end])
self.count.append(1)
self.count.append(1)
double = 1
break
if double == 0:
self.intervals.append([start, end])
self.booked[start, end] = 1
self.count.append(1)
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)4가지 경우마다 interval 수정..
짜면서도 넘 극혐이었던 코드...
Solution 1: Accepted (Runtime: 488 ms / Memory Usage: 14.9 MB)
class MyCalendarTwo:
def __init__(self):
self.calendar = []
self.overlaps = []
def book(self, start: int, end: int) -> bool:
for i, j in self.overlaps:
if start < j and end > i:
return False
for i, j in self.calendar:
if start < j and end > i:
self.overlaps.append((max(start, i), min(end, j)))
self.calendar.append((start, end))
return True
# Your MyCalendarTwo object will be instantiated and called as such:
# obj = MyCalendarTwo()
# param_1 = obj.book(start,end)self.calendar 는 첫번째 예약된 것
self.overlaps 는 두번째 예약된 것
i 는 end 와 비교하고 j 는 start 와 비교 => double 확인
overlap 되면 self.overlaps 에 더 좁은 범위를 추가
0개의 댓글
관련 채용 정보
