哈希表--剑指 Offer II 034. 外星语言是否排序&&剑指 Offer II 035. 最小时间差

剑指 Offer II 033. 变位词组

给定一个字符串数组 strs ，将 变位词 组合在一起。 可以按任意顺序返回结果列表。

**注意：**若两个字符串中每个字符出现的次数都相同，则称它们互为变位词

理解题意

题目是什么意思呢？通过阅读题目有点懵😵，不是特别清楚，我们看下样例1：

题目的意思是给一个字符串，去找在这个对应的长字符串中是否有它的变位词，如果有变位词，如果有变位词，则将他们放到一起

思路分析： 第一种解法：将单词映射到数字–106/114测试用例

1. 将每一个小写字母都映射到一个质数，如把’a’映射到数字2，把’b’映射到3，以此类推，以此类推映射26个小写的英文字母，每给出一组单词，就把单词中所有的字母对应的数字相乘，于是每个单词都可以算出一个数字
2. 如果两个单词互为变位词，那么它们中每个字母出现的次数都对应相同，由于乘法满足交换律，因为上述算法把一组变为此映射到同一个数值，由于每个字母都是映射到一个质数，因此不互为变位词的两个单词一定会映射到不同的数字
3. 因此我们可以顶一个哈希表，哈希表的键是单词中字母映射数字的乘积，而值为一组变位词。

如果输入有N个单词，平均每个单词有M个字母，那么该算法的时间复杂度为o(mn)

代码–会溢出

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        //如果用这种方法的话字符串太长就会无法存储，溢出
        int hash[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101};
        unordered_map<long long ,vector<string>>mp;
        for(auto s:strs){
            long long wordHash=1;
            for(int i=0;i<s.length();i++){
                wordHash*=hash[s[i]-'a'];
            }
            //在这里用一个数组来解决哈希冲突的模拟链地址法,这里的话是在后面插入，所以会跟题目的输出稍微有点不一样，目前我也解决不了这个问题
            mp[wordHash].emplace_back(s);
        }
        vector<vector<string>>ans;
        for(auto it=mp.begin();it!=mp.end();it++){
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

我们发现用质数是不可以的，我们数字用小一点，从0开始算一下试试-对于这道题

我们发现是不行是，会出现哈希冲突

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        int hash[]={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,26};
        unordered_map<long long ,vector<string>>mp;
        for(auto s:strs){
            long long wordHash=0;
            for(int i=0;i<s.length();i++){
                wordHash*=hash[s[i]-'a'];
            }
            //在这里用一个数组来解决哈希冲突的模拟链地址法
            mp[wordHash].emplace_back(s);
        }
        vector<vector<string>>ans;
        for(auto it=mp.begin();it!=mp.end();it++){
            ans.emplace_back(it->second);
        }
        return ans;
    }
};

这中方法不行，通过的样例更少了第一种还多一定，以我目前的能力搞不定了，换个方法吧，这道题搞了一个半小时，时间过得可真快

第2种解法：将单词的字母排序–通过

1. 将一组变位词映射到同一个单词。由于互为变为此的单词字母出现的次数分别相同，因此如果把单词中的字母排序就会得到相同的字符串。
2. 因此定义一个哈希表，哈希表的键是把单词所有字母排序得到的字符串，而其值为一组变位词

代码

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>>mp;
        for(auto s:strs){
            string k=s;
            //快速排序函数对s进行排序
            sort(k.begin(),k.end());
            //在这里要注意，排好序的是k，那么要加入的值是s ,不要像我一样，范错误将K给放进去孩子发现错了呀😭
            mp[k].push_back(s);
        }
        vector<vector<string>>arr;
        for(auto it=mp.begin();it!=mp.end();it++){
            arr.push_back(it->second);
        }
        return arr;
    }
};

剑指 Offer II 034. 外星语言是否排序 分析

1. 创建一个哈希表–其键值为字母表的每个字母，其对应的值为字母在字母表中的顺序
2. 让后进行对应的每个字母与其对应的值进行比较

如果输入n个单词，每个单词的平均长度为m，那么该算法的时间复杂度为o(mn)，空间复杂度是o(1)

代码

