准备T家OA,网上看的面经
最直接的方法,从target降到1,如果是奇数就减一,偶数就除2
public static void main(String[] args) {
int a = shortest(17);
System.out.println(a);
} public static int shortest(int target) {
if (target < 1) {
return -1;
}
int count = 1;
while (target != 1) {
if (target % 2 == 0) {
target /= 2;
} else {
target -= 1;
}
count ++;
}
return count;
}
分析:这道题就是看这个二进制数most significant bit的1左移了多少位,即是所需的乘2次数;然后除开Most Significant bit的这个1之后的其它1的个数,就是需要加1的次数
比如15,1111,most significant bit的1是左移三位得到的,所以需要乘2三次,剩下111三个1,所以需要加1 三次,总操作3+3+1=7次。
还没有评论呢,快来抢沙发~