[leetcode, JS] 338. Counting Bits

문제

문제 링크 : Counting Bits

풀이

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(n) {
    let result = new Array(n+1).fill(0);
    for(let i=1; i<n+1; i++) {
        result[i] = i.toString(2).match(/1/g).length
    }

    return result
    
};

1. n+1 길이로 array를 생성하고
2. for문을 돌며, array[i] 에 i의 2진수 값중 1의 개수를 구하여 할당

• Runtime 95 ms, Memory 52.7 MB

다른 풀이

/**
 * @param {number} n
 * @return {number[]}
 */
var countBits = function(n) {
    let dp = new Array(n + 1).fill(0);
	let offset = 1;
	for (let i = 1; i <= n; i++) {
		if (offset * 2 === i) offset = i;
		dp[i] = 1 + dp[i - offset];
	}
	return dp;
    
};

1. 1의 개수가 나오는 규칙을 통해 만든 풀이

• Runtime 76 ms, Memory 47.6 MB