今日刷题记录
1. 二的幂数组中查询范围内的乘积leetcode.2438
关键词：前缀和 位运算
问题解析：
- 找到一个只包含 2 的幂的且和为给定 n,按不严格递增排序,没有要求连续,要求长度最短的数组 power
- 给定一个二维数组 queries 包含 left 和 right 两个元素,要求返回 answers 数组,每个元素为 power 中下标从 left 到 right 的元素累乘
- answers 长度和 queries 长度一样,每个 answer 对 10e9+7 取余
核心思路
- 既然要求最短,那么一定是从大的开始找,这个思路很好想,但是 2 的幂可以用位运算来求
- 15 分解为 2 的幂,转化为二进制为 1111,对应 1,2,4,8;
- 所以分解为 2 的幂,就是取该值转化为二进制后 1 位子对应的数
vector<int> arr;
int t = 1;
while(n>0){
if((n&1)) arr.push_back(t);
t *= 2;
n>>=1;
}- 直接暴力没得说,这题考点主要是位运算,对于第二个暴力其实不怎么样,复杂度为 O(n^10)按道理是会超时的,但是就这么过了,我来优化一下第二部分
- 因为是连续的区间内累乘,所以我想到了前缀和,其实就是这样,但是加法的逆元是减法,可是累乘之后取余无法再像普通乘法那样逆元了,这是一个最大的难点,但是只要计算逆元一定要往和去想,我们可以这样想,powers 数组里的都是 2 的幂,也就是说底数相同那么
- \ 2^2+2^3+2^4+2^5 = 2^ 可以看到可以直接先计算指数的和,再来计 算 2的幂, 2的幂要先预处理
//预处理
const int mod = 1000000007;
int qpow[436] = {1};
int init = []{
for(int i = 1;i<436;i++){
qpow[i] = qpow[i-1]*2%mod;
}
return 0;
}();
vector<int> ans;
int m = powers.size();
vector<int> pre(m+1);
for(int i = 0;i<m;i++){
pre[i+1] = pre[i]+powers[i];
}
for(auto q:queries){
int sum = pre[q[1]+1] - pre[q[0]];
ans.push_back(qpow[sum]);
}- 还有一个我一直区分错了的,我一直以为前缀和其实就是预处理,但这两者有区别,预处理是一个手段,而前缀和是预处理的特别应用,以下是预处理,先打好每一种情况的表,再去查询
vector<int> ans;
int m = powers.size();
vector pre_arr(m,vector<int>(m));
for(int i = 0;i<m;i++){
pre_arr[i][i] = powers[i];
for(int j = i+1;j<m;j++){
pre_arr[i][j] = (long long)pre_arr[i][j-1]*powers[j]%mod;
}
}
for(auto q:queries){
ans.push_back(pre_arr[q[0]][q[1]]);
}最终代码片段：
const int mod = 1000000007;
int qpow[436] = {1};
int init = []{
for(int i = 1;i<436;i++){
qpow[i] = qpow[i-1]*2%mod;
}
return 0;
}();
class Solution {
public:
vector<int> productQueries(int n, vector<vector<int>>& queries) {
vector<int> powers;
int t = 0;
while(n>0){
if((n&1)) powers.push_back(t);
t++;
n>>=1;
}
vector<int> ans;
int m = powers.size();
vector<int> pre(m+1);
for(int i = 0;i<m;i++){
pre[i+1] = pre[i]+powers[i];
}
for(auto q:queries){
int sum = pre[q[1]+1] - pre[q[0]];
ans.push_back(qpow[sum]);
}
return ans;
}
};学到的点：
- 位运算应用
- 正确区分预处理和前缀和的区别
- 前缀和技巧和正确预处理
今日算法收获
-
新技巧：
- 实际上没有学到什么,这题只是特殊情况罢了
- 但是我知道了还有这种新情况的存在,我以后会往这方面想,也算是长见识了
-
待加强：
- 我以为我掌握了前缀和但只限于普通和,而不能灵活的把其他问题转变为和
-
明日计划：
- [ ]
- [ ]