数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究无限字符串前 N 个字符中仅包含数字 4 的最长子字符串
介绍
在本教程中，我们将实现一种方法，利用无限字符串的前 N 个字符来查找仅包含数字 4 的最长子字符串。无限字符串使用数字 4，看起来像这样：“44444444……”，对于此字符串，我们定义了要考虑的字符长度以解决任务。为了解决本教程的问题，请考虑一个输入数字字符串，我们将使用以下两个条件来解决此问题：
考虑一个包含随机数字的输入字符串，并从该字符串中生成仅包含数字 4 的最长子字符串。
我们考虑一个由 4、5、44、45 等组合组成的无限字符串。此字符串将包含按升序排列的 4 和 5 的组合的数字。使用此字符串查找仅包含数字 4 的最长子字符串的长度。
演示 1
String = “3444445443”
输出
the longest substring containing 4’s is 44444
解释
在上述输入字符串 444445443 中，存在 3、4 和 5。任务是生成一个仅包含数字 4 的子字符串。因此，使用输入字符串执行任务的输出为 44444。
演示 2
在此演示中，我们采用一个按升序排列的 4 和 5 数字组合的输入字符串。我们定义输入字符串的长度，并以仅包含数字 4 的最长子字符串的长度的形式生成输出。
Total characters in the string = 6
输出
3
解释
我们为输入字符串取 6 个字符，生成的输入字符串为 454445。使用此字符串，使用前 N 个字符仅包含数字 4 的子字符串的长度为 3。
演示 3
Length of the string = 8
输出
3
输入字符串的长度为 8，为此，可能的输入字符串为 45444554。使用初始字符仅包含数字 4 的子字符串的长度为 3。
C++ 库函数
语法
length() : 这是一个字符串类库函数，用于返回字符串的长度。字符串的字节格式长度是字符串中所有字符的总和。
string_name.length();
substr(): 它定义在字符串类头文件中。它使用输入字符串生成子字符串。它接受 2 个参数：begin，length。
string_name.substr(begin, length);
算法 1
获取输入字符串长度。
函数 maxlengthSubstr() 返回仅包含数字 4 的最长子字符串的长度。
初始化一个前缀数组以生成可能的输入字符串组合。
该数组将从数组变量迭代到 MAXN。
通过计算 result 变量值来查找子字符串的长度。
示例 1
在此实现中，用户定义的函数 maxLengthSubstr() 返回仅包含数字 4 的最长子字符串的长度。初始化一个 pre_arr{} 来计算长度。不要完整生成输入字符串，而是指定其长度。常量变量 MAXN 在代码开头定义。
其 C++ 实现如下：
#include <bits/stdc++.h>
using namespace std;
#define MAXN 30
// Function returning the length of the longest substring containing only 4
int maxLengthSubstr(int Num)
{
//variable containing the result
int ans;
// Initialize array to make groups
int pre_arr[MAXN], q = 1;
pre_arr[0] = 0;
for (int x = 1; x < MAXN; x++)
{
q *= 2;
pre_arr[x] = pre_arr[x - 1] + x * q;
}
int l;
//Finding the length of the longest substring
for (int x = 1; x < MAXN; x++)
{
if (pre_arr[x] >= Num)
{
l = x;
break;
}
}
int i = Num - pre_arr[l - 1];
int j = 2 * l - 1;
if (i >= j)
ans = min(i, j);
else
ans = max(i, 2 * (l - 2) + 1);
return ans;
}
// Controller
int main()
{
int Num = 8;
cout << "Maximum length of the longest substring of 8 string characters containing only 4s is : " << maxLengthSubstr(Num);
return 0;
}
输出
Maximum length of the longest substring of 8 string characters containing only 4s is : 3
示例 2
在此实现中，用户定义的函数 longestSubstr() 返回使用输入字符串的前 N 个字符仅包含数字 4 的最长子字符串。输入字符串的每个字符都与数字 4 进行比较，当匹配时，计数器变量的值增加。
以下是上述说明的 C++ 实现。
#include <iostream>
#include <string>
using namespace std;
//function returning the longest substring containing only 4
string longestSubstring(const string& str)
{
int maxLen = 0;
int start = 0;
int currentLen = 0;
int currentStartIndex = 0;
//iterating characters of the string
for (int x = 0; x < str.length(); x++)
{
if (str[x] == '4')
{
if (currentLen == 0)
{
currentStartIndex = x;
currentLen = 1;
}
else
{
currentLen++;
}
if (currentLen > maxLen)
{
maxLen = currentLen;
start = currentStartIndex;
}
}
else
{
currentLen = 0;
}
}
string longestSubstr = str.substr(start, maxLen);
return longestSubstr;
}
//Controller
int main()
{
string str = "344444405474444";
string longestSubstr = longestSubstring(str);
cout << "Longest substring of only 4's: " << longestSubstr << endl;
return 0;
}
输出
Longest substring of only 4's: 44444
结论
我们已经完成了从输入字符串的前 N 个字符中查找仅包含数字 4 的最长子字符串的任务。这是使用 C++ 逻辑完成的。第一个解决方案涉及将输入字符串中的每个字符进行比较，以查找仅包含数字 4 的最长子字符串。在第二个解决方案中，确定仅包含数字 4 的最长子字符串的长度。这是通过使用一个包含数字 4 和 5 按升序排列的字符串（如 4、5、44、45……）来完成的。
这两个解决方案都通过使用一些 C++ 库函数帮助解决了问题。一些演示用于详细说明问题陈述的目的。
81 次浏览
