Description
牛客网 校招真题 小招喵跑步
Solving Ideas
逆向思维，计算从终点到原点需要的最少步数
当x为偶数时，则x /= 2
当x为奇数时，如果(x + 1) / 2为偶数，则x++；如果(x - 1) / 2为偶数，则x–；
特别地，如x <= 3，则x–
对于任意的x，x属于整数，(x + 1) / 2为偶数和(x - 1) / 2为偶数有且只有一个会成立。
Time complexity : O ( l o g x ) O(logx) O(logx)
Space complexity : O ( 1 ) O(1) O(1)
Solution
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;/*** @author wylu*/public class Main {public static void main(String[] args) throws IOException {BufferedReader br = new BufferedReader(new InputStreamReader(System.in));int x = Math.abs(Integer.parseInt(br.readLine()));int res = 0;while (x != 0) {if (x % 2 == 0) x >>= 1;else x += ((x + 1) / 2 % 2 == 0 && x > 3) ? 1 : -1;res++;}System.out.println(res);}}
如果觉得《牛客网 校招真题 招商银行信用卡 小招喵跑步》对你有帮助，请点赞、收藏，并留下你的观点哦！
