forked from DaleStudy/leetcode-study
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathYjason-K.ts
More file actions
25 lines (22 loc) Β· 868 Bytes
/
Yjason-K.ts
File metadata and controls
25 lines (22 loc) Β· 868 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
* κ° μμ λΉνΈμ κ°μλ₯Ό κ³μ°νλ ν¨μ
* @param {number} nums - μ΅λ μ
* @returns {number[]} - κ° μμ λΉνΈμ κ°μ λ°°μ΄
*
* μκ° λ³΅μ‘λ: O(n)
* - nums λ§νΌ λ°λ³΅νλ©°, κ° μμ λΉνΈμ κ°μλ₯Ό κ³μ°
*
* κ³΅κ° λ³΅μ‘λ: O(n)
* - dp λ°°μ΄μ μ¬μ©νμ¬ O(n) λ§νΌ μΆκ° 곡κ°μ΄ νμ
*/
function countBits(nums: number): number[] {
// dp λ°°μ΄μ μμ±νκ³ , λͺ¨λ 0μΌλ‘ μ΄κΈ°νν©λλ€.
const dp: number[] = new Array(nums + 1).fill(0);
// κ° μμ λν΄, λΉνΈμ κ°μλ₯Ό κ³μ°ν©λλ€.
for (let num = 1; num <= nums; num++) {
// numμ 2μ§μλ‘ νννμ λ, 1μ κ°μλ 2μ§μλ‘ λ³ννμ¬ λ¬Έμμ΄λ‘ λ³ν ν,
// '1'μ΄ ν¬ν¨λ λ¬Έμμ΄μ κΈΈμ΄λ₯Ό κ³μ°ν©λλ€.
dp[num] = dp[Math.floor(num / 2)] + (num % 2);
}
return dp;
}