数据结构
网络
关系数据库管理系统
操作系统
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 次浏览
