目錄

?兩數(shù)之和

面試題 01.02. 判定是否互為字符重排

?存在重復(fù)元素

?存在重復(fù)元素 II

字母異位詞分組

---

兩數(shù)之和

?1. 兩數(shù)之和

思路1：兩層for循環(huán)

思路2：逐步添加哈希表

思路3：一次填完哈希表

? ? ? ? ? ? ? 如果一次填完，那么相同元素的值，所映射的下標(biāo)是最后一個(gè)的，然而并不會導(dǎo)致代碼出問題，不管? i? 是正向還是反向遍歷，原因1：只需要能找到num的下標(biāo)就行；2：對于num = target / 2 時(shí) ，當(dāng)前元素不影響，說結(jié)果就是這里的覆蓋并不影響，因?yàn)樗悸?也是會覆蓋掉之前出現(xiàn)過的元素

? ? ? ? ? ? ? 細(xì)節(jié)：當(dāng)前下標(biāo)不能和?hash[num] 相同 反例：{1?，3， 4} target = 6，也就是當(dāng)前元素只有一個(gè)，且為 target / 2這時(shí)候可能出錯(cuò)

?參考代碼2

class Solution1 {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;hash[nums[0]] = 0;for (int i = 1; i < nums.size(); i++){int num = target - nums[i];if (hash.count(num)) return { hash[num], i };hash[nums[i]] = i;}return { -1, -1 };}
};

?參考代碼3

class Solution1 {
public:vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;int n = nums.size();for (int i = 0; i < n; i++)hash[nums[i]] = i;//for (int i = 0; i < n; i++)for (int i = n - 1; i >= 0; i--){int num = target - nums[i];if (hash.count(num) && hash[num] != i)return { i, hash[num] };}return { -1, -1 };}
};

面試題 01.02. 判定是否互為字符重排

?面試題 01.02. 判定是否互為字符重排

?

?思路1：兩個(gè)數(shù)組，一個(gè)去比較另一個(gè)

?思路2：一個(gè)數(shù)組，去比較0

?思路3：sort排序string， sort要求是的一個(gè)可以下標(biāo)隨機(jī)訪問的容器，string重載了[]

參考代碼 兩個(gè)數(shù)組

class Solution {
public:bool CheckPermutation(string s1, string s2) {if (s1.size() != s2.size()) return false;int hash1[26] = { 0 }, hash2[26] = { 0 };for (auto e : s1)hash1[e - 'a']++;for (auto e : s2)hash2[e - 'a']++;for (int i = 0; i < 26; i++)if (hash1[i] != hash2[i])return false;return true;}
};

一個(gè)數(shù)組

class Solution {
public:bool CheckPermutation(string s1, string s2) {if (s1.size() != s2.size()) return false;int hash[26] = { 0 };for (auto e : s1)hash[e - 'a']++;for (auto e : s2)//也可以在里面判斷hash[e - 'a']--;for (int i = 0; i < 26; i++)if (hash[i] < 0) return false;return true;}
};

?sort

class Solution {
public:bool CheckPermutation(string s1, string s2) {if (s1.size() != s2.size()) return false;sort(s1.begin(), s1.end());sort(s2.begin(), s2.end());return s1 == s2;}
};

?存在重復(fù)元素

?217. 存在重復(fù)元素

參考代碼

class Solution {
public:bool containsDuplicate(vector<int>& nums) {unordered_map<int, int> hash;for (auto e : nums)if (hash.count(e)) return true;else hash[e]++;return false;}
};

?存在重復(fù)元素 II

219. 存在重復(fù)元素 II

參考代碼

class Solution {
public:bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash;for(int i = 0; i < nums.size(); i++){if(hash.count(nums[i]) && hash[nums[i]] + k >= i) return true;hash[nums[i]] = i;}return false;}
};

字母異位詞分組

49. 字母異位詞分組

?

對于往ret里壓數(shù)據(jù)，是參考資料的，原來是這么想的，但是不對，hash只會用一點(diǎn)，還沒學(xué)。。

參考代碼

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {unordered_map<string, vector<string>> hash;for(auto e : strs){string tmp = e;sort(tmp.begin(), tmp.end());hash[tmp].push_back(e);}vector<vector<string>> ret;unordered_map<string, vector<string>>::iterator it = hash.begin();while (it != hash.end()){ret.push_back(it->second);++it;}return ret;}
};