😍 LeetCode Easy Collections II - 20 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)만에 크기 고정한 채로 맨 앞과 맨 뒤만 케어해서 리스트 오른쪽 끝까지 슬라이드 해주면 끝

---

0112. Path Sum / 0804. Unique Morse Code Words

# 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 hasPathSum(self, root: Optional[TreeNode], targetSum: int) -> bool:
        def dfs(node, curSum):
            if not node: #empty tree
                return False
            
            curSum += node.val
            if not node.left and not node.right: #if this is a leaf node
                return curSum == targetSum
            
            #if not a leaf node
            return (dfs(node.left, curSum) or dfs(node.right, curSum))
        return dfs(root, 0)

 

😍 0112) 주어진 binary tree에서 root부터 leaf node까지 진행하는 경로 내의 모든 노드의 숫자의 합이 targetSum이 존재하는 지의 여부를 확인하는 문제. dfs 재귀 활용.

 

① 먼저 return 조건) 주어진 node가 존재하지 않으면 return

 

② 주어진 node가 존재한다면 현재의 값 curSum에서 value 더함. 그리고 해당 node가 leaf node라면 curSum과 targetSum이 같은 지 다른 지 리턴. 만약 leaf node가 아니라면 dfs 재귀적으로 돌리면 된다.

 

class Solution:
    def uniqueMorseRepresentations(self, words: List[str]) -> int:
        hashmap = dict()
        values = [".-","-...","-.-.","-..",".","..-.","--.","....","..",".---","-.-",".-..","--","-.","---",".--.","--.-",".-.","...","-","..-","...-",".--","-..-","-.--","--.."]
        keys = list('abcdefghijklmnopqrstuvwxyz')
        for key, value in zip(keys, values):
            hashmap[key] = value

        ans = set()
        for word in words:
            ans_str = ''
            for alphabet in word:
                ans_str += hashmap[alphabet]
            ans.add(ans_str)
        return len(ans)

 

😍 0804) a~z에 대응하는 morse code: hash map 활용. 직접 for문 일일이 돌리며 set() 자료구조 활용해 중복 여부 확인하고 길이 출력

---

0771. Jewels and Stones / 0706. Design HashMap

class Solution:
    def numJewelsInStones(self, jewels: str, stones: str) -> int:
        ans=0
        for stone in stones:
            if stone in jewels:
                ans+=1
        return ans

 

class MyHashMap:

    def __init__(self):
        self.hashmap = dict()
        

    def put(self, key: int, value: int) -> None:
        self.hashmap[key] = value


    def get(self, key: int) -> int:
        if key in self.hashmap.keys():
            return self.hashmap[key]
        else:
            return -1
        

    def remove(self, key: int) -> None:
        if key in self.hashmap.keys():
            del self.hashmap[key]
        


# Your MyHashMap object will be instantiated and called as such:
# obj = MyHashMap()
# obj.put(key,value)
# param_2 = obj.get(key)
# obj.remove(key)

---

0290. Word Pattern / 0509. Fibonacci Number

class Solution:
    def wordPattern(self, pattern: str, s: str) -> bool:
        match_dict = dict()
        s = s.split()
        print(s)
        if len(pattern) != len(s):
            return False
        for i in range(len(pattern)):
            # print(match_dict)
            if pattern[i] in match_dict.keys():
                if match_dict[pattern[i]] != s[i]:
                    return False
            else:
                if s[i] in match_dict.values():
                    return False
                match_dict[pattern[i]] = s[i]
        return True

 

😍 0290) 일대일 대응이 되는 지 여부 확인. X -> Y에서 X의 길이와 Y의 길이가 다르거나 / X에 존재하는데 Y 데이터가 서로 다른 경우 / Y에 존재하는 데 X 데이터가 서로 다른 경우 False / 나머지는 True

class Solution:
    def fib(self, n: int) -> int:
        
        def fibo(n):
            if n <= 1:
                return n
            
            return fibo(n-1) + fibo(n-2)
        
        return fibo(n)

---