入门篇-字符串处理--《算法笔记》同步笔记总结与补充

2020-03-02

专题要点：

本专题极其考验代码能力，逻辑能力与分析能力。我个人认为这一专题是区分新手和入门的分界线。许多新手出现的问题是：初看题目比较简单，易懂，但在字符串的输入输出就卡住了（字符串与字符数组的输入输出问题）；许多入门的“新手”也有一些问题是：初看题目比较简单，但越分析越复杂，越分析越毫无头绪，导致最后心态炸裂。文章最后我在补充重新总结两道比较让我觉得费脑子的题目。
因此我作为新手，通过自己在这一章联系中出现的问题，进行整理总结，希望可以和共勉！

几点注意：

做题过程中完全了解掌握字符串与字符数组还有单个字符的差异和输入输出方法，区别不同字符输入函数，掌握algorithm函数，字符串或字符数组的函数和一些技巧，如打表和预处理；除此之外还有做题思路上也是值得注意的

字符串与字符数组的基本问题：

在做这一专题的题目时，我明显感觉到自己对字符串与字符数组的了解非常浅！因此这个基本问题的内容会相对较多（只是对我个人而言，这些小细节刚刚弄明白）
1、%c与%s，前者是将字符一个一个输入，遇见空格和回车停止；后者是接收字符串，从第一个非空白字符串开始到下一个空白字符前的所有字符都是输入，同样都是遇见空格和回车停止
引申出来二维字符数组的输入问题，两种方法：

char s[100][10];
for(int i = 0; i < 100; i++)
{
	scanf("%s", s[i]);
}
//或者！
for(int i = 0; i < 100; i++)
{
	for(int j = 0; j < 9; j++)
	{
		scanf("%c ", &s[i][j]);//也可以带‘&’
	}
}

输出与输入同理
2、scanf(&)中的“&”的问题，只有字符数组不加“&”，其他都要加！其他类型的数组更得加了！因为字符串只要告诉首地址即可往后依次读取
3、灵活的scanf()，两个变量之间可以加很多符号来满足不同要求的题目输入格式，甚至加“\n”，scanf(“%s\n%s”, str1, str2)也可

字符串与字符数组的进阶问题：

1、区别scanf(),gets(),fgets(str,max,file),cin,getline(cin, str), cin.getline(str[], max),getchar()
见博客区别字符输入函数scanf(),gets(),fgets(str,max,file),cin,getline(cin, str), cin.getline(str, max),getchar()
2、由于string是STL库的容器，在debug不是特别方便，一般建议使用char数组，涉及大量字符串比较和拼接时建议使用string

做题思路：

1、做题前要理清思路，切忌边做边想边修改！！首先考虑题目的细节，边界，特值的处理，不能想当然做题
2、要做预处理！把题目要求的输入格式转化为自己擅长处理的数据格式，千万不要嫌麻烦，而且一定要做到位，否则找错误会花费相当长的时间
3.千万不要将自己思路和代码思想局限于stereotype（刻板印象），要灵活！！比如，习惯性的使用“行”作二重循环的外循环，而PAT.A1077却使用“列”作外循环；习惯性从数字的低位开始遍历或取某一位的数字，而PAT.A1082却是从高位进行。

数据处理：

1、遇到字符串与数组下标之间存在一定的关系时，可考虑打表（尽量少用switch，前章已经提到过switch易出错）。此关系如，星期对应的英文表达、数字对应字符串（英文或拼音表达阿拉伯数字）、十六进制等等。
2、对于有明确的分隔符的字符串，可以采用二维数组存储，如读入若干串字符串或英文单词并以空格或回车分割，用二维字符串数组比较合适（每个单词占一行）
3、关于控制行末空格与行末换行的控制，两种方法
4、使用sprintf()与sscanf()对字符串和int进行转换
5、输出细节，看清楚要求。其中PAT.A1035输出的“There is”与“There are”，还有名词的单复数，很细节。
6、适当考虑提高代码效率，提前对数据做预处理，做取模运算（防止大数运算溢出）

PAT关于字符串处理的较复杂题目

关于这一专题的上机训练中，我个人对A1065.A+B and C 和 B1010.一元多项式求导有优于书本的解题思路

B1024/A1073科学计数法

本人做了两遍但都花费了很长的时间，这道题我认为逻辑比较复杂，细节处理的地方很多（指数与底数的符号问题，小数点问题）。当然本题的关键就是指数大小与小数点的位数比较问题

思路

根据指数符号分为3类，0，正，负
0：原样输出
正：指数大于等于小数点后的位数时，先写数再补零；小于时先写数，点小数点，再写数
负：先补零，再写数
题目不再赘述

