資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++中子字串出現次數的最大值
假設我們有一個字串s，我們需要找到滿足以下規則的任何子字串出現的最大次數：
- 子字串中不同字元的數量必須小於或等於maxLetters。
- 子字串的大小必須在minSize和maxSize（包含）範圍內。
因此，如果輸入類似於：“aababcaab”，maxLetters = 2，minSize = 3，maxSize = 4，則輸出為2。子字串“aab”在原始字串中出現2次。這滿足條件：2個唯一字元和大小為3（在minSize和maxSize之間）。
為了解決這個問題，我們將遵循以下步驟：
- 定義一個對映m
- 對於sz範圍從minSize到maxSize
- 建立一個對映x，建立一個臨時變數temp，初始為空
- 對於i範圍從0到sz – 1
- 將x[s[i]]增加1
- temp := temp + s[i]
- 對於j為0，i範圍從sz到s的大小 – 1，i和j都增加1
- 如果x的大小 <= maxLetters，則將m[temp]增加1
- 將x[temp[0]]減少1
- 如果x[temp[0]]為0，則從x中刪除temp[0]
- 從temp本身刪除第一個和第二個元素
- 將x[s[i]]增加1
- temp := temp + s[i]
- 如果x的大小 <= maxLetters，則將m[temp]增加1
- ans := 0
- 當對映m有一些元素時，則
- ans := ans和第i個鍵值對的值中的最大值
- 返回ans
示例（C++）
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int maxFreq(string s, int maxLetters, int minSize, int maxSize) {
unordered_map <string ,int > m;
for(int sz = minSize; sz <= minSize; sz++){
unordered_map <char, int> x;
string temp ="";
for(int i = 0; i < sz; i++){
x[s[i]]++;
temp += s[i];
}
for(int j = 0, i = sz; i < s.size(); i++, j++){
if(x.size() <= maxLetters){
m[temp]++;
}
x[temp[0]]--;
if(x[temp[0]] == 0)x.erase(temp[0]);
temp.erase(temp.begin(),temp.begin() + 1);
x[s[i]]++;
temp += s[i];
}
if(x.size() <= maxLetters){
m[temp]++;
}
}
int ans = 0;
unordered_map <string ,int > :: iterator i = m.begin();
while(i != m.end()){
ans = max (ans, i->second);
i++;
}
return ans;
}
};
main(){
Solution ob;
cout << (ob.maxFreq("aababcaab",2,3,4));
}輸入
"aababcaab" 2 3 4
輸出
2
更新於：2020年4月30日
489 次瀏覽
廣告