关于周赛1498题的疑惑
来源：3-1 从二分查找法看如何写出正确的程序
v不离不弃v
2020-07-01
波波老师，周赛1498题我是利用排序+双指针，可是我总是在数组在32以下的都可以AC，但是数据量超过32就不行，我加了快速幂，但是还是不行，现在不知道怎么办了，波波老师，您可以帮我看看我的逻辑有错嘛，我已经困扰这个问题好几天了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。
class Solution {
public int numSubseq(int[] nums, int target) {
Arrays.sort(nums);
int res = 0;
int l = 0, r = nums.length - 1;
//双指针，始终保持左边的数有效
while (l <= r) {
if (nums[l] + nums[r] > target)
r--;
else {
res = (int)((res + myPow(2, r - l)) % (1000000000 + 7));
l++;
}
}
return res;
}
//快速幂
private long myPow(int x, int n){
if(n == 0) return 1;
long t = x;
long res = 1;
while(n > 0){
if((n & 1) == 1)
res *= t;
t *= t;
n >>= 1;
}
return res;
}
}
写回答
1回答
-
liuyubobobo
2020-07-01
myPow 中的 res 和 t 是可能溢出的。
改成下面的方式就 ok 了：
private long myPow(int x, int n){ if(n == 0) return 1; long t = x; long res = 1; while(n > 0){ if((n & 1) == 1) res = (res * t) % (1000000000 + 7); t = (t * t) % (1000000000 + 7); n >>= 1; } return res % (1000000000 + 7); }继续加油！：）
022020-07-01
相似问题