目录
LeetCode349 easy
LeetCode350 easy
LeetCode242 easy
LeetCode202 easy
LeetCode290 easy
LeetCode205 easy
LeetCode451 medium
LeetCode349 easy
方法1：使用set
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result; //保存结果，为了去重，所以用set
unordered_set<int> nums(nums1.begin(),nums1.end()); //将nums1变成set
for(int num:nums2) //遍历nums2中的元素
{
if(nums.find(num)!=nums.end())
{
result.insert(num); //如果找到就放到结果集合中
}
}
return vector<int>(result.begin(),result.end()); //将set变成vector
}
};LeetCode350 easy
方法1：使用unordered_map
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> um;
vector<int> res;
for(auto temp:nums1)
{
um[temp]++;
}
for(auto temp:nums2)
{
if(um[temp]>0)
{
res.push_back(temp);
um[temp]--;
}
}
return res;
}
};方法2：排序+双指针
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
sort(nums1.begin(), nums1.end());
sort(nums2.begin(), nums2.end());
int length1 = nums1.size(), length2 = nums2.size();
vector<int> intersection;
int index1 = 0, index2 = 0;
while (index1 < length1 && index2 < length2) {
if (nums1[index1] < nums2[index2]) {
index1++;
} else if (nums1[index1] > nums2[index2]) {
index2++;
} else {
intersection.push_back(nums1[index1]);
index1++;
index2++;
}
}
return intersection;
}
};LeetCode242 easy
class Solution {
public:
bool isAnagram(string s, string t) {
int s1=s.size();
int s2=t.size();
if(s1!=s2)
{
return false;
}
int res[26]={0};
for(auto c:s)
{
res[c-'a']++;
}
for(auto c:t)
{
res[c-'a']--;
}
for(auto c:res)
{
if(c!=0)
return false;
}
return true;
}
};
LeetCode202 easy
方法1：使用快慢指针
class Solution {
public:
int bitSquareSum(int n) { //求n的各位数字的平方和
int sum = 0;
while(n > 0)
{
int bit = n % 10;
sum += bit * bit;
n = n / 10;
}
return sum;
}
bool isHappy(int n) {
int slow = n, fast = n;
do{
//慢指针走一步
slow = bitSquareSum(slow);
//快指针走两步
fast = bitSquareSum(fast);
fast = bitSquareSum(fast);
}while(slow != fast);
return slow == 1; //判断是否是因为1导致的循环
}
};
LeetCode290 easy
class Solution {
public:
bool wordPattern(string pattern, string s) {
unordered_map<string,char> str2ch; //保存str到ch的映射
unordered_map<char,string> ch2str; //保存ch到str的映射
int m=s.length(); //字符串的长度
int i=0; //s的索引
for(auto ch:pattern)
{
if(i>=m) //pattern还没结束，但是s已经结束
{
return false;
}
int j=i; //从i开始找下一个空格或者末尾
while(j<m && s[j]!=' ')
j++;
string tmp=s.substr(i,j-i); //截取子串
if(str2ch.count(tmp) && str2ch[tmp]!=ch) //有别的ch对应tmp
{
return false;
}
if(ch2str.count(ch) && ch2str[ch]!=tmp) //ch对应别的tmp
{
return false;
}
str2ch[tmp]=ch;
ch2str[ch]=tmp;
i=j+1;
}
return i>=m;
}
};
LeetCode205 easy
class Solution {
public:
bool isIsomorphic(string s, string t) {
int len1=s.size();
int len2=t.size();
if(len1!=len2) //如果字符串s和t的长度不相等
{
return false;
}
unordered_map<char,char> s2t; //s到t的映射
unordered_map<char,char> t2s; //t到s的映射
for(int i=0;i<len1;i++) //逐个比较
{
if(s2t.count(s[i]) && s2t[s[i]] != t[i]) //s[i]对应的不是t[i]
{
return false;
}
else if(t2s.count(t[i]) && t2s[t[i]]!=s[i]) //t[i]对应的不是s[i]
{
return false;
}
else
{ //添加到map
s2t[s[i]]=t[i];
t2s[t[i]]=s[i];
}
}
return true;
}
};
LeetCode451 medium
方法1：哈希表+排序
struct node{
char ch;
int cnt;
node(){
ch = '0';
cnt = 0;
}
bool operator<(const node& o)const{
return cnt > o.cnt;
}
};
class Solution {
public:
string frequencySort(string s) {
vector<node> hash(256);
for(auto x : s){
hash[x].ch = x;
hash[x].cnt++;
}
sort(hash.begin(),hash.end());
string ans;
for(auto x : hash){
if(x.cnt){
ans += string(x.cnt,x.ch);
}
}
return ans;
}
};方法2：桶排序
class Solution {
public:
string frequencySort(string s) {
unordered_map<char, int> map;
int maxCount(0);
for (char c: s)
maxCount = max(maxCount, ++map[c]);
vector<vector<int>> buckets(maxCount + 1);
for (auto i(map.begin()); i != map.end(); i++)
buckets[i->second].push_back(i->first);
string ans;
//有maxCount个频次桶
for (int i(maxCount); i >= 1; i--)
//对频次桶里的元素进行遍历，换言之，这个桶里的元素频次一样
for (int j(0); j < buckets[i].size(); j++) {
//把这个字母放到ans中i次，也就是频次次
for (int z(0); z < i; z++)
ans.push_back(buckets[i][j]);
}
return ans;
}
};
