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

开启你的职业生涯

完成课程获得认证

开始学习
广告