当前位置: 首页 > news >正文

​LeetCode解法汇总1969. 数组元素的最小非零乘积

 目录链接:

力扣编程题-解法汇总_分享+记录-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最大。所以这道题,我们就是要让大的数越大,小的数越小。

以p=3为例,有7个数:[1,2,3,4,5,6,7],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;}
}

相关文章:

​LeetCode解法汇总1969. 数组元素的最小非零乘积

目录链接&#xff1a; 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目&#xff1a; https://github.com/September26/java-algorithms 原题链接&#xff1a;. - 力扣&#xff08;LeetCode&#xff09; 描述&#xff1a; 给你一个正整数 p 。你有一个下标从 1 开…...

学习vue3第九节(新加指令 v-pre/v-once/v-memo/v-cloak )

1、v-pre 作用&#xff1a;防止编译器解析某个特定的元素及其内容&#xff0c;即v-pre 会跳过当前元素以及其子元素的vue语法解析&#xff0c;并将其保持原样输出&#xff1b; 用于&#xff1a;vue 中一些没有指令和插值表达式的节点的元素&#xff0c;使用 v-pre 可以提高 Vu…...

二开飞机机器人群发,实现自动给多个频道发送消息

频道1 频道2 二开代码部分&#xff1a; const CChatIdListprocess.env.CHANNEL_CHAT_ID_LIST; var channelChatIdArray CChatIdList.split(,);channelChatIdArray.forEach(function(item) {console.log(item); // 这里可以替换为您需要对数组中每个值进行的操作bot.sendM…...

AI如何支持慈善组织

为各种有意义的事业提供支持&#xff0c;无论是努力寻找治愈疾病的方法、研发使生活更轻松的技术&#xff0c;还是为有需要的人提供服务&#xff0c;都是无比崇高的使命。提供捐款或是投入时间支持的捐助者和志愿者往往对他们选择支持的事业的目标、服务和资源分配存有诸多疑虑…...

Git如何清除账户凭证

场景&#xff1a;一般发生在Git用户变更的情况 1.git base 操作 Git会使用凭证助手 credential.helper来储存账户凭证&#xff0c;通过以下命令移除&#xff1a; git config --system --unset credential.helper 除了system系统级外&#xff0c;还有 global、local范围。 查…...

【YUNBEE云贝-PostgreSQL】FDW应用

注: 本文为云贝教育 刘峰 原创&#xff0c;请尊重知识产权&#xff0c;转发请注明出处&#xff0c;不接受任何抄袭、演绎和未经注明出处的转载。 前言 Wrapper&#xff08;FDW&#xff09;是一项关键特性&#xff0c;它赋予数据库用户直接通过SQL语句访问存储于外部数据源的能…...

Spring MVC文件上传配置

版权声明 本文原创作者&#xff1a;谷哥的小弟作者博客地址&#xff1a;http://blog.csdn.net/lfdfhl 文件上传 Spring MVC文件上传基于Servlet 3.0实现&#xff1b;示例代码如下&#xff1a; Overrideprotected void customizeRegistration(ServletRegistration.Dynamic reg…...

JavaScript高级(十八)---进程和线程,宏任务和微任务

进程和线程 进程&#xff08;process&#xff09;&#xff1a;计算机已经运行的程序&#xff0c;是操作系统管理程序的一种方式&#xff0c;我们可以认为&#xff0c;启动一个应用程序&#xff0c;就会默认启动一个进程&#xff08;也可能是多个进程&#xff09;。 线程&…...

How to install mongodb on redhat 7.7

下载rpm: mongodb-enterprise-server-6.0.3-1.el7.x86_64.rpmmongodb-org-server-6.0.4-1.el7.x86_64.rpmmongodb-mms-6.0.9.100.20230201T2148Z.x86_64.rpm rpm -ivh mongodb-org-server-6.0.4-1.el7.x86_64.rpm rpm -ivh mongodb-mms-6.0.9.100.20230201T2148Z.x86_64.rpm …...

关于继承是怎么样的?那当然是很好理解之

本文描述了关于继承的大部分知识&#xff0c;但是并不全&#xff0c;每篇博客之间的知识都有互串&#xff0c;所以需要把几篇文章合起来看&#xff0c;学会融会贯通&#xff01; 温馨提示&#xff1a;使用PC端观看&#xff0c;效果更佳&#xff01; 目录 1.继承是什么 2.什…...

