PAT A1120 Friend Numbers(C++)

PAT甲级目录 | PAT乙级目录

题目描述

原题地址:A1120 Friend Numbers
中文版:B1064 朋友数

解题思路

方法一:利用 map,每出现一个新的朋友证号就会在 map 中增加一个元素。最后遍历 map 输出即可得到有序结果序列。和方法二相比,主要优势在于节约了内存空间。

方法二:利用 hash 数组,记录每个数是否是朋友证号,如是设为 true,最后按顺序遍历数组,输出值为 true 的序号。

也许陌生的知识点

  • map<int, int> m;
    • 用于映射,键和值可以是任意类型
    • 直接使用 m[<键>] = <值> 即可向map中添加一组键值对
    • 需要的头文件:map
  • for(auto it = m.begin(); it != m.end(); it++){}
    • 可用于遍历 map/vector/set 等容器, auto 实现自动匹配对应迭代器类型
    • 如果不用 auto it = m.begin() 则要写成 std::map<char, int>::iterator it = m.begin()
    • map<char,int> 在其他情况下可替换成对应元素的类型如 vector<int>
    • 所需头文件: map / set / vector
  • it->firstit->second
    • it->first 为 map 中对应元素的关键字
    • it->second 为 map 中对应关键字的值
    • 所需头文件: map

代码示例:

  • 方法一:利用 map

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    #include <string>
    #include <iostream>
    #include <map>
    using namespace std;
    int main(){
    int n, cnt = 0;
    string temp;
    map<int, int> m;
    scanf("%d", &n);
    for(int i = 0; i < n; i++){
    int sum = 0;
    cin >> temp;
    for(int j = 0; j < temp.length(); j++) sum = sum + (int)(temp[j] - '0');
    m[sum]++;
    }
    printf("%d\n", m.size());
    for(auto it = m.begin(); it != m.end(); it++, cnt++){
    if(cnt != 0) printf(" ");
    printf("%d", it->first);
    }
    return 0;
    }
  • 方法二:利用 hash 数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    #include <cstdio>
    int main() {
    int n, num = 0;
    bool h[50] = {false};
    scanf("%d", &n);
    for(int i = 0, temp, sum; i < n; i++, sum = 0){
    scanf("%d", &temp);
    while(temp!=0){
    sum = sum + temp % 10;
    temp /= 10;
    }
    if(h[sum] == false){
    num++;
    h[sum] = true;
    }
    }
    printf("%d\n", num);
    int flag = 0;
    for(int i = 1; i < 50; i++){
    if(h[i]) {
    if(flag != 0) printf(" ");
    printf("%d", i);
    flag++;
    }
    }
    return 0;
    }