回文子串
题目描述
给定一个字符串,输出所有长度至少为2的回文子串。
回文子串即从左往右输出和从右往左输出结果是一样的字符串,比如:abba,cccdeedccc都是回文字符串。
输入
一个字符串,由字母或数字组成。长度500以内。
输出
输出所有的回文子串,每个子串一行。
子串长度小的优先输出,若长度相等,则出现位置靠左的优先输出。
样例输入
123321125775165561
样例输出
33 11 77 55 2332 2112 5775 6556 123321 165561
解题思路:
·看到题目的第一个反应是要写一个判断回文的函数
·题目的输出说,要从小的字符串输出,然后再从靠左的优先输出
·因为要形成回文字符串,所以最小长度为2,长度再逐渐增加,但是这样还不能满足题意
·再定义一个起点i,从0开始,如果与len相加等于字符串长度,则终止遍历
纯文字说,可能比较抽象,大家可以直接看代码
代码如下:
#include <iostream>
#include <vector>
#include <string>
using namespace std;
bool huiwen(const string& s, int l, int r) {//判断是否是回文
while (l <= r) {
if (s[l] != s[r]) return false;
l++;
r--;
}
return true;
}
void findAll(const string& s) {//寻找字符串中的所有子串
int n = s.length();
int len;
for (int len = 2; len <= n; len++) {//为终点,从2开始
for (int i = 0; i <= n - len; i++) {//为起点,终止条件为n-len防止越界
if (huiwen(s, i, i + len - 1)) {
cout << s.substr(i, len) << endl;//substr输出从i到len的字符串
}
}
}
}
int main() {
string str; cin >> str;
findAll(str);
return 0;
}
难点
·判断回文字符串的函数
·想不到如何使用两层循环进行遍历,并且定义他们的和终点
·substr函数的使用
总结
这算是一道有些上难度的题目了,第二个函数,如果大家有不明白的地方,可以代入准确数字进行演算,即可知道为什么这样写了,而且也很好推算出来。其实第二个函数可以继续优化,使用双指针法进行求解,可以提高运行速度
蛇形填充数组
题目描述:
用数字1,2,3,4,...,n*n这n2个数蛇形填充规模为n*n的方阵。
蛇形填充方法为:
对于每一条左下-右上的斜线,从左上到右下依次编号1,2,...,2n-1;按编号从小到大的顺序,将数字从小到大填入各条斜线,其中编号为奇数的从左下向右上填写,编号为偶数的从右上到左下填写。
比如n=4时,方阵填充为如下形式:
1 2 6 7 3 5 8 13 4 9 12 14 10 11 15 16
输入
输入一个不大于10的正整数n,表示方阵的行数。
输出
输出该方阵,相邻两个元素之间用单个空格间隔。
样例输入
4
样例输出
1 2 6 7 3 5 8 13 4 9 12 14 10 11 15 16
解题思路
·这道题我们需要将数组分为两部分进行输出,上半部分以及下半部分
·定义一个flag进行判断数组是斜向上遍历(flag = 0),还是斜向下遍历(flag = 1)
·我们要找到斜向上输出的循环不变量,以及斜向下输出的循环不变量,通过画图观察可以知道
如图是上半部分输出图,可以观察得出,斜向上的数组中,列的起初值不变,斜向下的数组中,行的初始值不变
·再看下半部分
依旧与上半部一样的情况,只不过初始值进行了改变,但方法并未改变
代码如下:
#include <iostream>
using namespace std;
int main() {
int i = 1, j = 1, x = 1, flag = 0, n; cin >> n;
int a[20][20];
for (int k = 1; k <= n; k++) {
if (flag == 0) {//斜向上遍历
i = k, j = 1;//斜向上初始位置,j不变
while (i != 0) {//防止越界
a[i][j] = x++;
i--, j++;//斜向上遍历
}
flag = 1;//修改为斜向下遍历
}
else {//斜向上
i = 1, j = k;//斜向下初始位置,i不变
while (j != 0) {//防止越界
a[i][j] = x++;
i++, j--;//斜向下遍历
}
flag = 0;//修改为斜向上遍历
}
}
for (int k = 2; k <= n; k++) {//与上半部分方法一致
if (flag == 0) {
i = n, j = k;
while (j != n + 1) {
a[i][j] = x++;
i--, j++;
}
flag = 1;
}
else {
i = k, j = n;
while (i != n + 1) {
a[i][j] = x++;
i++, j--;
}
flag = 0;
}
}
for (int i = 1; i <= n; i++) {//输出数组
for (int j = 1; j <= n; j++) {
cout << a[i][j] << " ";
}
cout << endl;
}
}
难点
·盲目寻找数字规律,没有找图像规律
·不知道怎么定义边界
·没有找到循环过程中的循环不变量
总结
输出蛇形数组,还是一道比较经典二位数组的题目,比较考察逻辑思维能力,可能在做这题之前没有什么思路,或则思路比较乱,但是看了题目之后,思路就会比较清晰了,这是一道经典的基础题,同学们一定要掌握
笨小猴
题目描述
笨小猴的词汇量很小,所以每次做英语选择题的时候都很头疼。但是他找到了一种方法,经试验证明,用这种方法去选择选项的时候选对的几率非常大!
这种方法的具体描述如下:假设maxn是单词中出现次数最多的字母的出现次数,minn是单词中出现次数最少的字母的出现次数,如果maxn-minn是一个质数,那么笨小猴就认为这是个Lucky Word,这样的单词很可能就是正确的答案。
输入
只有一行,是一个单词,其中只可能出现小写字母,并且长度小于100。
输出
共两行,第一行是一个字符串,假设输入的的单词是Lucky Word,那么输出“Lucky Word”,否则输出“No Answer”;
第二行是一个整数,如果输入单词是Lucky Word,输出maxn-minn的值,否则输出0。
样例输入
样例 #1: error 样例 #2: olympic
样例输出
样例 #1: Lucky Word 2 样例 #2: No Answer 0
提示
单词error中出现最多的字母r出现了3次,出现次数最少的字母出现了1次,3-1=2,2是质数。
单词olympic中出现最多的字母i出现了2次,出现次数最少的字母出现了1次,2-1=1,1不是质数。
解题思路
·有的同学可能会有思路,就是将每个字母存入数组中,再寻找最大值和最小值,这样确实可以书写出来,现在,我要教大家一种更简便的方法
·使用count()函数,可以直接将字符数组中的每个单词出现的次数直接统计出,就可以方便很多
·剩下的只需要写一个判断素数的函数了
代码如下
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
bool isprime(int n) {//判断素数,如果是使用C++的同学,一定要使用cmath这个头文件
if (n <= 1) return false;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) return false;
}
return true;
}
int MaxMin(string s) {//统计出现次数最多和最少的字母
int maxn = 0, minn = 101;
for (int i = 0; i < s.size(); i++) {
int cnt = count(s.begin(), s.end(), s[i]);
if (cnt > maxn)
maxn = cnt;
if (cnt < minn)
minn = cnt;
}
return maxn - minn;
}
int main() {
string s; cin >> s;
int ans = MaxMin(s);
if (isprime(ans)) {
cout << "Lucky Word" << endl;
cout << ans;
}
else {
cout << "No Answer" << endl;
cout << 0;
}
return 0;
}
易错点
·不会书写判断素数的函数
·对count函数使用的不熟练
总结
如果知道方法,那么这道题就是一个简单题,但是如果不知道方法,就会复杂一些,所有要多做题,多见识一些方法,这样才能更快的进行求解
单词排序
题目描述
输入一行单词序列,相邻单词之间由1个或多个空格间隔,请按照字典序输出这些单词,要求重复的单词只输出一次。(区分大小写)
输入
一行单词序列,最少1个单词,最多100个单词,每个单词长度不超过50,单词之间用至少1个空格间隔。数据不含除字母、空格外的其他字符。
输出
按字典序输出这些单词,重复的单词只输出一次。
样例输入
She wants to go to Peking University to study Chinese
样例输出
Chinese Peking She University go study to wants
解题思路
·很多同学可能第一思路就是,创建字符数组,把每个数组存入,再求每个单词的头字母的ascii码值,以此进行排序,但是题目还有说要只输出一次,说实话,这么多条件在这,直接毁灭吧,下一题算了
·其实可以使用函数以及set进行求解,可以实现单词的比较,排序以及去重
·使用sstream对单词进行分割,再存入set中,因为set自动实现排序以及去重,再输出即可
代码如下
#include <iostream>
#include <set>
#include <sstream>
#include <string>
using namespace std;
int main() {
string line; getline(cin, line);
set<string> s;//定义集合
string word;
stringstream ss(line);//将字符串分割成单词,存在ss中
while (ss >> word) {//读取单词
s.insert(word);//将单个单词存入集合中
}
for (auto w : s) {
cout << w << endl;//输出集合中的元素
}
}
难点
·不知道使用sstream
·不知道set的使用,部分同学只知道set可以去重,而不知道可以排序
总结
本题也没有什么代码或者逻辑的难度,只是单纯的提供了一种解题方法,以及工具的使用方式