数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究C++程序：从数字字符串中删除字符，使其可被8整除
给定一个以字符串形式表示的数字，我们需要找到在删除零个或多个元素后使其可被8整除的位置。换句话说，我们需要找到该字符串是否存在一个可被8整除的子序列。返回修改后的字符串，如果不可能，则返回-1。
任何最后三位数字可被8整除的数字也一定可被8整除。例如，56992992和476360可被8整除，但2587788不可。如果结果为整数，则原数字可被8整除。
我们可以从0到1000迭代8的倍数，如0、8、16、24、32…1000，并检查此数字是否作为子序列存在于给定字符串中。让我们取两个字符串，一个可以转换为可被8整除的字符串，另一个不可以，并找到每种情况下的输出。
示例
#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 “74513” 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年5月18日
190 次浏览
广告