d570 - 神龍見首不見尾

🔗 前往 ZeroJudge 原題

題目描述

題目要求讀取一個正整數，並逐次移除尾數數字，將每次移除尾數後的數字輸出到一行。輸出總共應有 k 行，其中 k 是原始數字的位數。

解題思路

這題的解題思路很直接，就是將輸入的字串逐次縮短，每次縮短一個字元，並輸出縮短後的字串。使用迴圈迭代字串，並控制輸出，直到字串長度為 0。 程式碼中 al 變數追蹤剩餘字串的長度，i 變數迭代字串的每個字元。當 al 等於 i-1 時，表示已經輸出了一行，需要重置 al 並換行。

複雜度分析

• 時間複雜度: O(n^2)，其中 n 是輸入數字的位數。因為外層迴圈迭代 n 次，內層迴圈在每次迭代中可能需要迭代 n 次。
• 空間複雜度: O(1)，因為程式碼只使用了常數額外的空間。

程式碼

#include <iostream>
using namespace std;
int main(){
	cin.tie(0); ios::sync_with_stdio(false);
	string a;
	while(cin >> a){
		int al=a.length()-1;
		for(int i=0;al>=0;++i){
			if(al==i-1){
				--al;
				cout << "\n";
				i=0;
			}
			if(al==-1)
				break;
			cout << a[i] ;
		}
	}
}