C++程式：去除數字字串中的字元使其可被8整除

給定一個數字字串，我們需要找到刪除零個或多個元素後使其可被8整除的方法。換句話說，我們需要找到該字串是否存在一個可被8整除的子序列。返回修改後的字串，如果不可能則返回-1。

根據整除規則，任何最後三位數字可被8整除的數字也可被8整除。例如，56992992和476360可被8整除，但2587788不可被8整除。如果結果是整數，則原數字可被8整除。

讓我們來看一些詳細解釋該方法的輸入場景：

如果輸入方法的數值字串包含任何可被8整除的子串，則在結果列表中，我們將獲得可被8整除的子串：

Input: 2567992
Result: 56

如果輸入方法的數值字串不包含任何可被8整除的子串，則輸出返回為：

Input: 77777777777
Result: -1

演算法

  • 遍歷字串輸入的每個元素，以檢查是否存在任何子串是8的倍數。

  • 如果輸入中存在任何連續的子串，則將該子串作為輸出返回。

  • 如果找到子串，則程式終止；否則重複步驟2，直到找到子串。

  • 如果輸入中沒有可被8整除的子串，則輸出返回為-1。

示例

在下面的C++程式中，讓我們取兩個字串，一個可以轉換為可被8整除的字串，另一個不可以，並找出每種情況下的輸出。我們可以迭代從0到1000，使用8的倍數如0, 8, 16, 24, 32 … 1000，並檢查此數字是否存在於給定字串中作為子序列。

#include <iostream>
using namespace std;
int checkIfSubstringExist(string req, string given) {
   int index = 0;
   for (char ch : given) {
      if (req[index] == ch) {
         index++;
      }
   }
   return index == (int)req.size();
}
string solve(string s) {
   for (int i = 0; i < 1e3; i += 8) {
      string num = to_string(i);
      if (checkIfSubstringExist(num, s)) {
         return num;
      }
   }
   return "-1";
}
int main() {

   // the string “95256” can be converted to a string divisible by 8
   // the string “74516” cannot be converted to a string divisible by 8
   // let’s run our code to find the output in each case
   string s1 = "95258", s2="74516";
   cout << solve(s1) << "\n" << solve(s2) << endl;
   return 0;
}

輸出

8
16

正如你在上面的輸出中看到的，從95258中刪除了9525，從74516中刪除了745，使剩餘數字可被8整除。

結論

正如我們所看到的，經過簡單的觀察，我們只需要檢查子集是否存在。我們檢查字串是否存在子序列，在最壞的情況下，它將檢查整個字串，所以如果給定長度為n的數字字串，則最壞時間複雜度為O(126*n)，即O(n)。

更新於：2022年8月10日

瀏覽量：135

開啟你的職業生涯

完成課程獲得認證

開始學習
廣告