codetop哈希表刷题！！！刷穿地心版)

1.H指数

给你一个整数数组 citations ，其中 citations[i] 表示研究者的第 i 篇论文被引用的次数。计算并返回该研究者的 h 指数。

根据维基百科上 h 指数的定义：h 代表“高引用次数” ，一名科研人员的 h 指数 是指他（她）至少发表了 h 篇论文，并且 至少 有 h 篇论文被引用次数大于等于 h 。如果 h 有多种可能的值，h 指数 是其中最大的那个。

分析一下，核心：至少有h篇论文的引用次数都大于或等于h
首先，排序，h逐步加大，不用管加大之后，前面遍历的cite还合不合法，因为是从大到小排序的，如果后面遍历到的数字都满足>h，那么前面的一定大于h

其中if (citations[i] >= h + 1)非常关键，使用 h + 1 是因为我们正在检查是否可以将 h 增加 1，也就是说，当前引用次数必须至少满足 h + 1 才能使 h 增加。

class Solution {
public:
    int hIndex(std::vector<int>& citations) {
        sort(citations.begin(), citations.end(), greater<int>()); // 从大到小排序
        int h = 0;
        
        for (int i = 0; i < citations.size(); ++i) {
            if (citations[i] >= h + 1) { // 检查是否满足 h 指数条件
                h++;
            } else {
                break; // 如果不满足条件，直接结束
            }
        }
        
        return h; // 返回最终的 h 指数
    }
};

2.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

示例 1: 输入: s = “anagram”, t = “nagaram” 输出: true

示例 2: 输入: s = “rat”, t = “car” 输出: false

说实话，滑动窗口也能解决,但是有点大刀砍苍蝇了…
放在这篇blog，是用哈希来解决的
数组其实就是个简单的哈希表，而且这题里面只有小写字符，那么就可以定义一个组，来记录字符串s里的字符出现的次数。

class Solution {
public:
    bool isAnagram(string s, string t) {
        if(s == t) return false;
        int record[26] = {0};
        for(int i = 0; i < s.size(); i ++){
            record[s[i] - 'a'] ++;
        }
        for(int i = 0; i < t.size(); i ++){
            record[t[i] - 'a'] --;
        }
        for(int i = 0; i < 26; i ++){
            if(record[i] != 0) return false;
        }
        return true;
    }
};

3.快乐数

编写一个算法来判断一个数是不是快乐数：

• 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
• 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
• 如果这个过程 结果为 1，那么这个数就是快乐数。

如果无法true，那么一定会陷入死循环！以此为入口
先写一个函数，用来取出各个位上的单数之和

int getSum(int n){
	int sum = 0;
	while(n){
		sum += (n % 10) * (n % 10);
		n = n / 10;
	}
	return sum;
}

isHappy函数：

bool isHappy(int n){
	unordered_set<int> set;
	while(1){
		int sum = getSum(n);
		if(sum == 1) return true;
		if(set.find(sum) != set.end()){
			return false;
		}else{
			set.insert(sum);
		}
		n = sum;
	}
};

4.赎金信

给你两个字符串：ransomNote 和 magazine ，判断
给定一个赎金信 (ransom) 字符串和一个杂志(magazine)字符串，判断第一个字符串 ransom 能不能由第二个字符串 magazines 里面的字符构成。如果可以构成，返回 true ；否则返回 false。

magazine 中的每个字符只能在 ransomNote 中使用一次。

有效字符串要的是相互组成，这个是a能否由b组成
因为题目说只有小写字母，那可以采用空间换取时间的哈希策略，用一个长度为26的数组来记录magazine里字母出现的次数。
不用随便用map，数据量散的话用map是不划算的！

class Solution {
public:
    bool canConstruct(string ransomNote, string magazine) {
        int record[26] = {0};
        if(ransomNote.size() > magazine.size()) return false;
        for(int i = 0; i < magazine.size(); i ++) record[magazine[i] - 'a']++;
        for(int i = 0; i < ransomNote.size(); i ++){
            record[ransomNote[i] - 'a'] --;
            if(record[ransomNote[i] - 'a'] < 0) return false;
        }
        return true;
    }
};

5.前k个高频元素

返回频率最高的，任意顺序

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> valTohz;
        for(int i = 0; i < nums.size(); i ++){
            valTohz[nums[i]]++;
        }
        vector<pair<int, int>> vec(valTohz.begin(), valTohz.end());
        sort(vec.begin(), vec.end(), [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});

        vector<int> res;
        for(int i = 0; i < k; i ++){
            res.push_back(vec[i].first);
        }
        return res;

    }
};

6.O(1)时间插入、删除和获取随机元素

实现一个RandomizedSet类：

• RandomizedSet() 初始化 RandomizedSet 对象
• bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
• bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
• int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。

你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

思路：
对于一个HashSet，无法在O(1)时间内实现getRandom函数。因为元素是被哈希函数分散到整个数组里面的，基本做不到O(1)时间等概率。
换句话说，对于 getRandom 方法，如果想「等概率」且「在 O(1) 的时间」取出元素，一定要满足：

• 底层用数组实现，且数组必须是紧凑的，这样我们就可以直接生成随机数作为索引，选取随机元素。
• 但如果用数组存储元素的话，常规的插入，删除的时间复杂度又不可能是 O(1)。然而，对数组尾部进行插入和删除操作不会涉及数据搬移，时间复杂度是 O(1)。

解决：
底层用数组实现，元素的排列必须紧凑，另外，删除元素的时候，用尾部元素与其交换，删除尾部元素，利用pop

class RandomizedSet {
public:
	vector<int> nums;//记录元素
	unordered_map<int, int> valToIndex;//记录每个元素对应的索引
    RandomizedSet() {

    }
    
    bool insert(int val) {
    	//如果val已经存在,那么就不用再插入了
    	if(valToIndex.count(val)) return false;
    	//如果val不存在
    	valToIndex[val] = nums.size();
    	nums.push_back(val);//插到尾部O(1)
    	return true;
    }
    
    bool remove(int val) {
    	//如果val不存在,那么就不用再移除了
    	if(!valToIndex.count(val)) return false;
    	//如果val存在
    	int index = valToIndex[val];
    	swap(nums[index], nums[nums.size() - 1]);
    	valToIndex[nums[index]] = index;//换到前面的尾部元素更新索引
    	nums.pop_back();//移除出nums
    	valToIndex.erase(val);//移除出索引
    	return true;
    }
    
    int getRandom() {
    	return nums[rand() % nums.size()];
    }
};

7.TinyURL的加密与解密

输入一个网址，想办法设计一个加密算法encode和一个解密算法decode，使输入一个网址，这一串完整经过加密和解密之后输出原网址

使用异或^来解决，将字母和数字进行异或操作是常见的，尤其是在执行简单的加密或编码任务时。字母和其他字符在底层都是以整数形式存储的，通常是 ASCII 码的形式。这意味着每个字符都对应一个整数值，因此可以直接与其他整数进行二进制运算。
编码和解码都和相同的值异或就行。

class Solution {
public:
    // Encodes a URL to a shortened URL.
    string encode(string longUrl) {
        int len = longUrl.size();
        for(int i = 0; i < len; i ++){
            longUrl[i] ^= 1;
        }
        return longUrl;        
    }

    // Decodes a shortened URL to its original URL.
    string decode(string shortUrl) {
        for(int i = 0; i < shortUrl.size(); i ++){
            shortUrl[i] ^= 1;
        }
        return shortUrl;        
    }
};