9号

问题: 你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。数组仅包含仅包含小写字母 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 1:

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

思路: 1.对每个数组的字符串元素拆分成字符数组,然后对字符数组进行排序 2.然后将排序后的字符数组作为key,将原字符串作为value存入哈希表中
3.重复上述步骤,直到遍历完整个数组 4.将哈希表中的value存入一个List中返回 代码:

cclass Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String,List<String>> m =new HashMap<>();
        for (String str : strs) {
            char[] s = str.toCharArray();
            Arrays.sort(s);
            //s相同的字符串分到同一组
            m.computeIfAbsent(new String(s), k -> new ArrayList<>()).add(str);
        }
        return new ArrayList<>(m.values());
    }
}

问题: 给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 意味着本题是不能排序的，因为排序的时间复杂度是 O(nlogn)

示例 1： 输入：nums = [100,4,200,1,3,2] 输出: 示例 2： 输入：nums = [0,3,7,2,5,8,4,6,0,1] 输出：9

思路:对于 nums 中的元素 x，以 x 为起点，不断查找下一个数 x+1,x+2,⋯ 是否在 nums 中，并统计序列的长度。 为了做到 O(n) 的时间复杂度，需要两个关键优化： 把 nums 中的数都放入一个哈希集合中，这样可以 O(1) 判断数字是否在 nums 中。 如果 x−1 在哈希集合中，则不以 x 为起点。为什么？因为以 x−1 为起点计算出的序列长度，一定比以 x 为起点计算出的序列长度要长！这样可以避免大量重复计算。比如 nums=[3,2,4,5]，从 3 开始，我们可以找到 3,4,5 这个连续序列；而从 2 开始，我们可以找到 2,3,4,5 这个连续序列，一定比从 3 开始的序列更长。

代码:

class Solution {
    public int longestConsecutive(int[] nums) {
        int ans = 0;
        Set<Integer> st = new HashSet<>();
        for (int num : nums) {
            st.add(num); // 把 nums 转成哈希集合
        }
        for (int x : st) { // 遍历哈希集合
            if (st.contains(x - 1)) {
                continue;
            }
            // x 是序列的起点
            int y = x + 1;
            while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中
                y++;
            }
            // 循环结束后，y-1 是最后一个在哈希集合中的数
            ans = Math.max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数
        }
        return ans;
    }
}