磐安县建设局网站,wordpress系列怎么做,海南百度推广电话,网站建设贝尔利文章目录 Power of Heroes 英雄的力量问题描述#xff1a;分析代码Math Tag Power of Heroes 英雄的力量
问题描述#xff1a;
给你一个下标从 0 开始的整数数组 nums #xff0c;它表示英雄的能力值。如果我们选出一部分英雄#xff0c;这组英雄的 力量 定义为#xff… 文章目录 Power of Heroes 英雄的力量问题描述分析代码Math Tag Power of Heroes 英雄的力量
问题描述
给你一个下标从 0 开始的整数数组 nums 它表示英雄的能力值。如果我们选出一部分英雄这组英雄的 力量 定义为 i 0 i 1 . . . i k i_0 i_1 ... i_k i0i1...ik 表示这组英雄在数组中的下标。那么这组英雄的力量为 m a x ( n u m s [ i 0 ] , n u m s [ i 1 ] . . . n u m s [ i k ] ) 2 ∗ m i n ( n u m s [ i 0 ] , n u m s [ i 1 ] . . . n u m s [ i k ] ) max(nums[i_0],nums[i_1] ... nums[i_k])2 * mi_n(nums[i_0],nums[i_1] ... nums[i_k]) max(nums[i0],nums[i1]...nums[ik])2∗min(nums[i0],nums[i1]...nums[ik]) 。 请你返回所有可能的 非空 英雄组的 力量 之和。由于答案可能非常大请你将结果对 10^9 7 取余。 1 n u m s . l e n g t h 1 0 5 1 n u m s [ i ] 1 0 9 1 nums.length 10^5\\ 1 nums[i] 10^9 1nums.length1051nums[i]109
分析
一次周赛的hard当时没时间做。 一开始没看清问题的意思以为要计算子数组而实际上是要求子集。 子集也可以认为是原数组的一个子序列虽然这个说法不是很严谨。
假如有一个子序列这个子序列的 p o w e r power power就是 m a x ∗ m a x ∗ m i n max*max*min max∗max∗min. 暴力 如果是使用暴力的方式就是枚举所有的子序列然后对每个子序列进行找 m a x m i n maxmin maxmin。 以当前数组的规模可能有 2 100000 2^{100000} 2100000个子序列很明显这样不可能即使可以枚举出所有的子序列在计算power的过程中的时间复杂度也是 O ( L ) O(L) O(L),和子序列的长度有关。
既然是找最大和最小那就先排序从小到大。因为是找子序列所以排个序不会影响最终结果。
假设区间 [ j , i ] , i j [j,i],ij [j,i],ij,那么必然 a [ i ] a [ j ] a[i]a[j] a[i]a[j]此时以 a [ i ] a[i] a[i]为最大的子序列就可以计算出来,即 2 i 2^i 2i个,从左向右计算: a [ 0 ] a[0] a[0]为 m i n min min时可以与 a [ i ] a[i] a[i]构造的序列数量为 2 i − 1 2^{i-1} 2i−1它们可以为最终的ans提供 a [ 0 ] ∗ a [ i ] ∗ 2 i − 1 a[0]*a[i]*2^{i-1} a[0]∗a[i]∗2i−1.
同理可以计算得到 a [ 1 ] ∗ a [ i ] ∗ 2 i − 2 a[1]*a[i]*2^{i-2} a[1]∗a[i]∗2i−2. a [ 2 ] ∗ a [ i ] ∗ 2 i − 3 a[2]*a[i]*2^{i-3} a[2]∗a[i]∗2i−3. a [ 3 ] ∗ a [ i ] ∗ 2 i − 4 a[3]*a[i]*2^{i-4} a[3]∗a[i]∗2i−4. … a [ i − 2 ] ∗ a [ i ] ∗ 2 i − 1 − i 2 a[i-2]*a[i]*2^{i-1-i2} a[i−2]∗a[i]∗2i−1−i2 a [ i − 1 ] ∗ a [ i ] ∗ 2 i − 1 − i 1 a[i-1]*a[i]*2^{i-1-i1} a[i−1]∗a[i]∗2i−1−i1 最后还要补一个 a [ i ] 3 a[i]^3 a[i]3单个的也要算。 到此以a[i]为最大的所有子序列的power都可以计算出。 p [ i ] a [ i ] 3 a [ 0 ] ∗ a [ i ] ∗ 2 i − 1 a [ 1 ] ∗ a [ i ] ∗ 2 i − 2 . . a [ i − 1 ] ∗ a [ i ] ∗ 2 i − 1 − i 1 p [ i ] a [ i ] ∗ ( a [ i ] 2 a [ 0 ] ∗ 2 i − 1 a [ 1 ] ∗ 2 i − 2 . . a [ i − 1 ] ∗ 2 i − 1 − i 1 ) p[i] a[i]^3 a[0]*a[i]*2^{i-1} a[1]*a[i]*2^{i-2} .. a[i-1]*a[i]*2^{i-1-i1}\\ p[i] a[i]*( a[i]^2 a[0]*2^{i-1} a[1]*2^{i-2} .. a[i-1]*2^{i-1-i1}) p[i]a[i]3a[0]∗a[i]∗2i−1a[1]∗a[i]∗2i−2..a[i−1]∗a[i]∗2i−1−i1p[i]a[i]∗(a[i]2a[0]∗2i−1a[1]∗2i−2..a[i−1]∗2i−1−i1) 如果此时让k i1,即右移一位 p [ k ] a [ k ] ∗ ( a [ k ] 2 a [ 0 ] ∗ 2 i − 1 ∗ 2 a [ 1 ] ∗ 2 i − 2 ∗ 2 . . a [ i − 1 ] ∗ 2 i − 1 − i 1 ∗ 2 a [ i ] ) p[k] a[k]*( a[k]^2 a[0]*2^{i-1}*2 a[1]*2^{i-2}*2 .. a[i-1]*2^{i-1-i1}*2 a[i])\\ p[k]a[k]∗(a[k]2a[0]∗2i−1∗2a[1]∗2i−2∗2..a[i−1]∗2i−1−i1∗2a[i]) 由于右端点的移动新增了1位a[k],导致一部分同时乘2。 假设计算下标 i i i时 令 S i a [ 0 ] ∗ 2 i − 1 a [ 1 ] ∗ 2 i − 2 . . a [ i − 1 ] ∗ 2 i − 1 − i 1 S_i a[0]*2^{i-1} a[1]*2^{i-2} .. a[i-1]*2^{i-1-i1} Sia[0]∗2i−1a[1]∗2i−2..a[i−1]∗2i−1−i1 那么 p [ i ] a [ i ] ∗ ( a [ i ] 2 S i ) p[i] a[i]*( a[i]^2 S_i) p[i]a[i]∗(a[i]2Si)
而当计算下标 k k k时不需要重复计算 这一部分S而是可以通过前一个i的S来计算出当前所需要的 S k S_k Sk。 S k 2 ∗ S i a [ i − 1 ] S_k 2*S_i a[i-1] Sk2∗Sia[i−1] p [ k ] a [ k ] ∗ ( a [ k ] 2 S k ) ; p[k] a[k]*( a[k]^2 S_k); p[k]a[k]∗(a[k]2Sk); 计算过程中还需要注意取余 代码 Math
class Solution {long MOD (long)1e97;public int sumOfPower(int[] nums) { Arrays.sort(nums);long sum 0,s 0;int n nums.length; for(int i0;in;i){long cur ((long)nums[i])%MOD;long pow (cur*cur)%MOD; sum (sum (pow*((cur s)%MOD))%MOD)%MOD;s ( 2*s cur)%MOD; }return (int)sum;}
}时间复杂度 O ( N L o g N ) O(NLogN) O(NLogN)
空间复杂度 O ( L o g N ) O(LogN) O(LogN)
Tag
Array Math Sort
