C++ 中的数字编码

假设我们有一个非负整数 n，我们需要找到它的编码形式。编码策略如下：

所以如果数字是 23，则结果将是 1000，如果数字是 54，则结果将是 10111

为了解决这个问题，我们将遵循以下步骤：

• 创建一个名为 bin 的方法，它将接收 n 和 k 作为参数，此方法将按以下方式执行
• res := 空字符串
• 当 n > 0 时
  • res := res + n 模 2 的数字
  • n := n /2
• 反转数字 res
• 当 x > res 的长度时
  • res := 在 res 前面添加 0
• 返回 res
• 实际方法如下：
• 如果 n = 0，则返回空字符串，如果 n 为 1，则返回“0”，或者当 n 为 2 时，则返回“1”
• x := 以 2 为底 n 的对数
• 如果 2 ^ (x + 1) – 1 = n，则
  • ans := 空字符串
  • 将 x 加 1
  • 当 x 不为 0 时，则 ans := 在 ans 后面追加 0，并将 x 加 1
  • 返回 ans
• 返回 bin(n – 2^x + 1, x)

让我们看下面的实现来更好地理解：

示例

 在线演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   string bin(int n, int x){
      string result = "";
      while(n>0){
         result += (n%2) + '0';
         n/=2;
      }
      reverse(result.begin(), result.end());
      while(x>result.size())result = '0' + result;
      return result;
   }
   string encode(int n) {
      if(n == 0)return "";
      if(n == 1)return "0";
      if(n==2) return "1";
      int x = log2(n);
      if(((1<<(x+1)) - 1) == n){
         string ans = "";
         x++;
         while(x--)ans+="0";
         return ans;
      }
      return bin(n - (1<<x) + 1, x);
   }
};
main(){
   Solution ob;
   cout << (ob.encode(23)) << endl;
   cout << (ob.encode(56)) << endl;
}

输入

23
54

输出

1000
11001

Arnab Chakraborty

更新于: 2020年5月2日

462 次查看

启动您的 职业生涯

通过完成课程获得认证

开始学习