C++ 中檢查字串是否包含大小為 K 的所有二進位制程式碼

假設我們有一個二進位制字串 s 和一個整數 k。我們必須檢查長度為 k 的每個二進位制程式碼是否都是 s 的子字串。否則，返回 False。

因此，如果輸入類似於 S = "00110110"，k = 2，則輸出將為 true。長度為 2 的二進位制程式碼為“00”、“01”、“10”和“11”。它們分別位於索引 0、1、3 和 2 處。

要解決此問題，我們將遵循以下步驟：

  • 定義一個集合 v

  • temp := 空字串

  • req := 2^k

  • 初始化 i := 0，當 i < s 的大小，更新（i 增加 1），執行：

    • temp := temp + s[i]

    • 如果 i >= k，則：

      • 從 temp 的第一個索引刪除一個字元

    • 如果 i >= k - 1，則：

      • 將 temp 插入 v

    • 如果 v 的大小與 req 相同，則：

      • 返回 true

  • 返回 false

示例

讓我們看看以下實現以更好地理解：

線上演示

#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
class Solution {
public:
   lli fastPow(lli b, lli p){
      lli ret = 1;
      while (p) {
         if (p & 1) {
            ret *= b;
         }
         b *= b;
         p >>= 1;
      }
      return ret;
   }
   bool hasAllCodes(string s, int k) {
      unordered_set<string> v;
      string temp = "";
      lli req = fastPow(2, k);
      for (lli i = 0; i < s.size(); i++) {
         temp += s[i];
         if (i >= k) {
            temp.erase(0, 1);
         }
         if (i >= k - 1) {
            v.insert(temp);
         }
         if ((lli)v.size() == req)
            return true;
      }
      return false;
   }
};
main(){
   Solution ob;
   cout << (ob.hasAllCodes("00110110",2));
}

輸入

"00110110",2

輸出

1

更新於： 2020-11-18

192 次瀏覽

開啟您的 職業生涯

透過完成課程獲得認證

開始學習
廣告