PAT A1120 Friend Numbers(C++)

题目描述

原题地址：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->first 和 it->second
- it->first 为 map 中对应元素的关键字
- it->second 为 map 中对应关键字的值
- 所需头文件： map

代码示例：

方法一：利用 map

#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 数组

#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;
}