# 397. Integer Replacement多种方法比较

``class Solution { public: //此题设置“全局变量”vector<int> result;会导致run code和submit的时候结果不一致 //采用DP递推的方法，当数比较大的时候（百万，千万）会造成内存不够     int integerReplacement(int n) {         if( n <= 0) return 0;         if(n == 2147483647) return 32;          vector<int> result(n+1,0);         result[0] = result[1] = 0;         result[2] = 1;         for(int i = 2; i <= n; i++)         {             if(i%2 == 0) result[i] = result[i >> 1] + 1;             else if(i%2 == 1)              {                 int a = result[(i-1) >> 1];                 int b = result[(i+1) >> 1];                 result[i] = a < b ? (a+2) : (b+2);             }         }         return result[n];     } };``

``class Solution { public: //此题设置“全局变量”vector<int> result;会导致run code和submit的时候结果不一致 //采用DP递推的方法，当数比较大的时候（百万，千万级别的时候），会造成内存不够：Memory Limit Error //采用递归的这种方式倒是可以 //考虑最大值2147483647     int integerReplacement(int n) {         if( n <= 1) return 0;         if(n == INT_MAX) return 32;         if(n%2 == 0) return integerReplacement(n>>1) + 1;         else return min(integerReplacement(n+1)+1, integerReplacement(n-1)+1);          ｝     };``

``class Solution  {     int res = 0; public:     int integerReplacement(int n)      {         if (n == 1)             return res;         if (n == 3)         {             res += 2;             return res;         }         if (n == INT_MAX)             return 32;          res ++;         if (n & 1)             if ((n + 1) % 4 == 0)                 integerReplacement(n + 1);             else                 integerReplacement(n - 1);         else             integerReplacement(n / 2);          return res;     } };``

``class Solution  {     public:      int integerReplacement(int n) {         if (n <= 1) {             return 0;         } else if (n == INT_MAX) {             return 32;         }         if(n == 3)  return 2; //后期添加即可。         if (n & 1) {             return (numTrailingOnes(n) > 1) ? (integerReplacement(n + 1)+1) : (integerReplacement(n - 1)+1);         }         else {             return integerReplacement(n >> 1) + 1;         }     }      int numTrailingOnes(int num) {         int shift = 0;         while (((num >> shift) & 1)) {             shift++;         }         cout << shift;         return shift;     } };``