LeetCode 337. House Robber III
문제 요약: 이진 트리가 주어졌을때 서로 인접하지 않는 노드들의 최대값을 구하시오. 예: input : [3,2,3,null,3,null,1] output: 7 input: [3,4,5,1,3,null,1] output: 9 문제 접근: root 노드부터 자기자신을 포함했을때와, 안포함했을때의 값을 저장해 둔다음, 자식노드의 값을 비교하여 마지막 노드까지 내려간다. 처음 예제에서 3과 2+3을 가지고 있고 그 자식노드에서 3+3+1과 2+3를 저장해두고 또 자식노드로 가서 비교를 하는 방식으로 구현하면 될 거 같다. 구현 코드: /** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * Tr..
LeetCode 338. Counting Bits
문제 요약: 숫자(input)가 주어졌을때, 1부터 주어진 숫자까지 각각 2진수로 변환했을때, 각각 1의 갯수를 배열로 반환 하시오. 예: input: 2 -> 정답: [0,1,1] input: 5 -> 정답: [0,1,1,2,1,2] 문제 접근: 단순하게 반복문을 돌면서, 각각의 숫자를 2진수로 변환해서 1의 갯수를 구하면되는데, 구글링중 2진수의 규칙을 쉽게 구현할 수 있을거 같아서, 그 원리를 코드로 구현했다. 더 효율적인 코드들이 있는거 같지만 이해하는데는 이게 제일 쉬운거 같아서 아래와 같이 구현했다. 2진수 규칙: 2의 제곱수다음 숫자는 다음 2의 제곱수가 오기 전까지, 현재의 제곱수에 1부터 더하는 규칙을 가지고 있다. 말로 쓰기 어려워서 아래와 같이 보면 이해하기 쉬울?수도 있다. 0 ->..