leetcode 1261(트리), 1395(구현), 1829(bit 비트연산)

1261 https://leetcode.com/problems/find-elements-in-a-contaminated-binary-tree/
이진 트리가 오염되었다고 하고 복구를 먼저 한다음 풀라고 한다. 복구 조건은 루트값은 0부터 시작해서 왼쪽 자식은 2*부모+1, 오른쪽 자식은 2*부모+2이다. init에서 복구하면서 존재하는 값들을 set에 넣어준 후 계산하면된다.

class FindElements(object):
    def __init__(self, root):
        self.val_set = set()
        queue = [[root, 0]]
        while queue:
            n, n_value = queue.pop(0)
            n.val = n_value
            self.val_set.add(n_value)
            if n.left:
                queue.append([n.left, 2*n_value+1])
            if n.right:
                queue.append([n.right, 2*n_value+2])                    
        
    def find(self, target):
        return target in self.val_set

1395 https://leetcode.com/problems/count-number-of-teams/
단순하게 3중 반복문 돌렸는데 이 문제가 의도한게 아닌것같다. 답을 봤는데 알고나니 별거 아닌데 왜 이걸 생각못했는지 모르겠다.
O(n^2)으로 돌면서 현재 값을 기준으로 왼쪽에 현재 값보다 큰 숫자와 작은 숫자의 카운트를 저장한다.
현재 값을 기준으로 오른쪽에 현재 값보다 큰 숫자와 작은 숫자의 카운트를 저장한다.
현재 값보다 작은 왼쪽에 있는 숫자 * 현재 값보다 큰 오른쪽에 있는 숫자 + 현재 값보다 큰 왼쪽에 있는 숫자 * 현재 값보다 작은 오른쪽에 있는 숫자가 답이 된다.

class Solution(object):
    def numTeams(self, r):
        len_r = len(r)
        ret = 0
        for i in xrange(len_r):
            cur,left_low,left_high,right_low,right_high = r[i],0,0,0,0  # cur은 현재 위치의 값.
            for j in xrange(i):  # 현재 숫자의 왼쪽
                if r[j] < cur:
                    left_low += 1  # 왼쪽에 있으면서 낮은애들을 카운트.
                elif r[j] > cur:
                    left_high += 1  # 왼쪽에 있으면서 높은애들을 카운트.
            for j in xrange(i+1, len_r):  # 현재 숫자의 오른쪽
                if r[j] < cur:  # 오른쪽에 있으면서 낮은애들
                    right_low += 1
                elif r[j] > cur:  # 오른쪽에 있으면서 높은애들
                    right_high += 1
            ret += left_low*right_high + left_high*right_low
        return ret

1829 https://leetcode.com/problems/maximum-xor-for-each-query/
문제를 빠르게 한번 훑으면 이해가 잘 안되면서 되게 어려운것처럼 느껴졌는데 찬찬히 읽어보면서 3번정도 읽어보니 이해하면 하나도 어렵지 않다..

class Solution(object):
    def getMaximumXor(self, nums, maximumBit):
        dp = [nums[0]]
        for i in xrange(1, len(nums)):
            dp.append(dp[i-1]^nums[i])  # 현재까지 xor한 값들을 저장해둔다.
        ret = []
        for i in xrange(len(dp)-1, -1, -1):  # 거꾸로 반복하면서 최대값과 xor해준다.
            ret.append(dp[i]^(2**maximumBit-1))
        return ret