原题链接在这里：https://leetcode.com/problems/integer-replacement/
题目：
Given a positive integer n and you can do operations as follow:
n/2.n + 1 or n - 1.What is the minimum number of replacements needed for n to become 1?
Example 1:
Input: 8 Output: 3 Explanation: 8 -> 4 -> 2 -> 1
Example 2:
Input: 7 Output: 4 Explanation: 7 -> 8 -> 4 -> 2 -> 1 or 7 -> 6 -> 3 -> 2 -> 1
题解：
n是偶数时除以2是确定的，问题是n是奇数时+1 还是 -1. 尽可能的消除1 bit, +1 或 -1后哪个1 bit少就选哪个.
若+1或-1后1 bit相同，那么除了3特殊情况下其他都选+1.
Time Complexity: O(1), int最多32位，最多64次操作.
Space: O(1).
AC Java:
1 public class Solution { 2 public int integerReplacement(int n) { 3 int count = 0; 4 while(n != 1){ 5 if((n & 1) == 0){ 6 n >>>= 1; 7 }else if(n == 3 || Integer.bitCount(n+1) > Integer.bitCount(n-1)){ 8 n--; 9 }else{ 10 n++; 11 } 12 count++; 13 } 14 return count; 15 } 16 }
除了3特例之外，看n的倒数第二位，若是1, n++, 若是0, n--.
Time Complexity: O(1). Space: O(1).
AC Java:
1 public class Solution { 2 public int integerReplacement(int n) { 3 int count = 0; 4 while(n != 1){ 5 if((n & 1) == 0){ 6 n >>>= 1; 7 }else if(n == 3 || ((n >>> 1) & 1) == 0){ 8 n--; 9 }else{ 10 n++; 11 } 12 count++; 13 } 14 return count; 15 } 16 }
Reference: https://discuss.leetcode.com/topic/58334/a-couple-of-java-solutions-with-explanations
原文：http://www.cnblogs.com/Dylan-Java-NYC/p/6273182.html