Solution 1: # Hash Table
class Solution {
public:
bool isAnagram(string s, string t) {
unordered_map<char, int> mp;
for(auto c : s){ // count the numberof every character of s
mp[c]++;
}
for(auto c : t){ // if the character of t matches that of s
mp[c]--; // then mp[c]--
if(mp[c] == 0) mp.erase(c); // if the number of al character matches
}
if(mp.size() == 0) return true; //if all characters are the same
return false;
}
};Solution 2 : 手搓一个哈希映射
class Solution {
public:
bool isAnagram(string s, string t) {
vector<int>count(26, 0);
for(auto c : s){
count[c - 'a']++;
}
for(auto c : t){
count[c - 'a']--;
}
for(auto num : count){
if(num != 0) return false;
}
return true;
}
};Solution 3: # Sort
class Solution {
public:
bool isAnagram(string s, string t) {
sort(s.begin(), s.end()); // 按照字典序从小到大排
sort(t.begin(), t.end());
if(s == t) return true;
return false;
}
};Solution 1: # Hash Table
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
unordered_map<char, int> count;
for(auto c : magazine) count[c]++; //把magazine上面的字符放到货架上
for(auto c : ransomNote){
if(!count[c]) return false; // 要取货的时候没货了就false
count[c]--; // 有货则取货
}
return true;
}
};Solution 2: # 用数组模拟一个哈希表
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int count[26] = {0};
for(auto c : magazine) count[c-'a']++;
for(auto c : ransomNote){
if(!count[c - 'a']) return false; // when the number of the letter <= 0
else count[c - 'a']--; // if the number of the letter is enough, take off one
}
return true;
}
};Solution 1: # Hash Table， 这个就很简单粗暴....
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<int>> record;
for(int i = 0; i < strs.size(); i++){
string tmp = strs[i];
sort(tmp.begin(), tmp.end());
record[tmp].push_back(i); // record the position of the sorted strs[i]
}
vector<vector<string>> ans(record.size());
int i = 0;
for(auto p : record){
for(auto idx : p.second) ans[i].push_back(strs[idx]);
i++;
}
return ans;
}
};Solution 2: # 建立更好的哈希映射,同时利用vector的特性
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string, vector<string>> mp;
for(auto s : strs){
string t = s;
sort(t.begin(), t.end());
mp[t].push_back(s);
}
vector<vector<string>> ans;
for(auto p : mp) ans.push_back(p.second);
return ans;
}
};438. Find All Anagrams in a String
Solution1 : # Brute force, 虽然会爆超时.......
class Solution {
public:
bool isAnagrams(string s, string t){
sort(s.begin(), s.end());
sort(t.begin(), t.end());
return s == t;
}
vector<int> findAnagrams(string s, string p) {
vector<int> idx;
int n = s.size();
int m = p.size();
for(int i = 0; i <= n - m; i++){ //暴力比对s的每个子串
string tmp = s.substr(i, m);
if(isAnagrams(tmp, p)) idx.push_back(i);
}
return idx;
}
};Solution2 : # Sliding window # Hash table
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> sFreq(26, 0), pFreq(26, 0), ans;
int m = s.size(), n = p.size();
if(n > m) return ans;
for(char c : p) pFreq[c - 'a']++;
for(int i = 0; i < m; i++){
sFreq[s[i] - 'a']++;
if(i >= n) sFreq[s[i - n] - 'a']--; // make sure the sliding window record the current substring 's frequency
if(i >= n - 1 && sFreq == pFreq) ans.push_back(i - n + 1);
}
return ans;
}
};349. Intersection of Two Arrays
Solution1: # Hash table, 用set来去重
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result; // to elimilate duplicates in nums2
unordered_set<int> hash(nums1.begin(), nums1.end()); // to elimilate duplicates in num1;
for(auto num : nums2){
if(hash.find(num) != hash.end()) result.insert(num); // if num exists in nums1
}
return vector<int>(result.begin(), result.end());
}
};Solution2: 更简洁的做法
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> s(nums1.begin(), nums1.end());
vector<int> result;
for(int x : nums2){
if(s.erase(x)) result.push_back(x); //如果存在则删除 x 并返回 true，同时将 x 添加到 result 中。
}
return result;
}
};Solution3: 用数组来模拟哈希表
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result;
int hash[1001] = {0};
for(int x : nums1) hash[x] = 1; // 用数组模拟哈希表
for(int x : nums2){
if(hash[x] == 1) result.insert(x);
}
return vector<int>(result.begin(), result.end());
}
};350. Intersection of Two Arrays II
Solution1: # unordered_map
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int, int> mp;
for(auto x : nums1) mp[x]++;
vector<int> result;
for(auto x : nums2){
if(mp[x]){
result.push_back(x);
mp[x]--;
}
}
return result;
}
};Solution2: Sort each array and use two pointers to check if the pointed element matches
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
int m = nums1.size(), n = nums2.size();
vector<int> ans;
if(m == 0 || n == 0) return ans;
int i = 0, j = 0;
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
while(i < m && j < n){
if(nums1[i] < nums2[j]) i++;
else if(nums1[i] > nums2[j]) j++;
else{
ans.push_back(nums1[i]);
i++, j++;
}
}
return ans;
}
};Solution1: # unordered_set，用set来检查是否有循环♻️
class Solution {
public:
int getValue(int n){ //get the value
int sum = 0;
while(n){
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> check; // to check whether the current value exists before
while(1){
int cur = getValue(n);
if(cur == 1) return true;
else if(check.find(cur) != check.end()) return false; // there is a loop
else check.insert(cur); // record the cur if it doesn't appear before
n = cur; // update n for the next loop
}
return false;
}
};Solution2: # Tow pointers，快指针一次性走两步，慢指针一次性走一步
class Solution {
public:
int getValue(int n){
int sum = 0;
while(n){
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
int slow = n;
int fast = n;
do{
slow = getValue(slow); // 每次更新1步
fast = getValue(getValue(fast)); // 每次更新2步
if(fast == 1) return true;
} while(fast != slow); // 注意do{...} while(...); 要加';'在末尾!!!!
return false;
}
};#Solution1: # Hash Table, 就是记录每个元素的下标，然后去查找是否存在target减去当前元素的下标
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> mp;
for(int i = 0; i < nums.size(); i++){
if(mp.find(target - nums[i]) != mp.end()) return{i, mp[target - nums[i]]};
else mp[nums[i]] = i; // record the index of the current element
}
return {}; // no solution
}
};Solution2: #手搓一个哈希映射，然后对容器排序，最后用双指针指向容器的头和尾移动看能否match
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<pair<int, int>> v;
for(int i = 0; i < nums.size(); i++) v.push_back({nums[i], i});
sort(v.begin(), v.end()); // make the vector in order & use two pointers
int i = 0, j = v.size() - 1;
while(i < j){
if(v[i].first + v[j].first == target) return{v[i].second, v[j].second};
else if(v[i].first + v[j].first > target) j--;
else i++;
}
return {};
}
};Solution1: # Hash function
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int, int> mp; // record the sum of nums1 & nums2
for(auto a : nums1){
for(auto b : nums2) mp[a + b]++;
}
int ans = 0;
for(auto c : nums3){
for(auto d : nums4){ // check if -(c + d) exists
if(mp.find(-(c + d)) != mp.end()) ans += mp[-(c + d)];
}
}
return ans;
}
};#Solution1: # Hash Function, 这里的去重真的很麻！！！
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result; // 存储答案
sort(nums.begin(), nums.end()); // 方便循环
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0) break; // 后面肯定都大于0，进行剪枝
if(i > 0 && nums[i] == nums[i - 1]) continue; // 对a去重
unordered_set<int> set;
for(int j = i + 1; j < nums.size(); j++){
if(j > i + 2 && nums[j] == nums[j - 1] && nums[j - 1] == nums[j - 2]) continue; //对b去重
int c = 0 - nums[i] - nums[j];
if(set.find(c) != set.end()){
result.push_back({nums[i], nums[j], c});
set.erase(c);
}
else set.insert(nums[j]);
}
}
return result;
}
};Solution2: # Two pointers
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for(int i = 0; i < nums.size(); i++){
if(nums[i] > 0) break;
if(i > 0 && nums[i] == nums[i - 1]) continue;
int left = i + 1;
int right = nums.size() - 1;
while(left < right){
if(nums[i] + nums[left] + nums[right] > 0) right--;
else if(nums[i] + nums[left] + nums[right] < 0) left++;
else{
result.push_back({nums[i], nums[left], nums[right]}); //找到答案后进行去重
while(right > left && nums[right] == nums[right - 1]) right--;
while(right > left && nums[left + 1] == nums[left]) left++;
left++;
right--;
}
}
}
return result;
}
};Solution: #Tow pointers, 主要思想就是先给数组排序好，然后考虑剪枝的情况，再移动双指针找到合适的组合
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<vector<int>> result;
for(int k = 0; k < nums.size(); k++){
if(nums[k] > target && nums[k] >= 0) break; // pruning
if(k > 0 && nums[k] == nums[k - 1]) continue; // remove duplicates
for(int i = k + 1; i < nums.size(); i++){
if(nums[k] + nums[i] > target && nums[k] + nums[i] >= 0) break; // pruning
if(i > k + 1 && nums[i] == nums[i - 1]) continue; // remove duplicates
int left = i + 1;
int right = nums.size() - 1;
while(right > left){ // use tow pointers to find the combinations
if((long)nums[k] + nums[i] + nums[left] + nums[right] > target) right--;
else if((long)nums[k] + nums[i] + nums[left] + nums[right] < target) left++;
else{
result.push_back({nums[k], nums[i], nums[left], nums[right]});
while(right > left && nums[right] == nums[right - 1]) right--; // remove duplicates
while(right > left && nums[left] == nums[left + 1]) left++; // remove duplicates
left++;
right--;
}
}
}
}
return result;
}
};