C++程序，用于删除数字字符串中的字符，使其能被8整除

Given a number in the form of a string, we need to find where to make it divisible by eight after deleting zero or more elements. In other words, we need to find whether there is a subsequence of the string, which is divisible by 8. Return the modified string or -1 if it is not possible.

根据可整除规则，任何最后三位数字可被8整除的数也可被8整除。例如，56992992和476360可被8整除，但2587788不能。如果结果是一个整数，则原始数可被8整除。

Let us look at some input scenarios that explain the method in detail −

如果传递给该方法的输入是包含任何可被8整除的子字符串的数字字符串，则在结果列表中我们可以获得可被8整除的子字符串−

立即学习“C++免费学习笔记（深入）”；

Input: 2567992Result: 56

如果输入给方法的是一个不包含任何可被8整除的子字符串的数字字符串，输出结果将返回为−

Input: 77777777777Result: -1

Algorithm

字符串输入被遍历，检查是否有任何子字符串是8的倍数。

If there is any consequent substring present in the input, the substring is returned as the output.

如果找到子字符串，则程序终止，否则重复步骤2直到找到子字符串。

如果输入中没有可被8整除的子字符串，则返回输出为-1。

Example

在下面的C++程序中，我们取两个字符串，一个可以转换为可被8整除的字符串，另一个不能，然后找出每种情况下的输出。我们可以从0到1000迭代，以8的倍数如0、8、16、24、32…1000，并检查这个数字是否作为给定字符串的子序列存在。

#include 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;}

输出

816

As you can see in the above output, 9525 is removed from 95258, and 745 is removed from 74516 to make the left number divisible by 8.

Conclusion

正如我们所看到的，在简单观察之后，我们只需要检查子集是否存在。我们检查字符串是否包含子序列，最坏情况下，它将检查整个字符串。因此，如果我们给定一个长度为n的数字字符串，最坏时间复杂度为O(126*n)，即O(n)。

以上就是C++程序，用于删除数字字符串中的字符，使其能被8整除的详细内容，更多请关注创想鸟其它相关文章！