数据结构
网络
关系型数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
时尚研究
法律研究查找S的非空子字符串中值最大的偶数整数
在这个问题中，我们需要找到给定字符串中值最大的偶数子字符串。偶数字符串的末尾总是包含2、4、6、8、0。因此，我们可以取给定字符串的所有子字符串，如果任何子字符串是偶数且大于最大子字符串，我们可以更新最大子字符串的值。
问题陈述 – 我们给定一个仅包含数字的字符串str。我们需要找到str的最大子字符串，该子字符串是一个偶数整数。
示例
输入
str = "1234789"
输出
123478
解释 – 最大的偶数子字符串是123478。
输入
str = ‘3208’
输出
3208
解释 – 字符串本身就是偶数。所以，它打印字符串本身。
输入
str = "13579";
输出
‘Not Possible’
解释 – 字符串不包含任何偶数子字符串。所以，它打印了“不可能”。
方法一
在这种方法中，我们将遍历给定字符串的所有子字符串。如果子字符串的最后一个字符能被2整除，则表示该字符串是偶数。之后，我们将检查当前字符串是否大于最大字符串。如果是，则替换最大字符串。
算法
步骤1 – 用空字符串初始化“largeEven”字符串。
步骤2 – 使用for循环从第0个索引开始遍历字符串。在循环内，初始化“temp”字符串并使用嵌套循环从pth索引开始遍历字符串。
步骤3 – 从索引中取字符并将其附加到“temp”字符串。
步骤4 – 如果字符串的最后一个字符能被2整除，则执行getMaxStr()函数以查找最大字符串并将它的返回值存储到largeEven字符串。
步骤4.1 – 在getMaxStr()函数中，如果第一个字符串的长度大于第二个字符串的长度，则返回第一个字符串。否则，返回第二个字符串。
步骤4.2 – 如果两个字符串的长度相同，则使用循环开始匹配字符串的所有字符。
步骤4.3 – 如果第一个字符串中pth索引处的字符更大，则返回第一个字符串。否则，返回第二个字符串。如果相同索引处的字符相同，则继续进行下一次迭代。
步骤5 – 返回“largeEven”字符串。
示例
#include <bits/stdc++.h>
using namespace std;
string getMaxStr(string num1, string num2) {
// Comparing the size of both strings
if (num1.length() > num2.length()){
return num1;
} else if (num1.length() < num2.length()) {
return num2;
}
// For the same length of strings
for (int p = 0; p < num1.length(); ++p) {
if (num1[p] > num2[p])
return num1;
else if (num1[p] < num2[p])
return num2;
}
// If strings are equal
return num1;
}
string findStr(string str) {
// string size
int len = str.size();
string largeEven = "";
// get all substrings of the string
for (int p = 0; p < len; p++) {
string temp = "";
for (int q = p; q < len; q++) {
temp += str[q];
int tempLen = temp.size();
// check if the substring is even
if ((temp[tempLen - 1] - '0') % 2 == 0)
{
// Get maximum string
largeEven = getMaxStr(largeEven, temp);
}
}
}
return largeEven;
}
int main() {
string str = "1234789";
string result = findStr(str);
if (result == ""){
cout << "Not possible";
} else {
cout << "The largest possible even number is " << result << "\n";
}
return 0;
}
输出
The largest possible even number is 123478
时间复杂度 – O(N*N)，因为我们得到了给定字符串的所有子字符串。
空间复杂度 – O(N) 用于存储子字符串。
方法二
在这种方法中，我们将从最后遍历字符串并找到偶数数字的第一次出现。我们可以将从第0个索引到当前数字的子字符串作为字符串的最后一位数字将是偶数。
算法
步骤1 – 用-1初始化“index”变量以存储从最后开始的第一个偶数数字的索引。
步骤2 – 从最后遍历字符串。
步骤3 – 如果当前数字能被2整除，则将“index”变量的值更新为“I”并中断循环。
步骤4 – 如果index的值为-1，则返回空字符串，因为字符串仅包含奇数数字。否则，返回从第0个索引开始且长度等于“index + 1”的子字符串。
示例
#include <bits/stdc++.h>
using namespace std;
string findStr(string str) {
int len = str.length();
int index = -1;
// Traverse string from right to left
for (int i = len - 1; i >= 0; i--) {
// Getting the first even digit from the right
if ((str[i] - '0') % 2 == 0) {
index = i;
break;
}
}
if (index == -1)
return "";
else
return str.substr(0, index + 1);
}
int main(){
string str = "1234879";
string result = findStr(str);
if (result == "") {
cout << "Not possible";
} else {
cout << "The largest possible even number is " << result << "\n";
}
return 0;
}
输出
The largest possible even number is 12348
时间复杂度 – O(N) 用于反向遍历字符串或获取子字符串。
空间复杂度 – O(1)，因为我们没有使用额外的空间。
第一种方法是朴素的方法，第二种方法是优化的。在第二种方法中，我们使用了偶数字符串的最后一位数字能被2整除的逻辑，并且当我们从最后遍历时，我们可以得到长度最大的子字符串。
浏览量：119
