資料結構
網路
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 次瀏覽
廣告