Day68:49. 字母异位词分组、128. 最长连续序列

49.字母异位词分组

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

字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:

输入: strs = [""]
输出: [[""]]
示例 3:

输入: strs = ["a"]
输出: [["a"]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

这里是之前有效的字母异位词的延伸，但是之前的题是两个单词比较，因此创建一个26大小的数组先加后减就可以了，但这题要比较的是很多单词。我自己想的是思路是：

• 仿照之前的思路，为每一个字符编码，编码的是每一个字母的出现次数：

string encode(string s){
        vector<char> alphabet(26,0);
        for(char c: s){
            alphabet[c - 'a']++;
        }
        return string(alphabet.begin(),alphabet.end());
    }
1
2
3
4
5
6
7

注意这里打印时打印不出来的，因为编码后不一定是可读字符。

• 创建一个unordered_map> codeGroup，用来存放相同编码的字符串；
• 把unordered_map转化为vector。

最终代码：

class Solution {
public:
    string encode(string s){
        vector<char> alphabet(26,0);
        for(char c: s){
            alphabet[c - 'a']++;
        }
        return string(alphabet.begin(),alphabet.end());
    }
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string,vector<string>> codeGroup;
        for(string str: strs){
            string code = encode(str);
            codeGroup[code].push_back(str);
        }
        vector<vector<string>> res;
        for(auto dict : codeGroup){
            res.push_back(dict.second);
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

128. 最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

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

示例 1：

输入：nums = [100,4,200,1,3,2]
输出：4
解释：最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2：

输入：nums = [0,3,7,2,5,8,4,6,0,1]
输出：9
1
2
3
4
5
6
7
8
9
10
11
12
13

首先这题没办法排序，因为排序算法的时间复杂度最少都是O(NlogN)，不符合题目要求，因此可采取用空间换时间的方法，使用hash表来做。观察一下本题的数据规模：

• 0 <= nums.length <= 105
• -109 <= nums[i] <= 109

说明不好用数组当hashtable，因此选择set去重。具体思路如下：

• 把数组转化为unordered_set;
• 遍历set，如果找到了num - 1在set中，那么说明此时的num肯定不是每个连续序列的第一个，转到下一个num。
• 找到可以用的num之后，开始计算长度，统计num+ 1在不在set中，并用res实时更新。

最终代码：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        //没办法排序，排序后时间复杂度肯定超O(N)了。
        //sort(nums.begin(), nums.end());

        unordered_set<int> set(nums.begin(), nums.end());
        int res = 0;
        for(int num: set){
            if(set.count(num - 1)){
                continue;
            }
            int curNum = num;
            int curLen = 1;
            while(set.count(curNum + 1)){
                curLen++;
                curNum++;
            }
            res = max(curLen, res);

        }
        return res;


    }
};
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

算法相关时间复杂度分析

上图中虽然 for 循环嵌套 while 循环，但是每个元素只会被遍历到最多两次，所以均摊时间复杂度依然为 O(N)。