国庆放假都没做题，一直玩哈哈哈，今天说要做ppt，出门前摸了U盘，转手不知道放在那里啦，那就晚上在回去做ppt吧。
小机灵鬼
题目是整数替换；
给定一个数字N，若N是偶数，就用N/2替代，反之就用N-1或者N+1代替。求N变为1的最小次数。

示例1：

输入:
8

输出:
3

解释1:

8 -> 4 -> 2 -> 1

示例2：

输入:
7

输出:
4

解释2:

7 -> 8 -> 4 -> 2 -> 1
或
7 -> 6 -> 3 -> 2 -> 1

题解：

这一道题就用字面上的意思来解决，N为偶数就用N/2替代；若n为奇数，我们需要判断是用N+1还是N-1来替代。经过多个数字的计算，若N+1能被4整除，我们就用N+1来替代（注意：3是特别的，用N-1来替代），反之则用N-1替代。
注意：int 的范围是-2147483647~2147483647，在这题中我们需要用long，否则会数据溢出。

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

import java.util.*;
import java.math.*;

public class ZYH {
	public int integerReplacement(int n) {
		int ans = 0;
		long m = n;
		while (m != 1) {
			if (m % 2 == 0) {
				m = m / 2;
				ans++;
			} else if (m % 2 != 0) {
				if (m != 3 && (m + 1) % 4 == 0) {
					m = m + 1;
					ans++;
				} else {
					m = m - 1;
					ans++;
				}
			}
		}
		return ans;
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		ZYH s = new ZYH();
		int b = 2147483647;
		int a = s.integerReplacement(b);
		System.out.print(a);

	}
}