有效的字母异位词
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size()) return false;
map<char,int>mps, mpt;
for (int i = 0; i < s.size(); i ++) {
mps[s[i]] ++, mpt[t[i]] ++;
}
for (char v = 'a'; v <= 'z'; v ++) {
if (mps[v] != mpt[v]) return false;
}
return true;
}
};
class Solution {
public:
bool canConstruct(string ransomNote, string magazine) {
map<char,int>mps, mpt;
for (int i = 0; i < ransomNote.size(); i ++) {
mps[ransomNote[i]] ++;
}
for (int i = 0; i < magazine.size(); i ++) {
mpt[magazine[i]] ++;
}
for (int i = 0; i < ransomNote.size(); i ++) {
if (mpt[ransomNote[i]] < mps[ransomNote[i]]) return false;
}
return true;
}
};
首先相同的字母异位词进行排序后的字符串一定相同，所以我们使用哈希表存储一下所有相同的字符串即可。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
// 如果两个词是异位词，那么他们的字母数量一定是一样的
unordered_map<string,vector<string>>mp;
for (string str : strs) {
string word = str;
sort(word.begin(),word.end());
mp[word].push_back(str);
}
vector<vector<string>>res;
for (auto x : mp) {
res.push_back(x.second);
}
return res;
}
};
class Solution {
public:
unordered_map<char,int> ccnt, cnt;
bool check() {
for (auto x : ccnt) {
if (x.second != cnt[x.first]) return false;
}
return true;
}
vector<int> findAnagrams(string s, string p) {
for (auto x : p) {
cnt[x] ++;
}
int length = p.size();
vector<int>res;
for (int i = 0, j = 0; i < s.size(); i ++) {
ccnt[s[i]] ++;
while (i - j + 1 >= length && j <= i) {
if (check()) res.push_back(j);
ccnt[s[j ++]] --;
}
}
return res;
}
};
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> res, s1;
for (int i = 0; i < nums1.size(); i ++) {
s1.insert(nums1[i]);
}
for (int i = 0; i < nums2.size(); i ++) {
if (s1.find(nums2[i]) != s1.end()) {
res.insert(nums2[i]);
}
}
return vector<int>(res.begin(), res.end());
}
};
两个数组的交集
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> mp;
for (int i = 0; i < nums1.size(); i ++) mp[nums1[i]] ++;
vector<int>res;
for (int num : nums2) {
if (mp.find(num) != mp.end()) {
mp[num] --;
res.push_back(num);
}
if (mp[num] == 0) mp.erase(num);
}
return res;
}
};
快乐数
class Solution {
public:
int get_num(int x) {
int res = 0;
while (x) {
res += (x % 10) * (x % 10);
x /= 10;
}
return res;
}
bool isHappy(int n) {
unordered_map<int,int> mp;
while (1) {
int t = get_num(n);
n = t;
if (t == 1) return true;
if (mp.find(t) != mp.end()) return false;
mp[t] = 1;
}
}
};
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int>mp;
vector<int>res;
for (int i = 0; i < nums.size(); i ++) {
mp[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i ++) {
int t = target - nums[i];
if (mp.find(t) != mp.end() && mp[t] != i) {
res.push_back(mp[target - nums[i]]);
res.push_back(i);
break;
}
}
return res;
}
};
首先暴力的思想是直接四重循环求解，时间上肯定是会超时的，所以我们可以进行优化。这里的优化的关键点是选取中点进行分割两个数组，使用哈希表存储一半，然后枚举另一半。
引用一段总结：
看到形如：A+B....+N=0的式子，要转换为(A+…T)=-((T+1)…+N)再计算，这个T的分割点一般是一半，特殊情况下需要自行判断。定T是解题的关键
class Solution {
public:
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int>mp1;
for (int i = 0; i < nums1.size(); i ++) {
for (int j = 0; j < nums2.size(); j ++) {
mp1[nums1[i] + nums2[j]] ++;
}
}
int res = 0;
for (int i = 0; i < nums3.size(); i ++) {
for (int j = 0; j < nums4.size(); j ++) {
int t = -(nums3[i] + nums4[j]);
if (mp1.find(t) != mp1.end()) {
res += mp1[t];
}
}
}
return res;
}
};
15. 三数之和
暴力做法
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
unordered_map<int,int>mp;
vector<vector<int>> res;
int cnt = 0;
for (int i = 0; i < nums.size(); i ++) {
mp[nums[i]] = i;
}
for (int i = 0; i < nums.size(); i ++) {
for (int j = i + 1; j < nums.size(); j ++) {
int t = -(nums[i] + nums[j]);
if (mp.find(t) != mp.end() && mp[t] != i && mp[t] != j) {
vector<int>q;
q.push_back(nums[i]);
q.push_back(nums[j]);
q.push_back(t);
sort(q.begin(), q.end());
if (find(res.begin(), res.end(), q) == res.end()) res.push_back(q);
}
}
}
return res;
}
};
双指针+排序
单调性：排序后当a指针确定后，当b指针向右移动的时候（增大），c指针一定只会向左移动（减小）。并且c指针一定要大于b指针，因为我们是不重复枚举。
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); i ++) {
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
// 双指针处理剩下的b和c
int target = -nums[i];
int k = nums.size() - 1;
for (int j = i + 1; j < nums.size(); j ++) {
if (j > i + 1 && nums[j] == nums[j - 1]) {
continue;
}
while (j < k && nums[j] + nums[k] > target) {
k --;
}
if (j == k) break; // 一定不存在解
if (nums[j] + nums[k] == target) {
res.push_back({nums[i], nums[j], nums[k]});
}
}
}
return res;
}
};
和之前的三数之和是一样的
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
int n = nums.size();
for (int i = 0; i < n; i ++) {
if (i != 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n; j ++) {
if (j != i + 1 && nums[j] == nums[j - 1]) continue;
long long tar = target - (long long)(nums[i] + nums[j]);
int l = n - 1;
for (int k = j + 1; k < n; k ++) {
if (k != j + 1 && nums[k] == nums[k - 1]) continue;
while (k < l && (long long)nums[l] + nums[k] > tar) l --;
if (k == l) break;
if (nums[l] + nums[k] == tar) res.push_back({nums[i], nums[j], nums[k], nums[l]});
}
}
}
return res;
}
};
