[leetcode] 105, 116, 191, 202

191. Number of 1 Bits

https://leetcode.com/problems/number-of-1-bits/

My Answer 1: Accepted (Runtime: 32 ms - 60.45% / Memory Usage: 14.2 MB - 67.99%)

class Solution:
    def hammingWeight(self, n: int) -> int:
        return bin(n).count("1")

n 을 2 진수로 바꾼 후, 1 의 개수 세주기

• bin() 함수를 사용하면 맨 앞에 0b 가 붙는다

My Answer 2: Accepted (Runtime: 36 ms - 21.55% / Memory Usage: 14.3 MB - 5.61%)

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        
        while n:
            ans += n % 2
            n //= 2
        
        return ans

2 로 계속 나누면서 나머지 값 1 만 ans 에 더해주기

Solution 1: Accepted (Runtime: 32 ms - 60.45% / Memory Usage: 14.1 MB - 67.99%)

class Solution:
    def hammingWeight(self, n: int) -> int:
        ans = 0
        while n:
            n &= (n-1)
            ans += 1
        return ans

2 로 나누는 건 너무 오래 걸리니까 & 연산 하기

ex) 11 = 1011
n = 11 => 11 & 10 => 1011 & 1010 = 1010
n = 10 => 10 & 9 => 1010 & 1001 = 1000
n = 8 => 8 & 7 => 1000 & 0111 = 0000
n = 0 => ans 는 총 3 번

훨씬 빠르다!!

---

202. Happy Number

https://leetcode.com/problems/happy-number/

My Answer 1: Accepted (Runtime: 32 ms - 81.45% / Memory Usage: 14.2 MB - 76.89%)

class Solution:
    def isHappy(self, n: int) -> bool:
        nums = []
        
        while n not in nums:
            sums = 0
            nums.append(n)
            while n:
                a = n % 10
                sums += a ** 2
                n //= 10
            if sums == 1:
                return True
            n = sums
        
        return False

unhappy 숫자들은 무한으로 반복되므로
nums 에 n 을 계속 넣어주면서 이미 나왔던 n 을 또 만나서 무한반복 하는지 확인

sums 가 1 이 되면 return True

Solution 1: Accepted (Runtime: 28 ms - 94.97% / Memory Usage: 14.2 MB - 76.89%)

class Solution:
    def isHappy(self, n: int) -> bool:
        if n == 1:
            return 1
        
        happy = 0
        
        while n:
            happy += pow(n%10, 2)
            n = n//10
        
        if happy == 2 or happy == 4:
            return False
        else:
            return self.isHappy(happy)

저번에 풀었던 것..
각 자리 수 제곱의 합이 2 또는 4 이면 반복된다는 의미라네요

Floyd's Cycle-Finding Algorithm

Solution 2: Accepted (Runtime: 40 ms - 20.14% / Memory Usage: 14.3 MB - 17.03%)

class Solution:
    def isHappy(self, n: int) -> bool:
        def get_next(number):
            total_sum = 0
            while number > 0:
                number, digit = divmod(number, 10)
                total_sum += digit ** 2
            return total_sum

        slow_runner = n
        fast_runner = get_next(n)
        while fast_runner != 1 and slow_runner != fast_runner:
            slow_runner = get_next(slow_runner)
            fast_runner = get_next(get_next(fast_runner))
        return fast_runner == 1

거북이와 토끼 기법

slow 는 n 부터, fast 는 다음 n 부터 시작해서
slow 가 한 칸씩 갈 동안 fast 는 다음, 다음 칸까지 감

slow 와 fast 가 같아지면 무한 반복된다는 뜻~

---

105. Construct Binary Tree from Preorder and Inorder Traversal

https://leetcode.com/problems/construct-binary-tree-from-preorder-and-inorder-traversal/

My Answer 1: Accepted (Runtime: 176 ms - 40.82% / Memory Usage: 88.8 MB - 8.19%)

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        def func(p, i):
            if len(p) == 0 or len(i) == 0:
                return None
            root = p.pop(0)
            idx = i.index(root)
            i_left = i[:idx]
            i_right = i[idx+1:]
            newTree = TreeNode(root, func(p[:len(i_left)], i_left), func(p[len(i_left):], i_right))
            return newTree
        
        return func(preorder, inorder)

preorder => root - left - right 순으로 저장
inorder => left - root - right 순으로 저장

root 는 무조건 preorder[0] 으로 잡고 만들기 => root = p.pop(0)

preorder 에서 left, right 의 범위가 어느정도인지 알 수 없음 => inorder 에서 알 수 있음
inorder 에서 root 의 인덱스 앞은 left, 뒤는 right 가 된다는 점 이용
=> i_left = i[:idx], i_right = i[idx+1:]

그럼 i_left, i_right 의 길이로 preorder 에서도 left, right 를 찾을 수 있게 됨
preorder 와 inorder 를 같은 범위로 묶어서 다음 매개변수로 넘겨줌
=> left: func(p[:len(i_left)], i_left), right: func(p[len(i_left):], i_right)

재귀로 계속 노드 생성해서 return 하면 쭉 연결된다~

Solution 1: Accepted (Runtime: 184 ms - 38.36% / Memory Usage: 88.3 MB - 21.59%)

# 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 buildTree(self, preorder: List[int], inorder: List[int]) -> Optional[TreeNode]:
        if not preorder or not inorder:
            return None
        
        result = TreeNode(preorder[0])
        root = inorder.index(preorder[0])
        result.left = self.buildTree(preorder[1:root+1], inorder[:root])
        result.right = self.buildTree(preorder[root+1:], inorder[root+1:])
        
        return result

더 깔끔한 루션이

length 를 구할 필요 없이 그냥 root 인덱스로 끝내기 가능!!

---

116. Populating Next Right Pointers in Each Node

https://leetcode.com/problems/populating-next-right-pointers-in-each-node/

My Answer 1: Accepted (Runtime: 68 ms - 32.52% / Memory Usage: 15.8 MB - 32.29%)

"""
# Definition for a Node.
class Node:
    def __init__(self, val: int = 0, left: 'Node' = None, right: 'Node' = None, next: 'Node' = None):
        self.val = val
        self.left = left
        self.right = right
        self.next = next
"""

class Solution:
    def connect(self, root: 'Node') -> 'Node':
        queue = [root]
        
        while queue:
            level = len(queue)
            prev = queue[0]
            for i in range(level):
                r = queue.pop(0)
                if r:
                    if prev != r:
                        prev.next = r
                        prev = prev.next
                    if r.left:
                        queue.append(r.left)
                    if r.right:
                        queue.append(r.right)
        
        return root

level order 보듯이 함

queue 길이 만큼이 한 레벨
=> 한 레벨씩 보면서 prev 에 r 을 이어줌

if prev != r: => 맨 처음엔 prev 와 r 이 같으므로 이어주기 패스~

left, right 는 queue 에 계속 저장