PAT 乙级 1039.到底买不买 C++/Java

题目来源

小红想买些珠子做一串自己喜欢的珠串。卖珠子的摊主有很多串五颜六色的珠串,但是不肯把任何一串拆散了卖。于是小红要你帮忙判断一下,某串珠子里是否包含了全部自己想要的珠子?如果是,那么告诉她有多少多余的珠子;如果不是,那么告诉她缺了多少珠子。

为方便起见,我们用[0-9]、[a-z]、[A-Z]范围内的字符来表示颜色。例如在图1中,第3串是小红想做的珠串;那么第1串可以买,因为包含了全部她想要的珠子,还多了8颗不需要的珠子;第2串不能买,因为没有黑色珠子,并且少了一颗红色的珠子。

PAT 乙级 1039.到底买不买 C++/Java

图 1

输入格式:

每个输入包含 1 个测试用例。每个测试用例分别在 2 行中先后给出摊主的珠串和小红想做的珠串,两串都不超过 1000 个珠子。

输出格式:

如果可以买,则在一行中输出 Yes 以及有多少多余的珠子;如果不可以买,则在一行中输出 No 以及缺了多少珠子。其间以 1 个空格分隔。

输入样例 1:

ppRYYGrrYBR2258
YrR8RrY

输出样例 1:

Yes 8

输入样例 2:

ppRYYGrrYB225
YrR8RrY

输出样例 2:

No 2

分析:

思路1

颜色总共有0-9,a-z,A-Z种,用了两个数组来保存摊主的珠串,以及小红需要的珠串(数组长度为123,因为z的ASCII码最大,为122)

输入的字符串,将字符的出现次数保存到sell和need数组。同时用bool exist数组(初始化false)表示小红需要的珠串(设为true)

用sell的每一位减去need的每一位,如果不是小红需要的,就是多余的;如果是小红需要的,且sell[I]-need[i]<0,说明缺了

思路2

将摊主的珠串和小红需要的珠串进行比较,相同的字符统一设为@或者#或者%等符号都ok

接着分别遍历两个字符串,摊主中如果有的字符不是我们设置的符号,就说明有多余

小红需求中如果有的字符不是我们设置的符号,就说明有缺少

C++实现:

思路1

PAT 乙级 1039.到底买不买 C++/Java
 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 
 5 int sellArr[123] = { 0 };
 6 int needArr[123] = { 0 };
 7 bool exist[123] = { false };
 8 int main()
 9 {    
10     string sell;
11     string need;
12     int less = 0;
13     int more = 0;
14     int index = 0;
15     cin >> sell >> need;
16 
17     if (sell == need){
18         printf("Yes 0");
19         return 0;
20     }
21 
22     for (int i = 0; i < sell.length(); ++i){
23         index = (int)(sell[i]);
24         sellArr[index]++;
25     }
26 
27     for (int i = 0; i < need.length(); ++i){
28         index = (int)(need[i]);
29         needArr[index]++;
30         exist[index] = true;
31     }
32 
33     for (int i = 48/*0的ASCII*/; i < 123; ++i){
34         int temp = sellArr[i] - needArr[i];
35         if (exist[i] != true){
36             more = more + temp;
37         }
38         else if (exist[i] == true){
39             if (temp < 0){
40                 less = less - temp;
41             }
42         }
43     }
44     if (less == 0){
45         printf("Yes %d", more + 1);
46     }
47     else{
48         printf("No %d", less);
49     }
50     return 0;
51 }
View Code

 

思路2

PAT 乙级 1039.到底买不买 C++/Java
 1 #include <iostream>
 2 #include <string>
 3 using namespace std;
 4 int main()
 5 {
 6     string sell;
 7     string need;
 8     int less = 0;
 9     int more = 0;
10 
11     cin >> sell >> need;
12     for(int i = 0; i < sell.size(); ++i)
13     {
14         for(int j = 0; j < need.size(); ++j)
15         {
16             //为什么不是sell[j]?
17             //有可能 need.size() > sell.size();
18             //sell[j] 会越界
19             if(need[j] == sell[i])
20             {
21                 need[j] = '@';
22                 sell[i] = '@';
23             }
24         }
25     }
26 
27     for (int i = 0; i < sell.size(); ++i)
28     {
29         if (sell[i] != '@')
30         {
31             more++;
32         }
33     }
34     for (int i = 0; i < need.size(); ++i)
35     {
36         if (need[i] != '@')
37         {
38             less++;
39         }
40     }
41     if (less != 0)
42     {
43         cout << "No " << less;
44     }
45     else
46     {
47         cout << "Yes " << more;
48     }
49     return 0;
50 }
View Code

 

Java实现:

 

 

 

 

 

上一篇:node.js安装中途遇到的问题


下一篇:如何在CALayer设置滤镜