資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的最短公共子串
假設我們有一個小寫的字母字串 s，我們必須找到最短子串的長度（最小長度為 2），這種長度的子串中，某個字母出現的次數多於其他字母出現的次數之和。如果找不到任何解，則返回 -1。
因此，如果輸入類似於“abbbcde”，那麼輸出將為 2，子串“bb”具有最短長度，並且出現的次數多於其他字母。
為了解決這個問題，我們將執行以下步驟 -
定義一個函式 ok()，它將採用一個數組 cnt，
total := 0，maxVal := 0
對於 cnt 中的每個元素，進行以下操作，
total := total + it
maxVal := maxVal 和 it 的最大值
在 maxVal > (total - maxVal) 時返回 true
在主方法中，執行以下操作 -
n := s 的大小
ret := inf
對於 i 的初始化 := 0，當 i < n 時，更新（將 i 加 1），執行以下操作 -
如果 i + 1 < n 並且 s[i] 與 s[i + 1] 相同，則 -
返回 2
否則當 i + 2 < n 並且 s[i] 與 s[i + 2] 相同時，則 -
ret := 3
返回（如果 ret 與 inf 相同，則 -1，否則 ret）
讓我們看看以下實現，以獲得更好的理解 -
示例
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
bool ok(vector <int>& cnt){
int total = 0;
int maxVal = 0;
for(auto& it : cnt){
total += it;
maxVal = max(maxVal, it);
}
return maxVal > (total - maxVal);
}
int solve(string s) {
int n = s.size();
int ret = INT_MAX;
for(int i = 0; i < n; i++){
if(i + 1 < n && s[i] == s[i + 1]){
return 2;
}else if(i + 2 < n && s[i] == s[i + 2]){
ret = 3;
}
}
return ret == INT_MAX ? -1 : ret;
}
};
int main(){
Solution ob;
cout << (ob.solve("abbbcde"));
}輸入
"abbbcde"
輸出
2
更新於: 02-Sep-2020
275 次瀏覽
廣告