😍 LeetCode Easy Collections II - 14 Problems

0283. Move Zeroes / 0344. Reverse String

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        length=len(nums)
        if length != 1:
            first_encountered = False
            for x in range(length-1):
                if nums[x] == 0:
                    if not first_encountered:
                        first_encountered = True
                        y = x + 1
                    while y<length:
                        if nums[y] != 0:
                            nums[x],nums[y] = nums[y],nums[x]
                            break
                        y+=1

class Solution:
    def reverseString(self, s: List[str]) -> None:
        """
        Do not return anything, modify s in-place instead.
        """
        x,y=0,len(s)-1
        while x<y:
            s[x],s[y]=s[y],s[x]
            x+=1
            y-=1
        return s

 

😍 0283) 한 쪽에서 동시에 시작하는 투 포인터 유형으로, 투 포인터 x는 0을, y는 0이 아닌 쪽을 가리키면서 시작. x는 0을 가리킬 때만(for문 돌면서), y는 (x+1)부터 시작해 0이 아닌 곳을 찾는다면 바로 swap. 투 포인터 유형은 x와 y 모두 각각 전체 범위 딱 한 번씩만 traverse하므로, 한 번 x가 0을 가리킬 때 y를 처음에 딱 x + 1이라 설정하고. 그 이후는 y를 전체 범위까지 쭉 한번만 돌리게 하면 된다(first_encountered flag 변수 활용)

😍 0344) 두 포인터(x,y)를 양쪽 끝에 잡고 가운데로 향하면서 s[x], s[y] = s[y], s[x] swap 진행. x와 y 합쳐서 한바퀴만 진행하므로 O(N)

---

0917. Reverse Only Letters / 0674. Longest Continuous Increasing Subsequence

class Solution:
    def reverseOnlyLetters(self, s: str) -> str:
        s=list(s)
        x,y=0,len(s)-1
        while x<y:
            if s[x].isalpha():
                if s[y].isalpha():
                    s[x],s[y]=s[y],s[x]
                    x+=1
                    y-=1
                else:
                    y-=1
            else:
                x+=1
        return ''.join(s)

class Solution:
    def findLengthOfLCIS(self, nums: List[int]) -> int:
        dp=[1]*len(nums)
        for x in range(1,len(nums)):
            if nums[x-1] < nums[x]:
                dp[x] = dp[x-1] + 1
        return max(dp)

 

😍 0917) 위 344와 동일 유형. 단, 알파벳일 경우만 swap 해주면 된다. 언제 포인터를 업데이트 해줄 지 경우의 수 확인하면 된다.

😍 0674) dp 활용. LIS의 '연속한' subarray 버전. (i-1) 인덱스 원소와 (i) 인덱스 원소가 있다면, i-1이 가리키는 원소보다 i가 가리키는 원소가 strictly increasing(<)하다면 i-1이 가리키는 dp 테이블의 값보다 1을 추가(i인덱스 원소 1개가 붙으므로)

---

0226. Invert Binary Tree / 0110. Balanced Binary Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        stack=[root]
        while stack:
            node = stack.pop()
            if not node:
                continue
            node.left, node.right = node.right, node.left
            stack += [node.left, node.right]
        return root
        
#----------------------------------------------------------------------------------
class Solution:
    def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
        if not root:
            return None

        left,right = root.left, root.right
        root.left = self.invertTree(right)
        root.right = self.invertTree(left)
        return root

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isBalanced(self, root: Optional[TreeNode]) -> bool:
        def get_depth_of_a_tree(root):
            if not root: return 0
            left, right = root.left, root.right
            return max(get_depth_of_a_tree(left), get_depth_of_a_tree(right)) + 1

        def dfs(tree):
            if not tree:
                l_h, r_h = 0,0
                return
            l_h, r_h = get_depth_of_a_tree(tree.left), get_depth_of_a_tree(tree.right)
            if abs(l_h-r_h) > 1:
                return -1
            left, right = tree.left, tree.right
            dl, dr = dfs(left), dfs(right)
            if dl == -1 or dr == -1:
                return - 1
        return dfs(root) != -1

 

😍 0226) root라는 tree 전체 클래스로 주어졌을 때, 재귀적으로 왼쪽 subtree와 오른쪽 subtree를 바꾸면 된다. 파이썬은 swap 알고리즘으로 매우 쉽게 node의 left와 node의 right를 바꾸면 된다. 만약 tree의 depth가 매우 깊어질 경우 재귀 오류 가능성(아래 솔루션 (2)). 이럴 경우 stack을 활용해 먼저 tree 전체 클래스를 넣고, 넣은 클래스의 왼쪽 subtree와 오른쪽 subtree를 swap한 다음 차례대로 stack에 넣는다. 그 다음 left와 right subtree 각각 다시 빼서 존재하는 node라면 다시 해당 node의 left와 right swap하고 stack에 다시 넣는다. 재귀를 stack으로 표현할 수 있는 이유는, 최근 iteration 진행한 부분에서 다시 iteration 깊게 진행하므로 stack 자료구조 특성 상 최근에 넣은 데이터를 꺼낸 다는 성질이 동일.

😍 0110) Binary Tree가 Balanced 되었다는 건 tree내의 모든 sub-tree가 root 제외 left와 right의 depth 차이가 1보다 크지 않다는 뜻이다. 즉 재귀적으로, 전체 root부터 시작해 left와 right sub-tree의 depth 차이가 1보다 크지 않은 지 계속 확인. 차이가 1보다 크다면 바로 -1 return. dfs(left)와 dfs(right)의 결과 중 최소 1개가 -1이면 전체 unbalanced이므로 -1 return.

