資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會學
服裝設計
法學C++ 最小視窗子串
假設我們有兩個字串 S 和 T。我們需要在 S 中找到包含 T 中所有字元的最小視窗。例如，如果輸入字串為“ABHDAXCVBAGTXATYCB”，而 T = “ABC”，則結果為：“CVBA”。
為了解決這個問題，我們將遵循以下步驟：
建立一個對映 m
將 x 的頻率儲存到 m 中
length := s 的大小，left := 0，right := 0，ansLeft := 0，ansRight := 0
counter := x 的大小，flag := false，ans := 空字串
當 height < s 的大小：
c := s[right]
如果 c 存在於 m 中，則
如果 m[c] > 0，則將 counter 減 1
將 m[c] 減 1
當 counter = 0 且 left <= right
如果 right – left + 1 <= length
length := right – left + 1
flag := true
ansLeft := left，ansRight := right
如果 left = right，則跳出迴圈
c := s[left]
如果 c 存在於 m 中，則將 m[c] 加 1
如果 m[c] > 0，則將 counter 加 1
將 left 加 1
將 right 加 1
如果 flag 為 false，則返回 ans
否則，對於 i 從 ansLeft 到 ansRight，將 s[i] 追加到 ans 中
返回 ans
示例
讓我們來看下面的實現，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
string minWindow(string s, string x) {
map <char, int> m;
for(int i =0;i<x.size();i++)m[x[i]]++;
int length = s.size();
int left = 0, right = 0 , ansLeft = 0, ansRight = 0;
int counter = x.size();
bool flag = false;
string ans = "";
while(right<s.size()){
char c = s[right];
if(m.find(c)!=m.end()){
if(m[c]>0)counter--;
m[c]--;
}
while(counter == 0 && left<=right){
if(right-left+1 <=length){
length = right-left+1;
flag = true;
ansLeft = left;
ansRight = right;
}
if(left == right)break;
c = s[left];
if(m.find(c)!=m.end()){
m[c]++;
if(m[c]>0)counter++;
}
left++;
}
right++;
}
if(!flag)return ans;
else
for(int i =ansLeft;i<=ansRight;i++)ans+=s[i];
return ans;
}
};
main(){
Solution ob;
cout << (ob.minWindow("ABHDAXCVBAGTXATYCB", "ABC"));
}輸入
"ABHDAXCVBAGTXATYCB" "ABC"
輸出
CVBA
更新於：2020年5月26日
554 次瀏覽
廣告