第一版(不完整)
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
int main() {
int n, k;
vector<string> strs;
string s, x;
getline(cin , s);
istringstream iss(s);
iss >> n;
for (int i = 0; i < n; i++) {
iss >> strs[i];
}
iss >> x;
iss >> k;
// 得到x与x的全部兄弟单词,如果兄弟单词排好序就更好
string word = x;
sort(word.begin(), word.end());
vector<string> words;
// ?
// 拿x的兄弟单词表去依次对比strs中的单词,然后选出合适的单词并统计数量
vector<string> results;
int count;
for(string s1 : words){
for(string s2 : strs){
if(s1 == s2 && s2 != x){
results.push_back(s2);
count++;
}
}
}
cout << count;
if (count > 0) {
cout << results[k-1];
}
}
// 64 位输出请用 printf("%lld")
- 笔者解法:
- 基本思路:先用输入字符流对象切割字符串得到所有输入,再通过某种方法得到并记录x的全排列,最后逐一对比并用results记录符合条件的兄弟单词。
- 问题关键:不知道如何获得x的全排列,猜测可以用vector<string>记录。
- 智能反馈:
- 内存管理对于长度为10的字符串,全排列有10! = 3,628,800种可能,这会导致性能问题和内存消耗过大。
- 如果x中有重复字符,全排列会产生大量重复结果,需要去重。
- vector<string> strs没有初始化大小,直接使用strs[i]会导致越界错误。
- 更优解法:
- 两个字符串是兄弟单词当且仅当——1)不一样;2)长度相等;3)排序后相同。
- 完全可以定义一个判定字符串是不是兄弟单词的函数,就像判空函数那样。
第二版(段错误)
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
bool isbrother(string &s1, string &s2){
if(s1 == s2 || s1.length() != s2.length()){
return false;
}
string a = s1;
string b = s2;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) {
return true;
}else {
return false;
}
}
int main() {
int n, k;
vector<string> strs;
string x;
string input;
getline(cin, input);
istringstream iss(input);
iss >> n;
for (int i = 0; i < n; i++) {
iss >> strs[i];
}
iss >> x;
iss >> k;
vector<string> words;
for(string s : strs){
if (isbrother(s, x)) {
words.push_back(s);
}
}
sort(words.begin(), words.end());
cout << words.size() << endl;
if(words.size() > 0){
cout << words[k-1];
}
}
// 64 位输出请用 printf("%lld")
- 段错误:疑似数组越界或堆栈溢出(如递归调用太多)。
第三版(0/11)
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
bool isbrother(string &s1, string &s2){
if(s1 == s2 || s1.length() != s2.length()){
return false;
}
string a = s1;
string b = s2;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) {
return true;
}else {
return false;
}
}
int main() {
string input;
getline(cin, input);
istringstream iss(input);
int n, k;
string x;
iss >> n;
vector<string> strs(n);
for (int i = 0; i < n; i++) {
iss >> strs[i];
}
iss >> x;
iss >> k;
vector<string> words(n);
for(string s : strs){
if (isbrother(s, x)) {
words.push_back(s);
}
}
sort(words.begin(), words.end());
cout << words.size() << endl;
if(words.size() > 0){
cout << words[k-1];
}
}
// 64 位输出请用 printf("%lld")
- 声明了每个数组的容量后,段错误消失了,但是一个用例也没通过。
第三版(AC)
#include <algorithm>
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
bool isbrother(string &s1, string &s2){
if(s1 == s2 || s1.length() != s2.length()){
return false;
}
string a = s1;
string b = s2;
sort(a.begin(), a.end());
sort(b.begin(), b.end());
if (a == b) {
return true;
}else {
return false;
}
}
int main() {
string input;
getline(cin, input);
istringstream iss(input);
int n, k;
string x;
iss >> n;
vector<string> strs(n);
for (int i = 0; i < n; i++) {
iss >> strs[i];
}
iss >> x;
iss >> k;
vector<string> brothers;
for(string s : strs){
if (isbrother(s, x)) {
brothers.push_back(s);
}
}
sort(brothers.begin(), brothers.end());
cout << brothers.size() << endl;
if(brothers.size() > 0 && k <= brothers.size()){
cout << brothers[k-1];
}
return 0;
}
// 64 位输出请用 printf("%lld")
- 首先是把words变成更合适的brothers,更容易理解。
- 其次是增加了对k的限制,因为k虽然在1~n之间,但完全可能比兄弟单词的数量多。
- 最后修改了brothers(n),改为空串brother,否则用push_back()会导致在
brother[n]
处添加第一个,导致brothers的长度和序号出问题。 - 注意数组为啥会产生越界错误——
brothers[k-1]
是不越界的,因为之前的if语句里对k做出了限制。strs[i]
是不越界的,因为之前声明了strs(n)
。 - 假如按第二版的没声明,就会导致你用到strs[i]的时候它其实是个空串。