[代码随想录一刷] day4 链表
● 哈希表理论基础 ● 242.有效的字母异位词 ● 349. 两个数组的交集 ● 202. 快乐数 ● 1. 两数之和
当题目有判断元素是否在集合中出现过，就要想到用哈希。
有效的字母异位词
C++
由于是字母长度有限可以用数组哈希，先记录字符串1每个单词对应的出现次数，再遍历字符串2减去，如果最后数组所有元素都为0，则代表匹配可以互相替换。
class Solution {
public:
bool isAnagram(string s, string t) {
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;
}
};
C#
public class Solution {
public bool IsAnagram(string s, string t) {
int[] record = new int[26];
for(int i = 0; i < s.Length; i++ ) {
record[s[i] - 'a']++;
}
for(int i = 0 ; i < t.Length; i++) {
record[t[i] - 'a']--;
}
for(int i = 0 ;i < 26; i++) {
if(record[i] != 0) return false;
}
return true;
}
}
两个数组的交集
C++
先把一个数组使用unordered_set存储，遍历另一个数组的元素判断是否在set中出现过，如果出现过，则加入到结果set中（去重），最后转为vector。
- 使用数组来做哈希的题目，需要明确使用空间的大小，太大数组存不了。
- 而且如果哈希值比较少、特别分散、跨度非常大，使用数组就造成空间的极大浪费。
- unordered_set不可重复，只存key值，查询，增删效率为O(1)，底层是哈希表实现，可以理解成一个可以无限扩容的数组，可以用来去重。
- unordered_set查找，找不到返回末尾迭代器，即set.end();
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;
unordered_set<int> num_set(nums1.begin(), nums1.end());
for(int num : nums2) {
if(num_set.find(num) != num_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
C#
C#的HashSet等同于C++的unordered_set,容器对应关系参考。
public class Solution {
public int[] Intersection(int[] nums1, int[] nums2) {
HashSet<int> n1 = new HashSet<int>();
HashSet<int> res = new HashSet<int>();
foreach(int item in nums1) {
n1.Add(item);
}
foreach(int item in nums2) {
if(n1.Contains(item)) {
res.Add(item);
}
}
return res.ToArray();
}
}
快乐数
C++
- 在平方和更新为1之前判断，如果这个数出现过，则陷入了无线循环，不符合快乐数的定义。
- 理解无限循环，如果不是快乐数（循环后平方和为1），则会重复出现
class Solution {
public:
int getSum(int n){
int sum = 0;
while(n != 0) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> result;
int sum = n;
while(1) {
sum = getSum(sum);
if(sum == 1) return true;
if(result.find(sum) != result.end()) {
return false;
} else {
result.insert(sum);
}
}
}
};
C#
public class Solution {
public bool IsHappy(int n) {
HashSet<int> res = new HashSet<int>();
int sum = n;
while(1 > 0) {
sum = getSum(sum);
if(sum == 1) return true;
if(res.Contains(sum)) return false;
res.Add(sum);
}
}
public int getSum(int n) {
int sum = 0;
while(n > 0) {
sum += (n % 10) * (n % 10);
n = n / 10;
}
return sum;
}
}
两数之和
A+B=target->判断target-B是否在已遍历的集合中->哈希存遍历过的元素集合。
- 为什么使用哈希，A+B =target转化为找是否已遍历target-B。
- 为什么使用std::unordered_map,首先查找需要记录值，而返回结果需要记录下标，<key,value>结构即使用map，unorderedmap无序，不可重复，查询效率更高为O(1).
- map用来存遍历过的元素。
- map的key存遍历的数组值，value存数组下标，应为数组值是查询的依据。
C++
C+的语法有点麻烦，插入还要构建pair，访问还要find，不能直接索引（目前看到的），补坑：插入可以直接访问key索引赋值，访问也可以直接访问key。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int,int> map;
for(int i = 0; i < nums.size(); i++) {
auto iter = map.find(target- nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
简便写法。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> res;
for(int i = 0; i < nums.size(); i++) {
if(res.find(target - nums[i]) != res.end()) {
return {res[target - nums[i]], i};
}
res[nums[i]] = i;
}
return {};
}
};
C#
C#的dic注意下插入的时候要判断下元素不重复，和C+ unordered_map不一样（插入重复不会报错，会自动去重），插入是不允许重复的。
public class Solution {
public int[] TwoSum(int[] nums, int target) {
Dictionary<int, int> dic = new Dictionary<int, int>();
for(int i = 0; i< nums.Length; i++) {
if(dic.ContainsKey(target - nums[i])) {
return new int[]{dic[target - nums[i]], i};
}
if(!dic.ContainsKey(nums[i]))
dic.Add(nums[i], i);
}
return new int[]{};
}
}
二刷
242 有效的字母异位词
用unordered_map代替数组，熟悉了API。
#include<iostream>
#include<unordered_map>
using namespace std;
class Solution {
public:
unordered_map<char, int> smap;
unordered_map<char, int> tmap;
bool isAnagram(string s, string t) {
for (char it : s) {
smap[it]++;
}
for (char it : t) {
if (smap.find(it) != smap.end()) {
smap[it]--;
if (smap[it] == 0) {
smap.erase(smap.find(it));
}
}
else {
return false;
}
}
if (smap.size() == 0) return true;
return false;
}
};
int main() {
Solution s1;
string s;
string t;
cin >> s >> t;
cout << s1.isAnagram(s, t);
return 0;
}
349 两个数组的交集
利用迭代及将set和vector进行转换可以更简单一点，下边是第一反应，转换见一刷。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> data;
unordered_set<int> data2;
vector<int> res;
for (const int it : nums1) {
data.insert(it);
}
for (const int it : nums2) {
if (data.find(it) != data.end() && data2.find(it) == data.end()) {
res.push_back(it);
}
data2.insert(it);
}
return res;
}
};
202 快乐数
#include<iostream>
#include<unordered_set>
using namespace std;
class Solution {
public:
bool isHappy(int n) {
//n转换为每个位置上数的vector
vector<int> data;
unordered_set<int> pset;
while (n != 1) {
while (n > 0) {
int m = n % 10;
n = n / 10;
data.push_back(m);
}
reverse(data.begin(), data.end());
for (int i : data) cout << i << " ";
cout << endl;
//遍历vector计算平方和，判断是否重复，然后重复过程
int sum = 0;
for (int i : data) {
sum += i * i;
}
if (pset.find(sum) != pset.end()) {
return false;
}
pset.insert(sum);
n = sum;
data.clear();
}
return true;
}
};
1 两数之和
-
注意更新记录要后置，避免自己和自己相加符合条件，实际查询的时候用的都是当前点之前插入的数据，同时前面的数据也不可能有重复的，因为题目限定不能有重复解，相同元素只可能相邻且就是target/2。
-
map存的是<值，索引>的键值对，用于找到目标key后返回下标作为结果。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> data;
for (int i = 0; i < nums.size(); i++) {
auto it = data.find(target - nums[i]);
if (it != data.end()) {
return vector<int>{i, it->second};
}
data[nums[i]] = i;
}
return vector<int>();
}
};
京公网安备 11010502036488号