資料結構
網路
關係型資料庫管理系統 (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
