[leetcode] 49, 50, 108, 118

108. Convert Sorted Array to Binary Search Tree

https://leetcode.com/problems/convert-sorted-array-to-binary-search-tree/

My Answer 1: Accepted (Runtime: 52 ms - 96.40% / Memory Usage: 15.7 MB - 17.50%)

# 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 sortedArrayToBST(self, nums: List[int]) -> TreeNode:
        def func(nums):
            if len(nums) == 0:
                return None
            
            v = nums[len(nums)//2]
            
            r = TreeNode(v)
            r.left = func(nums[:len(nums)//2])
            r.right = func(nums[len(nums)//2+1:])
            
            return r
            
        root = func(nums)
        
        return root

처음에는 root 값과 비교해서 작으면 left 에 크면 right 에 노드를 생성해줬는데
그러면 height-balanced binary tree 를 만족하지 못함..

두 서브트리의 깊이 차이도 맞춰줘야 한다!!

그래서 고루고루 밸런스를 맞추기 위해
nums 를 반으로 갈라서 가운데 값은 노드 생성하고
"시작 ~ 반" 까지는 노드의 left 로, "반 ~ 끝" 까지는 노드의 right 로 넘김

---

118. Pascal's Triangle

https://leetcode.com/problems/pascals-triangle/

My Answer 1: Accepted (Runtime: 32 ms - 59.12% / Memory Usage: 14.1 MB - 82.78%)

class Solution:
    def generate(self, numRows: int) -> List[List[int]]:
        ans = []
        for i in range(1, numRows+1):
            if i == 1:
                ans.append([1])
            elif i == 2:
                ans.append([1,1])
            else:
                tmp = []
                for j in range(len(ans[-1])-1):
                    tmp.append(ans[-1][j] + ans[-1][j+1])
                tmp = [1] + tmp + [1]
                ans.append(tmp)
        
        return ans

이건 그냥 문제 그대로 품

1 부터 numRows 까지 보면서
1, 2 일 때는 [1], [1,1] 로 베이스 만들어주고
나머지는 두개씩 더해서 tmp 에 저장하고 tmp 앞 뒤에 1 추가

---

49. Group Anagrams

https://leetcode.com/problems/group-anagrams/

My Answer 1: Accepted (Runtime: 108 ms - 42.55% / Memory Usage: 17.9 MB - 50.08%)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = {}
        for s in strs:
            if str(sorted(s)) in dic:
                dic[str(sorted(s))].append(s)
            else:
                dic[str(sorted(s))] = [s]
                
        return dic.values()

정렬한 문자열을 딕셔너리의 키로 잡아서 같은 스트링끼리 묶어줌

Solution 1: Accepted (Runtime: 112 ms - 40.06% / Memory Usage: 19.9 MB)

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        dic = collections.defaultdict(list)
        
        for s in strs:
            count = [0] * 26
            for c in s:
                count[ord(c) - ord('a')] += 1
            dic[tuple(count)].append(s)
        
        return dic.values()

그냥 아스키 계산하듯이.. count 튜플을 key 값으로 사용하기

{(1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0)
: ['eat', 'tea']}
이런식으로 저장됨

---

50. Pow(x, n)

https://leetcode.com/problems/powx-n/

My Answer 1: Accepted (Runtime: 24 ms - 95.84% / Memory Usage: 14.1 MB - 79.39%)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n *= -1
        
        return x ** n

n 이 음수일 때만 처리해주고 n 제곱

pow() 안썼으니까 괜찮다고 믿고싶다..^^

My Answer 2: Time Limit Exceeded (291 / 304 test cases passed.)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1 / x
            n *= -1
        
        if n == 0:
            return 1.0
            
        ans = x
        i = 2
        while i < n:
            ans *= ans
            i *= 2
        
        for _ in range(i//2, n):
            ans *= x
        
        return ans

그냥 반복문으로 n 번 곱하면 타임리밋 걸리길래
좀 더 빠르게 하려고 ans *= ans 로 곱해주고 (2 -> 4 -> 16 -> 256 -> ...)
나머지 n - i 만큼 x 더 곱해줌

그러나 타임리밋...

Solution 1: Accepted (Runtime: 32 ms - 63.45% / Memory Usage: 14.2 MB - 82.16%)

class Solution:
    def myPow(self, x: float, n: int) -> float:
        if n < 0:
            x = 1/x
            n = -n
        
        power = 1
        cur = x
        
        while n > 0:
            if n%2 : 
                power = power * cur
            cur = cur * cur
            n = n//2
        
        return power

n 을 2 로 나눠가면서 짝수일 때만 power 에 cur 을 곱해줌
cur 은 x 의 제곱수

이런거라는데 그냥.. 그렇구나 하렵니다..