神刀安全网

397. Integer Replacement多种方法比较

又碰到一个很有意思的题目,拿过来纪录一下过程。
首先,我使用了Dynamic Programming的方法:

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];     } };

当n达到10000000的时候,会报“Memory Limit Exceeded”错误,也就是爆内存了。当然,数比较小的时候是可以的。

然后,又考虑普通的递归方案:

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);          }     };

酱紫,是可以AC的。

然后,看到讨论区的一个答案:

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;     } };

然后又稍微思考了一下,这里面的原因,我觉得,从二进制的思路考虑,能够让n尽快的变成1的原因是,让n的二进制尾数中的连续的1尽快的变成0,给出如下方案:

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;     } };

哈哈, 居然是Wrong Answer, 原来是忽略了n==3的情况。OK

转载本站任何文章请注明:转载至神刀安全网,谢谢神刀安全网 » 397. Integer Replacement多种方法比较

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址