g005 - 倒置文章 (Inversion)

🔗 前往 ZeroJudge 原題

題目描述

題目要求將輸入字串根據 '+' 和 '-' 符號進行分割，並對 '+' 符號後面的字串片段進行反轉，然後將所有片段連接起來形成最終的輸出字串。

解題思路

這題的核心思想是遍歷輸入字串，遇到 '+' 或 '-' 符號時，將當前累積的字串片段進行反轉（如果遇到 '+' 符號），或者直接添加到結果字串（如果遇到 '-' 符號）。然後，根據 '+' 或 '-' 符號更新一個布林變數 t，用於指示後續字符應該添加到結果字串還是累積到當前片段。最後，處理字串末尾可能存在的未處理片段。

複雜度分析

• 時間複雜度: O(n)，其中 n 是輸入字串的長度。因為需要遍歷字串一次，並且反轉操作在最壞情況下也需要 O(n) 的時間，但反轉操作只會在遇到 '+' 符號時執行，因此整體時間複雜度仍然是 O(n)。
• 空間複雜度: O(n)，其中 n 是輸入字串的長度。因為需要使用額外的字串 ans 和 buf 來存儲結果和臨時片段，在最壞情況下，它們的大小可能與輸入字串相同。

程式碼

#include <iostream>
#include <algorithm>
using namespace std;
bool t;
string a,ans,buf;
int main(){
	cin >> a;
	for(int i=0;i<a.length();++i){
		if(a[i]=='+'||a[i]=='-'){
			reverse(buf.begin(),buf.end());
			ans+=buf;
			buf.clear();
			if(a[i]=='+')
				t=0;
			else
				t=1;
		}
		else{
			if(t==1)
				buf+=a[i];
			else
				ans+=a[i];
		}
	}
	reverse(buf.begin(),buf.end());
	ans+=buf;
	cout << ans;
}