資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究檢查是否存在給定字串的排列，該排列不包含任何單調子串
單調子串是指給定字串的連續子串，其中字元的值全部嚴格遞增或嚴格遞減。單調子串是值嚴格遞增或嚴格遞減的字串序列。
方法
動態規劃
回溯法
方法 1：動態規劃
一種技術是應用動態規劃來構建子問題的表格，這裡表格中的每個專案 (i, j) 表示是否存在字串 S[i...j] 的排列，該排列不包含任何單調子串。當 i=j 時，子串僅包含一個字元，因此是微不足道的單調的。
語法
令 s 為長度為 n 的輸入字串，dp[k][i] 為布林變數，如果 s 的前 k 個字元的排列以第 i 個字元結尾並且不包含任何單調子串，則返回 true。
對於所有 1 ≤ i ≤ n，dp[1][i] 等於 true。
如果 k > 1 且 i > j，則當且僅當 dp[k-1] [j] 為 true 且 s[i] 不在以索引 j 結尾的排列的最後兩個字母生成的單調子串中時，dp[k][i] = true。
問題的解決方案為 true 當且僅當存在值 k 使得對於某些 1 ≤ i ≤ n，dp[k][i] 為 true。
演算法
步驟 1 − 假設 S 是長度為 n 的輸入字串。
步驟 2 − 建立一個大小為 n x 2 的二維布林陣列 DP，這裡 DP[i][0] 表示以位置 i 結尾的遞減子序列的存在，而 DP[i][1] 表示以位置 i 結尾的遞增序列的存在。
步驟 3 − 將 DP [0][0] 和 DP [0][1] 都設定為 false。
步驟 4 − 對從 1 到 n-1 的每個 i 執行以下操作 −
如果存在 j 使得 0 ≤ j < i 且 S[j] > S[i] 並且 DP[j][1] 為 true，則將 DP[i][0] 設定為 true。
如果存在 j 使得 0 ≤ j < i 且 S[j] ≤ S[i] 並且 DP[j][0] 為 true，則將 DP[i][1] 設定為 true。
步驟 5 − 確定是否存在點 i 使得 DP[i][0] 和 DP[i][1] 都為 true。如果發生這種情況，則返回 false，表示排列中存在單調子串。
步驟 6 − 否則，返回 true，因為輸入字串的任何排列中都不存在單調子串。
示例
為了開始我們對這個問題的方法，我們首先建立一個名為“dp”的二維 DP 矩陣。在此矩陣中，每個元素都表示形成長度為 i 的字串所需的升序和降序字元。最初，為了正確設定我們矩陣以備將來使用，我們將單元格 [1] 內的兩個元素的值都分配為“一”。向前填充後續單元格，我們的遞迴關係使用以下公式：“dp[i-1],[0]”用於計算“dp[[i],[0]]”，而“dp[[i-13,[01'+[j-11,[j41',[i]]”生成“dpi[l,[I],l”。但是，在使用此處提到的上下文中任何進一步的策略之前；在透過 [cnt] 計算給定字串中特定字元出現的次數後，我們考慮是否存在重新排列的概念，從而導致小於或等於“dp[i][0]+dp[i][1]”的微小/大量子序列計數值。在評估後收到“true”驗證了我們方法的合法性，而其他任何內容都可能被視為不令人滿意的輸出。
#include <iostream>
#include <cstring>
using namespace std;
bool checkMonotonous(string s) {
int n = s.length();
int dp[n + 1][2];
memset(dp, 0, sizeof(dp));
dp[1][0] = dp[1][1] = 1;
for (int i = 2; i <= n; i++) {
dp[i][0] = dp[i - 1][1];
dp[i][1] = dp[i - 1][0] + dp[i - 1][1];
}
int cnt[26] = {0};
for (int i = 0; i < n; i++) {
cnt[s[i] - 'a']++;
}
for (int i = 1; i <= n; i++) {
if (dp[i][0] + dp[i][1] > cnt[i - 1]) {
return false;
}
}
return true;
}
int main() {
string s = "aabbcc";
if (checkMonotonous(s)) {
cout << "There exists a permutation of the given string which doesn't contain any monotonous substring.\n";
} else {
cout << "There does not exist permutation of given string which does not contain monotonous substring.\n";
}
return 0;
}
輸出
There does not exist permutation of given string which does not contain monotonous substring.
方法 2：回溯法
回溯法也可用於生成字串的所有可能排列，然後檢查其中任何一個是否包含單調子串。由於排列數量對於大型字串來說可能非常大，因此這種方法可能會延遲，但它保證如果存在解決方案則會找到解決方案。
語法
在 C++ 中使用回溯法解決檢查字串排列（不包含單調子串）問題的通用語法。
bool hasMonotonousSubstring(string s) {
sort(s.begin(), s.end());
do {
bool valid = true;
for (int i = 2; i < s.length(); i++) {
if (s[i] == s[i-1] + 1 && s[i-1] == s[i-2] + 1) {
valid = false;
break;
}
else if (s[i] == s[i-1] - 1 && s[i-1] == s[i-2] - 1) {
valid = false;
break;
}
}
if (valid) return true;
} while (next_permutation(s.begin(), s.end()));
return false;
}
演算法
使用 C++ 中的回溯法生成不包含單調子串的給定字串的排列的通用方法如下 −
步驟 1 − 生成提供的字串的所有排列。
步驟 2 − 檢查每個排列以檢視它是否包含任何單調子串。如果不是，則該排列是有效的解決方案。
步驟 3 − 返回有效解決方案並在發現解決方案時結束過程。
步驟 4 − 如果您已生成所有可能的排列並且沒有一個是有效的，則返回到上一步並嘗試不同的候選解決方案。
示例 2
isMonotonous () 方法確定提供的字串是否包含任何單調子串。它透過遍歷文字並查詢長度為 3 的嚴格遞增或嚴格遞減的子串來實現此目的。
permute () 函式透過回溯生成提供的字串的所有排列。它將字串 s、初始索引 l 和結束索引 r 作為輸入。如果初始索引等於結束索引，則我們已生成排列。使用 isMonotonous () 方法，我們確定此排列是否包含任何單調子串。
main () 函式初始化輸入字串並將其按字典序升序排序。然後，它呼叫 permute () 函式，起始索引為 0，結束索引為字串長度減 1。如果未找到任何無單調子串的排列，我們列印“未找到排列”。
#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
bool isMonotonous(string s) {
for (int i = 2; i < s.length(); i++) {
if ((s[i] > s[i-1] && s[i-1] > s[i-2]) || (s[i] < s[i-1] && s[i-1] < s[i-2])) {
return true;
}
}
return false;
}
bool permute(string s, int l, int r) {
if (l == r) {
if (!isMonotonous(s)) {
cout << s << endl;
return true;
}
}
else {
for (int i = l; i <= r; i++) {
swap(s[l], s[i]);
if (permute(s, l+1, r)) {
return true;
}
swap(s[l], s[i]);
}
}
return false;
}
int main() {
string s = "abc";
sort(s.begin(), s.end()); // sort the string in lexicographically increasing order
if (!permute(s, 0, s.length()-1)) {
cout << "No permutation found" << endl;
}
return 0;
}
輸出
acb
結論
總而言之，確定給定字串是否具有不包含任何單調子串的排列是一項具有挑戰性的任務，需要仔細的分析和演算法設計。
一種可能的解決方案是生成字串的所有可能排列，並檢查每個排列中是否存在單調子串。但是，由於對於較大的輸入大小，排列的數量可能非常大，因此這種方法效率低下。
214 次檢視
