双模幂运算
难度:
标签:
题目描述
You are given a 0-indexed 2D array variables where variables[i] = [ai, bi, ci, mi], and an integer target.
An index i is good if the following formula holds:
0 <= i < variables.length((aibi % 10)ci) % mi == target
Return an array consisting of good indices in any order.
Example 1:
Input: variables = [[2,3,3,10],[3,3,3,1],[6,1,1,4]], target = 2 Output: [0,2] Explanation: For each index i in the variables array: 1) For the index 0, variables[0] = [2,3,3,10], (23 % 10)3 % 10 = 2. 2) For the index 1, variables[1] = [3,3,3,1], (33 % 10)3 % 1 = 0. 3) For the index 2, variables[2] = [6,1,1,4], (61 % 10)1 % 4 = 2. Therefore we return [0,2] as the answer.
Example 2:
Input: variables = [[39,3,1000,1000]], target = 17 Output: [] Explanation: For each index i in the variables array: 1) For the index 0, variables[0] = [39,3,1000,1000], (393 % 10)1000 % 1000 = 1. Therefore we return [] as the answer.
Constraints:
1 <= variables.length <= 100variables[i] == [ai, bi, ci, mi]1 <= ai, bi, ci, mi <= 1030 <= target <= 103
代码结果
运行时间: 21 ms, 内存: 16.1 MB
/*
* 思路：
* 对于每个变量组 [a, b, c, m]，计算 (a^b % 10)^c % m 并判断是否等于 target。
* 使用 Java Stream 处理数组。
*/
import java.util.Arrays;
import java.util.List;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class SolutionStream {
public List<Integer> findGoodIndices(int[][] variables, int target) {
return IntStream.range(0, variables.length)
.filter(i -> {
int a = variables[i][0];
int b = variables[i][1];
int c = variables[i][2];
int m = variables[i][3];
// 计算 (a^b % 10)
int mod = (int) (Math.pow(a, b) % 10);
// 计算 (mod^c) % m
int value = (int) (Math.pow(mod, c) % m);
// 判断是否等于 target
return value == target;
})
.boxed()
.collect(Collectors.toList());
}
public static void main(String[] args) {
SolutionStream solution = new SolutionStream();
int[][] variables = {{2, 3, 3, 10}, {3, 3, 3, 1}, {6, 1, 1, 4}};
int target = 2;
System.out.println(solution.findGoodIndices(variables, target)); // 输出: [0, 2]
}
}
解释
方法:
对于每个元素 [ai, bi, ci, mi]，首先计算 a^b 的最后一位数字，这是通过 a^b % 10 实现的。接下来，计算这个结果的 ci 次幂，然后取模 mi，即 ((a^b % 10)^c) % mi。如果这个结果等于 target，那么这个索引 i 就是一个好下标。算法对每个元素进行此操作，并将所有好下标收集到结果列表中。
时间复杂度:
O(n)
空间复杂度:
O(n)
代码细节讲解
🦆
在双模幂运算中，为什么先计算 a^b % 10 而不是直接计算整个 a^b 的值？
▷🦆
对于算法中的幂运算，有没有可能因为 b 或 c 的值很大而导致计算过程中的溢出问题？
▷🦆
题解中提到的算法对于每个元素都进行了幂运算和模运算，是否考虑过使用快速幂算法来优化这些计算？
▷🦆
题解中的算法在实现时未提及对于输入数据的特殊边界情况（如空数组或极大的数值），这会不会影响算法的鲁棒性或导致运行错误？
▷