d272 - 11583 - Alien DNA
題目描述
題目要求計算將給定的 DNA 序列切割成最少刀數，使得每個切割後的 DNA 序列至少有一個共同的字母集合。
解題思路
這題可以使用貪心演算法來解決。我們遍歷每個 DNA 序列，並維護一個當前已存在的字母集合。如果當前序列與已存在的字母集合沒有共同的字母，則需要進行一次切割，並將當前序列的字母集合加入到已存在的字母集合中。
具體來說，我們使用一個大小為 26 的陣列 la 來表示已存在的字母集合，la[i] 為 1 表示字母 i 存在於已存在的集合中，為 0 表示不存在。對於每個輸入的 DNA 序列 s，我們使用一個大小為 26 的陣列 k 來表示當前序列的字母集合。然後，我們檢查 la 和 k 是否有共同的元素。如果沒有共同的元素，則進行一次切割，並將 k 中的所有元素加入到 la 中。
最後，切割次數等於已進行的切割次數減 1。
複雜度分析
- 時間複雜度: O(N * M)，其中 N 是 DNA 序列的數量，M 是每個 DNA 序列的長度。
- 空間複雜度: O(1)，因為我們只使用了固定大小的陣列來存儲字母集合。
程式碼
#include <iostream>
using namespace std;
int main(){
cin.tie(0); ios::sync_with_stdio(false);
int t,n;
string s;
cin >> t;
while(t--){
cin >> n;
int ans=0,la[26]={0},tmp=0;
for(int i=0;i<n;++i){
cin >> s;
int k[26]={0};
for(int j=0;j<s.length();++j){
k[s[j]-'a']=1;
}
for(int i=0;i<26;++i){
if(la[i]){
if(k[i]==0){
la[i]=0;
--tmp;
}
}
}
if(tmp==0){
++ans;
for(int j=0;j<s.length();++j){
la[s[j]-'a']=1;
++tmp;
}
}
}
cout << ans-1 << "\n";
}
}