class Solution {
    int arr[26]{};
public:
    bool isAlienSorted(vector<string>& words, string order) {
        //用一个数组来模拟哈希-其键值为字母，其值为对应的i来记录其对应的位置
        for(int i=0;i<order.length();i++){
            arr[order[i]-'a']=i;
        }
        //在这里要注意，因为下面是比较words[i]与words[i+1]的值，所以上面是size-1
        for(int i=0;i<words.size()-1;i++){
            string s1=words[i],s2=words[i+1];
            if(!isSorted(words[i], words[i+1])){
                return false;
            }
        }
        return true;
    }
    bool isSorted(string &s1,string &s2){
        int i=0;
        for(;i<s1.length()&&i<s2.length();++i){
            //遍历两个单词，判断每个字母的位置，如果前一个单词的字母大于后面单词的字母那肯定不是按字典序排序的
            //如果小于那么肯定是按字典序排序的，如果大于肯定不是按照字典序排序的的，所以直接返回false
            //当单词相等的时候，继续判断下一个单词
            if(arr[s1[i]-'a']>arr[s2[i]-'a']){
                return false;
            }
            //只要其中一个单词的某个位置的字母在第二个之前那么就是有序的直接返回true 
            if(arr[s1[i]-'a']<arr[s2[i]-'a']){
                return true;
            }
        }
        //当前面单词的长度大于第2个单词时，返回第一个单词的长度
        return i==s1.size();
    }
};

剑指 Offer II 035. 最小时间差 分析：

1. 最直观的做法就是比较两个时间的间隔，然后得出最小的时间差。如果输入n的时间，那么需要计算每个时间与另外的n-1个时间的间隔，其时间复杂度就需要o(n^2)
2. 如果将直接排序之和，那么比较的话就只需要用(o(nlongn))
3. 如何来做优化：因为一天的时间为24个小时，1440分钟，我们可以使用一个长度为1440的数组来表示一天的时间，数组下标0表示的时间为00：00，下标为1的位置对应的时间为00：01,以此类推，数组中每个元素的是true或false来表示，表示对应的时间在数组当中
4. 因为数组下标表示的即为时间，所以数组下标差就是他们对应的时间差。
5. 在这里其实就是用一个数组来模拟了一个键为时间,值为true或false的哈希表，因此我们只需要一次扫描就可以得到最小的时间差，时间复杂度为o（1）

代码–哈希表的做法

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        bool tim[1440]{false};
        if(timePoints.size()>1440){
            return 0;
        }
        for(auto time:timePoints){
            //stoi：将字符串转换为10进制的整数
            // s.substr(pos, len)获取起始位置的第几个字符
            //那在时间中就是起始位置的第0个字符长度为2，起始地址为3长度为2
            int min=stoi(time.substr(0,2))*60+stoi(time.substr(3,2));
            //如果当中已经有这个对应的时间
            if(tim[min]){
                return 0;
            }
            //如果当中不存在对应的这个值，则将这个键的值改为true,表示有其对应的时间
            tim[min]=true;   
        }
       int mindiff=1440-1;//最大的时间差为1439
       //上一个时间点
       int prev=-1;
       //第一个时间点
       int first=mindiff;
       //最后一个时间点
       int last=-1;
       for(int i=0;i<1440;i++){
           //如果整整个时间存在
           if(tim[i]){
               //同时第一个时间点也是存在的
               //那么时间就等于i-prev与mindiff当中的最小值
               if(prev>=0){
                    mindiff=min(i-prev,mindiff);
               }
               //如果有对应的时间，那么更新上一个时间点
                prev=i;
                //同时记录第一个时间点和最后一个时间点，看两者是否在同一天
                first=min(i,first);
                last=max(i,last);
           }
       }
       //第一个时间点+1440表示第2天的同一个时间，求它与最后一个时间的时间差
       //例如["00:00","23:59","00:00"]
       mindiff=min(first+1440-last,mindiff);
       return mindiff;
    }
};

代码–排序做法-第一次出错（原因是第二天的时间排序到前面去了）

class Solution {
public:
    int findMinDifference(vector<string>& timePoints) {
        vector<int>tim;
        for(auto s:timePoints){
            //将时间换成分钟
            int minute=stoi(s.substr(0,2))*60+stoi(s.substr(3,2));
            //将时间保存到数组当中
            tim.push_back(minute);
        }
        //对时间进行队应的排序
        sort(tim.begin(),tim.end());
        int minDiff=1440;
        for(int i=1;i<tim.size();i++)
            minDiff=min(minDiff, tim[i]-tim[i-1]);
        return minDiff;
    }
};