乐趣区

关于算法-数据结构:PAT甲级1092-To-Buy-or-Not-to-Buy

题目粗心:

给出两串珠子中每颗珠子的色彩,问第一串中是否有第二串中的所有珠子,即对每种色彩来说,第一串中该色彩珠子的个数必须不小于第二串中该色彩珠子的个数。如果是,输入“Yes””,并输入第一串中除了用来和第二串珠子进行匹配以外,还剩多少珠子: 如果不是,则输入“No”, 并输入第串中还少多少个珠子,能力让第一串领有第二串中的所有珠子。

算法思路:

咱们应用 counts 记录抉择的珠子的每一个色彩的珠子呈现的次数,而后再遍历第二串珠子,对于每一个珠子咱们将其数量减一,示意已取得,如果呈现小于 0 的状况,阐明该色彩的珠子数量不够,令 isEnough 记录为 false。最初对于 isEnough 为 true 的状况,咱们间接将 counts 数组中每一种色彩的珠子的数目进行累计,对于 isEnough 为 false 的状况,咱们只累减数目小于 0 的珠子。这样就失去多进去或者少的珠子数目。

留神点:

1、对于珠子数目短缺的状况,能够间接应用长的珠子数目减去短的珠子数目来取得最初多进去的珠子数目。

提交后果:

AC 代码:
#include <unordered_map>
#include <iostream>

using namespace std;

int main()
{
    string s1,s2;
    cin>>s1>>s2;
    unordered_map<char,int> counts;
    for (int i = 0; i < s1.size(); ++i) {++counts[s1[i]];
    }
    bool isEnough = true;// 是否短缺
    for (int j = 0; j < s2.size(); ++j) {--counts[s2[j]];
        if(counts[s2[j]]<0){isEnough = false;}
    }
    int sum = 0;
    unordered_map<char,int>::iterator it;
    if(isEnough){
        // 统计多进去的珠子数目
        printf("Yes");
        for (it=counts.begin();it!=counts.end();++it) {sum += it->second;}

    } else {
        // 统计短少的珠子数目
        printf("No");
        for (it=counts.begin();it!=counts.end();++it) {if(it->second<0){sum -= it->second;}
        }
    }
    printf("%d",sum);
    return 0;
}
退出移动版