免费做app网站,爱站网 关键词挖掘,北京市住房建设投资中心网站,自营店网站建设目录链接#xff1a;
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目#xff1a;
https://github.com/September26/java-algorithms 原题链接#xff1a;. - 力扣#xff08;LeetCode#xff09; 描述#xff1a;
给你一个正整数 p 。你有一个下标从 1 开… 目录链接
力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目
https://github.com/September26/java-algorithms 原题链接. - 力扣LeetCode 描述
给你一个正整数 p 。你有一个下标从 1 开始的数组 nums 这个数组包含范围 [1, 2p - 1] 内所有整数的二进制形式两端都 包含。你可以进行以下操作 任意 次
从 nums 中选择两个元素 x 和 y 。选择 x 中的一位与 y 对应位置的位交换。对应位置指的是两个整数 相同位置 的二进制位。
比方说如果 x 1101 且 y 0011 交换右边数起第 2 位后我们得到 x 1111 和 y 0001 。
请你算出进行以上操作 任意次 以后nums 能得到的 最小非零 乘积。将乘积对 109 7 取余 后返回。
注意答案应为取余 之前 的最小值。 示例 1
输入p 1
输出1
解释nums [1] 。
只有一个元素所以乘积为该元素。示例 2
输入p 2
输出6
解释nums [01, 10, 11] 。
所有交换要么使乘积变为 0 要么乘积与初始乘积相同。
所以数组乘积 1 * 2 * 3 6 已经是最小值。示例 3
输入p 3
输出1512
解释nums [001, 010, 011, 100, 101, 110, 111]
- 第一次操作中我们交换第二个和第五个元素最左边的数位。- 结果数组为 [001, 110, 011, 100, 001, 110, 111] 。
- 第二次操作中我们交换第三个和第四个元素中间的数位。- 结果数组为 [001, 110, 001, 110, 001, 110, 111] 。
数组乘积 1 * 6 * 1 * 6 * 1 * 6 * 7 1512 是最小乘积。提示
1 p 60 解题思路
首先我们了解一个概念两个数之和不变时大的数越大小的数越小则乘积就越小。比如之和为8则1*7最小4*4最大。所以这道题我们就是要让大的数越大小的数越小。
以p3为例有7个数[1234567]1和7无法加减则让2和5结合2和4结合。得到[1,1,1,6,6,6,7]。
总结规律有2^(p-1)-1个1 以及 2^(p-1)-1个2^p-2以及1个2^p-1。
1可以忽略则最终就是 2^(p-1)-1个2^p-2和1个2^p-1的乘积。 代码
class Solution {public int minNonZeroProduct(int p) {if (p 1) {return 1;}long mod 1000000007;long x fastPow(2, p, mod) - 1;long y (long) 1 (p - 1);return (int) (fastPow(x - 1, y - 1, mod) * x % mod);}public long fastPow(long x, long n, long mod) {long res 1;for (; n ! 0; n 1) {if ((n 1) ! 0) {res res * x % mod;}x x * x % mod;}return res;}
}
