Scribbling

To solve this problem in-place, we can think of using two more states(2, 3) rather than two states(1, 0). class Solution: def gameOfLife(self, board: List[List[int]]) -> None: """ Do not return anything, modify board in-place instead. """ m, n = len(board), len(board[0]) for y in range(m): for x in range(n): cnt = self.countOnes(board, y, x) if board[y][x] == 0: if cnt == 3: board[y][x] = 3 else..

As a novice, it was not easy at all for me to solve this problem. I relied on other people's explanations and codes, and this post is to summarize their ideas. It is very tricky to solve this problem within O(N) time & O(1) memory. (* without modifying the array) The best way is "Floyd's Algorithm" as this problem can be seen as a linked list with a cycle. Check out the below video for further e..

O(N**2) Time Complexity, O(N) Memory Not an effective solution at all especially in terms of time complexity. class Solution: def numSquares(self, n: int) -> int: INT_MAX = int(1e5) dp = [INT_MAX] * (n+1) x = 1 while x * x int: psns = [] x = 1 while x * x int: INT_MAX = int(1e5) dp = [INT_MAX] * (n+1) dp[0] = 0 for i in range(1, n+1): for j in range(1, int(i**0.5)+1): dp[i] = min(dp[i], dp[i-j*j..

Several different solutions class Solution: def searchMatrix(self, matrix: List[List[int]], target: int) -> bool: j = bisect_right(matrix[0], target) - 1 i = bisect_right([mat[0] for mat in matrix], target) - 1 while i >= 0 and j >= 0: if matrix[i][j] < target: return False for k in range(0, i+1): if matrix[k][j] == target: return True for k in range(0, j+1): if matrix[i][k] == target: return Tr..

Using two pointers. class Solution: def moveZeroes(self, nums: List[int]) -> None: """ Do not return anything, modify nums in-place instead. """ j = 0 for i, num in enumerate(nums): if num != 0: nums[j] = num j += 1 for k in range(j, len(nums)): nums[k] = 0

Solution for Q.234 within O(N) time complexity and O(1) memory. To check whether it's a palindrome, we have to check two elements simultaneously from the head and tail. But in singly linked list, we have no way to check the elements in reverse order from the tail. So, the solution is simple. Reverse the second half of the list and compare two lists. Below is the code. # Definition for singly-lin..

가장 먼저 떠오른 방법은 Priority Queue를 사용하는 것. Time Complexity: O(N*logN) import heapq class PriorityQueue: def __init__(self): self.pq = [] self.removals = [] def insert(self, elem): heapq.heappush(self.pq, -elem) def gettop(self): return -self.pq[0] def remove(self, elem): if elem == -self.pq[0]: heapq.heappop(self.pq) while self.removals and self.pq[0] == self.removals[0]: heapq.heappop(self.pq) heapq..

아래 너튜버분께 매번 배우게 되는 것 같다. https://www.youtube.com/watch?v=GSBLe8cKu0s&t=3s 아래는 위의 영상에 나온 알고리즘의 파이썬 코드이다. from functools import cmp_to_key import heapq class Solution: def getSkyline(self, buildings: List[List[int]]) -> List[List[int]]: # [loc, height, isEnd] points = [] for l, r, h in buildings: points.append([l, h, 0]) points.append([r, h, 1]) def compare(p1, p2): if p1[0] != p2[0]: return p1[0]..

Iterative가 빠르다. # Definition for singly-linked list. # class ListNode: # def __init__(self, val=0, next=None): # self.val = val # self.next = next class Solution: def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]: cur, prv = head, None while cur: nxt = cur.next cur.next = prv prv = cur cur = nxt return prv

class Solution: def isHappy(self, n: int) -> bool: def calc(x): ret = 0 while x > 0: ret += (x % 10)**2 x //= 10 return ret numSet = set([n]) x = n while True: x = calc(x) if x == 1: return True if x in numSet: return False numSet.add(x)