【week3-入门组-周签】1月18日 ~ 1月24日

01.18

01.19

11.AcWing 1532 .找硬币

思路：

• 哈希表：
  用一个哈希集合存储硬币。
  对于每一枚硬币 x，判断在集合中是否存在 y，使得 x + y = m。
  如果存在，则是一组解，判断该解的小面值硬币是否小于 v1， 如果是，则存入 v1, v2。
  cin>>a;b=m-a哈希表插入每个硬币面额，hash.insert(a)然后hash.count(b)判断里面有没有这个数使用集合、
  如果存在解，则输出。否则无解。
• 双指针：先排序，再双指针走，因为要找i最小，即为j最大
  int i=0,j=n-1;i<j;i++

知识点： 哈希表用法，双指针用法

代码实现：哈希表

#include<iostream>
#include<unordered_set>//头文件
using namespace std;

const int INF=1001;//正无穷
int n,m;
int main(){
  cin>>n>>m;
  unordered_set<int> hash;//定义一个哈希表

  int v1=INF,v2;//设v1为一个肯定取不到的数
  for(int i=0;i<n;i++){
    int a,b;
    cin>>a;
    b=m-a;//b=m-a，判断哈希表中有没有b即可
    if(hash.count(b)){//hash里面有这个数，为1,否则为0
      hash.insert(a);
      if(a>b) swap(a,b);
      if(a<v1) v1=a,v2=b;
    }
    else  hash.insert(a);//最开始什么也没有，所以这里插入了第1个值。
    //一直都是先判断，再插入
  }
  if(v1==INF) cout<<"No Solution";
  else cout<<v1<<' '<<v2;
  return 0;

代码实现：双指针

#include<iostream>
#include<algorithm>
using namespace std;

const int maxn=100001;//数据范围
int n,m;
int a[maxn];

int main(){
  cin>>n>>m;
  for(int i=0;i<n;i++){
    cin>>a[i];
  }
  sort(a,a+n);//使用双指针要先排序，这里快排
  for(int i=0,j=n-1;i<j;i++){//两头开始
    while(i<j&&a[i]+a[j]>m) j--;//当i<j且a[i]+a[j]>m,j要--，这样才能变小
    if(i<j&&a[i]+a[j]==m){//当==m时，即为答案，return 0；结束即可，因为此时的j最大，即i最小；
      cout<<a[i]<<' '<<a[j];
      return 0;
    }
  }
  cout<<"No Solution";//如果走完循环，还没有退出，说明没找到，按要求输出
  return 0;
}

知识总结：

• 运用哈希表
• 双指针

扩展题

01.20

01.21

01.22

01.23

01.24