Ahri-珊

day24将分享LeetCode算法题292，303，326。

LeetCode

今天的三道题涉及到递归、数组区间。

303. Range Sum Query - Immutable

求数组i到j个元素的和

心路历程

1.这道题第一反应就是直接遍历相加，心想怎么会有这么简单的题= =

2.然后很正常的时长超出了

3.因为，每次调用sunRange都要遍历一次数组，所以太耗费时间了

4.所以，我们在构造函数里就把0-i的和存到新的数组arr，这样sunRange函数里直接取arr数组值就可以啦

代码：

var NumArray = function(nums) {
    var arr = [];
    arr[0] = nums[0];
    for(let i=1;i<nums.length;i++)
        {
            arr[i] = nums[i]+arr[i-1];
        }
    this.nums = arr;
};
NumArray.prototype.sumRange = function(i, j) {
      return i==0?this.nums[j]:this.nums[j]-this.nums[i-1];
};

292. Nim Game

把数组中的零都甩到最后去

心路历程

1.有4个石子，无论怎么拿都会输，有5-7个石子，你可以让对手只有4个石子，可以赢

2.继续找规律你会发现，石子个数是4的倍数的时候你就没办法赢啦

代码：

var canWinNim = function(n) {
   if(n%4==0)
       return false;
    else
        return true;
};

326. Power of Three

不用循环判断n是不是三的倍数

心路历程

1.由于题目要求不允许使用循环，所以我们采用递归的方法

2.如果n不能被3整除，返回false

3.如果n能被3整除，将n/3作为下一次递归的参数

4.如果n等于1，返回true

5.特殊情况：不能作为被除数的0返回false

代码：

var isPowerOfThree = function(n) {
    if(n==0)
        return false;
    if(n==1)
        return true;
    if(n%3==0)
        {
            return isPowerOfThree(Math.floor(n/3));
        }
    else
        return false;
    
};

END