【leetcode算法300】：哈希板块

哈希表板块

快乐数

leetcode

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。

思路

我们判断要么出现循环，要么出现一，不可能不出现循环且不唯一，因为不可能一直增大。对于三位数及以上，每个为的平方和最多为99 * n, 显然是有限的。

class Solution {
public:int getNextNum(int n){int ret = 0;while(n){int tmp = n % 10;n /= 10;ret += (tmp * tmp);}return ret;}bool isHappy(int n) {// 看是否存在循环std::unordered_set<int> cache;while(n != 1){cache.insert(n);n = getNextNum(n);if(cache.count(n)) return false;}return true;}
};

计数质数

(leetcode)[https://leetcode.cn/problems/count-primes/description/]

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

思路

这是一道很好的题目，利用厄拉多塞筛法, 可以看看这个思路，最经典的就是从i * i向后填充，保证了时间复杂度为o(n)左右吧

class Solution {
public:int countPrimes(int n) {std::vector<int> isPrime(n, 1);int count = 0;for(long long i = 2; i < n;i++){if(isPrime[i] == 1) {count++;long long j = i * i;for(;j < n;j += i)isPrime[j] = 0;}}return count;}
};

同构字符串

给定两个字符串 s 和 t ，判断它们是否是同构的。

如果 s 中的字符可以按某种映射关系替换得到 t ，那么这两个字符串是同构的。

每个出现的字符都应当映射到另一个字符，同时不改变字符的顺序。不同字符不能映射到同一个字符上，相同字符只能映射到同一个字符上，字符可以映射到自己本身。

单词规律

(leetcode)[https://leetcode.cn/problems/word-pattern/description/]

给定一种规律 pattern 和一个字符串 s ，判断 s 是否遵循相同的规律。

这里的 遵循 指完全匹配，例如， pattern 里的每个字母和字符串 s 中的每个非空单词之间存在着双向连接的对应规律。

示例1:

输入: pattern = “abba”, s = “dog cat cat dog”
输出: true
示例 2:

输入:pattern = “abba”, s = “dog cat cat fish”
输出: false
示例 3:

输入: pattern = “aaaa”, s = “dog cat cat dog”
输出: false

class Solution {
public:bool wordPattern(string pattern, string s) {std::unordered_map<char,string> map1;std::unordered_map<string,char> map2;int i = 0; // i表示所处的pattern的下标s.push_back(' ');string word;for(int j = 0;j < s.size();j++){if(s[j] != ' ') word.push_back(s[j]);else {// 得到了wordif(i >= pattern.size()) return false; // 长度不匹配// 处理从左往右if(map1.count(pattern[i]) && map1[pattern[i]] != word) return false;else if(!map1.count(pattern[i])) map1[pattern[i]] = word; // 处理从右往左if(map2.count(word) && map2[word] != pattern[i]) return false;else if(!map2.count(word)) map2[word] = pattern[i];i++;word = "";}}return i == pattern.size();}
};

字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

class Solution {
public:int firstUniqChar(string s) {int arr[26] = { 0 };memset(arr,0,26);for (auto e : s) {++arr[e - 'a'];}for(size_t i = 0;i < s.size();i++){if(arr[s[i] - 'a'] == 1){return i;}}return -1;}
};

最长的和谐数组

和谐数组是指一个数组里元素的最大值和最小值之间的差别 正好是 1 。

给你一个整数数组 nums ，请你在所有可能的 子序列 中找到最长的和谐子序列的长度。

数组的 子序列 是一个由数组派生出来的序列，它可以通过删除一些元素或不删除元素、且不改变其余元素的顺序而得到

class Solution {
public:int findLHS(vector<int>& nums){std::map<int,int> Counter;for(auto num : nums) Counter[num]++;auto it = Counter.begin();int maxLen = 0;while(it != Counter.end()){auto next = it;++next;// if(next != Counter.end() && next->first - it->first == 1) maxLen = std::max(maxLen, it->second + next->second);it = next;}return maxLen;}
};

两个列表的最小索引总和

给定两个字符串数组 list1 和 list2，找到 索引和最小的公共字符串。

公共字符串 是同时出现在 list1 和 list2 中的字符串。

具有 最小索引和的公共字符串 是指，如果它在 list1[i] 和 list2[j] 中出现，那么 i + j 应该是所有其他 公共字符串 中的最小值。

返回所有 具有最小索引和的公共字符串。以 任何顺序 返回答案

class Solution {
public:struct Value{int first_offset = -1;int second_offset = -1;};vector<string> findRestaurant(vector<string>& list1, vector<string>& list2) {unordered_map<string,Value> ump;for(int i = 0;i < list1.size();i++){ump[list1[i]].first_offset = i;}int minoffsetSum = INT32_MAX;// 得到minoffsetSumfor(int i = 0;i < list2.size();i++){if(ump.count(list2[i]) == false) continue;auto& val = ump[list2[i]];val.second_offset = i;if(val.first_offset + val.second_offset < minoffsetSum){minoffsetSum = val.first_offset + val.second_offset;}}std::vector<string> ret;if(minoffsetSum != INT32_MAX){for(auto& val : ump){if(val.second.second_offset != -1 && val.second.first_offset + val.second.second_offset == minoffsetSum) ret.push_back(list1[val.second.first_offset]);}}   return ret;}
};

错误的集合

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复 。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

class Solution {
public:vector<int> findErrorNums(vector<int>& nums) {std::vector<int> rmDup(nums.size() + 1, 0);int lose = -1, dup = -1;for(auto i : nums){if(rmDup[i] == 1) dup = i;else rmDup[i] = 1;}for(int i = 1;i < rmDup.size();i++)if(rmDup[i] == 0) lose = i;return { dup, lose };}
};

词典中最长的单词

leetcode

给出一个字符串数组 words 组成的一本英语词典。返回能够通过 words 中其它单词逐步添加一个字母来构造得到的 words 中最长的单词。

若其中有多个可行的答案，则返回答案中字典序最小的单词。若无答案，则返回空字符串。

请注意，单词应该从左到右构建，每个额外的字符都添加到前一个单词的结尾。

class Solution {
public:static bool cmpStr(const std::string& l,const std::string& r){return l.size() < r.size();}string longestWord(vector<string>& words) {sort(words.begin(), words.end(),cmpStr);if(words[0].size() != 1) return "";int curSize = 1;std::vector<unordered_set<string>> cache(32); for(int i = 0; i < words.size(); i++){auto& curStr = words[i];if(curStr.size() == 1) cache[curStr.size()].insert(curStr);else{if(cache[curStr.size() - 1].count(curStr.substr(0, curStr.size() - 1)))cache[curStr.size()].insert(curStr);}}for(int i = 0;i < cache.size();i++){std::cout << "lenth:" << i << " ";for(auto& str : cache[i])std::cout << str << " ";std::cout << std::endl;}auto rit = cache.rbegin();string ret = "";while(rit != cache.rend()){auto& hash = *rit;if(hash.size()) {auto it = std::min_element(hash.begin(), hash.end());ret = *it;break;}rit++;}return ret;}
};

强整数

给定三个整数 x 、 y 和 bound ，返回 值小于或等于 bound 的所有 强整数 组成的列表 。

如果某一整数可以表示为 xi + yj ，其中整数 i >= 0 且 j >= 0，那么我们认为该整数是一个 强整数 。

你可以按 任何顺序 返回答案。在你的回答中，每个值 最多 出现一次。

思路

version1.0

我的第一个版本，因为，涉及到指数，他的指数的最大值不会太大，所以，我才去遍历所有的可能性。

class Solution {
public:void createPosibleArray(std::vector<int>& array, int base, int inf){array.push_back(1);if(base == 1) return;else {int i = base;for(;i <= inf;i *= base)array.push_back(i);}}vector<int> powerfulIntegers(int x, int y, int bound) {std::vector<int> posible_x, posible_y;createPosibleArray(posible_x, x, bound);createPosibleArray(posible_y, y, bound);for(auto i : posible_x) std::cout << i << " ";std::cout << std::endl;for(auto j : posible_y) std::cout << j << " ";std::cout << std::endl;std::unordered_set<int> rmDup;for(int i = 0;i < posible_x.size();i++){for(int j = 0;j < posible_y.size();j++){if(posible_x[i] + posible_y[j] <= bound)rmDup.insert(posible_x[i] + posible_y[j]);}}std::vector<int> ret;std::copy(rmDup.begin(), rmDup.end(), std::back_inserter(ret));return ret;}
};

无重复的的最长子串

leetcode

给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。

思路

经典的滑动窗口问题

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 };int Max = -INT_MAX;for(int left = 0, right = 0;right < s.size();right++){char cur = s[right];hash[cur]++;// 保证窗口的合法性if(hash[cur] >= 2){while(hash[cur] >= 2){hash[s[left++]]--;}}// 更新结果Max = std::max(Max,right - left + 1);}return Max == -INT_MAX ? 0 : Max;}
};

数组中的第K大的做大元素

给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。

请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。‘

• 思路一: 小根堆

  class Solution {
  public:int findKthLargest(vector<int>& nums, int k) {priority_queue<int, vector<int>, greater<int>> res;for (auto& a : nums) {res.push(a);if (res.size() > k)res.pop();}return res.top();}};
  

• 思路二 ： 分治的思想
  时间复杂度由于堆，为o(n),但是更急复杂。

  class Solution {
  public:Solution(){srand(time(nullptr));}int findKthHelper(vector<int>& nums, int begin, int end, int k){int random = nums[begin + rand() % (end - begin + 1)];int left = begin - 1, right = end + 1;for(int cur = begin; cur < right;){if(nums[cur] > random) std::swap(nums[++left], nums[cur++]);else if(nums[cur] == random) cur++;else std::swap(nums[--right], nums[cur]);}int a = left - begin + 1;int c = end - right + 1;int b = end - begin + 1 - a - c;//if(k <= a) return findKthHelper(nums,begin,left,k);else if(k <= a + b) return random;else return findKthHelper(nums, right, end, k - a - b);}int findKthLargest(vector<int>& nums, int k) {// 得到一个随机数 nums[random() % size]// a个数 < random b个数 = radom  c个数 > random// if k <= a finreturn findKthHelper(nums,0, nums.size() - 1, k);}};
  

前k个高频词

给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

思路

思路还是使用小根堆的思想

class Compare
{
public: bool operator()(const pair<int,int>& l,const pair<int,int>& r){return l.second > r.second;}
};
class Solution {
public:vector<int> topKFrequent(vector<int>& nums, int k) {unordered_map<int,int> Counter;for(auto num : nums)++Counter[num];std::priority_queue<std::pair<int,int>,std::vector<std::pair<int,int>>, Compare> pque;for(auto& val : Counter) {if(pque.size() < k) pque.push(val);else{auto& top_size = pque.top().second;if(val.second > top_size){pque.pop();pque.push(val);}}}std::vector<int> ret;while(pque.size()){auto t = pque.top();pque.pop();ret.push_back(t.first);}return ret;}
};

o(1)时间插入删除，获取随机元素

leetcode

实现RandomizedSet 类：

RandomizedSet() 初始化 RandomizedSet 对象
bool insert(int val) 当元素 val 不存在时，向集合中插入该项，并返回 true ；否则，返回 false 。
bool remove(int val) 当元素 val 存在时，从集合中移除该项，并返回 true ；否则，返回 false 。
int getRandom() 随机返回现有集合中的一项（测试用例保证调用此方法时集合中至少存在一个元素）。每个元素应该有 相同的概率 被返回。
你必须实现类的所有函数，并满足每个函数的 平均 时间复杂度为 O(1) 。

思路

插入删除的时间复杂度为o(1),所以一定会使用到hash，但是为了解决随机返回，我们还需要使用支持通过下标访问,vector, 所以我们通过hash存储索引, 删除的时候，我们将删除的位置和最后一个位置进行交换，然后进行pop_back, 因为vector::erase的成本过高，o(n)

class RandomizedSet {
public:RandomizedSet() {srand(time(nullptr));   }bool insert(int val) {if(hash_.count(val)) return false;hash_[val] = array_.size();array_.push_back(val);return true;}bool remove(int val) {if(hash_.count(val) == false) return false;auto pos = hash_[val];if(array_.size() > 1) {hash_[array_.back()] = pos;std::swap(array_[pos], array_[array_.size() - 1]);}array_.pop_back();    hash_.erase(val);return true;}int getRandom(){int randomPos = rand() % array_.size();return array_[randomPos];}
private:std::unordered_map<int,int> hash_;std::vector<int> array_;
};

根据字符串的频率排序

给定一个字符串 s ，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。

返回 已排序的字符串 。如果有多个答案，返回其中任何一个。

思路

我们记录通过hash进行记录，然后利用序列化容器排序，自定义排序机制。

class Solution {
public:struct Value{Value(char ch_,int frequency_) : ch(ch_), frequency(frequency_){}char ch;int frequency;};static bool compare(const Value& l,const Value& r){if(l.frequency != r.frequency) return l.frequency > r.frequency;else return l.ch < r.ch;}string frequencySort(string s) {unordered_map<char,int> Counter;for(auto ch : s)Counter[ch]++;std::vector<Value> array;for(auto& pair : Counter)array.push_back(Value(pair.first,pair.second));sort(array.begin(), array.end(), compare);std::string res;for(auto& val : array)for(int i = 0;i < val.frequency;i++) res.push_back(val.ch);return res;}
};

单词替换

leetcode

在英语中，我们有一个叫做 词根(root) 的概念，可以词根 后面 添加其他一些词组成另一个较长的单词——我们称这个词为 衍生词 (derivative)。例如，词根 help，跟随着 继承词 “ful”，可以形成新的单词 “helpful”。

现在，给定一个由许多 词根 组成的词典 dictionary 和一个用空格分隔单词形成的句子 sentence。你需要将句子中的所有 衍生词 用 词根 替换掉。如果 衍生词 有许多可以形成它的 词根，则用 最短 的 词根 替换它。

你需要输出替换之后的句子。

class Solution {
public:void initCache(unordered_map<int,unordered_set<string>>& cache, vector<string>& dict){for(auto& str : dict){cache[str.size()].insert(str);}}// 从最短开始替换std::string isReplace(unordered_map<int,unordered_set<string>>& cache, const std::string& word){for(int size = 1; size < word.size();size++){if(cache[size].count(word.substr(0, size))) return word.substr(0, size);}return "";}string replaceWords(vector<string>& dictionary, string sentence) {std::string ret;unordered_map<int,unordered_set<string>> cache;// 初始化缓存initCache(cache, dictionary);    sentence.push_back(' ');std::string word = "";for(auto ch : sentence){if(ch != ' ') word.push_back(ch);else {// 切分字符串std::string rpStr = isReplace(cache, word);if(rpStr == "") ret.append(word + " ");else ret.append(rpStr + " ");word = "";}}ret.pop_back();return ret;}
};

最长的重复子数组

leetcode

给两个整数数组 nums1 和 nums2 ，返回 两个数组中 公共的 、长度最长的子数组的长度 。

思路

这道题目的思路很明显可以利用动态规划的思想，因为由于这里的子数组是连续的，我们可以假设dp[i][j]表示以nums1[i], nums[j]的结尾的两个的字符串的最长子数组, 同时子数组的结尾是i 和 j

• 构建状态转移方程

  假设i, j表示第i个位置，j个位置，而不是下标

  1. dp[i] == dp[j] dp[i][j] = dp[i - 1][j - 1] + 1
  2. dp[i] != dp[j] dp[i][j] = 0 // 表示他们是不能构成条件的

• 状态的初始化
  dp[0][j] = 0
  dp[i][j] = 0

代码

class Solution {
public:int findLength(vector<int>& nums1, vector<int>& nums2){int m = nums1.size(), n = nums2.size();// 创建dp表std::vector<std::vector<int>> dp(m + 1,std::vector<int>(n + 1,0));//初始化//int Max = 0;for(int i = 1;i <= m;i++){for(int j = 1;j <= n;j++){if(nums1[i - 1] == nums2[j - 1]) dp[i][j] = dp[i - 1][j - 1] + 1;else dp[i][j] = 0;Max = std::max(dp[i][j],Max);}}    return Max;}
};