#include <bits/stdc++.h>
using namespace std;
char str[10005];
char nums[10005], ans[10005]; 
char exps[10];
int main(int argc, char *argv[]) {
	cin >> str;
	int len = strlen(str);
	int start = 0;
	if(str[0] == '-')
	{
		printf("%c", str[0]);
		start++;
	}
	//拆分 
	bool flag = false;//false表示底数
	int lenNums = 0, lenExps = 0; 
	for(int i = start; i < len; i++)
	{
		if(str[i] == 'E')
		{
			flag = true;
		}
		else if(flag == false)//底数阶段 
		{
			if(str[i] != '+')
				nums[lenNums++] = str[i];//含小数点 
		}
		else if(flag == true)//指数阶段，带正负号 
		{
			exps[lenExps++] = str[i];
		}
	}
	int index = 0;//记录ans数组
	int ex = 0;//指数的值
	int actCnt = lenNums - 2;//实际小数点后的位数 
	sscanf(exps, "%d", &ex); 
	if(ex == 0)//指数是0次幂 
	{
		for(int i = 0; i < lenNums; i++)
		{
			ans[index++] = nums[i];//若为底数为正数，nums[0]是'+'
		}
	}
	else if(exps[0] == '+')//指数为正 
	{
		//对底数操作 
		ans[index++] = nums[0];//处理小数点前的一位 
		if(ex >= actCnt)//指数大于等于小数点后的位数 
		{
			for(int i = 2; i < actCnt + 2; i++)//i从小数点后的一位开始 
			{
				ans[index++] = nums[i]; 
			}
			for(int i = 0; i < ex - actCnt; i++)//多出来的补零 
			{
				ans[index++] = '0';
			}
		}
		else//指数小于后面的位数，要点小数点 
		{
			for(int i = 2; i < ex + 2; i++)//先写数 
			{
				ans[index++] = nums[i];
			} 
			ans[index++] = '.';
			for(int i = ex + 2; i < lenNums; i++)
			{
				ans[index++] = nums[i];
			}
		}
	} 
	
	else if(exps[0] == '-')//指数为负 
	{
		ex = -ex;//取相反数 
		ans[index++] = '0';
		ans[index++] = '.';
		if(ex > 1)
		{
			for(int j = 0; j < ex - 1; j++)
			{
				ans[index++] = '0';
			}
		}
		for(int i = 0; i < lenNums; i++)
		{
			if(nums[i] != '+' && nums[i] != '.')
			{
				ans[index++] = nums[i];
			}	
		}
	}
	//输出
	if(str[0] == '0' || str[1] == '0')
	{
		printf("0");
	} 
	else
	{
		for(int i = 0; i < index; i++)
		{
			printf("%c", ans[i]);
		}
	}	
	return 0;
}

A1082

这道题目就是，刚看题目觉得很容易，但越分析越复杂，还涉及大小单位

思路

按节处理，《算法笔记》的思路的一个巧妙之处，与常规不同，此题是从高位向低位遍历，即第一节是最高位的
通过left与right标记每一节的高位与低位

提醒

要注意right的作用！标记从高位节到低位节的每一节末位，即个位
末尾index推导过程，right是每一节的个位，len-1是字符串的个位，二者相减定能被4整除。因为只有“万”“亿”需要用大单位，可推导出最后需要加上常数项2

#include <bits/stdc++.h>
using namespace std;
char num[15][15] = {"ling", "yi", "er", "san", "si", "wu", "liu", "qi", "ba", "jiu"};
char unit[10][10] = {"ge", "Shi", "Bai", "Qian", "Wan", "Yi"};
int main(int argc, char *argv[]) {
	char N[15];
	scanf("%s", N);
	int len = strlen(N);
	int left = 0, right = len - 1;
	if(len == 1 && N[0] == '0')//就一位且还是0 
	{
		printf("ling");
	}
	else
	{
		if(N[0] == '-')
		{
			printf("Fu"); 
			left++;
		}
		while(left + 4 <= right)//从最高节开始 
		{
			right -= 4;//保证了left，right在同一节，且left在高位，right在该节的最低位 
		}
		while(left < len)
		{
			bool flag = false;//标记是否有积累的0 
			bool isPrint = false;//是否已经输出过其中的位 
			while(left <= right)//从该节的高位left一直走到低位right 
			{
				if(N[left] == '0')//若当前位为0 
				{
					flag = true;//有积累的0 
				} 
				else//当前位置不为0，说明前面的一串0都已经遍历过了 
				{
					if(flag == true)//前面已经有积累的0了
					{
						printf(" ling");//发音一次0即可 
						flag = false;//flag重置 
					} 
					if(left > 0)//表示不是首位 ，即不是第一个输出的元素，则在前面先输出空格
					{
						printf(" ");
					}	
					int indexNum = N[left] - '0';
					printf("%s", num[indexNum]);
					isPrint = true;//该节有过输出
					//处理每一节中的十，百， 千的小单位问题
					if(left != right)//该位不是个位
					{
						int indexUint = right - left;
						printf(" %s", unit[indexUint]);//已设置好空格 
					} 	 
				}
				left++; 
			}
			//处理亿，万大单位问题
			//此节有过输出（避免100000000的情况），且不是个位节 
			if(isPrint == true && right != len - 1)
			{
				int indexUint = (len - 1 - right) / 4 + 3;
				//这里也需要推导斟酌
				printf(" %s", unit[indexUint]);
			}
			right += 4;
		} 
	}
	return 0;
}