《算法集训传送门》

  ?引言

? ❄️我们的算法之路❄️?

   众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
              ☀️?短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼?☀️
   ?二分，?贪心，?并查集，?二叉树，?图论，?深度优先搜索(dfs)，?宽度优先搜索（bfs），?数论，?动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！???

今日主题：哈希表

 ?⭐️第一题?

   ✨题目

       1.多数元素

   ✨思路：

C++STL的map就是好用

   ✨代码：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        unordered_map<int,int>ans;
        int n=nums.size(),f=n/2;
        vector<int>res;
        for(int i=0;i<n;i++){
           int t= ++ans[nums[i]];
            if(t>f)return nums[i];
        }return 0;
    }
};

 ?⭐️第二题?

   ✨题目

      2.数组中的k-diff数对

   ✨思路：

哈希表模拟

   ✨代码：

class Solution {
public:
    int findPairs(vector<int>& nums, int k) {
        unordered_set<int> visited;
        unordered_set<int> res;
        for (int num : nums) {
            if (visited.count(num - k)) {
                res.emplace(num - k);
            }
            if (visited.count(num + k)) {
                res.emplace(num);
            }
            visited.emplace(num);
        }
        return res.size();
    }
};

 ?⭐️第三题?

   ✨题目

       3.缺失的第一个正数

   ✨思路：

对于一个长度为 nn 的数组，其中没有出现的最小正整数只能在[1, n + 1][1,n+1]中。这是因为如果[1, n][1,n] 都出现了，那么答案是 n + 1n+1，否则答案是[1, n][1,n]中没有出现的最小正整数。

   ✨代码：

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i = 0; i < n; i++){
            while(nums[i] >= 1 && nums[i] <= n && nums[i] != nums[nums[i] - 1]){
                swap(nums[i], nums[nums[i] - 1]);
            }
        }
        for(int i = 0; i < n; i++){
            if(nums[i] != i + 1)
                return i + 1;
        }
        return n + 1;
    }
};

 ?⭐️第四题?

   ✨题目

       4.Pupils Redistribution

   ✨代码：

#import<iostream>
using namespace std;
int i,k,n,p,s,a[6],b[6];
main(){
for(cin>>n;i++<n;a[k]++)
cin>>k;
for(;--i;b[k]++)
cin>>k;
for(;i++<5;p+=a[i]+b[i]&1)
s+=abs(a[i]-b[i]);
cout<<(p?-1:s/4);}

?写在最后?：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！???