编程生活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可以去重,而不知道可以排序

总结

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

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/515131.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

求m和n的最大公约数(C语言)

一、运行结果&#xff1b; 二、源代码&#xff1b; # define _CRT_SECURE_NO_WARNINGS # include <stdio.h>int main() {//初始化变量值&#xff1b;int remainder 1;int m 0;int n 0;int middle 0;//提示用户&#xff1b;printf("请输入整数m和n的值&#xff…

处理SAP报错:消息GLT2076 没有项目种类分配到科目 1481010102/1000

财务新建了个科目入账时报错&#xff1a;没有项目种类分配到科目。 查了下原因。原来是我们公司实施时启用了凭证分割功能。其中有个配置是这样的&#xff1a;给总账科目分类&#xff1a;IMG-财务会计&#xff08;新&#xff09;-总账会计核算-业务交易-凭证分解-为文档拆分给总…

分布式架构中一些常用算法的理解

对分布式算法 - 一致性Hash算法的理解 一致性哈希算法是一种分布式算法&#xff0c;用于解决数据分布和负载均衡问题。它通过将数据和节点映射到一个哈希环上&#xff0c;实现了数据在节点之间的均匀分布和最小化数据迁移。 一致性哈希算法的核心思想是将数据和节点都映射到哈…

1.数据结构和算法

文章目录 数据结构逻辑结构集合结构线性结构树形结构图形结构 物理结构顺序存储结构链式存储结构 算法基本特性目标 总结数据结构总结算法总结 数据结构 「数据结构」指的是&#xff1a;数据的组织结构&#xff0c;用来组织、存储数据。 逻辑结构 逻辑结构&#xff08;Logic…

Dubbo入门项目搭建【Dubbo3.2.9、Nacos2.3.0、SpringBoot 2.7.17、Dubbo-Admin 0.6.0】

B站学习视频 基于Dubbo3.2.9、Nacos2.3.0、SpringBoot 2.7.17、Dubbo-Admin 0.6.0、Jdk1.8 搭建的Dubbo学习Demo 一、前置安装 1-1、Nacos 安装 我本地是通过docker-compose来安装nacos的&#xff0c;如果需要其它方式安装可以去百度找下教程&#xff0c;版本是2.3.0的 docker…

C语言要点细细梳理(下)

10. 运算符补充 10.1 位运算 位运算符&#xff1a;<< >> & | ~ ^ << >> &#xff1a;按位左移右移&#xff0c;移出去的数直接丢掉&#xff0c;符号不动 &&#xff1a;按位与 |&#xff1a; 按位或 ~&#xff1a;按位非 ^&#xff1a;按…

iOS使用CoreML运用小型深度神经网络架构对图像进行解析

查找一个图片选择器 我用的是ImagePicker 项目有点老了&#xff0c;需要做一些改造&#xff0c;下面是新的仓库 platform :ios, 16.0use_frameworks!target learnings dosource https://github.com/CocoaPods/Specs.gitpod ImagePicker, :git > https://github.com/KevinS…

基于VUE实现的餐厅经营游戏项目源码

WebMOOC 餐厅游戏 项目介绍 实现了一个类游戏的餐厅经营模拟&#xff0c;涉及的前端知识有移动端 HTML 页面布局及样式实现。实现了厨师、顾客等角色的关键操作&#xff0c;完成从顾客等位、点菜、烹饪、用餐、支付的一系列状态变更的数据、信息、交互、展现的变化及处理。 …

巨控560:走向国际,我们的设备如何拥抱远程控制技术?

走向国际&#xff0c;我们的设备如何拥抱远程控制技术&#xff1f; 描述&#xff1a;随着国内设备走向国际市场&#xff0c;客户需求的多样性和不确定性大大增加。本文将深入探讨在这一背景下&#xff0c;是否有必要为我们的设备加装远程PLC控制模块&#xff0c;以及如何应对频…

分布式系统架构中的相关概念

1.1、衡量网站的性能指标 响应时间&#xff1a;指执行一个请求从开始到最后收到响应数据所花费的总体时间。并发数&#xff1a;指系统同时能处理的请求数量。 并发连接数&#xff1a;指的是客户端向服务器发起请求&#xff0c;并建立了TCP连接。每秒钟服务器连接的总TCP数量请…

