資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究字串的最小子字串數量，使所有子字串均為 5 的冪
介紹
在本教程中，我們將使用 C++ 實現兩個示例來查詢給定字串中的最小子字串數量。這些子字串都是 5 的冪，這意味著子字串是數字 5 的因子。為了實現該示例，請獲取一個輸入二進位制字串並生成儘可能少的 5 的因子子字串。如果要確定子字串是否是 5 的冪，請檢查其十進位制值。
二進位制字串是 1 和 0 的組合，我們無法找到某個特定的二進位制字串是 5 的倍數還是不是。例如，0101 的十進位制值為 5。
演示 1
String = “101101”
輸出
2
使用上述輸入字串，可以形成的 5 的冪子字串的數量為 2。可能的子字串為“101”和“101”（子字串可以是任意一個）。這些子字串是 5 的冪。101 的十進位制值為 5，可以被 5 整除。
演示 2
String = “1111111
輸出
2
在上述示例中，使用上述輸入字串，可以形成的 5 的冪子字串的數量為 2，它們分別是 1111 和 11111111。1111 的十進位制值為 15，11111111 的十進位制值為 225，這兩個十進位制值都是 5 的因子或 5 的冪。
演算法
以二進位制形式獲取輸入字串。
使用 length() 函式查詢字串的長度。
使用輸入字串生成可能的子字串。
檢查生成的子字串是否是 5 的因子。
如果子字串是 5 的冪，則將該值儲存在計數器變數中。
列印計數器變數的值。
語法
在下面的示例中，使用了以下 C++ 庫函式
length() : 這是一個內建的字串庫函式。它以位元組形式返回輸入字串的長度。長度定義字串中字元的數量。
string_name.length();
memset() : 它將連續的記憶體塊分配給特定值。它有 3 個引數：字元、長度和一個整數值。
memset(char, len, int);
unordered_set() : 這是一個無序的資料結構，允許以無序模式插入和刪除元素。
unordered_set(data_type) set_name;
unordered_set.insert():它是 unordered_set 標頭檔案的一個庫函式。它以無序的方式將元素插入到集合中。
unordered_set_name.insert(value);
unordered_set.find() : 用於查詢 unordered_set 中儲存的值。它在 unordered_set 標頭檔案中定義。
unordered_set_name.find(value);
substr() : 它是一個字串類庫函式，用於使用輸入字串生成子字串。它接受兩個引數，分別定義子字串的起始點和長度。
string_name.substr(pos, len);
stoi() : 此標準字串類庫函式將字串轉換為整數。它在 C++ 程式設計中經常使用。stoi() 代表字串到整數的值。
stoi(string str, position, base);
vector : 它是一個動態陣列。此外，它為其元素提供連續的記憶體位置。
vector<data_type> vector_name;
示例 1
我們透過定義一個 long long 型別的標頭檔案來實現一個示例。獲取輸入字串並生成子字串，然後檢查子字串是否是 5 的冪因子。列印可以使用輸入字串形成的最小子字串數量。
#include <bits/stdc++.h>
using namespace std;
#define ll unsigned long long
//function to check substring is power of 5
bool ispowerOfFive(ll len)
{
if (len < 125)
return (len == 1 || len == 5 || len == 25);
if (len % 125 != 0)
return false;
else
return ispowerOfFive(len / 125);
}
//function to return decimal value
ll decimalValue(string str, int x, int y)
{
ll result = 0;
for (int i = x; i < y; i++)
{
result = result * 2 + (str[i] - '0');
}
return result;
}
int minCutValue(string str, int len)
{
int dpg[len + 1];
// memory allocation using memset
memset(dpg, len + 1, sizeof(dpg));
dpg[0] = 0;
for (int x = 1; x <= len; x++)
{
if (str[x - 1] == '0')
continue;
for (int y = 0; y < x; y++)
{
if (str[y] == '0')
continue;
ll value = decimalValue(str, y, x);
// calling function
if (!ispowerOfFive(value))
continue;
dpg[x] = min(dpg[x], dpg[y] + 1);
}
}
return ((dpg[len] < len + 1) ? dpg[len] : -1);
}
int main()
{
string str = "1011011011";
int len = str.length();
cout << minCutValue(str, len);
return 0;
}
輸出
4
示例 2
我們透過使用一些使用者定義的函式來實現一個示例。使用 vector（類似於沒有預定義大小的陣列）和動態程式設計方法，使用輸入字串生成子字串。使用 substr() 函式生成子字串後，檢查它們是否是 5 的冪。
#include <vector>
#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
using namespace std;
bool isPower(int n)
{
while (n % 5 == 0)
{
n /= 5;
}
return n == 1;
}
int countSubstr(const string& s)
{
int l = s.length();
unordered_set<int> powersOfFive;
// Pre-compute powers of 5 up to the maximum length of substring possible
for (int x = 0; x < l; x++)
{
int pwr = 1;
for (int y = 0; y <= x; y++)
{
pwr *= 5;
}
powersOfFive.insert(pwr);
}
// Dynamic programming approach to count minimum substrings
vector<int> dpg(l + 1, l + 1);
dpg[0] = 0;
for (int x = 1; x <= l; x++)
{
for (int y = 0; y < x; y++)
{
string sb = s.substr(y, x - y);
int sbNum = stoi(sb, nullptr, 2); // Parse binary string as integer
if (powersOfFive.find(sbNum) != powersOfFive.end())
{
dpg[x] = min(dpg[x], dpg[y] + 1);
}
}
}
return dpg[l] == l + 1 ? -1 : dpg[l];
}
int main() {
string s = "1111101";
int output = countSubstr(s);
if (output == -1)
{
cout << "No valid substrings found." << endl;
}
else
{
cout << "Minimum number of substrings: " << output << endl;
}
return 0;
}
輸出
Minimum number of substrings: 1
結論
在本教程中，我們使用 C++ 實現了兩個示例，使用不同的邏輯來確定輸入字串中的子字串數量。這些子字串是 5 的冪。使用 length()，我們確定子字串是否是 5 的因子。length() 函式有助於確定字串的長度。
為了使任務要求更加清晰，我們本教程中使用了 3 個演示，並使用了各種 C++ 庫函式來實現示例。
133 次瀏覽
