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 次檢視

啟動您的 職業生涯

透過完成課程獲得認證

開始學習