【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 
            {
                // 得到了word
                if(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;
        // 得到minoffsetSum
        for(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 fin
          return 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;
    }
};