397 Integer Replacement 整数替换
2024-08-29 07:21:15
给定一个正整数 n，你可以做如下操作：
1. 如果 n 是偶数，则用 n / 2替换 n。
2. 如果 n 是奇数，则可以用 n + 1或n - 1替换 n。
n 变为 1 所需的最小替换次数是多少？
示例 1:
输入:
8
输出:
3
解释:
8 -> 4 -> 2 -> 1
示例 2:
输入:
7
输出:
4
解释:
7 -> 8 -> 4 -> 2 -> 1
或
7 -> 6 -> 3 -> 2 -> 1
详见：https://leetcode.com/problems/integer-replacement/description/
C++：
方法一：
class Solution {
public:
int integerReplacement(int n) {
long long t = n;
int cnt = 0;
while (t > 1)
{
++cnt;
if (t & 1)
{
if ((t & 2) && (t != 3))
{
++t;
}
else
{
--t;
}
}
else
{
t >>= 1;
}
}
return cnt;
}
};
方法二：
class Solution {
public:
int integerReplacement(int n)
{
if (n == 1)
{
return 0;
}
if (n % 2 == 0)
{
return 1 + integerReplacement(n / 2);
}
else
{
long long t = n;
return 2 + min(integerReplacement((t + 1) / 2), integerReplacement((t - 1) / 2));
}
}
};
参考：https://www.cnblogs.com/grandyang/p/5873525.html
最新文章
- Maven的包依赖冲突可引发java.lang.IncompatibleClassChangeError错误
- Tomcat在Linux上的安装与配置
- JS调用水晶报表打印翻页按钮事件
- static（静态、修饰符）
- 火狐 SSL 收到了一个弱临时 Diffie-Hellman 密钥的解决办法
- Jpush推送模块
- php pdo mysql数据库操作类
- Android消息机制不完全解析（下）
- EF如何操作内存中的数据和加载外键数据：延迟加载、贪婪加载、显示加载
- git 强制覆盖本地文件
- 学习HTML5一周的收获1
- JsRender练习总结
- projects(好代码好工具)每天进步一点点
- vue基础篇---路由的实现
- 从YOLOv1到YOLOv3，目标检测的进化之路
- selenium css定位方式
- (转)【深度长文】循序渐进解读Oracle AWR性能分析报告
- JavaScript Promise迷你书（中文版）
- 多数据源报错 expected single matching bean but found 2: xxx,xxx
- 安装Xampp-配置appche，mysql运行环境遇到的坑