题目

题目描述 A string s is LUCKY if and only if the number of different characters in s is a fibonacci number. Given a string consisting of only lower case letters , output all its lucky non-empty substrings in lexicographical order. Same substrings should be printed once. 输入描述: a string consisting no more than 100 lower case letters.

输出描述: output the lucky substrings in lexicographical order.one per line. Same substrings should be printed once.

输入例子: aabcd

输出例子: a aa aab aabc ab abc b bc bcd c cd d

答案

#include <iostream> #include <string> #include <vector> #include <set> #include <algorithm> using namespace std; vector<int> fibonacci({ 1, 2, 3, 5, 8, 13, 21 }); //计算一个字符串出现的不同字符的个数 //使用了STL中的count函数 bool isLucky(string &s){ int word[26] = { 0 }; int countNum = 0; for (int i = 0; i<s.size(); i++){ if (word[s[i] - 'a'] == 0){ countNum++; word[s[i] - 'a'] = 1; } } return count(fibonacci.begin(), fibonacci.end(), countNum); } int main(){ set<string> resultStr; set<string>::iterator iter; string str; cin >> str; for (int i = 0; i < str.length(); i++){ for (int j = i+1; j<=str.length(); j++){ //string subStr(str, i, j-i); 也可以这样实现 string subStr(&str[i], &str[j]); if (isLucky(subStr)) resultStr.insert(subStr); } } for (iter = resultStr.begin(); iter != resultStr.end(); iter++) cout << *iter << endl; getchar(); getchar(); return 0; }

总结

在这道题里面需要注意的点： 1. 计算一个字符串中出现的不同字符的个数 2. STL中count（）函数的用法 3. String 函数的不同构造函数的区别 4. 为什么getchar（）在这里用了两次