leetcode 442(find duplicate), 529(bfs), 107(트리), 637, 429, 111, 993, 50(pow)

442 https://leetcode.com/problems/find-all-duplicates-in-an-array/

이전에 https://qkqhxla1.tistory.com/1044 요글의 leetcode 287번에서 중복되는 숫자 1개를 찾는 문제를 링크드 리스트에 사이클이 있다고 생각하여 사이클의 시작점을 찾는거로 풀수 있었는데, 같은 조건의 중복되는 숫자가 2개 이상일 경우에는 cycle sort라는게 있다.

class Solution:
    def findDuplicates(self, nums: List[int]) -> List[int]:
        self.cyclicSort(nums)
        output = []
        for i in range(len(nums)):
            if nums[i] != i+1:
                output.append(nums[i])
        return output
    
    def cyclicSort(self, nums):
        i = 0
        while i < len(nums):
            correct = nums[i] - 1
            if nums[correct] != nums[i]:
                nums[correct], nums[i] = nums[i], nums[correct]
            else:
                i += 1

이건 신기해서 가져왔다.

원글 : https://leetcode.com/problems/find-all-duplicates-in-an-array/discuss/92387/Java-Simple-Solution

class Solution(object):
    # 반복문을 돌면서 nums[i]-1위치의 값들을 음수로 바꿔준다. 이미 음수이면 이전에 한번 나왔던 수이니 중복되는 수이다.
    # nums[i]-1위치의 값들을 음수로 바꾸는 이유는 수가 1~n 범위이기 때문이다.(리스트 범위는 0~n-1 니까.)
    def findDuplicates(self, nums):
        answer = []
        for i in xrange(len(nums)):
            index = abs(nums[i])-1
            if nums[index] < 0:
                answer.append(abs(nums[i]))
            else:
                nums[index] = -nums[index]
        return answer

529 https://leetcode.com/problems/minesweeper/

 

지뢰찾기에서 클릭했을때 지뢰찾기판의 상태를 구현하는 문제이다.

from collections import deque

class Solution(object):
    def updateBoard(self, board, click):
        if board[click[0]][click[1]] == 'M':
            board[click[0]][click[1]] = 'X'
            return board
        
        queue = deque([click])
        visited = set(tuple(click))
        number_location = set()
        while queue:
            x, y = queue.popleft()
            if (x, y) in number_location:
                continue
            mine_count = 0
            temp_queue = deque()
            for _x, _y in [[-1, -1], [-1, 0], [-1, 1], [0, -1], 
                           [0, 1], [1, -1], [1, 0], [1,1]]:
                next_x, next_y = x + _x, y + _y
                if not (0 <= next_x < len(board)) or not (0 <= next_y < len(board[0])):
                    continue
                if board[next_x][next_y] == 'M':
                    mine_count += 1
                if (next_x, next_y) not in visited and board[next_x][next_y] == 'E':
                    temp_queue.append([next_x, next_y])
                    
            if mine_count > 0:
                board[x][y] = str(mine_count)
                number_location.add((x,y))
            else:
                board[x][y] = 'B'
                for each in temp_queue:
                    visited.add((each[0], each[1]))
                queue += temp_queue

        return board

107 https://leetcode.com/problems/binary-tree-level-order-traversal-ii/

class Solution:
    def levelOrderBottom(self, root: Optional[TreeNode]) -> List[List[int]]:
        if not root:
            return root
        
        d = {}
        queue = [[root, 0]]
        while queue:
            node, depth = queue.pop(0)
            if depth not in d:
                d[depth] = []
            d[depth].append(node.val)
            if node.left:
                queue.append([node.left, depth + 1])
            if node.right:
                queue.append([node.right, depth + 1])
        return [r[1] for r in sorted(d.items(), key=lambda x: -x[0])]

637 https://leetcode.com/problems/average-of-levels-in-binary-tree/

 

바로 위의 107번 소스에서 끝만 바꿔준다.

class Solution:
    def averageOfLevels(self, root: Optional[TreeNode]) -> List[float]:
        if not root:
            return root
        
        d = {}
        queue = [[root, 0]]
        while queue:
            node, depth = queue.pop(0)
            if depth not in d:
                d[depth] = []
            d[depth].append(node.val)
            if node.left:
                queue.append([node.left, depth + 1])
            if node.right:
                queue.append([node.right, depth + 1])
        return [sum(r[1])/len(r[1]) for r in sorted(d.items(), key=lambda x: x[0])]

429 https://leetcode.com/problems/n-ary-tree-level-order-traversal/

 

위의 107번 소스에서 중간 if node.left:~ if node.right:~ 탐색부분 4줄을 돌아가면서 탐색하도록 하면 된다.

class Solution:
    def levelOrder(self, root: 'Node') -> List[List[int]]:
        if not root:
            return root
        
        d = {}
        queue = [[root, 0]]
        while queue:
            node, depth = queue.pop(0)
            if depth not in d:
                d[depth] = []
            d[depth].append(node.val)
            for child in node.children:
                if child:
                    queue.append([child, depth + 1])
        return [r[1] for r in sorted(d.items(), key=lambda x: x[0])]

111 https://leetcode.com/problems/minimum-depth-of-binary-tree/

from collections import deque

class Solution:
    def minDepth(self, root: Optional[TreeNode]) -> int:
        if not root:
            return 0
        
        queue = deque([[root, 1]])
        min_level = 99999999999
        while queue:
            node, level = queue.popleft()
            if not node.left and not node.right:
                min_level = min(min_level, level)
            if node.left and level + 1 < min_level:
                queue.append([node.left, level + 1])
            if node.right and level + 1 < min_level:
                queue.append([node.right, level + 1])
        return min_level

993 https://leetcode.com/problems/cousins-in-binary-tree/

from collections import deque

class Solution(object):
    def isCousins(self, root, x, y):
        if not root:
            return []
         
        queue = deque([[root, root.val, 0]])
        nodelist = []
        while queue:
            node, parent, level = queue.popleft()
            if node.val in [x, y]:
                nodelist.append([parent, level])
            if node.left:
                queue.append([node.left, node.val, level + 1])
            if node.right:
                queue.append([node.right, node.val, level + 1])
                
        return nodelist[0][0] != nodelist[1][0] and nodelist[0][1] == nodelist[1][1]

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

 

pow구현 문제. 배워갑니다. https://leetcode.com/problems/powx-n/discuss/19560/Shortest-Python-Guaranteed

class Solution(object):
    def myPow(self, x, n):
        if n < 0:
            x = 1 / x
            n = -n
            
        p = 1
        while n:
            if n & 1:
                p *= x
            
            x *= x
            n >>= 1
        return p