Ahri-珊

day9将分享LeetCode算法题191，198，202。

LeetCode

今天的三道题涉及到2进制数、动态规划、递归。

191. Number of 1 Bits

计算一个数转换成2进制数后有多少个1。

心路历程

1.将整数转化为2进制。

2.若n%2等于1的时候，计数器加1

3.当n=0时退出循环

代码：

var hammingWeight = function(n) {
    var count = 0;
    while(n>0)
        {
            if(n%2==1)
                count++;
            n = Math.floor(n/2);
        }
    return count;
};

198. House Robber

小偷只能抢不相邻的房间，计算小偷最多能抢多少钱！

心路历程

题目类型：动态规划

1.若数组长度为3，则最优解为nums[1]与nums[2]+nums[0]中更大的那

个。

2.从第四个值开始，它可以选择它的前一个不相邻元素也可以选择前第

二个不相邻元素，局部最优为nums[i]+nums[i-3]与nums[i]+nums[i-2]

中更大的那一个。

3.将局部最优解存在nums[i];

4.最后只需比较倒数第一个元素与倒数第二个元素谁更优就行了。

代码：

var rob = function(nums) {
    if(nums.length==0)
        return 0;
    if(nums.length==1)
        return nums[0];
    if(nums.length==2)
        return Math.max(nums[0],nums[1]);
    if(nums.length==3)
        return Math.max(nums[0]+nums[2],nums[1]);
    nums[2] = nums[0]+nums[2];
    for(let i=3;i<nums.length;i++)
        {
            nums[i] = Math.max(nums[i]+nums[i-3],nums[i]+nums

[i-2]);
        }
    return Math.max(nums[nums.length-1],nums[nums.length-2]);
};

202. Happy Number

求快乐数，若一个数每位的平方相加所得结果的每位数平方再相加，如此下去，最终能得到1，则它就是快乐的！

心路历程

1.解题方法：递归

2.做什么：对当前数的每一位求平方相加，将所得之和作为下一次递归

的参数。

3.递归出口：当所得之和为1的时候返回true，当所得之和在已经出现

过了返回false(比如2:每次执行递归函数的结果为 4，16，37，58，89

，42，20，4(返回false))

代码：

var nums = [];
var isHappy = function(n) {
    var temp=0;
    while(n>=1)
    {
        temp = temp+(n%10)*(n%10);
        n = Math.floor(n/10);
    }
    if(temp==1)
        {
            nums = [];
            return true;
        }
    if(nums.indexOf(temp)!=-1)
        {
            nums = [];
            return false;
        }
    nums.push(temp);
    return isHappy(temp);
};

END