贖金信

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {// 小寫字母int r_cnt[26];int m_cnt[26];for(int i = 0; i< magazine.size(); i++) {m_cnt[magazine[i]-'a']++; // 統計}// 對比for(int i = 0; i< ransomNote.size(); i++) {if(m_cnt[ransomNote[i]-'a']) {m_cnt[ransomNote[i]-'a']--;} else {return false;}}return true;}
};

class Solution {
public:bool canConstruct(string ransomNote, string magazine) {// 小寫字母int r_cnt[26];int m_cnt[26];for(int i = 0; i< magazine.size(); i++) {m_cnt[magazine[i]-'a']++; // 統計}// 對比for(int i = 0; i< ransomNote.size(); i++) {if(m_cnt[ransomNote[i]-'a']) {m_cnt[ransomNote[i]-'a']--;} else {return false;}}return true;}
};

同構字符串

class Solution {
public:bool isIsomorphic(string s, string t) {unordered_map<char,char> s_map;unordered_map<char,char> t_map;int s_size = s.size();int t_size = t.size();if(s_size != t_size) {return false;} for(int i = 0; i< s_size; i++) {char x = s[i];char y = t[i];if((s_map.count(x) && s_map[x] != y) || (t_map.count(y) && t_map[y] != x)) {return false;}s_map[x] = y;t_map[y] = x;}return true;    }
};

收獲

了解了一下 有關于 unordered_map 中 count 函數的使用
s_map.count(x) 就是 鍵為 x 的個數

逐步解析

方法二
思路

通過 match 建立關系
通過 count 記錄 t[i] 是否已經有映射

這部分是表示, 不存在 s[i] 的映射, 但是發現 t[i] 已經做好映射了 ( count[t[i]] > 0 ) 直接返回 false

  			if (match[s[i]] == '\0') { // 如果當前字符沒有映射關系if (count[t[i]] == 0) { // 如果當前字符在t中沒有出現過match[s[i]] = t[i]; // 建立映射關系count[t[i]] = 1; // 將該字符在t中的出現次數加1}elsereturn false; // 如果當前字符在t中已經出現過，則返回false}

圖解

class Solution {
public:bool isIsomorphic(string s, string t) {unordered_map<char, char> match; // 用于存儲字符之間的映射關系unordered_map<char, int> count; // 用于記錄字符在t中出現的次數for (int i = 0; i < s.size(); i++) {if (match[s[i]] == '\0') { // 如果當前字符沒有映射關系if (count[t[i]] == 0) { // 如果當前字符在t中沒有出現過match[s[i]] = t[i]; // 建立映射關系count[t[i]] = 1; // 將該字符在t中的出現次數加1}elsereturn false; // 如果當前字符在t中已經出現過，則返回false}else { // 如果當前字符已經有映射關系if (match[s[i]] != t[i]) { // 如果映射關系不正確return false; // 返回false}}}return true; // 所有字符都滿足同構條件，返回true}
};

class Solution {
public:bool wordPattern(string pattern, string s) {unordered_map<string,char> s_patterMap;unordered_map<char, string> pattern_sMap;// 遍歷int p_len = pattern.size();int left = 0;int right = 0;for(int i = 0; i< p_len ; i++) {if(left >= s.size()) {return false;}// 遍歷while(right < s.size() && s[right] != ' ') right++;// 右邊界 right string str = s.substr(left, right-left);if(s_patterMap.count(str) && s_patterMap[str] != pattern[i]) {return false;}if(pattern_sMap.count(pattern[i]) && pattern_sMap[pattern[i]] != str) {return false;}s_patterMap[str] = pattern[i];pattern_sMap[pattern[i]] = str;left = right + 1;right = left;}if(right < s.size()) {return false;} else {return true;}}
};

有效的字母異位詞

方法一: 使用長度為 26 的數組對 小寫字母進行統計

class Solution {
public:bool isAnagram(string s, string t) {// 用數組統計字母次數就可以了int s_char[26];int t_char[26];for(int i = 0; i< s.size(); i++) {s_char[s[i] - 'a']++;} for(int i = 0; i< t.size() ; i++) {t_char[t[i] - 'a'] ++;}for(int i = 0; i< 26; i++) {if(s_char[i] != t_char[i]) {return false;}}return true;}
};

方法二: 使用 unordered_map 進行統計

• 對比字符串長度
• 記錄一個字符串字母組成
• 遍歷另外一個字符串, 然后做減法

class Solution {
public:bool isAnagram(string s, string t) {unordered_map<char,int> s_char;// 長度對比if(s.size() != t.size()) {return false;}for(int i = 0; i< s.size(); i++) {s_char[s[i]]++;} // 遍歷 t 字符串for(auto c : t){if(--s_char[c] < 0) return false;}   return true;}
};

49. 字母異位分組

注意:

這里有個很好的思路, 如果是相同字母組成的單詞, 對單詞進行排序后, 肯定是相等, 所以通過遍歷,然后對單詞排序,
然后加入到 unordered_map<string, vector> 中就 , 后面就是對 unordered_map 進行遍歷

要點
① 對一個單詞進行排序

string str = "afdaf";
sort(str.begin(), str.end())

② 對 unordered_map<string , vector> 操作
加入

mp[key].emplace_back(strs[i]);

③ 對 unordered_map<string, vector> 遍歷操作

for(auto pair: mp) {vector<string> values = pair.second;for(auto value: values) {cout<<value<<endl;}// ......
}

class Solution {
public:vector<vector<string>> groupAnagrams(vector<string>& strs) {// 分組vector<vector<string>> result; // 結果if(strs.size() == 0  || strs.size() == 1) {result.push_back(strs);return result;}// 如果是同一組字母組成的單詞, 排序后 可以畫上等號unordered_map<string, vector<string>> mp; // 表示一種組合 所有單詞 后面表示字符數組for(int i = 0; i< strs.size() ; i++) {string key = strs[i];sort(key.begin(), key.end());mp[key].emplace_back(strs[i]);}// 遍歷 這個 mapfor(auto pair: mp) {result.emplace_back(pair.second);}return result;}
};

兩數之和

class Solution {
public:vector<int> twoSum(vector<int>& nums, int target) {// unordered_map<int,int> value;for(int i = 0; i< nums.size(); i++) {if(value.find(target - nums[i]) != value.end()) {auto it = value.find(target - nums[i]);return {it->second,i};}value[nums[i]] = i;}return {};}
};

思考: 如果不止一種結果,代碼又是如何寫呢???