高可用系统有哪些设计原则

1.降级 主动降级&#xff1a;开关推送 被动降级&#xff1a;超时降级 异常降级 失败率 熔断保护 多级降级2.限流 nginx的limit模块 gateway redisLua 业务层限流 本地限流 gua 分布式限流 sentinel 3.弹性计算 弹性伸缩—K8Sdocker 主链路压力过大的时候可以将非主链路的机器给…...

LeetCode-回文数

LeetCode-回文数 解体思路&#xff1a; ①第一种&#xff1a;转换成字符串&#xff0c;使用字符串的现有api方法进行反转 ②第二种&#xff1a;直接使用循环除余乘10方法&#xff0c;进行反转 涉及知识点&#xff1a; 循环判断&#xff0c;StringBuffer&#xff0c;int类型…...

50. 【Linux教程】源码安装软件

本小节介绍如何使用软件的源码包安装软件&#xff0c;以安装 nginx 源码包为例。 1.下载软件源码包 使用如下命令下载 nginx 源码包&#xff1a; wget http://nginx.org/download/nginx-1.18.0.tar.gz执行结果如下图所示&#xff1a; 2.解压源码包 下载好了压缩包之后&#…...

《操作系统实践-基于Linux应用与内核编程》第10章--实验 Qt聊天程序

前言: 内容参考《操作系统实践-基于Linux应用与内核编程》一书的示例代码和教材内容&#xff0c;所做的读书笔记。本文记录再这里按照书中示例做一遍代码编程实践加深对操作系统的理解。 引用: 《操作系统实践-基于Linux应用与内核编程》 作者&#xff1a;房胜、李旭健、黄…...

探究Kafka主题删除失败的根本原因

欢迎来到我的博客&#xff0c;代码的世界里&#xff0c;每一行都是一个故事 探究Kafka主题删除失败的根本原因 前言主题删除的基础主题删除的定义和作用&#xff1a;删除操作的基本流程&#xff1a; 可能存在删除异常的因素数据积压的处理方法Broker状态异常处理方法通用方法 前…...

JavaSE(上)-Day7

JavaSE&#xff08;上&#xff09;-Day7 类和对象封装privatethis构造方法标准JavaBean对象的内存图执行Test类main方法生成一个User对象的内存过程 基本数据类型和引用数据类型的区别this的内存原理成员变量和局部变量区别 类和对象 类是设计图纸&#xff0c;对象是真正的实例…...

记录一下在Pycharm中虚拟环境的创建

如果在Pycharm中要新建一个虚拟环境&#xff0c;那你可以在Terminal中选择Command Prompt&#xff0c;在这里面执行相关命令 一、安装了Anaconda&#xff0c;创建虚拟环境 当你使用解释器是Anaconda提供的时&#xff0c;你可以使用conda命令执行&#xff0c;见以下操作&#x…...

Python从入门到精通秘籍九

一、Python中文件编码概念 在Python中&#xff0c;文件编码指的是将文本内容转换为字节序列的过程。不同的编码方式使用不同的字符集和字节表示形式。下面是一个示例代码&#xff1a; # 写入文本到文件 text "你好&#xff0c;世界&#xff01;" with open("…...

善于利用window挂在全局变量

开发过程成中遇到一个奇怪的问题&#xff0c;打开一个echats图表之后&#xff0c;关闭echarts图再进入其他页面页面会报错提示 $&#xff08;...&#xff09;.draggble not a function经过一步步定位&#xff0c;发现echats图是通过后端获取js、css文件然后在本地绘制而成。而获…...

《C缺陷和陷阱》-笔记(5)

目录 一、整数溢出 溢出 如何防止溢出 二、为函数main提供返回值 连接 一、什么是连接器 连接器工作原理 三、声明与定义 四、命名冲突与static 修饰符 statia 一、整数溢出 溢出 C语言中存在两类整数算术运算&#xff0c;有符号运算与无符号运算。 在无…...

10分钟掌握Fideo:免费开源直播录制软件的终极指南

10分钟掌握Fideo&#xff1a;免费开源直播录制软件的终极指南 【免费下载链接】fideo-live-record A convenient live broadcast recording software! Supports Tiktok, Youtube, Twitch, Bilibili, Bigo!(一款方便的直播录制软件! 支持tiktok, youtube, twitch, 抖音&#xff…...

