编程生活day6--回文子串、蛇形填充数组、笨小猴、单词排序

回文子串

题目描述

给定一个字符串，输出所有长度至少为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可以去重，而不知道可以排序

总结

本题也没有什么代码或者逻辑的难度，只是单纯的提供了一种解题方法，以及工具的使用方式