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;
};
Comments