特别的排列
难度:
标签:
题目描述
You are given a 0-indexed integer array nums containing n distinct positive integers. A permutation of nums is called special if:
- For all indexes
0 <= i < n - 1, eithernums[i] % nums[i+1] == 0ornums[i+1] % nums[i] == 0.
Return the total number of special permutations. As the answer could be large, return it modulo 109 + 7.
Example 1:
Input: nums = [2,3,6] Output: 2 Explanation: [3,6,2] and [2,6,3] are the two special permutations of nums.
Example 2:
Input: nums = [1,4,3] Output: 2 Explanation: [3,1,4] and [4,1,3] are the two special permutations of nums.
Constraints:
2 <= nums.length <= 141 <= nums[i] <= 109
代码结果
运行时间: 305 ms, 内存: 29.2 MB
/*
* 思路：
* 1. 使用Java Stream API和递归来生成所有可能的排列。
* 2. 对于每一个排列，检查是否满足条件，即对于0 <= i < n - 1，要么nums[i] % nums[i+1] == 0，要么nums[i+1] % nums[i] == 0。
* 3. 统计所有满足条件的排列数目。
* 4. 将结果对10^9 + 7取余。
*/
import java.util.*;
import java.util.stream.*;
public class SpecialPermutationsStream {
private static final int MOD = 1000000007;
public int specialPermutations(int[] nums) {
return (int)permute(nums, 0).stream()
.filter(this::isSpecialPermutation)
.count() % MOD;
}
private List<List<Integer>> permute(int[] nums, int start) {
if (start == nums.length) {
return Collections.singletonList(Arrays.stream(nums).boxed().collect(Collectors.toList()));
}
List<List<Integer>> result = new ArrayList<>();
for (int i = start; i < nums.length; i++) {
swap(nums, start, i);
result.addAll(permute(nums, start + 1));
swap(nums, start, i);
}
return result;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
private boolean isSpecialPermutation(List<Integer> permutation) {
for (int i = 0; i < permutation.size() - 1; i++) {
int a = permutation.get(i);
int b = permutation.get(i + 1);
if (a % b != 0 && b % a != 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
SpecialPermutationsStream sps = new SpecialPermutationsStream();
int[] nums1 = {2, 3, 6};
int[] nums2 = {1, 4, 3};
System.out.println(sps.specialPermutations(nums1)); // 输出：2
System.out.println(sps.specialPermutations(nums2)); // 输出：2
}
}
解释
方法:
该题解采用了动态规划与深度优先搜索（DFS）结合的方法来解决问题。首先对数组进行排序，利用排序的特性简化除法运算的条件检查。接着，构建一个图的表示方式，用一个整数数组g来表示节点之间的连接关系，其中g[i]的二进制中的第j位如果是1，表示nums[i]和nums[j]之间可以相互整除。然后，通过DFS遍历所有可能的排列组合，使用位掩码技术来表示当前已经选择的元素集合。最后，利用缓存机制（@cache）来优化重复计算，提高效率。
时间复杂度:
O(n * 2^n)
空间复杂度:
O(n + 2^n)
代码细节讲解
🦆
在题解中提到了使用排序来简化运算，排序后的数组具体如何简化除法条件的检查？
▷🦆
题解中提到使用一个整数数组g来表示节点之间的连接关系，具体是如何使用二进制位来表示这种关系的？能否详细解释一下这种表示方法的原理和优势？
▷🦆
题解中提到了查找端点，这里的端点是指什么？为什么端点的数量超过2会导致返回0？
▷🦆
DFS函数中使用了位掩码技术，位掩码在此算法中扮演了什么角色？如何利用位掩码来跟踪哪些元素已被选中？
▷