面试编程题1：充分利用已知的计算条件

上篇说到，要想在面试中处于不败之地，不能靠简单的刷题，而是要学会分析题目，尽可能找出内在规律，思维要敏捷。要想达到这种功力，需要平时多注意进行有意识的训练总结。

今天继续，训练一个实际题目。

先看题目，给定一个数字num，找出序列[0,1,2,…,num]的每一个数字中二进制表示1的个数，要求时间复杂度为O(n)

确定每一个数二进制表示的1的个数，是很容易的，时间复杂度为O(sizeof(i))，如果求n个数，则时间复杂度为O(n*sizeof(i))，但是它不能满足时间性能要求。

这进一步验证了容易想到的，往往不是高效的。

既然时间复杂度可以优化，则一定可以找出内在的规律，如果能根据已知1s的个数，推理出要求数的1s，则无疑可以降低时间复杂度。所谓的动态规划，其实就是这个思想。

借助例子寻找规律是最自然不过的事情，采用此方法：

1Input: 5，则需要找到0,1,2,3,4,5这六个数字的1s:
2Output: [0,1,1,2,1,2]

观察到2,4,8，..。， 以此类推，这类2的整数次幂的1s个数一定为1，比如寻找数字5的1s个数，我们该如何利用已经求得的0,1,2,3,4的1s个数？设定f(i)表示数字i的1s个数，则

将数字5分解为比它小的两个数字的和： 5 = 5/2 + 5%2 , 这就转化成求数字2和3的1s个数，因为f(2)和f(3)在计算f(5)前已经计算出来，所以这样就找到了一个转移方程：

1f(i) = f(i/2) + f(i%2)

如果直接拿这个公式，基本3行代码，提交后会报错！为什么，因为没有考虑dp状态方程的初始条件！

一旦找到转移方程，切记：一定要考虑状态方程的初始条件

1f(0) = 0
2f(1) = 1

这样再提交代码：

 1class Solution {
 2    public int[] countBits(int num) {
 3        int[] rtn = new int[num+1]; 
 4        rtn[0]=0;
 5        rtn[1]=1;
 6        for(int i=1; i<=num;i++){    
 7            rtn[i] = rtn[i/2]+ rtn[i%2];
 8        }
 9        return rtn;
10    }
11}

还是有问题，因为没有考虑算法的边界情况。

当num=0时，返回的数组个数只有1个元素，但是以上算法中默认rtn中至少有两个元素。所以会出现越界的错误。

最终代码：

 1class Solution {
 2    public int[] countBits(int num) {
 3        int[] rtn = new int[num+1]; 
 4        if(num==0)
 5            return rtn;
 6        rtn[1]=1;
 7        for(int i=1; i<=num;i++){    
 8            rtn[i] = rtn[i/2]+ rtn[i%2];
 9        }
10        return rtn;
11    }
12}

面试时，准确无误地计算出结果才能pass，即便找到规律，解决了最主要的部分，如果忽视细节，也不能过关。因此，平时训练中也要细心一些，这样才不至于被挂在细节上！

以上就是题目分析过程。接下来将与BAT面试题系列齐头并进，敬请大家关注，如果觉得不错，欢迎点赞和转发。