【C++贪心 数论】991. 坏了的计算器|1909

server/2024/11/29 16:08:18/

本文涉及知识点

C++贪心

数论:质数、最大公约数、菲蜀定理

LeetCode991. 坏了的计算器

在显示着数字 startValue 的坏计算器上,我们可以执行以下两种操作:
双倍(Double):将显示屏上的数字乘 2;
递减(Decrement):将显示屏上的数字减 1 。
给定两个整数 startValue 和 target 。返回显示数字 target 所需的最小操作数。
示例 1:
输入:startValue = 2, target = 3
输出:2
解释:先进行双倍运算,然后再进行递减运算 {2 -> 4 -> 3}.
示例 2:
输入:startValue = 5, target = 8
输出:2
解释:先递减,再双倍 {5 -> 4 -> 8}.
示例 3:

输入:startValue = 3, target = 10
输出:3
解释:先双倍,然后递减,再双倍 {3 -> 6 -> 5 -> 10}.
提示:
1 <= startValue, target <= 109

贪心 数量

情况一:start 等于target。直接返回0。
情况二:start > target。
令最近解为start 、i1 ⋯ \cdots i2 target。
性质一:target 只会出现一次,且在最后,否则提前结束。
性质二:不会有数小于target。 假设i2是第一个小于target的数,它的前一个数是i1。由于i1 > target ,故i1-1 >= target,与假设矛盾;
i12 > target2 >= target,也与假设矛盾。
性质三:不会出现乘以2。令最后一个乘法是i1乘以2是i2。根据性质一性质二,i1> target。i1减到target比i1*2减少到target需要的次数少得多。
总结:返回 start - target。
情况三:start < target
令start 最少乘以2 m次后,大于等于target。令 x = start × \times × 2m- target
如果x的第0位(最低位)是1,乘2 m次后,减1。
如果x的第1位 是1,乘2 m-1次后,减1。
即:x 0到m-1位的1,可以一次减掉。其它的乘2之前,一次可以减少 2m

代码

核心代码

class Solution {public:int brokenCalc(int startValue, int target) {if (startValue > target) { return startValue- target; }int m = 0;for (; startValue < target; startValue*=2, m++);int x = startValue - target;int ans = 0;for (int i = 0; i < m; i++) {if ((1 << i) & x) {x -= (1 << i);ans++;}}return m+ ans + x / (1 << m);}};

单元测试

int startValue,  target;TEST_METHOD(TestMethod11){startValue = 2, target = 3;auto res = Solution().brokenCalc(startValue, target);AssertEx(2, res);}TEST_METHOD(TestMethod12){startValue = 5, target = 8;auto res = Solution().brokenCalc(startValue, target);AssertEx(2, res);}TEST_METHOD(TestMethod13){startValue = 3, target = 10;auto res = Solution().brokenCalc(startValue, target);AssertEx(3, res);}TEST_METHOD(TestMethod14){startValue = 3, target = 3;auto res = Solution().brokenCalc(startValue, target);AssertEx(0, res);}TEST_METHOD(TestMethod15){startValue = 13, target = 3;auto res = Solution().brokenCalc(startValue, target);AssertEx(10, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题,可以按类别查阅鄙人的算法文章,请点击《算法与数据汇总》。
学习算法:按章节学习《喜缺全书算法册》,大量的题目和测试用例,打包下载。重视操作
有效学习:明确的目标 及时的反馈 拉伸区(难度合适) 专注
闻缺陷则喜(喜缺)是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛
失败+反思=成功 成功+反思=成功

视频课程

先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。


http://www.ppmy.cn/server/145942.html

相关文章

快速排序 C++

题目一 解题思路 快排思路 首先设定一个分界值(基准值)&#xff0c;通过该分界值将数组分成左右两部分。将大于或等于分界值的数据集中到数组右边&#xff0c;小于分界值的数据集中到数组的左边。此时&#xff0c;左边部分中各元素都小于分界值&#xff0c;而右边部分中各元素…

【Maven Helper】分析依赖冲突案例

目录 Maven Helper实际案例java文件pom.xml文件运行抛出异常分析 参考资料 Maven Helper A must have plugin for working with Maven. easy way for analyzing and excluding conflicting dependenciesactions to run/debug maven goals for a module that contains the cur…

通过DBUA升级 Oracle 11g到Oracle12c版本

Oracle 11g升级到Oracle12c Oracle11g数据库环境准备与数据备份 环境&#xff1a; oracle11.2.0.4 to oralce12.2.0.1 升级方案&#xff1a; 升级方案很多种&#xff0c;我们ORACLE培训课程第8阶段有所讲所有的升级方案&#xff0c;我们这里采用DBUA官方建议的方法 1、手…

ctfshow -web 89-115-wp

89. 显然&#xff0c;这里是需要绕过preg_match&#xff0c;绕过preg_match有三种方法 CTF 总结02&#xff1a;preg_match()绕过_pregmatch函数绕过-CSDN博客 90. 考intval。 这个与赣ctf有道题差不多&#xff0c;我是直接传入num4476a&#xff0c;intval&#xff08;4476a&a…

Vue 开发中为什么要使用穿透符::deep()

在 Vue 开发中&#xff0c;有时候样式需要穿透才能生效&#xff0c;通常是因为使用了作用域样式 (scoped styles) 的缘故。 1. 什么是作用域样式 (scoped styles)? 在 Vue 单文件组件 (SFC) 中&#xff0c;使用 <style scoped> 声明的样式只会作用于当前组件的元素。Vu…

【Qt】QDateTimeEdit控件实现清空(不保留默认时间/最小时间)

一、QDateTimeEdit控件 QDateTimeEdit 提供了一个用于编辑日期和时间的控件。用户可以通过键盘或使用上下箭头键来增加或减少日期和时间值。日期和时间的显示格式根据设置的格式显示&#xff0c;可以通过 setDisplayFormat() 方法来设置。 二、如何清空 我在使用的时候&#…

第十二章 使用 BIND 提供域名解析服务

1. DNS 域名解析服务 相较于由数字构成的 IP 地址&#xff0c;域名更容易被理解和记忆&#xff0c;所以我们通常更习惯通过域名的方式来访问网络中的资源。但是&#xff0c;网络中的计算机之间只能基于 IP 地址来相互识别对方的身份&#xff0c;而且要想在互联网中传输数据&…

Anaconda3 2024 jupyter notebook 配置默认文件路径

我的版本如下&#xff1a; 第一步&#xff1a; 打开命令行anaconda prompt &#xff0c; 敲下面命令生成配置文件 jupyter notebook --generate-config 如下图&#xff1a; 修改配置jupyter_notebook_config.py 文件中搜索c.ServerApp.root_dir &#xff08; 对于 Anac…