新手怎么优化网站,seo是什么部门,网站备案帐号,j建设网站需要的工具说在前面 #x1f388;不知道大家对于算法的学习是一个怎样的心态呢#xff1f;为了面试还是因为兴趣#xff1f;不管是出于什么原因#xff0c;算法学习需要持续保持。 题目描述
给你一个正整数 n #xff0c;你需要找到一个下标从 0 开始的数组 powers #xff0c;它包…说在前面 不知道大家对于算法的学习是一个怎样的心态呢为了面试还是因为兴趣不管是出于什么原因算法学习需要持续保持。 题目描述
给你一个正整数 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] 都对 109 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 。答案对 10^9 7 取余后结果相同所以返回 [2] 。提示
1 n 10^91 queries.length 10^50 starti endi powers.length
思路分析
首先我们要先理解一下题目的意思题目会给我们一个正整数 n 我们需要找到一个下标从 0 开始的数组 powers 它包含 最少 数目的 2 的幂且它们的和为 n。得到powers数组之后我们需要根据给出的二维整数数组 queries 进行相应的计算其中 queries[i] [lefti, righti] 我们需要求出满足 lefti j righti 的所有 powers[j] 的乘积。
1、获取powers数组
powers数组需要满足以下两个条件 - 它包含 最少 数目的 2 的幂 - 它们的和为 n 所以我们可以先找出小于等于n的所有正整数
const powList [];
let num 1;
while(num n){powList.push(num);num * 2;
}优先取powList中的最大值这样可以用最少数目的整数来组成powers数组
let ind powList.length - 1;
while(n 0){while(powList[ind] n) ind--;n - powList[ind];powers.unshift(ind);
}2、计算乘积
我们初中的时候都学过幂运算这里只需要用到一个简单的运算法则 指数相乘运算公式am·ana^mn。指数是幂运算aⁿa≠0中的一个参数a为底数n为指数指数位于底数的右上角幂运算表示指数个底数相乘。当n是一个正整数aⁿ表示n个a连乘。当n0时aⁿ1。 幂运算是一种关于幂的数学运算。同底数幂相乘底数不变指数相加。同底数幂相除底数不变指数相减。幂的乘方底数不变指数相乘。 所以我们只需要计算指数和再求幂即可。
for(let i 0; i queries.length; i){let ind 0;for(let j queries[i][0]; j queries[i][1]; j) ind powers[j];res.push(quickPow(2,ind));
}完整AC代码如下
AC代码
/*** param {number} n* param {number[][]} queries* return {number[]}*/var productQueries function(n, queries) {const res [];const powers [];const powList [];let num 1;const mod BigInt(1000000007);const quickPow function(a, b) {a BigInt(a);b BigInt(b);let ret BigInt(1);a a % mod;while (b) {if (b BigInt(1)) ret ret * a % mod;a a * a % mod;b b BigInt(1);}return ret;};while(num n){powList.push(num);num * 2;}let ind powList.length - 1;while(n 0){while(powList[ind] n) ind--;n - powList[ind];powers.unshift(ind);}for(let i 0; i queries.length; i){let ind 0;for(let j queries[i][0]; j queries[i][1]; j) ind powers[j];res.push(quickPow(2,ind));}return res;};公众号
关注公众号『前端也能这么有趣』获取更多有趣内容。
说在后面 这里是 JYeontu现在是一名前端工程师有空会刷刷算法题平时喜欢打羽毛球 平时也喜欢写些东西既为自己记录 也希望可以对大家有那么一丢丢的帮助写的不好望多多谅解 写错的地方望指出定会认真改进 偶尔也会在自己的公众号『前端也能这么有趣』发一些比较有趣的文章有兴趣的也可以关注下。在此谢谢大家的支持我们下文再见 。
