首页 > 其他分享 >【力扣】3145.大数组元素的乘积

【力扣】3145.大数组元素的乘积

时间:2024-08-28 13:54:28浏览次数:13  
标签:乘积 nums big long 力扣 re 3145 数组 queries

题目描述

一个非负整数 x 的 强数组 指的是满足元素为 2 的幂且元素总和为 x 的最短有序数组。下表说明了如何确定 强数组 的示例。可以证明,x 对应的强数组是独一无二的。

数字二进制表示强数组
100001[1]
801000[8]
1001010[2, 8]
1301101[1, 4, 8]
2310111[1, 2, 4, 16]

我们将每一个升序的正整数 i (即1,2,3等等)的 强数组 连接得到数组 big_nums ,big_nums 开始部分为 [1, 2, 1, 2, 4, 1, 4, 2, 4, 1, 2, 4, 8, ...] 。

给你一个二维整数数组 queries ,其中 queries[i] = [fromi, toi, modi] ,你需要计算 (big_nums[fromi] * big_nums[fromi + 1] * ... * big_nums[toi]) % modi 。

请你返回一个整数数组 answer ,其中 answer[i] 是第 i 个查询的答案。

示例 1:

输入:queries = [[1,3,7]]

输出:[4]

解释:

只有一个查询。

big_nums[1..3] = [2,1,2] 。它们的乘积为 4。结果为 4 % 7 = 4

示例 2:

输入:queries = [[2,5,3],[7,7,4]]

输出:[2,2]

解释:

有两个查询。

第一个查询:big_nums[2..5] = [1,2,4,1] 。它们的乘积为 8 。结果为  8 % 3 = 2

第二个查询:big_nums[7] = 2 。结果为 2 % 4 = 2

提示:

  • 1 <= queries.length <= 500
  • queries[i].length == 3
  • 0 <= queries[i][0] <= queries[i][1] <= 1015
  • 1 <= queries[i][2] <= 105

AC代码

class Solution {
public:
    int fastpow(long long x, long long m, long long mod) { //递归快速幂
        if (mod == 1) return 0; //特例
        if (m == 0) return 1;
        long long re = fastpow(x, m / 2, mod);
        if (m % 2) return re * re * x % mod;
        else return re * re % mod;
    }

    long long psum(long long p) {
        long long re = 0, n = 0, cnt = 0, sum = 0;
        for (long long i = __lg(p + 1); i >= 0; i--) { //__lg取二进制最高位的1
            long long num = (cnt << i) + (i << i >> 1); // 新增的幂次个数
            if (num <= p) {
                p -= num;
                re += (((i * (i - 1)) << i >> 2) + (sum << i));
                sum += i; // 之前填的 1 的幂次之和
                cnt++; // 之前填的 1 的个数
                n |= 1LL << i; // 填 1, 1LL临时扩容
            }
        }
        while (p--) {
            re += __builtin_ctzll(n); //返回二进制末尾0的个数
            n &= n - 1; // 去掉最低位的 1(置为 0)
        }
        return re;
    }

    vector<int> findProductsOfElements(vector<vector<long long>>& queries) {
        vector<int> ans;
        for (auto& q : queries) {
            auto l = psum(q[0]);
            auto r = psum(q[1] + 1);
            ans.push_back(fastpow(2, r - l, q[2]));
        }
        return ans;
    }
};

标签:乘积,nums,big,long,力扣,re,3145,数组,queries
From: https://blog.csdn.net/2302_80216196/article/details/141638968

相关文章

  • 56. 合并区间【 力扣(LeetCode) 】
    一、题目描述  以数组intervals表示若干个区间的集合,其中单个区间为intervals[i]=[starti,endi]。请你合并所有重叠的区间,并返回一个不重叠的区间数组,该数组需恰好覆盖输入中的所有区间。二、测试用例示例1:输入:intervals=[[1,3],[2,6],[8,10],[15,18]]输......
  • 力扣刷题---链表专题(超详细解析!!!)
    文章目录题目203.移除链表元素876.链表的中间结点024.反转链表21.合并两个有序链表面试题02.04分割链表面试题02.02.返回倒数第K个节点023.相交链表题目203.移除链表元素题目链接这个题目有两种方法,第一种是创建新的链表,然后将原链表遍历一遍,跳过所有值为val的......
  • 力扣34
    classSolution{publicint[]searchRange(int[]nums,inttarget){intx=left(nums,target);if(x==-1){returnnewint[]{-1,-1};}else{returnnewint[]{x,right(nums,target)};}}......
  • 力扣35
    1.Java的二分查找publicintsearchInsert(int[]nums,inttarget){inti=0,j=nums.length-1;while(i<=j){intm=(i+j)>>>1;if(target<nums[m]){j=m-1;}......
  • 二分查找算法:朴素二分+左右边界二分&力扣实战应用
    目录:1、二分查找算法简介2、算法原理及时间复杂度分析2.1朴素二分算法3.2查找左右边界的二分算法3.2.1查找左边界3.2.2查找右边界3.3时间复杂度分析3、二分查找算法模版3.1朴素二分模版3.2查找左右边界的二分模版4、算法应用【leetcode】4.1题一:搜素插入位......
  • 用哈希表求解力扣第217题 存在重复元素
    前言记录一下刷题历程力扣第217题存在重复元素两数之和原题目:给你一个整数数组nums。如果任一值在数组中出现至少两次,返回true;如果数组中每个元素互不相同,返回false。示例1:输入:nums=[1,2,3,1]输出:true示例2:输入:nums=[1,2,3,4]输出:false示例3:输......
  • 程序员必备的的5个刷题网站。大厂面试稳了 力扣 https://leetcode.cn
    程序员必备的的5个刷题网站。大厂面试稳了力扣https://leetcode.cn1、leetcode力扣。网址:https://leetcode.cnLeetCode是一个定位为求职的刷题网站,其中又以算法题为主。很多大厂在面试的时候,都会考算法。有空就刷一刷这里面的算法题,你的算法水平肯定会有大幅的提升,不管是求职,......
  • 【数据结构-前缀异或和】力扣1177. 构建回文串检测
    给你一个字符串s,请你对s的子串进行检测。每次检测,待检子串都可以表示为queries[i]=[left,right,k]。我们可以重新排列子串s[left],…,s[right],并从中选择最多k项替换成任何小写英文字母。如果在上述检测过程中,子串可以变成回文形式的字符串,那么检测结果为......
  • 力扣刷题(1)
    两数之和两数之和-力扣思路:动态开辟一个数组,用来存放下标;两个for循环嵌套来判断,数组中的两个数相加是否与target相等若相等,则将*returnSize赋值为2,表示数组中两个数,并将arr数组进行赋值若不存在两数相加为target的数,则将*returnSize赋值为0int*twoSum(int*nums,in......
  • 秋招力扣Hot100刷题总结——二叉树
    二叉树相关的题目基本上都会使用递归,因此做二叉树的题目时首先使用递归,明确递归结束的条件。1.二叉树的层序遍历题目链接题目要求:给你二叉树的根节点root,返回其节点值的层序遍历。(即逐层地,从左到右访问所有节点)。代码及思路使用队列存储每一层的节点,左边节点先......