怎么做网站seo优化百度推广方法
只是记录
题目链接
题目链接
自己想出来的 第一种解法
思路简述
遍历[0,n]之间的数字，对于每一个数字按照二进制的方式展开，判断最低位置是否为1，若为1则+1，反之不加，直到该数字等于0就停止。
public static int[] countBits(int n) {int[] res = new int[n+1];res[0] = 0;for(int i=1;i<=n;i++){int t = i;int sum = 0;while (t>0){sum = sum + (t&1);t/=2;}res[i]=sum;}return res;}
时间复杂度：O（NlogN）
空间复杂度：O(N)
解法二 动态规划
我是没有想到的哈，我想到的是题目既然说有一种时间复杂度为O(N)的解法
我当时想到的是找数字和他们二进制数中含1的个数之间的规律。但冥思苦想了好久，实在想不出来，看别人的讲解
下面的推导过程
十进制 二进制 二进制中含1的个数
000 − > 000 − > 0 000->000->0 000−>000−>0
001 − > 001 − > 1 001->001->1 001−>001−>1
002 − > 010 − > 1 002->010->1 002−>010−>1
003 − > 0011 − > 2 003->0011->2 003−>0011−>2
004 − > 0100 − > 1 004->0100->1 004−>0100−>1
005 − > 0101 − > 2 005->0101->2 005−>0101−>2
006 − > 0110 − > 2 006->0110->2 006−>0110−>2
007 − > 0111 − > 3 007->0111->3 007−>0111−>3
008 − > 1000 − > 1 008->1000->1 008−>1000−>1
既然是偶数，那么一定可以将2左移一定次数后得到该偶数。我们假设左移1位的数字是n,不做任何操作的数字是n/2, 那么dp[n] = dp [n/2],
例如6和3，他们中的二进制数含1的个数是一样的
偶数解决了，奇数怎么办？奇数可以看成偶数+1，又因为偶数是dp[n]=dp[n/2],所以奇数直接就是dp[n]=dp[n/2]+1
好，递推公式搞定，接下来初始化问题，当n为0的时候，那么结果就是0，所以你不用初始化也可以
public static int[] countBits(int n) {int[] res = new int[n+1];res[0] = 0;for(int i=1;i<=n;i++){if(i % 2 == 0)res[i] = res[i/2];elseres[i] = res[i/2] + 1;}return res;}
搞定