「PAT乙级真题解析」Basic Level 1039 到底买不买 (问题分析+完整步骤+伪代码描述+提交通过代码)
题目给定两个字符串, 要求计算出两个信息: 1. 第二个字符串的字符的种类以及出现的次数是否是被第一串覆盖。 2. 覆盖时: 两串字符串的长度差值 没有覆盖时: 没有覆盖的字符的次数差值总和 所以这道题依旧是一道统计题。我们需要统计两个字符串中出现的字符种类的次数, 然后对统计数据进行比较, 并输出所求结果.
Table of Contents
乙级的题目训练主要用来熟悉编程语言的语法和形成良好的编码习惯和编码规范。从小白开始逐步掌握用编程解决问题。
问题分析
题目给定两个字符串, 要求计算出两个信息: 1. 第二个字符串的字符的种类以及出现的次数是否是被第一串覆盖。 2. 覆盖时: 两串字符串的长度差值 没有覆盖时: 没有覆盖的字符的次数差值总和 所以这道题依旧是一道统计题。我们需要统计两个字符串中出现的字符种类的次数, 然后对统计数据进行比较, 并输出所求结果.
统计数据的存储
在前面的题目中多次提到了, 不再赘述思路。 这里我们用C语言数组存储统计数据, 用字符的ascii编码值作为数组索引来存储字符出现的次数.
统计数据的比较
我们要检查第二个字符串的统计结果是否被第一个字符串的统计结果所覆盖。 "覆盖"具体表现为: 对于第二个字符串中出现的字符, 在第一个字符串中出现的次数大于等于在第二个字符串中的出现的次数 (没有出现时, 认为出现次数为0)
完整描述步骤
- 获取两个字符串
- 初始化统计数据计数器: 将所有可能出现的字符的出现次数置为0
- 统计两个字符串的字符出现次数, 即对于字符串中的每一个字符:
- 在计数器中将字符对应的计数值+1
- 初始化差值计数器: 多出的珠子数目计数器, 少了的珠子数目计数器
- 设置标志位: 是否被覆盖的标志位, 初始值为True
- 对于第二个字符串的计数器中非零的每个字符:
- 检查其计数值是否小于等于第一个字符串计数器中相同字符的计数值
- 如果小于, 则: 多出的珠子数目计数器 加上 差值
- 如果大于, 则: 覆盖标志位置为False 少了的珠子数目计数器 加上 差值
- 根据覆盖标志位输出对应信息:
- 覆盖标志位为True: Yes 多出的珠子数目计数器的计数值
- 覆盖标志位为False: No 少了的珠子数目计数器的计数值
伪代码描述
-
get input of string: sale, want
-
init counter and flag: sale_counter[256] = {0} want_counter[256] = {0} could_buy_flag = True more_amount = 0 less_amount = 0
-
for each char in sale: sale_counter[code of char] += 1
-
for each char in want: want_counter[code of char] += 1
-
for each char in want_counter: if count_value_in_want <= count_value_in_sale: more_amount += count_value_in_sale - count_value_in_want else: less_amount += count_value_in_want - count_value_in_sale could_buy_flag = False
-
if could_buy_flag == true: print("Yes" + more_amount) else: print("No" + less_amount)
完整提交代码
/*
# 问题分析
题目给定两个字符串, 要求计算出两个信息:
1. 第二个字符串的字符的种类以及出现的次数是否是被第一串覆盖。
2. 覆盖时: 两串字符串的长度差值
没有覆盖时: 没有覆盖的字符的次数差值总和
所以这道题依旧是一道统计题。我们需要统计两个字符串中出现的字符种类的次数,
然后对统计数据进行比较, 并输出所求结果.
# 统计数据的存储
在前面的题目中多次提到了, 不再赘述思路。
这里我们用C语言数组存储统计数据, 用字符的ascii编码值作为数组索引来存储字符出现的次数.
# 统计数据的比较
我们要检查第二个字符串的统计结果是否被第一个字符串的统计结果所覆盖。
"覆盖"具体表现为:
对于第二个字符串中出现的字符,
在第一个字符串中出现的次数大于等于在第二个字符串中的出现的次数
(没有出现时, 认为出现次数为0)
# 完整描述步骤
1. 获取两个字符串
2. 初始化统计数据计数器: 将所有可能出现的字符的出现次数置为0
3. 统计两个字符串的字符出现次数, 即对于字符串中的每一个字符:
- 在计数器中将字符对应的计数值+1
4. 初始化差值计数器: 多出的珠子数目计数器, 少了的珠子数目计数器
5. 设置标志位: 是否被覆盖的标志位, 初始值为True
5. 对于第二个字符串的计数器中非零的每个字符:
- 检查其计数值是否小于等于第一个字符串计数器中相同字符的计数值
- 如果小于, 则:
多出的珠子数目计数器 加上 差值
- 如果大于, 则:
覆盖标志位置为False
少了的珠子数目计数器 加上 差值
5. 根据覆盖标志位输出对应信息:
- 覆盖标志位为True: Yes 多出的珠子数目计数器的计数值
- 覆盖标志位为False: No 少了的珠子数目计数器的计数值
# 伪代码描述
1. get input of string: sale, want
2. init counter and flag:
sale_counter[256] = {0}
want_counter[256] = {0}
could_buy_flag = True
more_amount = 0
less_amount = 0
3. for each char in sale:
sale_counter[code of char] += 1
4. for each char in want:
want_counter[code of char] += 1
5. for each char in want_counter:
if count_value_in_want <= count_value_in_sale:
more_amount += count_value_in_sale - count_value_in_want
else:
less_amount += count_value_in_want - count_value_in_sale
could_buy_flag = False
6. if could_buy_flag == true:
print("Yes" + more_amount)
else:
print("No" + less_amount)
*/
# define MAXLEN 1001
int main(){
char sale[MAXLEN];
char want[MAXLEN];
scanf("%s\n%s", sale, want);
int frequency_of_sale[256] = {0};
int frequency_of_want[256] = {0};
int less_amount = 0;
int more_amount = 0;
int could_buy = 1;
for (int i = 0; sale[i]; i++)
frequency_of_sale[(int)sale[i]]++;
for (int i = 0; want[i]; i++)
frequency_of_want[(int)want[i]]++;
for (int i = 0; i < 256; i++){
int difference_amount = frequency_of_sale[i] - frequency_of_want[i];
if (difference_amount >= 0){
more_amount += difference_amount;
}
else{
less_amount -= difference_amount;
could_buy = 0;
}
}
if (could_buy == 1){
printf("Yes %d", more_amount);
} else {
printf("No %d", less_amount);
}
return 0;
}