数据结构
网络
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 次浏览
广告