首页 > 代码库 > LeetCode之整数替换
LeetCode之整数替换
最近在开始做LeetCode的算法题
做的第一题是的题目如下:
Given a positive integer n and you can do operations as follow:
- If n is even, replace n with
n/2
.- If n is odd, you can replace n with either
n + 1
orn - 1
.What is the minimum number of replacements needed for n to become 1?
可以看到题目最难的是在数为奇数时如何判断是加还是减。
最开始我的想法是如果这个基数在加一之后是2的n次幂的话+1,否则就减一,因为程序效率方面的要求的话,使用位操作来判断
代码如下
if((n+1) & n ==0) n++; else n--;
但是这段代码提交之后出错:n == 3时,代码出错,我认为这是个特例,所以在代码里面加了额外的判断
再次提交,程序在10000的时候有出现错误。分析之后我发现最初的思路并不能行。
在论坛看了排名第一的解之后恍然大悟:https://discuss.leetcode.com/topic/58334/a-couple-of-java-solutions-with-explanations
对数的二进制分析(毕竟和2关系很大),发现奇数的最后两位只有两种情况:01和11
分析后可以发现,在01时减1,11时加1得出的解最优。
但是,这里还有一个叛徒,那就是3(还真是特殊额),你会发现他二进制为11,但是按规则加一并不是最优解。
对3进行特殊处理。
之后的代码就是:
int integerReplacement(int n) { unsigned int x; int count = 0; x = n; while(x != 1) { if((x & 1) == 0) x >>= 1; else if(x == 3 || ((x >> 1) & 1) == 0) x--; else x++; count++; } return count ; }
LeetCode之整数替换
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。