目录
- 1 介绍
- 2 训练
- 3 参考
1 介绍
本博客用来记录代码随想录leetcode200题中哈希表部分的题目。
2 训练
题目1：242. 有效的字母异位词
C++代码如下，
class Solution {
public:
bool isAnagram(string s, string t) {
vector<int> cnt1(26, 0), cnt2(26,0);
for (char c : s) cnt1[c-'a']++;
for (char c : t) cnt2[c-'a']++;
for (int i = 0; i < 26; ++i) {
if (cnt1[i] != cnt2[i]) return false;
}
return true;
}
};
python3代码如下，
class Solution:
def isAnagram(self, s: str, t: str) -> bool:
cnt1 = [0] * 26
cnt2 = [0] * 26
for c in s:
cnt1[ord(c)-ord('a')] += 1
for c in t:
cnt2[ord(c)-ord('a')] += 1
for i in range(26):
if cnt1[i] != cnt2[i]:
return False
return True
题目2：349. 两个数组的交集
C++代码如下，
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,bool> visited1;
for (auto x : nums1) visited1[x] = true;
vector<int> res;
unordered_map<int,bool> visited2;
for (auto x : nums2) {
if (visited1[x] == true) {
if (visited2[x] == false) {
res.emplace_back(x);
visited2[x] = true;
}
}
}
return res;
}
};
python3代码如下，
class Solution:
def intersection(self, nums1: List[int], nums2: List[int]) -> List[int]:
vis1 = collections.defaultdict(bool)
for x in nums1:
vis1[x] = True
res = []
vis2 = collections.defaultdict(bool)
for x in nums2:
if vis1[x]:
if vis2[x] == False:
res.append(x)
vis2[x] = True
return res
题目3：202. 快乐数
C++代码如下，
class Solution {
public:
bool isHappy(int n) {
set<int> vis;
while (n != 1 && vis.count(n) == 0) { //n要么为1，要么无限循环
vis.insert(n);
int t = 0;
while (n > 0) {
t += (n % 10) * (n % 10);
n /= 10;
}
n = t; //更新
}
//cout << "n = " << n << endl;
return n == 1;
}
};
python3代码如下，
class Solution:
def isHappy(self, n: int) -> bool:
vis = set()
while n != 1 and (n not in vis):
vis.add(n)
x = 0
while n > 0:
x += int((n % 10) * (n % 10))
n //= 10
n = x
return n == 1
题目4：1. 两数之和
C++代码如下，
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> map_val_idx; //一边加入一边查询
for (int i = 0; i < nums.size(); ++i) {
int x = nums[i];
int y = target - x;
if (map_val_idx.count(y) != 0) {
return {i, map_val_idx[y]};
}
map_val_idx[x] = i;
}
return {-1,-1};
}
};
python3代码如下，
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
map_val_idx = collections.defaultdict(int)
for i in range(len(nums)):
x = nums[i]
y = target - x
if y in map_val_idx:
return [i, map_val_idx[y]]
map_val_idx[x] = i
return [-1,-1]
题目5：454. 四数相加 II
C++代码如下，
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int n = nums1.size();
int res = 0;
unordered_map<int, int> cnt;
for (int i = 0; i < n; ++i) {
int a = nums1[i];
for (int j = 0; j < n; ++j) {
int b = nums2[j];
cnt[a+b]++;
}
}
for (int i = 0; i < n; ++i) {
int a = nums3[i];
for (int j = 0; j < n; ++j) {
int b = nums4[j];
res += cnt[-a-b];
}
}
return res;
}
};
python3代码如下，
class Solution:
def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) -> int:
cnt = collections.defaultdict(int)
for a in nums1:
for b in nums2:
cnt[a+b] += 1
res = 0
for a in nums3:
for b in nums4:
res += cnt[-a-b]
return res
题目6：383. 赎金信
C++代码如下，
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
vector<int> cnt1(26, 0);
vector<int> cnt2(26, 0);
for (auto c : ransomNote) cnt1[c-'a']++;
for (auto c : magazine) cnt2[c-'a']++;
for (int i = 0; i < 26; ++i) {
if (cnt1[i] > cnt2[i]) return false;
}
return true;
}
};
python3代码如下，
class Solution:
def canConstruct(self, ransomNote: str, magazine: str) -> bool:
cnt1 = [0] * 26
cnt2 = [0] * 26
for c in ransomNote:
cnt1[ord(c)-ord('a')] += 1
for c in magazine:
cnt2[ord(c)-ord('a')] += 1
for i in range(26):
if cnt1[i] > cnt2[i]:
return False
return True
题目7：15. 三数之和
以下解法的时间复杂度过高，后续更正
C++代码如下，
//注意nums[i],nums[j],nums[k]去重
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
map<int, int> map_val_cnt;
for (auto x : nums) map_val_cnt[x]++;
vector<int> vals;
for (auto [k, v] : map_val_cnt) vals.emplace_back(k);
set<int> vis;
for (auto x : vals) vis.insert(x);
int n = vals.size();
set<vector<int>> ans;
for (int i = 0; i < n; ++i) {
int a = vals[i];
for (int j = 0; j < n; ++j) {
int b = vals[j];
int c = 0 - a - b;
if (vis.count(c) != 0) {
unordered_map<int,int> curr_cnt;
curr_cnt[a]++;
curr_cnt[b]++;
curr_cnt[c]++;
if (curr_cnt[a] <= map_val_cnt[a] &&
curr_cnt[b] <= map_val_cnt[b] &&
curr_cnt[c] <= map_val_cnt[c]) {
vector<int> t = {a, b, c};
sort(t.begin(), t.end());
ans.insert(t);
}
}
}
}
vector<vector<int>> res(ans.begin(), ans.end());
return res;
}
};
python3代码如下，
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
map_val_cnt = collections.defaultdict(int)
for x in nums:
map_val_cnt[x] += 1
vals = []
for val in map_val_cnt:
vals.append(val)
vis = set()
for val in vals:
vis.add(val)
ans = set()
n = len(vals)
for i in range(n):
a = vals[i]
for j in range(n):
b = vals[j]
c = 0 - a - b
if c in vis:
curr_cnt = collections.defaultdict(int)
curr_cnt[a] += 1
curr_cnt[b] += 1
curr_cnt[c] += 1
if curr_cnt[a] <= map_val_cnt[a] and \
curr_cnt[b] <= map_val_cnt[b] and \
curr_cnt[c] <= map_val_cnt[c]:
t = [a, b, c]
t.sort()
ans.add(tuple(t))
ans = list(ans)
ans = [list(x) for x in ans]
return ans
题目8：18. 四数之和
以下解法的时间复杂度过高，后续更正
C++代码如下，
typedef long long LL;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
map<int, int> map_val_cnt;
for (auto x : nums) map_val_cnt[x] += 1;
vector<int> vals;
set<int> vis;
for (auto [k, v] : map_val_cnt) {
vals.emplace_back(k);
vis.insert(k);
}
set<vector<int>> ans;
int n = vals.size();
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
for (int k = 0; k < n; ++k) {
int a = vals[i];
int b = vals[j];
int c = vals[k];
LL t = (LL)target - a - b - c;
if (t > INT_MAX || t < INT_MIN) { //如果t超出了整型范围，那么vis.count(d)一定为0
continue;
}
int d = (LL)target - a - b - c;
if (vis.count(d) != 0) {
unordered_map<int,int> curr_cnt;
curr_cnt[a]++;
curr_cnt[b]++;
curr_cnt[c]++;
curr_cnt[d]++;
if (curr_cnt[a] <= map_val_cnt[a] && curr_cnt[b] <= map_val_cnt[b] &&
curr_cnt[c] <= map_val_cnt[c] && curr_cnt[d] <= map_val_cnt[d]) {
vector<int> t = {a, b, c, d};
sort(t.begin(), t.end());
ans.insert(t);
}
}
}
}
}
vector<vector<int>> res(ans.begin(), ans.end());
return res;
}
};
python3代码如下，
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
map_val_cnt = collections.defaultdict(int)
for x in nums:
map_val_cnt[x] += 1
vals = []
vis = set()
for x in map_val_cnt:
vals.append(x)
vis.add(x)
ans = set()
n = len(vals)
for i in range(n):
for j in range(n):
for k in range(n):
a = vals[i]
b = vals[j]
c = vals[k]
d = target - a - b - c
if d in vis:
curr_cnt = collections.defaultdict(int)
curr_cnt[a] += 1
curr_cnt[b] += 1
curr_cnt[c] += 1
curr_cnt[d] += 1
if curr_cnt[a] <= map_val_cnt[a] and curr_cnt[b] <= map_val_cnt[b] and \
curr_cnt[c] <= map_val_cnt[c] and curr_cnt[d] <= map_val_cnt[d]:
t = [a, b, c, d]
t.sort()
t = tuple(t)
ans.add(t)
res = list(ans)
res = [list(x) for x in res]
return res
3 参考
代码随想录官网
