侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 674 篇文章
  • 累计创建 128 个标签
  • 累计收到 20 条评论

目 录CONTENT

文章目录

【位运算, 模拟】二的幂数组中查询范围内的乘积【力扣第 89 场双周赛】

GabrielxD
2022-10-16 / 0 评论 / 0 点赞 / 192 阅读 / 720 字
温馨提示:
本文最后更新于 2022-11-04,若内容或图片失效,请留言反馈。部分素材来自网络,若不小心影响到您的利益,请联系我们删除。

题目

6209. 二的幂数组中查询范围内的乘积


给你一个正整数 n ,你需要找到一个下标从 0 开始的数组 powers ,它包含 最少 数目的 2 的幂,且它们的和为 n 。powers 数组是 非递减 顺序的。根据前面描述,构造 powers 数组的方法是唯一的。

同时给你一个下标从 0 开始的二维整数数组 queries ,其中 queries[i] = [lefti, righti] ,其中 queries[i] 表示请你求出满足 lefti <= j <= righti 的所有 powers[j] 的乘积。

请你返回一个数组 answers ,长度与 queries 的长度相同,其中 answers[i]是第 i 个查询的答案。由于查询的结果可能非常大,请你将每个 answers[i] 都对 10^9 + 7 取余 。

示例 1:

输入:n = 15, queries = [[0,1],[2,2],[0,3]]
输出:[2,4,64]
解释:
对于 n = 15 ,得到 powers = [1,2,4,8] 。没法得到元素数目更少的数组。
第 1 个查询的答案:powers[0] * powers[1] = 1 * 2 = 2 。
第 2 个查询的答案:powers[2] = 4 。
第 3 个查询的答案:powers[0] * powers[1] * powers[2] * powers[3] = 1 * 2 * 4 * 8 = 64 。
每个答案对 109 + 7 得到的结果都相同,所以返回 [2,4,64] 。

示例 2:

输入:n = 2, queries = [[0,0]]
输出:[2]
解释:
对于 n = 2, powers = [2] 。
唯一一个查询的答案是 powers[0] = 2 。答案对 109 + 7 取余后结果相同,所以返回 [2] 。

提示:

  • 1 <= n <= 10^9
  • 1 <= queries.length <= 10^5
  • 0 <= starti <= endi < powers.length

解题

方法一:位运算 模拟

思路

由题目给出的定义,要求出 powers 数组有一种简单的方法就是从低位开始遍历 n 的二进制位。
例如:当 n = 15 时,n=15(10)=1111(2)=1×23+1×22+1×21+1×20n = 15_{(10)} = 1111_{(2)}=1 \times 2^3 + 1 \times 2^2 + 1 \times 2 ^ 1 + 1 \times 2 ^ 0
此时:powers=[20,21,22,23]=[1,2,4,8]powers = [2^0, 2^1, 2^2,2^3] = [1, 2, 4, 8]

这样拿到 powers 数组之后剩下的就好做了,直接枚举区间求积就好了。
如果想提高效率可以用前缀积的方式来做,但要注意溢出。

代码

class Solution {
    static final int MOD = (int) 1e9 + 7;
    
    public int[] productQueries(int n, int[][] queries) {
        List<Integer> powers = new ArrayList<>();
        for (int i = 0; i < 32 && n != 0; ++i) {
            int mask = 1 << i;
            if ((n & mask) != 0) powers.add(mask);
        }
        int len = queries.length;
        int[] ans = new int[len];
        for (int i = 0; i < len; ++i) {
            long prod = 1;
            for (int j = queries[i][0], end = queries[i][1]; j <= end; ++j) {
                prod = prod * powers.get(j) % MOD;
            }
            ans[i] = (int) prod;
        }
        return ans;
    }
}
0

评论区