哈希表增加部分题目

SherlockUnknowEn · SherlockUnknowEn · commit 21e5f8e1ff71 · 2023-01-13T16:26:00.000+08:00
diff --git a/哈希表/299.猜数字游戏.cpp b/哈希表/299.猜数字游戏.cpp
@@ -0,0 +1,37 @@
+/*
+ * @lc app=leetcode.cn id=299 lang=cpp
+ *
+ * [299] 猜数字游戏
+ */
+
+// @lc code=start
+class Solution {
+public:
+    string getHint(string secret, string guess) {
+        // 数字对了 - 数字和位置全对了
+        // 1. 数字 位置全对了
+        int count1 = 0;
+        // 2. 数字对了，不论顺序
+        int count2 = 0;
+        vector<int> m1(10);
+        vector<int> m2(10);
+        int n = secret.size();
+        for (int i = 0; i < n; i++) {
+            if (secret[i] == guess[i])
+            {
+                count1++;
+            }
+            m1[secret[i] - '0']++;
+            m2[guess[i] - '0']++;
+        }
+        for (size_t i = 0; i < 10; i++)
+        {
+            count2 += min(m1[i], m2[i]);
+        }
+        stringstream oss;
+        oss << count1 << "A" << count2 - count1 << "B";
+        return oss.str();
+    }
+};
+// @lc code=end
+
diff --git a/哈希表/347.前-k-个高频元素.cpp b/哈希表/347.前-k-个高频元素.cpp
@@ -0,0 +1,43 @@
+/*
+ * @lc app=leetcode.cn id=347 lang=cpp
+ *
+ * [347] 前 K 个高频元素
+ */
+
+// @lc code=start
+class Solution {
+public:
+    static bool cmp(const pair<int, int>& a, const pair<int, int>& b) {
+        return a.second > b.second;
+    }
+
+    vector<int> topKFrequent(vector<int>& nums, int k) {
+        // 记录num的出现次数
+        unordered_map<int, int> counting;
+        for (int a : nums) {
+            counting[a]++;
+        }
+        // 小顶堆，前 k 个频次最高的num
+        // &Solution::cmp 类型为 void (*ptr)(const pair<int, int>&, const pair<int, int>&)
+        // decltype(&Solution::cmp) 获取Solution::cmp函数的声明类型
+        priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&Solution::cmp)> heap(Solution::cmp);
+        for (auto& kv : counting) {
+            if (heap.size() < k)
+                heap.push(kv);
+             else if (heap.size() >= k && kv.second >= heap.top().second) {
+                heap.push(kv);
+                heap.pop();
+            }
+        }
+
+        vector<int> ans;
+        for (int i = 0; i < k; i++) {
+            ans.push_back(heap.top().first);
+            heap.pop();
+        }
+        return ans;
+    }
+
+};
+// @lc code=end
+
diff --git a/哈希表/387.字符串中的第一个唯一字符.cpp b/哈希表/387.字符串中的第一个唯一字符.cpp
@@ -0,0 +1,24 @@
+/*
+ * @lc app=leetcode.cn id=387 lang=cpp
+ *
+ * [387] 字符串中的第一个唯一字符
+ */
+
+// @lc code=start
+class Solution {
+public:
+    int firstUniqChar(string s) {
+        vector<int> memo(255);
+        for (char c : s) {
+            memo[c]++;
+        }
+        for (int i = 0; i < s.size(); i++) {
+            if (memo[s[i]] == 1) {
+                return i;
+            }
+        }
+        return -1;
+    }
+};
+// @lc code=end
+
diff --git a/哈希表/389.找不同.cpp b/哈希表/389.找不同.cpp
@@ -0,0 +1,22 @@
+/*
+ * @lc app=leetcode.cn id=389 lang=cpp
+ *
+ * [389] 找不同
+ */
+
+// @lc code=start
+class Solution {
+public:
+    char findTheDifference(string s, string t) {
+        char ans = 0;
+        for (char c : s) {
+            ans = ans ^ c;
+        }
+        for (char c : t) {
+            ans = ans ^ c;
+        }
+        return ans;
+    }
+};
+// @lc code=end
+
diff --git a/哈希表/409.最长回文串.cpp b/哈希表/409.最长回文串.cpp
@@ -0,0 +1,31 @@
+/*
+ * @lc app=leetcode.cn id=409 lang=cpp
+ *
+ * [409] 最长回文串
+ */
+
+// @lc code=start
+class Solution {
+public:
+    int longestPalindrome(string s) {
+        // 双数一定能构造
+        // 只能有一个单数
+        int odd = 0;
+        int ans = 0;
+        unordered_map<char, int> memo;
+        for (char c: s) {
+            memo[c]++;
+        }
+        for (auto& kv : memo) {
+            if (kv.second % 2 == 0) {
+                ans += kv.second;
+            } else {
+                odd = 1;
+                ans += kv.second - 1;
+            }
+        }
+        return ans + odd;
+    }
+};
+// @lc code=end
+
diff --git a/哈希表/438.找到字符串中所有字母异位词.cpp b/哈希表/438.找到字符串中所有字母异位词.cpp
@@ -0,0 +1,33 @@
+/*
+ * @lc app=leetcode.cn id=438 lang=cpp
+ *
+ * [438] 找到字符串中所有字母异位词
+ */
+
+// @lc code=start
+class Solution {
+public:
+    vector<int> findAnagrams(string s, string p) {
+        if (s.size() < p.size()) return {};
+        int k = p.size();
+        vector<int> mp(256);
+        vector<int> ms(256);
+        for (int i = 0; i < k; i++) {
+            mp[p[i]]++;
+            ms[s[i]]++;
+        }
+        vector<int> ans;
+        if (mp == ms) ans.push_back(0);
+        // 滑动窗口
+        for (int i = k; i < s.size(); i++) {
+            // 丢弃一个
+            ms[s[i-k]]--;
+            // 加入一个
+            ms[s[i]]++;
+            if (mp == ms) ans.push_back(i-k+1); 
+        }
+        return ans;
+    }
+};
+// @lc code=end
+