基于SSM+Jsp+Mysql的图书仓储管理系统

开发语言&#xff1a;Java框架&#xff1a;ssm技术&#xff1a;JSPJDK版本&#xff1a;JDK1.8服务器&#xff1a;tomcat7数据库&#xff1a;mysql 5.7&#xff08;一定要5.7版本&#xff09;数据库工具&#xff1a;Navicat11开发软件&#xff1a;eclipse/myeclipse/ideaMaven包…

ospf的路由计算

LSA是链路状态信息&#xff08;描述接口信息&#xff09;&#xff0c;路由器将接口信息发给其他路由器&#xff0c;LSA有6个分类&#xff0c;1&#xff0c;2类描述区域内信息&#xff0c;3类是区域间的&#xff0c;5类是外部路由&#xff0c;4类是对5类的补充&#xff0c;7类是…

企微知识库优缺点解析:如何让其效益最大化

企业搭建企微知识库&#xff0c;作为企业内部知识的集中存储和共享平台&#xff0c;为企业带来了很多便利。但是&#xff0c;任何事物都有其两面性&#xff0c;企微知识库也不例外。今天我们就来详细探讨搭建企微知识库的优点和缺点&#xff0c;如何在使用企微知识库时使其发挥…

【群晖】NASTOOL-自动化处理影音视频工具

【群晖】NASTOOL-自动化处理影音视频 本文主要从获取、部署、使用、配置等方面进行手把手教学如何使用nastool工具进行影音视频自动化处理。从此靠别繁琐的网上各个网址找资源-下载-复制-改名-刮削等操作。 准备 DSM 7.1 &#xff08;我使用的是群晖 7.1 系统&#xff0c;不管…

【一站式学会Kotlin】第一节 kotlin 介绍

作者介绍&#xff1a; 百度资深Android工程师T6&#xff0c;在百度任职7年半。 目前&#xff1a;成立赵小灰代码工作室&#xff0c;欢迎大家找我开发Android、微信小程序、鸿蒙项目。 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默。给大家…

并发编程之线程池的应用以及一些小细节的详细解析

线程池在实际中的使用 实际开发中&#xff0c;最常用主要还是利用ThreadPoolExecutor自定义线程池&#xff0c;可以给出一些关键的参数来自定义。 在下面的代码中可以看到&#xff0c;该线程池的最大并行线程数是5&#xff0c;线程等候区&#xff08;阻塞队列)是3&#xff0c;即…

【Java集合进阶】list常见的方法和五种遍历方式数据结构

&#x1f36c; 博主介绍&#x1f468;‍&#x1f393; 博主介绍&#xff1a;大家好&#xff0c;我是 hacker-routing &#xff0c;很高兴认识大家~ ✨主攻领域&#xff1a;【渗透领域】【应急响应】 【python】 【VulnHub靶场复现】【面试分析】 &#x1f389;点赞➕评论➕收藏…

03-04java基础之数据类型举例

1、需要特殊注意的数据类型举例 1&#xff09;定义float类型&#xff0c;赋值时需要再小数后面带f float num11.2f; System.out.println(num1);2&#xff09;定义double类型&#xff0c;赋值时直接输入小数就可以 3&#xff09;另外需要注意&#xff0c;float类型的精度问题…

修改element-ui table组件展开/收起图标、支持点击行展开/收起、隐藏不可展开行得图标

Element中table默认支持的&#xff0c;展开和收起功能&#xff0c;如下&#xff1a; 针对表格的展开收起&#xff0c;本文改造的主要有3点&#xff1a; 1、修改展开/收起的图标&#xff1b; 2、对于不支持展开/收起的行&#xff0c;隐藏图标&#xff1b; 3、点击行&#xff0…

AcWing---转圈游戏---快速幂

太久没写快速幂了... 这是一道数学题orz&#xff0c;能看出来的话答案就是 &#xff0c;但是很大&#xff0c;同时还要mod n&#xff0c;直接用快速幂即可。 快速幂模版&#xff1a; long long int power(long long int a,long long int b,long long int mod){long long int r…