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

2024-10-20 04:10:44

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

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

图 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

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

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

思路3

用一个hashmap保存摊主的字符串，记录不同颜色珠子数量

遍历小红的珠串，同时hashmap中对应的颜色数量-1，如果数量小于0，就说明缺少这一颗珠子

如果都没有小于0，可以输出Yes

C++实现：

思路1

 #include <iostream>

 #include <string>

 using namespace std;

 int sellArr[] = {  };

 int needArr[] = {  };

 bool exist[] = { false };

 int main()

 {

     string sell;

     string need;

     int less = ;

     int more = ;

     int index = ;

     cin >> sell >> need;

     if (sell == need){

         printf("Yes 0");

         return ;

     }

     for (int i = ; i < sell.length(); ++i){

         index = (int)(sell[i]);

         sellArr[index]++;

     }

     for (int i = ; i < need.length(); ++i){

         index = (int)(need[i]);

         needArr[index]++;

         exist[index] = true;

     }

     for (int i = /*0的ASCII*/; i < ; ++i){

         int temp = sellArr[i] - needArr[i];

         if (exist[i] != true){

             more = more + temp;

         }

         else if (exist[i] == true){

             if (temp < ){

                 less = less - temp;

             }

         }

     }

     if (less == ){

         printf("Yes %d", more + );

     }

     else{

         printf("No %d", less);

     }

     return ;

 }

思路2

 #include <iostream>

 #include <string>

 using namespace std;

 int main()

 {

     string sell;

     string need;

     int less = ;

     int more = ;

     cin >> sell >> need;

     for(int i = ; i < sell.size(); ++i)

     {

         for(int j = ; j < need.size(); ++j)

         {

             //为什么不是sell[j]?

             //有可能 need.size() > sell.size();

             //sell[j] 会越界

             if(need[j] == sell[i])

             {

                 need[j] = '@';

                 sell[i] = '@';

             }

         }

     }

     for (int i = ; i < sell.size(); ++i)

     {

         if (sell[i] != '@')

         {

             more++;

         }

     }

     for (int i = ; i < need.size(); ++i)

     {

         if (need[i] != '@')

         {

             less++;

         }

     }

     if (less != )

     {

         cout << "No " << less;

     }

     else

     {

         cout << "Yes " << more;

     }

     return ;

 }

思路3

 #include <iostream>

 #include <unordered_map>

 #include <string>

 using namespace std;

 int main() {

     string sell, need;

     cin >> sell >> need;

     bool flag = true;    // 是否缺少

     unordered_map<char, int> sellMap;

     int less = ;    // 缺少的珠子数量

     for (int i = ; i < sell.size(); ++i) {

         sellMap[sell[i]]++;

     }

     for (int i = ; i < need.size(); ++i) {

         sellMap[need[i]]--;

         if (sellMap[need[i]] < ) {

             flag = false;

             less++;

         }

     }

     if (flag) {

         cout << "Yes " << sell.size() - need.size();    // 多出来的珠子

     }

     else {

         cout << "No " << less;

     }

     return ;

 }

Java实现：

最新文章

热门文章