【PAT甲級】1038 Recover the Smallest Number (30分)

解題過程的小記錄，如有錯誤歡迎指出。

難度：四星（用到的方法挺巧妙的）

小導航~

• 題目分析
• • • 注意點
• 我的解題過程
• • • 思路
    • bug
    • 代碼
• dalao的代碼
• • • 借鑒點

題目分析

給出一串可以以0開頭的數字，給出其組成的最小數字

注意點

1. 如果輸入的所有字元串都是0，那也要輸出0
2. 并不是簡單的字元串比較大小，還需要考慮排列組合的情況，如32和321，如采用字元串比較大小應該是32在前形成32321，而實際上32132更小

我的解題過程

思路

直接比較字元串需要考慮的東西很多，采用晴神的辦法就簡單很多，直接比較兩個字元串組合哪個在前形成的字元串更大，還需要注意輸出為0的情況，不然有一個測試點過不了

bug

靠自己的辦法會剩下幾個測試點過不了，然後采用晴神的同時考慮輸出為0的情況，想着直接把結果轉化為數字看看是不是全為0，采用了stoi的方法結果越界報錯了，因為stoi是轉化為int的，而結果的字元串長度已經超過了int，是以報錯，最後采用提出下标看是否全為0，不是的話去掉前面的0進行輸出，是的話輸出0

代碼

（注釋掉的是寫的過程中的一些試錯經曆orz，留個紀念吧）

#include<iostream>
#include<vector>
#include<algorithm>
#include<string>

using namespace std;

struct num {
	string original;
};


int comp2(num n1, num n2) {
	return n1.original + n2.original < n2.original + n1.original;
	/*
	if (n1.original.size() == n2.original.size()) {
		return n1.original < n2.original;
	}
	else {
		if (n1.original.size() < n2.original.size()) {
			while (n1.original.size() < n2.original.size()) {
				n1.original += n1.original;
			}
		}
		else {
			while (n1.original.size() > n2.original.size()) {
				n2.original += n2.original;
			}
		}
		return n1.original < n2.original;
	}
	*/
	
	/*
	bool flag = false;
	int i = 0;
	for (i; i < n1.original.size() && i < n2.original.size(); i++) {
		if (n1.original[i] != n2.original[i]) {
			flag = true;
			break;
		}
	}
	if (flag) return n1.original < n2.original;
	else {
		if (n1.original.size() > n2.original.size()) {
			string rest = n1.original.substr(i);
			return rest < n2.original;//有可能會錯這部分321321321111 321
		}
		else {
			string rest = n2.original.substr(i);
			return n1.original < rest;
		}
	}
	*/
}

int main()
{
	int n;
	cin >> n;
	vector<num> nums(n);
	for (int i = 0; i < n; i++) {
		cin >> nums[i].original;
	}
	sort(nums.begin(), nums.end(), comp2);
	string ans = "";
	for (int i = 0; i < nums.size() ; i++) {
		ans += nums[i].original;
	}
	//long long t = atoi(ans.c_str());超過int的範圍了
	bool isprit = false;
	int i = 0;
	for (i; i < ans.size(); i++) {
		if (ans[i] != '0') break;
	}
	if (i == ans.size()) {
		cout << 0;
		return 0;
	}
	ans = ans.substr(i);
	cout << ans;
    return 0;
}
           

dalao的代碼

全部代碼因版權原因不放出來，大家可以自行去柳神部落格購買或者參考晴神的上機筆記~

借鑒點

1. 最後要輸出的字元串存在各個單元内，可以先進行拼接，因為可能會出現連續好幾個都是0字元串的情況
2. 去除開頭0可以采用下面這個方法，去除後判斷size是否為0可以進行後續的輸出

while(ans.size() != 0&&ans[0] == '0'){
	ans.erase(ans.begin());
}