LeetCode 242.有效的字母異位詞
題目：
給定兩個(gè)字符串?s?和?t?躬存，編寫(xiě)一個(gè)函數(shù)來(lái)判斷?t?是否是?s?的字母異位詞。若s?和?t?中每個(gè)字符出現(xiàn)的次數(shù)都相同舀锨，則稱s?和?t?互為字母異位詞岭洲。
思路：
首先定義一個(gè)數(shù)組，大小為26坎匿，每一個(gè)位置表示對(duì)應(yīng)的字母盾剩，例如0表示'a'......。字符串s中每出現(xiàn)一個(gè)字母替蔬，就將數(shù)組的對(duì)應(yīng)位置+1告私，這里尋找數(shù)組下標(biāo)的方法是s[i] -'a'，用相對(duì)距離尋找下標(biāo)承桥。同理驻粟，字符串每出現(xiàn)一個(gè)字母，就將更新完的數(shù)組對(duì)應(yīng)位置-1。最后判斷數(shù)組蜀撑，如果數(shù)組全部為0挤巡，則返回true，否則返回false酷麦。
代碼：
class Solution {
public:
? ? bool isAnagram(string s, string t) {
? ? int hash[26]={0};
? ? for(int i=0;i<s.size();i++)
? ? {
? ? ? ? hash[s[i]-'a']++;
? ? }
? ? for(int i=0;i<t.size();i++)
? ? {
? ? ? ? hash[t[i]-'a']--;
? ? }
? ? for(int i=0;i<26;i++)
? ? {
? ? ? ? if(hash[i]!=0)
? ? ? ? return false;
? ? }
? ? return true;
? ? }
};
LeetCode 349.兩個(gè)數(shù)組的交集
題目：
給定兩個(gè)數(shù)組?nums1?和?nums2?矿卑，返回?它們的交集?。
思路：
因?yàn)楣俜綄?duì)于輸入的nums大小有限制沃饶，這道題可以用set來(lái)解決母廷，也可以用數(shù)組來(lái)解決。
思路1：
用set來(lái)解決糊肤。要找到兩個(gè)數(shù)組的交集琴昆，相當(dāng)于在一個(gè)數(shù)組里面找到另一個(gè)數(shù)組的元素，為了找的更快馆揉，應(yīng)該采用哈希表來(lái)解決椎咧。同時(shí)因?yàn)橹挥梅祷亟患脑囟豢紤]重復(fù)的次數(shù)，所以這里用unordered_set把介。
代碼1：
class Solution {
public:
? ? vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
? ? unordered_set<int> temp;
? ? unordered_set<int> num_set(nums1.begin(),nums1.end());
? ? for(int num:nums2)
? ? {
? ? ? ? if(num_set.find(num)!=num_set.end())
? ? ? ? {
? ? ? ? ? ? temp.insert(num);
? ? ? ? }
? ? }
? ? vector<int> result(temp.begin(),temp.end());
? ? return result;
? ? }
};
思路2：
因?yàn)楸绢}給了限制勤讽，數(shù)組最大1000，所以也可以使用數(shù)組來(lái)解決拗踢。注意：如果沒(méi)有規(guī)定數(shù)組的大小脚牍、或者數(shù)組過(guò)大、或者數(shù)組的元素很分散（例如：1巢墅，2诸狭，1000000），這些情況用set來(lái)解決更高效君纫。
代碼2：
class Solution {
public:
? ? vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
? ? unordered_set<int> temp;
? ? int hash[1010]={0};
? ? for(int i=0;i<nums1.size();i++)
? ? {
? ? ? ? hash[nums1[i]]=1;
? ? }
? ? for(int i=0;i<nums2.size();i++)
? ? {
? ? ? ? if(hash[nums2[i]]!=0)
? ? ? ? {
? ? ? ? ? ? temp.insert(nums2[i]);
? ? ? ? }
? ? }
? ? vector<int> result(temp.begin(),temp.end());
? ? return result;
? ? }
};
LeetCode 202.快樂(lè)數(shù)
題目：
編寫(xiě)一個(gè)算法來(lái)判斷一個(gè)數(shù)?n?是不是快樂(lè)數(shù)驯遇。「快樂(lè)數(shù)」定義為：對(duì)于一個(gè)正整數(shù)，每一次將該數(shù)替換為它每個(gè)位置上的數(shù)字的平方和蓄髓。然后重復(fù)這個(gè)過(guò)程直到這個(gè)數(shù)變?yōu)?1叉庐，也可能是?無(wú)限循環(huán)?但始終變不到 1。如果這個(gè)過(guò)程?結(jié)果為1会喝，那么這個(gè)數(shù)就是快樂(lè)數(shù)陡叠。如果?n?是?快樂(lè)數(shù)?就返回?true?；不是肢执，則返回?false?枉阵。
思路：
這道題的關(guān)鍵是“無(wú)線循環(huán)”，當(dāng)平方和sum不是1時(shí)预茄，函數(shù)則會(huì)陷入死循環(huán)兴溜，應(yīng)該找到一個(gè)終止的條件：保存每次sum的值，如果sum的值在之后的更新中一直不是1且又出現(xiàn)了，那說(shuō)明這個(gè)數(shù)一定不是快樂(lè)數(shù)拙徽，此時(shí)就可以返回false了刨沦，而判斷sum值是否重復(fù)，可以使用哈希表來(lái)搜索斋攀。
代碼：
class Solution {
public:
int getsum(int n)
? ? {
? ? ? ? int sum =0;
? ? ? ? while(n)
? ? ? ? {
? ? ? ? ? ? sum+=(n%10)*(n%10);
? ? ? ? ? ? n/=10;
? ? ? ? }
? ? ? ? return sum;
? ? }
? ? bool isHappy(int n) {
? ? unordered_set<int> result;
? ? int sum=0;
? ? while(1)
? ? {
? ? ? ? sum=getsum(n);
? ? ? ? if(sum==1)
? ? ? ? {
? ? ? ? ? ? return true;
? ? ? ? }
? ? ? ? if(result.find(sum)==result.end())
? ? ? ? {
? ? ? ? ? ? result.insert(sum);
? ? ? ? }else{
? ? ? ? ? ? return false;
? ? ? ? }
? ? ? ? n=sum;
? ? }
? ? }
};
LeetCode 1.兩數(shù)之和
題目：
給定一個(gè)整數(shù)數(shù)組?nums和一個(gè)整數(shù)目標(biāo)值?target，請(qǐng)你在該數(shù)組中找出?和為目標(biāo)值?target? 的那?兩個(gè)?整數(shù)梧田，并返回它們的數(shù)組下標(biāo)淳蔼。
思路：
暴力的解法是用兩層for循環(huán)下通過(guò)兩個(gè)數(shù)相加得到target的值。如果采用哈希法裁眯，用一個(gè)指針指向當(dāng)前的數(shù)值鹉梨，那么target減去當(dāng)前的數(shù)值就能得到我們需要找到的數(shù)值，通過(guò)哈希法在當(dāng)前數(shù)值之前搜索我們需要的數(shù)值就能找到問(wèn)題的解穿稳，這樣就避免了使用for循環(huán)查找存皂，復(fù)雜度就減小了。值得注意的是逢艘，首先因?yàn)槲覀円４婷恳粋€(gè)遍歷的數(shù)值以及下標(biāo)旦袋，所以采用map結(jié)構(gòu)；其次map的搜索是針對(duì)key值搜索它改，所以應(yīng)該把數(shù)值賦給key疤孕，而下標(biāo)值賦給value。
代碼：
class Solution {
public:
? ? vector<int> twoSum(vector<int>& nums, int target) {
? ? std::unordered_map<int,int> res;
? ? for(int i=0;i<nums.size();i++)
? ? {
? ? ? ? auto it=res.find(target-nums[i]);
? ? ? ? if(it!=res.end())
? ? ? ? {
? ? ? ? ? ? return {it->second,i};
? ? ? ? }
? ? ? ? res.insert(pair<int, int>(nums[i], i));
? ? }
? ? return {};
? ? }
};
