现在的位置: 首页 > 编程技术 > 算法学习 > 正文

leetcode Counting Bits 题解

2016年03月25日 算法学习 ⁄ 共 358字 ⁄ 字号 leetcode Counting Bits 题解已关闭评论 ⁄ 阅读 1178 次

https://leetcode.com/problems/counting-bits/

题目大意:给定一个非负整数num。对于每一个满足0 ≤ i ≤ num的数字i,计算其数字的二进制表示中1的个数,并以数组形式返回。

这道题要用前面的数字的结果来得出后面的才能保证时间复杂度,一个数的二进制一的个数等于他的二进制的数向右移一位的一个数加上他的最后一个的数字的是不是一的个数。这里i可以从0或者1开始,因为新建的数组默认每个都是0.

	
public class Solution {
		public int[] countBits(int num) {
			int[] results = new int[num + 1];
			for (int i = 1; i < num + 1; i++) { 
                          results[i] = results[i >> 1] + i % 2;
			}
			return results;
		}
	}

抱歉!评论已关闭.