题目

类型：贪心
image.png

解题思路

image.png

代码

  1. class Solution {
  2.     public int integerReplacement(int n) {
  3.         int ans = 0;
  4.         while (n != 1) {
  5.             if (n % 2 == 0) {
  6.                 ++ans;
  7.                 n /= 2;
  8.             } else if (n % 4 == 1) {
  9.                 ans += 2;
  10.                 n /= 2;
  11.             } else {
  12.                 if (n == 3) {
  13.                     ans += 2;
  14.                     n = 1;
  15.                 } else {
  16.                     ans += 2;
  17.                     n = n / 2 + 1;
  18.                 }
  19.             }
  20.         }
  21.         return ans;
  22.     }
  23. }