数组查询问题-LeetCode 303、304、306
数组查询问题-LeetCode 303、304、306
作者：TeddyZhang，公众号：算法工程师之路 1
编程题
【LeetCode #303】区域和检索-数组不可变
给定一个整数数组 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> sum;
NumArray(vector<int>& nums) {
if(!nums.empty()){
sum.push_back(nums[]);
for(int i = ; i < nums.size(); i++){
sum.push_back(sum[i-1]+nums[i]);
}
}
}
int sumRange(int i, int j) {
if(i == ) return sum[j];
else return sum[j]-sum[i-1];
}
};
/**
* Your NumArray object will be instantiated and called as such:
* NumArray* obj = new NumArray(nums);
* int param_1 = obj->sumRange(i,j);
*/
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/range-sum-query-immutable
【LeetCode #304】二维区域和检索-矩阵不可变
解题思路：
由于在程序中循环是从1开始的，因此dp矩阵大小为（M+1, N+1），并且dp[i][j]表示从matrix[0][0]到matrix[i-1][j-1]之间的矩形的数字之和！因此我们可以得出递推式： dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1].
class NumMatrix {
public:
NumMatrix(vector<vector<int>>& matrix) {
int M = matrix.size();
int N;
if(M == ) N = ;
else N = matrix[].size();
dp = vector<vector<int>>(M+, vector<int>(N+,));
for(int i = ; i <= M; i++){
for(int j = ; j <= N; j++){
dp[i][j] = matrix[i-1][j-1] +
dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];
}
}
}
int sumRegion(int row1, int col1, int row2, int col2) {
int res = dp[row2+][col2+];
res -= dp[row1][col2+];
res -= dp[row2+][col1];
res += dp[row1][col1];
return res;
}
private:
vector<vector<int>> dp;
};
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix* obj = new NumMatrix(matrix);
* int param_1 = obj->sumRegion(row1,col1,row2,col2);
*/
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/range-sum-query-immutable
【LeetCode #306】累加数
累加数是一个字符串，组成它的数字可以形成累加序列。 一个有效的累加序列必须至少包含 3 个数。除了最开始的两个数以外，字符串中的其他数都等于它之前两个数相加的和。 给定一个只包含数字 '0'-'9' 的字符串，编写一个算法来判断给定输入是否是累加数。 说明: 累加序列里的数不会以 0 开头，所以不会出现 1, 2, 03 或者 1, 02, 3 的情况。
示例 1: 输入: "112358" 输出: true 解释: 累加序列为: 1, 1, 2, 3, 5, 8 。1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8
class Solution {
private:
string addS(string &s1, string &s2)
{
int i=s1.size()-1, j=s2.size()-1,k=max(i,j), carrier=,temp;
string res(k+,'0');
for(; i>= || j>=; --i,--j)
{
temp = (i<?:(s1[i]-'0')) + (j<?:(s2[j]-'0')) + carrier;
res[k--] = (temp % + '0');
carrier = temp>;
}
return carrier>?'1'+res:res;
}
public:
bool isAdditiveNumber(string num) {
int i, j, curIdx, len = num.size();
string sum, op1, op2;
for(i=; i<= (num[] !='0'? (len-1)/:);++i)
{
for(j=; j <= (num[i] !='0'? len-i*:);++j)
{
if(len<i+j+max(i,j)) break;
op1 = num.substr(,i);
op2 = num.substr(i,j);
sum = addS(op1, op2);
curIdx=i+j;
while(curIdx<len && sum == num.substr(curIdx,sum.size()) )
{
curIdx += sum.size();
op1 = sum;
sum = addS(sum, op2);
op2 = op1;
}
if(curIdx==len) return true;
}
}
return false;
}
};
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/additive-number