242. 有效的字母异位词 - 力扣（LeetCode）
class Solution {
public:
bool isAnagram(string s, string t) {
if(s.size() != t.size()) return false;
int len = s.size(), record[26] = {0};
for (int i = 0; i < len; ++ i)
{
record[s[i] - 'a'] ++;
record[t[i] - 'a'] --;
}
for (int i : record) if(i) return false;
return true;
}
};
383. 赎金信 - 力扣（LeetCode）
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
int lenRand = ransomNote.size(), lenMaga = magazine.size();
// 实际题意：求 ransomeNote 是不是 magazine 的真子解，数学上的真子集。
if (lenRand > lenMaga) return false; // 因为匹配串(randsomeNote)求是不是模式串的真子集(magazine),所以不会有 len(匹配串) > len(模式串) 的情况
int record[26] = {0};
for(char c: magazine) record[c - 'a'] ++;
// 因为匹配串(randsomeNote)求是不是模式串的真子集(magazine),所以不会有 len(匹配串) > len(模式串) 的情况
// 所以下面可以这么写:
for(char c: ransomNote) if(--record[c - 'a'] < 0) return false;
return true;
}
};
349. 两个数组的交集 - 力扣（LeetCode）
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> record1,record2;
for(int i : nums1) record1.insert(i);
for (int i : nums2) if (record1.find(i) != record1.end()) record2.insert(i);
return vector<int>(record2.begin(),record2.end());
}
};
202. 快乐数 - 力扣（LeetCode）
class Solution {
public:
int getSum(int n){
int sum = 0;
while(n)
{
sum += pow(n%10,2);
n /= 10;
}
return sum;
}
// 快乐数，把每一位拆开平方后求和，那这个和集训拆开平方求和，反复套娃，最终回得到求和值为1 -- 这就是快乐数
// 不是快乐数，上面的步骤经过n 步后回重复出现刚才拆平方求和的值
bool isHappy(int n) {
int sum = n;
// unordered_set<int> O(1) 比 set<int> O(logN) 快，所以优化用 unordered_set<int>,其实用set<int>也可以
unordered_set<int> sumSet;
for(;;)
{
sum = getSum(sum);
if (sum == 1) break;
else if (sumSet.find(sum) != sumSet.end()) return false;
sumSet.insert(sum);
}
return true;
}
};
1. 两数之和 - 力扣（LeetCode）
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
// <elem,rank>
unordered_map<int,int> record;
for(int i = 0; i < nums.size(); ++ i)
{
auto iter = record.find(target - nums[i]);
if (iter != record.end()) return {iter->second,i};
record.insert(make_pair(nums[i],i));
}
return {};
}
};
454. 四数相加 II - 力扣（LeetCode）
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
int count = 0;
// <ret,cnt>
unordered_map<int,int> record;
for(int a : nums1)
for (int b : nums2)
record[a+b] ++;
for(int c : nums3)
for(int d : nums4)
if(record.find(0 - (c+d)) != record.end())
count += record[ 0 - (c+d)];
return count;
}
};
15. 三数之和 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
std::vector <std::vector<int>>res;
std::sort(nums.begin(), nums.end());
if (nums[0] > 0) return res;
int size = nums.size();
for (int Lbound = 0; Lbound < size; ++Lbound){
if (nums[Lbound] > 0) return res;
if (Lbound > 0 && nums[Lbound] == nums[Lbound - 1]) continue;
int lo = Lbound + 1, hi = size - 1;
while (lo < hi){
if (nums[Lbound] + nums[lo] + nums[hi] > 0) hi--;
else if (nums[Lbound] + nums[lo] + nums[hi] < 0) lo++;
else {
res.emplace_back(std::vector<int>({nums[Lbound],nums[lo],nums[hi]}));
// left diff
while (hi > lo && nums[lo] == nums[lo + 1]) lo ++;
// right diff
while (hi > lo && nums[hi] == nums[hi - 1]) hi --;
lo++;
hi--;
}
}
}
res.shrink_to_fit();
return res;
}
};
18. 四数之和 - 力扣（LeetCode）
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
std::vector<std::vector<int>> res;
std::sort(nums.begin(), nums.end());
int size = nums.size();
for (int LBSide = 0; LBSide < size; ++LBSide)
{
if (nums[LBSide] > target && nums[LBSide] >= 0) break;
if (LBSide > 0 && nums[LBSide] == nums[LBSide - 1]) continue;
for (int LBInner = LBSide + 1; LBInner < size; ++LBInner)
{
if (nums[LBSide] + nums[LBInner] > target && nums[LBSide] + nums[LBInner] >= 0) break;
if (LBInner > LBSide + 1 && nums[LBInner] == nums[LBInner - 1]) continue;
int lo = LBInner + 1, hi = size - 1;
while (lo < hi)
{
if (hi > lo && (long)nums[LBSide] + nums[LBInner] + nums[lo] + nums[hi] > target) hi--;
else if (hi > lo && (long)nums[LBSide] + nums[LBInner] + nums[lo] + nums[hi] < target) lo++;
else {
res.emplace_back(std::vector<int>({nums[LBSide],nums[LBInner], nums[lo],nums[hi]}));
while (hi > lo && nums[lo] == nums[lo + 1]) lo++;
while (hi > lo && nums[hi] == nums[hi - 1]) hi--;
lo++, hi--;
}
}
}
}
res.shrink_to_fit();
return res;
}
};