从VGG16到Xception:手把手拆解DeepLab系列四大版本的核心演进与代码实现

从VGG16到Xception&#xff1a;DeepLab系列四大版本核心技术演进与实战解析 语义分割技术正经历着从基础架构到精细化设计的快速迭代。作为这一领域的标杆性工作&#xff0c;DeepLab系列从2015年的v1版本到2018年的v3版本&#xff0c;展现了一条清晰的技术演进路径——从最初的…...

别再死记硬背BRDF公式了!用微表面模型和菲涅尔项,手把手教你写一个真实的PBR材质

从微表面到真实感&#xff1a;手把手实现PBR材质着色器 在图形学领域&#xff0c;物理真实感渲染(PBR)已经成为现代游戏和影视制作的标配技术。但很多开发者在学习PBR时&#xff0c;常常陷入复杂的数学公式推导而难以落地实践。本文将彻底改变这一现状——我们将直接从GAMES-10…...

TwinCAT 3 XML-Server保姆级教程:从安装TF6421到四种功能块实战(附避坑指南)

TwinCAT 3 XML-Server实战全攻略&#xff1a;从零搭建到工业级应用 记得第一次在产线上看到设备启动时自动加载参数配置的场景&#xff0c;那种"黑科技"般的体验让我对TwinCAT XML-Server产生了浓厚兴趣。作为工业自动化领域的"数据管家"&#xff0c;它能将…...

别再手动测Wi-Fi信号了!用IQview综测仪搞定802.11 a/b/g/n射频性能测试(附详细配置截图)

告别低效测试&#xff1a;用IQview综测仪实现Wi-Fi射频性能的精准自动化 每次看到测试工程师们拿着频谱分析仪在实验室里来回走动&#xff0c;手动记录信号强度时&#xff0c;我总忍不住想——这都2023年了&#xff0c;为什么还有人用这种石器时代的方法&#xff1f;在无线产品…...

ENVI 5.3 实战:手把手教你用Landsat 7数据反演城市热岛效应(附完整Band Math公式)

ENVI 5.3实战&#xff1a;城市热岛效应分析的完整技术路线与创新应用 城市热岛效应是当代城市规划与环境监测领域的重要课题。当我们在ENVI软件中打开一张Landsat 7影像时&#xff0c;那些看似普通的像素值背后隐藏着城市热环境的秘密。本文将带您走完从原始数据到热岛分析的全…...

你的LoRA微调为什么效果差?可能是这5个参数没调对(LLaMA-Factory实战避坑)

你的LoRA微调为什么效果差&#xff1f;可能是这5个参数没调对&#xff08;LLaMA-Factory实战避坑&#xff09; 当你在LLaMA-Factory中进行LoRA微调时&#xff0c;是否遇到过模型表现不如预期的情况&#xff1f;许多开发者在使用LoRA这种高效的参数高效微调方法时&#xff0c;常…...

如何用5分钟彻底告别水印烦恼:全网资源下载终极指南

如何用5分钟彻底告别水印烦恼&#xff1a;全网资源下载终极指南 【免费下载链接】res-downloader 视频号、小程序、抖音、快手、小红书、直播流、m3u8、酷狗、QQ音乐等常见网络资源下载! 项目地址: https://gitcode.com/GitHub_Trending/re/res-downloader 你是否曾经为…...

解锁学术新秘籍:书匠策AI——期刊论文的智能导航员

在学术的浩瀚海洋中&#xff0c;每一位探索者都渴望拥有一盏明灯&#xff0c;照亮前行的道路&#xff0c;尤其是在撰写期刊论文这一艰巨任务面前。传统上&#xff0c;这往往意味着无数次的文献检索、框架搭建、内容填充与反复修改&#xff0c;过程既耗时又费力。但如今&#xf…...

Scroll Reverser终极指南:如何为Mac触控板和鼠标设置独立的滚动方向

Scroll Reverser终极指南&#xff1a;如何为Mac触控板和鼠标设置独立的滚动方向 【免费下载链接】Scroll-Reverser Per-device scrolling prefs on macOS. 项目地址: https://gitcode.com/gh_mirrors/sc/Scroll-Reverser 你是否曾经在Mac上使用外接鼠标时&#xff0c;发…...