哈希表，Leetcode

本题目思想和上一篇一样，在此不过多分析。有和我一样白的，麻烦先参考一下这篇

https://blog.csdn.net/qq_40286920/article/details/124541380?spm=1001.2014.3001.5501

1.题目描述：

给你两个字符串：ransomNote 和 magazine ，判断 ransomNote 能不能由 magazine 里面的字符构成。如果可以，返回 true ；否则返回 false 。

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

示例1

输入：ransomNote = "a", magazine = "b"

输出：false

示例2

输入：ransomNote = "aa", magazine = "aab"

输出：true

2.题解思路：

本题想要返回true，必须让magazine中的字符，完全包含reansomNote中的字符,所以reansomNote的长度必须小于等于magazine

1.定义一个长度为26的数组(哈希表)

2.把字符串中的'a','b','c'...'z'分别映射到0,1,2....25。(即数组的索引上)

3.reansomNote中的字母每出现一次，数组索引对应的值+1。

   magazine中的字母每出现一次，数组索引对应的值-1。

4.遍历结束后，如果数组中的元素有大于0的，就返回false。

3.本地实现：

#include
#include
using namespace std;

class Solution
{
public:
	bool canConstruct(string ransomNote, string magazine) 
	{
		if (magazine.size() < ransomNote.size()) return false; 

		int hash[26] = { 0 };//创建一个长度为26的，全是0的数组，作为哈希表
		//把magazine里边的字母a、b、c....转化成数字0、1、2.....，哈希函数的思想
		for (int i = 0; i < magazine.size(); i++)
		{
			hash[magazine[i] - 'a']--;  //一种映射方法，保证'a'对应的是0。每出现一次，增加1
		}
		//遍历ransomNote
		for (int i = 0; i < ransomNote.size(); i++)
		{
			hash[ransomNote[i] - 'a']++;  //每出现一次，减少1
		}
		//遍历一边hash表
		for (int i = 0; i < (sizeof(hash) / sizeof(hash[0])); i++)
		{
			if (hash[i] > 0) return false;//一旦表内有大于0，返回false
		}
		return true;//否则返回true
	}
};

int main()
{
	string s = "a", t = "ab";
	Solution solution;
	cout << solution.canConstruct(s, t) << endl;
	system("pause");
	return 0;
}

谢谢访问