In this Leetcode Counting Bits problem solution we have given an integer n, return an array ans of length n + 1 such that for each i (0 <= i <= n), ans[i] is the number of 1's in the binary representation of i.
Problem solution in Python.
class Solution(object): def countBits(self, num): if num == 0: return [0] dp = [0]*(num+1) dp[0] = 0 dp[1] = 1 for i in range(2, num+1): if i%2 == 0: dp[i] = dp[i/2] else: dp[i] = 1 + dp[(i-1)/2] return dp
Problem solution in Java.
class Solution { public int[] countBits(int num) { int[] dp = new int[num+1]; dp[0] = 0; int nearest = 0; for (int k = 1; k <= num; k++) { if ((k & (k-1)) == 0) { dp[k] = 1; nearest = k; } else { dp[k] = dp[k-nearest] + dp[nearest]; } } return dp; } }
Problem solution in C++.
class Solution { public: vector<int> countBits(int num) { vector<int>res(num+1); res[0] = 0; for(int i = 1 ; i <= num ; i++) res[i] = res[i/2] + (i&1); return res; } };
Problem solution in C.
int* countBits(int num, int* returnSize) { int i =0,k = 4, ano = 4; int num1 = num; *returnSize = (num+1); int *arr = malloc(sizeof(int)*(num+1)); if(num1>3) num1 = 3; switch(num1){ case 3: arr[3] = 2; num--; num1--; case 2: arr[2] = 1; num--; num1--; case 1: arr[1] = 1; num--; num1--; case 0: arr[0] = 0; num--; break; } while(num >= 0){ if(i>=ano) { ano *= 2; i = 0; } arr[k] = arr[i%ano] + 1; i++; k++; num--; } return arr; }
0 Comments