LeetCode-338. Counting Bits
发布时间:2020-12-14 04:23:15 所属栏目:大数据 来源:网络整理
导读:Given a non negative integer number?num. For every numbers?i?in the range?0 ≤ i ≤ num?calculate the number of 1‘s in their binary representation and return them as an array. Example 1: Input: 2Output: [0,1,1] Example 2: Input: 5Output:
Given a non negative integer number?num. For every numbers?i?in the range?0 ≤ i ≤ num?calculate the number of 1‘s in their binary representation and return them as an array. Example 1: Input: 2
Output: [0,1,1]
Example 2: Input: 5
Output:
[0,2,2]
Follow up:
public int[] countBits(int num) {//位运算 my int[] res = new int[num+1]; for (int i = 0; i <=num ; i++) { res[i]=0; int n = i; while (0!=n){ n= n&(n-1); res[i]++; } } return res; } 时间复杂度O(n),找规律 public int[] countBits(int num) {// O(n) my int[] res = new int[num+1]; res[0]=0; int flag = 1; int j=0; if(num>0){ res[1]=1; } for (int i = 2; i <=num ; i++) { if(i==2*flag){ flag=flag*2; j=0; } res[i]=res[j]+1; j++; } return res; } ? 简洁版 f[i] = f[i / 2] + i % 2 public int[] countBits(int num) { int[] f = new int[num + 1]; for (int i=1; i<=num; i++) f[i] = f[i >> 1] + (i & 1); return f; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |