前两天终于实现了***,现在开刷leetcode,久闻大名,今天才开始真是惭愧!
刷题的奥义在于一定要分tag,一段时间(比如一周)只刷一种能行,浅尝辄止随便去刷很容易忘记,单恋一种题型又容易被困住思维,本周我选择动态规划!刷个十道,同时C++和java混用着做
给定一个整数数组 nums,求出数组从索引 i 到 j (i ≤ j) 范围内元素的总和,包含 i, j 两点。
示例:
给定 nums = [-2, 0, 3, -5, 2, -1],求和函数为 sumRange()
sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
说明:
你可以假设数组不可变。
会多次调用 sumRange 方法。
其实这道题不难,一眼就看出用数组循环
class NumArray {
public:
vector<int> nums;
NumArray(vector<int> nums) {
this->nums=nums;
}
int sumRange(int i, int j) {
int sum=0;
for(int b=i;b<j+1;b++){
sum+=nums[b];
}
return sum;
}
};
然而显示我速度只超过了2%的人,为什么不贴java的,因为java直接超时,过不了!
上面的代码的问题在于,当测试用例过多时,每次都必须重新计算,但实际上,由于数组没变,所以可以事先计算好大部分数据,用另外一个数组来保存,而此时,就用动态规划来保存
class NumArray {
int [] nums;
int len;
int [] sum;
public NumArray(int[] nums) {
this.nums=nums;
len=nums.length;
if(len>0){
sum=new int [len+1]
for(int i=1;i<len+1;i++)
//sum[i]不包括nums[i],因为sumRange中会被减掉
sum[i]=sum[i-1]+nums[i-1];
}
}
public int sumRange(int i, int j) {
int s=0;
s=sum[j+1]-sum[i];
return s;
}
}
上面的代码不仅可以用java,而且超过了80%的人哦!
那你可能会好奇,最快的代码是什么样的呢?
下面这个,同样的动态规划,用时只有我的一半!
class NumArray {
int[] nums;
public NumArray(int[] nums) {
//这里全盘使用this指针,创建的变量数达到最少
this.nums = new int[nums.length];
if(this.nums.length == 0) return;
this.nums[0] = nums[0];
for(int i=1; i<nums.length;i++) {
this.nums[i] = this.nums[i-1] + nums[i];
}
}
public int sumRange(int i, int j) {
//这里他没有新设变量,而是直接返回结果
return i==0? nums[j]:nums[j]-nums[i-1];
}
}