---

0104. Maximum Depth of Binary Tree / 0100. Same Tree

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def maxDepth(self, root: Optional[TreeNode]) -> int:
        if root is None:
            return 0
        return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def isSameTree(self, p: Optional[TreeNode], q: Optional[TreeNode]) -> bool:
        if not p and not q:
            return True
        if not p or not q or p.val != q.val:
            return False
        if p.val == q.val:
            return (self.isSameTree(p.left, q.left) and self.isSameTree(p.right, q.right))

 

😍 0104) 주어진 Binary Tree의 최대 깊이는 재귀함수로 해결할 수 있다. 주어진 root tree의 왼쪽과 오른쪽 subtree 각각의 최댓값 depth 중 max() 결과에 1을 더한 결과가 전체 root tree의 깊이(root 포함하므로 1 더해야 한다)

 

😍 0100) 재귀함수를 활용하여 left child와 right child 각각 p와 q로 not p and not q일 때까지 재귀 돌리면 된다. 현재 node의 val이 서로 같다면 그 다음 child (p.left / q.left) (p.right / q.right) 확인

---

0876. Middle of the Linked List / 0125. Valid Palindrome

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
        return slow

class Solution:
    def isPalindrome(self, s: str) -> bool:
        l = []
        for x in s:
            if x.isdigit():
                l.append(x)
            elif x.isalpha():
                l.append(x.lower())
        if l == l[::-1]:
            return True
        else:
            return False
            
#
class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

 

😍 0876) Linked List 문제풀이에서 가장 많이 사용되는 기법 fast pointer / slow pointer를 동시에 사용하면 쉽다. fast pointer가 주어진 linked list의 맨 오른쪽 끝 노드에 도달(홀수 개수 노드)하거나 오른쪽 끝의 그 다음 None(짝수 개수 노드)에 도달할 때 slow pointer가 도달한 곳이 문제에서 요구하는 middle of the linked list.

 

😍 0125) 숫자와 알파벳만 모두 모은 다음(알파벳이면 소문자로 바꾸고 모으기) 바로 팰린드롬 판정. 판정 시 [::-1]과 비교하거나 직접 양 옆에 두 개의 포인터를 놓고 traverse하면서 비교해도 된다

---

0206. Reverse Linked List / 0141. Linked List Cycle

# 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]:
        prev, node = None, head
        while node is not None:
            tmp = node.next
            node.next = prev
            prev = node
            node = tmp
        return prev

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def hasCycle(self, head: Optional[ListNode]) -> bool:
        slow, fast = head, head
        while fast and fast.next:
            slow = slow.next
            fast = fast.next.next
            if slow == fast:
                return True
        return False

 

😍 0206) reverse 과정을 진행하기 위해서는 현재 노드와 바로 앞의 노드 각각 node / prev라고 한 다음, node.next = prev로 가리키게 하면 된다. 이 때, node.next가 prev로 가리키는 순간, node 오른쪽으로 연결된 node와의 줄이 끊어지므로, 임시 tmp 노드로 만들어야 하는게 핵심

😍 0141) 주어진 linked list가 cycle이 있는 지 판별하는 코드 작성하기. 맨 마지막 node가 그 앞의 여러 node 중 연결된 경우가 있다면 cycle 존재. fast / slow로 나누어서 fast가 언젠가 slow를 가리키게 된다.

---

0234. Palindrome Linked List / 0643. Maximum Average Subarray I

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def isPalindrome(self, head: Optional[ListNode]) -> bool:
        rev = None
        slow, fast = head, head
        while fast and fast.next:
            fast = fast.next.next
            rev, rev.next, slow = slow, rev, slow.next

        if fast:
            slow = slow.next
        
        while rev and rev.val == slow.val:
            slow = slow.next
            rev = rev.next
        
        return not rev

class Solution:
    def findMaxAverage(self, nums: List[int], k: int) -> float:
        avg = sum(nums[:k]) / k
        avg_sum = sum(nums[:k])
        start=0
        for i in range(k,len(nums)):
            avg_sum-=(nums[start])
            avg_sum+=(nums[i])
            avg = max(avg,avg_sum/k)
            start+=1
        return avg

 

😍 0234) 문제의 핵심 아이디어는 두 런너(fast, slow)를 동시에 head부터 진행하며, fast가 끝까지 다다를 때까지 slow는 절반을 진행하고, 절반까지 진행하는 동안의 모든 node를 rev로 저장 / 그 다음 중간 지점부터 slow와 rev가 각각 다른 방향으로 뻗어나가며 차례대로 slow와 rev의 val을 비교. 최종적으로 rev가 일부 있다는 건 팰린드롬이 아니므로 False, rev가 비었다는 건 True이므로 not rev를 리턴

※ 단, 노드 개수가 홀수일 때, rev는 정확하게 중간 노드 바로 앞 노드를 시작점으로 가지지만, slow는 정확하게 중간 노드부터 가리킨다. 따라서, slow는 중간 노드 바로 뒷 노드를 가리키게끔 slow = slow.next로 업데이트

ex) 아래 예시) node 개수가 짝수일때 정확하게 rev / slow 스타팅 지점 중간 기준으로 나뉘지만, 홀수 개수일 때는 slow를 오른쪽으로 한 칸 이동해서 slow = slow.next로 업데이트

😍 0643) 전형적인 슬라이딩 윈도우 문제. 연속한, 정해진 k개의 개수의 평균 중 최댓값을 구하는 문제. 시간 복잡도 O(N)만에 크기 고정한 채로 맨 앞과 맨 뒤만 케어해서 리스트 오른쪽 끝까지 슬라이드 해주면 끝

---