d275 - 11586 - Train Tracks

🔗 前往 ZeroJudge 原題

題目描述

題目給定一串由 'M' (male) 和 'F' (female) 組成的軌道片段字串。目標是判斷這些片段是否能組成一個環形軌道。環形軌道的要求是 male 和 female 端點必須配對，且 male 和 female 的數量必須相等，並且數量大於 1。

解題思路

這個問題可以簡化為統計輸入字串中 'M' 和 'F' 的數量。如果 'M' 和 'F' 的數量相等，且數量都大於 1，則可以組成一個環。如果數量不相等，或者數量小於等於 1，則無法組成環。程式碼直接遍歷字串，統計 'M' 和 'F' 的數量，然後根據條件判斷是否可以組成環。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入字串的長度。程式碼只需要遍歷一次字串來統計 'M' 和 'F' 的數量。
• 空間複雜度: O(1)。程式碼只使用了幾個整數變數來存儲 'M' 和 'F' 的數量，空間使用是固定的，不隨輸入大小變化。

程式碼

#include <iostream>
#include <string>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	string b;
	getline(cin,b);
	while(getline(cin,b)){
		int F=0,M=0;
		for(int i=0,bb=b.length();i<bb;i++){
			if(b[i]=='F')
				F++;
			else if(b[i]=='M')
				M++;
		}
		(F==M&&F>1)?cout << "LOOP\n":cout << "NO LOOP\n";
	}
}