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. 数组元素的最小非零乘积
目录链接: 力扣编程题-解法汇总_分享记录-CSDN博客 GitHub同步刷题项目: https://github.com/September26/java-algorithms 原题链接:. - 力扣(LeetCode) 描述: 给你一个正整数 p 。你有一个下标从 1 开…...
学习vue3第九节(新加指令 v-pre/v-once/v-memo/v-cloak )
1、v-pre 作用:防止编译器解析某个特定的元素及其内容,即v-pre 会跳过当前元素以及其子元素的vue语法解析,并将其保持原样输出; 用于:vue 中一些没有指令和插值表达式的节点的元素,使用 v-pre 可以提高 Vu…...
二开飞机机器人群发,实现自动给多个频道发送消息
频道1 频道2 二开代码部分: const CChatIdListprocess.env.CHANNEL_CHAT_ID_LIST; var channelChatIdArray CChatIdList.split(,);channelChatIdArray.forEach(function(item) {console.log(item); // 这里可以替换为您需要对数组中每个值进行的操作bot.sendM…...
AI如何支持慈善组织
为各种有意义的事业提供支持,无论是努力寻找治愈疾病的方法、研发使生活更轻松的技术,还是为有需要的人提供服务,都是无比崇高的使命。提供捐款或是投入时间支持的捐助者和志愿者往往对他们选择支持的事业的目标、服务和资源分配存有诸多疑虑…...
Git如何清除账户凭证
场景:一般发生在Git用户变更的情况 1.git base 操作 Git会使用凭证助手 credential.helper来储存账户凭证,通过以下命令移除: git config --system --unset credential.helper 除了system系统级外,还有 global、local范围。 查…...
【YUNBEE云贝-PostgreSQL】FDW应用
注: 本文为云贝教育 刘峰 原创,请尊重知识产权,转发请注明出处,不接受任何抄袭、演绎和未经注明出处的转载。 前言 Wrapper(FDW)是一项关键特性,它赋予数据库用户直接通过SQL语句访问存储于外部数据源的能…...
Spring MVC文件上传配置
版权声明 本文原创作者:谷哥的小弟作者博客地址:http://blog.csdn.net/lfdfhl 文件上传 Spring MVC文件上传基于Servlet 3.0实现;示例代码如下: Overrideprotected void customizeRegistration(ServletRegistration.Dynamic reg…...
JavaScript高级(十八)---进程和线程,宏任务和微任务
进程和线程 进程(process):计算机已经运行的程序,是操作系统管理程序的一种方式,我们可以认为,启动一个应用程序,就会默认启动一个进程(也可能是多个进程)。 线程&…...
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 …...
关于继承是怎么样的?那当然是很好理解之
本文描述了关于继承的大部分知识,但是并不全,每篇博客之间的知识都有互串,所以需要把几篇文章合起来看,学会融会贯通! 温馨提示:使用PC端观看,效果更佳! 目录 1.继承是什么 2.什…...
高可用系统有哪些设计原则
1.降级 主动降级:开关推送 被动降级:超时降级 异常降级 失败率 熔断保护 多级降级2.限流 nginx的limit模块 gateway redisLua 业务层限流 本地限流 gua 分布式限流 sentinel 3.弹性计算 弹性伸缩—K8Sdocker 主链路压力过大的时候可以将非主链路的机器给…...
LeetCode-回文数
LeetCode-回文数 解体思路: ①第一种:转换成字符串,使用字符串的现有api方法进行反转 ②第二种:直接使用循环除余乘10方法,进行反转 涉及知识点: 循环判断,StringBuffer,int类型…...
50. 【Linux教程】源码安装软件
本小节介绍如何使用软件的源码包安装软件,以安装 nginx 源码包为例。 1.下载软件源码包 使用如下命令下载 nginx 源码包: wget http://nginx.org/download/nginx-1.18.0.tar.gz执行结果如下图所示: 2.解压源码包 下载好了压缩包之后&#…...
《操作系统实践-基于Linux应用与内核编程》第10章--实验 Qt聊天程序
前言: 内容参考《操作系统实践-基于Linux应用与内核编程》一书的示例代码和教材内容,所做的读书笔记。本文记录再这里按照书中示例做一遍代码编程实践加深对操作系统的理解。 引用: 《操作系统实践-基于Linux应用与内核编程》 作者:房胜、李旭健、黄…...
探究Kafka主题删除失败的根本原因
欢迎来到我的博客,代码的世界里,每一行都是一个故事 探究Kafka主题删除失败的根本原因 前言主题删除的基础主题删除的定义和作用:删除操作的基本流程: 可能存在删除异常的因素数据积压的处理方法Broker状态异常处理方法通用方法 前…...
JavaSE(上)-Day7
JavaSE(上)-Day7 类和对象封装privatethis构造方法标准JavaBean对象的内存图执行Test类main方法生成一个User对象的内存过程 基本数据类型和引用数据类型的区别this的内存原理成员变量和局部变量区别 类和对象 类是设计图纸,对象是真正的实例…...
记录一下在Pycharm中虚拟环境的创建
如果在Pycharm中要新建一个虚拟环境,那你可以在Terminal中选择Command Prompt,在这里面执行相关命令 一、安装了Anaconda,创建虚拟环境 当你使用解释器是Anaconda提供的时,你可以使用conda命令执行,见以下操作&#x…...
Python从入门到精通秘籍九
一、Python中文件编码概念 在Python中,文件编码指的是将文本内容转换为字节序列的过程。不同的编码方式使用不同的字符集和字节表示形式。下面是一个示例代码: # 写入文本到文件 text "你好,世界!" with open("…...
善于利用window挂在全局变量
开发过程成中遇到一个奇怪的问题,打开一个echats图表之后,关闭echarts图再进入其他页面页面会报错提示 $(...).draggble not a function经过一步步定位,发现echats图是通过后端获取js、css文件然后在本地绘制而成。而获…...
《C缺陷和陷阱》-笔记(5)
目录 一、整数溢出 溢出 如何防止溢出 二、为函数main提供返回值 连接 一、什么是连接器 连接器工作原理 三、声明与定义 四、命名冲突与static 修饰符 statia 一、整数溢出 溢出 C语言中存在两类整数算术运算,有符号运算与无符号运算。 在无…...
别再一篇篇下载了!用Zotero Connector插件,5分钟搞定知网、Google Scholar等网站的文献批量抓取
科研效率革命:用Zotero Connector实现文献管理的全自动流水线 深夜的实验室里,咖啡杯已经见了底,而电脑屏幕上还开着十几个文献检索页面——这种场景对科研工作者来说再熟悉不过。传统文献收集方式就像用勺子舀干游泳池,而Zotero …...
终极OneDrive卸载指南:彻底释放Windows系统资源的专业方案
终极OneDrive卸载指南:彻底释放Windows系统资源的专业方案 【免费下载链接】OneDrive-Uninstaller Batch script to completely uninstall OneDrive in Windows 10 项目地址: https://gitcode.com/gh_mirrors/on/OneDrive-Uninstaller 你是否厌倦了OneDrive在…...
MT5中文增强镜像GPU算力优化教程:FP16量化+梯度检查点降低显存占用50%
MT5中文增强镜像GPU算力优化教程:FP16量化梯度检查点降低显存占用50% 你是不是也遇到过这种情况:好不容易找到一个好用的中文文本增强工具,比如基于mT5的改写模型,兴致勃勃地部署到自己的GPU服务器上,结果一运行就提示…...
Janus-Pro-7B企业级应用:基于Dify构建智能客服知识库
Janus-Pro-7B企业级应用:基于Dify构建智能客服知识库 很多企业都想用AI来升级客服系统,但一提到大模型,大家的第一反应往往是:技术门槛高、部署复杂、成本难以控制。有没有一种方法,能让企业快速、低成本地搭建一个真…...
3步掌握猫抓浏览器扩展:高效捕获网页媒体资源的实战指南
3步掌握猫抓浏览器扩展:高效捕获网页媒体资源的实战指南 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 你是否经常遇到想要保存网页中…...
STM32F103ZE驱动PMW3901光流模块,从SPI配置到数据读取的完整避坑指南
STM32F103ZE驱动PMW3901光流模块实战全解析:从硬件对接到运动数据捕获 第一次拿到PMW3901这个神奇的小模块时,我盯着它那比指甲盖还小的尺寸,很难想象它能通过光学追踪实现精确的运动检测。作为嵌入式开发者,最兴奋的莫过于将这样…...
别再只用findContours了!OpenCV连通域分析connectedComponentsWithStats()保姆级教程
连通域分析进阶:用connectedComponentsWithStats()替代findContours()的五大理由 在图像处理项目中,我们经常需要分析图像中的独立区域。许多开发者第一反应就是使用findContours()函数——这确实是个经典选择,但它真的是最优解吗?…...
【C语言实战】NTC测温:从查表算法到代码优化全解析
1. NTC测温基础与查表法原理 NTC(负温度系数)热敏电阻是嵌入式测温的常见选择,它的电阻值随温度升高而降低。相比复杂的公式计算,查表法在资源有限的单片机中更实用。我做过一个智能恒温箱项目,就是用STM32的12位ADC读…...
Groovy 异常传播是怎么处理的?
异常传播指的是异常事件从嵌套的 try 块或嵌套的方法调用中传播的过程。一个 try 块可以嵌套在另一个 try 块中。同样,一个方法可以调用另一个方法,每个方法可以独立处理异常,或者抛出 checked/unchecked exceptions。每当在嵌套的 try 块/方…...
告别OpenCV!用STM32+OV7725从零搭建一个HSL颜色追踪小车(附完整源码)
STM32OV7725颜色追踪小车:从硬件搭建到PID调参全指南 在创客圈和机器人竞赛中,自动追踪特定颜色物体的小车一直是热门项目。传统方案依赖OpenCV等计算机视觉库,但在资源受限的嵌入式场景下,如何仅用STM32微控制器和OV7725摄像头实…...
