397. Integer Replacement
2024-03-09 13:46:52
先正统做法。
public class Solution {
public int integerReplacement(int n)
{
if(n == 1) return 0;
int res = 0;
while(n != 1)
{
if(n % 2 == 0)
{
n/=2;
res++;
}
else return res + odd(n);
}
return res;
}
public int odd(int n)
{
return Math.min(integerReplacement(n+1),integerReplacement(n-1))+1;
}
}
结果TLE
考虑下别的做法。
不管是/2 +1 -1都是1 bit操作，从bit上入手。
8 = 1 0 0 0 需要右移3次。
9 = 1 0 0 1 -1 /2 /2 /2
基本思路是；
如果是偶数，最右位(RMB)是0，直接/2；
如果是奇数，通过+ -去掉RMB的1. 但是+ -还是有学问的， 比如 1111 和 1001，第一个明显是+1好，第二个是-1好。
这里+1 -1的目的是为了shift right服务的，所以标准就是通过+1还是-1去掉的1越多越好。用brute-force就是都试试，然后计算机替你选择一个。作为人类，我们要发现规律。。。
所以就是能/2就/2，不能就数+1 -1哪个划算；哪个划算通过看哪个去掉1的个数多决定。其实-1只有在右起第二位是0的情况下划算（还有11的时候，这他妈是个大坑）。
public class Solution {
public int integerReplacement(int n)
{
int res = 0;
while(n != 1)
{
if(n % 2 == 0) n/=2;
else if( n == 3 || ((n>>1) & 1) == 0) n--;
else n++;
res++;
}
return res;
}
}
一开始在3上遇到大坑，拿3验证发现他妈不是那么回事啊。。结果3是个特例，因为对于3来说，通过+1去掉2个1，不如-1来的实在。。掉这个坑里一次。
然后另外就是，居然还是TLE... 有没有搞错啊。。
后来发现是各种运算都要换成bit的才行，/2 %2之类的。。
public class Solution {
public int integerReplacement(int n)
{
int res = 0;
while(n != 1)
{
if((n & 1) == 0) n >>>=1;
else if( n == 3 || ((n>>>1)&1)==0) n--;
else n++;
res++;
}
return res;
}
}
貌似因为>>>不需要判断符号，所以比>>要快？ >>>换成 >>就TLE
求高人指点。
最新文章
- javafx之HTTP协议交互
- jquery 使用方法(一)
- 信息安全系统设计基础实验一 20135210&20135218
- UVa 10375 (唯一分解定理) Choose and divide
- JavaScript日常会跳的坑系列（二）
- Z-stack之OSAL初始化流程
- shell 脚本阅读之二——ltp工具下的runltp
- JAVA取整以及四舍五入
- NTP时间同步 服务端 客户端 自动化安装配置
- kafka基础知识点
- Android Studio打开项目，停在gradle的解决方案
- 51nod 1387 移数字
- 20190412wdVBA 排版
- codeforces#766 D. Mahmoud and a Dictionary （并查集）
- 解决从本地文件系统上传到HDFS时的权限问题
- WPA3在2018年为无线安全添砖加瓦
- 7款精美HTML5应用
- cache-control 缓存
- android在不加载图片的前提下获得图片的宽高
- Qt5_vs2013_error_C2001: 常量中有换行符__ZC