LeetCode热题100(25.10.3)

一：字母异位词分组

1. 排序

字母异位词排序之后相同，可使用哈希表

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hashMap;
        for (string& str : strs)
        {
            string key = str;
            sort(key.begin(), key.end());
            hashMap[key].emplace_back(str);
        }
        vector<vector<string>> result;
        for (auto& row : hashMap)
        {
            result.emplace_back(row.second);
        }
        return result;
    }
};

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hashMap = new HashMap<>();
        for (String str : strs)
        {
            char[] arrayStr = str.toCharArray();
            Arrays.sort(arrayStr);
            String key = new String(arrayStr);
            List<String> value = hashMap.getOrDefault(key, new ArrayList<String>());
            // getOrDefault 它的作用是：如果 map 中存在 key，则返回 key 对应的值；
            // 如果不存在，则返回 new ArrayList<String>() 并添加到 map 中
            value.add(str);
            hashMap.put(key, value);
        }
        return new ArrayList<List<String>>(hashMap.values());
    }
}

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashMap = collections.defaultdict(list)
        for str in strs:
            # sorted(st) 返回一个按字母排序的列表 ['a', 'e', 't']
            # "".join(...) 将列表中的字符连接成字符串 "aet"
            key = "".join(sorted(str))
            hashMap[key].append(str)
        return list(hashMap.values())

2. 计数

跟排序道理相同，只不过增加了字符的次数

class Solution {
public:
    vector<vector<string>> groupAnagrams(vector<string>& strs) {
        unordered_map<string, vector<string>> hashMap;
        for (string& str: strs) {
            array<int, 26> counts{};
            for (char ch : str) 
                counts[ch - 'a'] ++;

            string key;
            for (auto count : counts) 
                key += to_string(count) + "#";

            hashMap[key].emplace_back(str);
        }

        vector<vector<string>> result;
        for (auto& row : hashMap)
            result.emplace_back(row.second);
        return result;
    }
};

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> hashMap = new HashMap<>();
        for (String str : strs)
        {
            int[] counts = new int[26];
            for (int i = 0; i < str.length(); i++)
                counts[str.charAt(i) - 'a']++;
            StringBuffer sb = new StringBuffer();
            for (int i = 0; i < 26; i++)
                if (counts[i] != 0)			// 这里也可以使用python的方式，但是必须在字符之间添加分界符，原因是出现次数超过10的字母会导致键不唯一
                {
                    sb.append((char)('a' + i));
                    sb.append(counts[i]);
                }
            String key = sb.toString();
            List<String> value = hashMap.getOrDefault(key, new ArrayList<String>());
            value.add(str);
            hashMap.put(key, value);
        }
        return new ArrayList<List<String>>(hashMap.values());
    }
}

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        hashMap = collections.defaultdict(list)
        for str in strs:
            counts = [0] * 26
            for ch in str:
                counts[ord(ch) - ord("a")] += 1
            hashMap[tuple(counts)].append(str)		# 直接使用计数数组，注意这里保留了顺序，因为生成的是元组
        return list(hashMap.values())

二：最长连续序列

1. 哈希表

将数据放入哈希表，然后不断寻找它的下一位，时间大概为线性，但有些数据没必要再次寻找，如已经找过的数据

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> hashSet;
        int maxCount = 0;
        for (auto num : nums) hashSet.insert(num);
        for (auto num : hashSet)
        {
            if (!hashSet.count(num - 1))
            {
                int count = 1;  
                while (hashSet.count(num + 1))
                {
                    ++count;
                    ++num;
                }
                maxCount = max(maxCount, count);
            }
        } 
        return maxCount;                                   
    }
};

class Solution {
    public int longestConsecutive(int[] nums) {
        Set<Integer> hashSet = new HashSet<>();
        int maxCount = 0;
        for (int num : nums) hashSet.add(num);
        for (int num : hashSet)
        {
            if (!hashSet.contains(num - 1))
            {
                int count = 1;  
                while (hashSet.contains(num + 1))
                {
                    ++count;
                    ++num;
                }
                maxCount = Math.max(maxCount, count);
            }
        } 
        return maxCount;    
    }
}

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hashSet = set(nums)
        maxCount = 0
        for num in hashSet:
            if num - 1 not in hashSet:
                count = 1  
                while (num + 1) in hashSet:
                    count += 1
                    num += 1
                maxCount = max(maxCount, count)
        return maxCount   

三：盛水最多的容器

1. 双指针

从两端开始，移动小的向中间靠近

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int maxA = 0;
        while (left < right)
        {
            int curArea = min(height[left], height[right]) * (right - left);
            if (height[left] < height[right]) ++left;
            else --right;
            maxA = max(maxA, curArea);
        }
        return maxA;
    }
};

class Solution {
    public int maxArea(int[] height) {
        int left = 0, right = height.length - 1;
        int maxA = 0;
        while (left < right)
        {
            int curArea = Math.min(height[left], height[right]) * (right - left);
            if (height[left] < height[right]) ++left;
            else --right;
            maxA = Math.max(maxA, curArea);
        }
        return maxA;
    }
}

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left, maxA = 0, 0
        right = len(height) - 1
        while left < right:
            curArea = min(height[left], height[right]) * (right - left)
            if (height[left] < height[right]): left += 1
            else: right -= 1
            maxA = max(maxA, curArea)
        return maxA

四：三数之和

1. 排序 + 双指针

首先对数组进行排序，外层循环从左往右，内层从右往左，题目要求三元组不重复意味着相同的值无需处理跳过即可

当我们想要枚举数组中的两个元素时，如果发现随着第一个元素的递增，第二个元素是递减的，那么就可以使用双指针的方法，将枚举的时间复杂度从 $O(N^2)$ 减少至 $O(N)$。为什么是 $O(N)$ 呢？这是因为在枚举的过程中，每一步中，“左指针”会向右移动一个位置，而“右指针”会向左移动若干个位置，这个与数组的元素有关，但我们知道它一共会移动的位置数为 $O(N)$。均摊下来，每次也只向右移动一个位置，因此时间复杂度为 $O(N)$。

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        int length = nums.size();
        vector<vector<int>> result;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < length; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int k = length - 1;
            for (int j = i + 1; j < length; ++j)
            {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                while (nums[i] + nums[j] + nums[k] > 0 && j < k) --k;
                if (j == k) break;
                if (nums[i] + nums[j] + nums[k] == 0) result.push_back({nums[i], nums[j], nums[k]});
            }
        }
        return result;
    }
};

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        int length = nums.length;
        List<List<Integer>> result = new ArrayList<List<Integer>>();
        Arrays.sort(nums);
        for (int i = 0; i < length; ++i)
        {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            int k = length - 1;
            for (int j = i + 1; j < length; ++j)
            {
                if (j > i + 1 && nums[j] == nums[j - 1]) continue;
                while (nums[i] + nums[j] + nums[k] > 0 && j < k) --k;
                if (j == k) break;
                if (nums[i] + nums[j] + nums[k] == 0)
                {
                    List<Integer> row = new ArrayList<>();
                    row.add(nums[i]);
                    row.add(nums[j]);
                    row.add(nums[k]);
                    result.add(row);
                }
            }
        }
        return result;
    }
}

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        length = len(nums)
        result = list()
        nums.sort()
        for i in range(length):
            if i > 0 and nums[i] == nums[i - 1]: continue
            k = length - 1
            for j in range(i + 1, length):
                if j > i + 1 and nums[j] == nums[j - 1]: continue
                while nums[i] + nums[j] + nums[k] > 0 and j < k: k -= 1
                if j == k: break
                if nums[i] + nums[j] + nums[k] == 0:
                    result.append([nums[i], nums[j], nums[k]])
        return result

五：无重复字符的最长子串

1. 滑动窗口

通过哈希表维护窗口，两个指针指向字符串，若右指针元素不在哈希表则添加并右移，若包含则左指针右移并剔除当前指向元素

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_set<char> hashSet;
        int right = 0;
        int length = s.size();
        int result = 0;
        for (int i = 0; i < length; ++i)
        {
            while (right < length && !hashSet.count(s[right]))
            {
                hashSet.insert(s[right]);
                ++right;
            }
            hashSet.erase(s[i]);
            result = max(result, right - i);
        }
        return result;
    }
};

class Solution {
    public int lengthOfLongestSubstring(String s) {
        Set<Character> hashSet = new HashSet<>();
        int right = 0;
        int length = s.length();
        int result = 0;
        for (int i = 0; i < length; ++i)
        {
            while (right < length && !hashSet.contains(s.charAt(right)))
            {
                hashSet.add(s.charAt(right));
                ++right;
            }
            hashSet.remove(s.charAt(i));
            result = Math.max(result, right - i);
        }
        return result;
    }
}

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        hashSet = set()
        right = 0
        length = len(s)
        result = 0
        for i in range(length):
            while (right < length and s[right] not in hashSet):
                hashSet.add(s[right])
                right += 1
            hashSet.remove(s[i])
            result = max(result, right - i)
        return result

六：找到字符串中所有字母异位词

1. 滑动窗口

p的长度固定，在s中寻找p可使用p的长度的作为窗口宽度，利用当前宽度两个字符串出现的次数即可作为判定

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        int sL = s.size(), pL = p.size();
        vector<int> pCharCount(26);
        vector<int> sCharCount(26);
        if (sL < pL) return result;
        for (int i = 0; i < pL; ++i)
        {
            ++pCharCount[p[i] - 'a'];
            ++sCharCount[s[i] - 'a'];
        }
        if (sCharCount == pCharCount) result.emplace_back(0);
        for (int i = 0; i < sL - pL; ++i)      // 开始滑动，剔除左边，增加右边 
        {
            --sCharCount[s[i] - 'a'];
            ++sCharCount[s[i + pL] - 'a'];
            if (sCharCount == pCharCount) result.emplace_back(i + 1);
        }
        return result;
    }
};

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int sL = s.length(), pL = p.length();
        int[] pCharCount = new int[26];
        int[] sCharCount = new int[26];
        if (sL < pL) return result;
        for (int i = 0; i < pL; ++i)
        {
            ++pCharCount[p.charAt(i) - 'a'];
            ++sCharCount[s.charAt(i) - 'a'];
        }
        if (Arrays.equals(pCharCount, sCharCount)) result.add(0);
        for (int i = 0; i < sL - pL; ++i)      // 开始滑动，剔除左边，增加右边 
        {
            --sCharCount[s.charAt(i) - 'a'];
            ++sCharCount[s.charAt(i + pL) - 'a'];
            if (Arrays.equals(pCharCount, sCharCount)) result.add(i + 1);
        }
        return result;
    }
}

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = list()
        sL, pL = len(s), len(p)
        pCharCount = [0] * 26
        sCharCount = [0] * 26
        if (sL < pL): return result
        for i in range(pL):
            pCharCount[ord(p[i]) - 97] += 1
            sCharCount[ord(s[i]) - 97] += 1
        if (sCharCount == pCharCount): result.append(0)
        for i in range(sL - pL):   
            sCharCount[ord(s[i]) - 97] -= 1
            sCharCount[ord(s[i + pL]) - 97] += 1
            if (sCharCount == pCharCount): result.append(i + 1)
        return result

2. 优化

不比较两个字符串在窗口的位置，直接比较差值

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> result;
        int sL = s.size(), pL = p.size();
        vector<int> charCount(26);
        if (sL < pL) return result;
        for (int i = 0; i < pL; ++i)
        {
            --charCount[p[i] - 'a'];
            ++charCount[s[i] - 'a'];
        }
        int dif = 0;
        for (int i = 0; i < 26; ++i)
            if (charCount[i] != 0) ++dif;
        if (dif == 0) result.emplace_back(0);
        for (int i = 0; i < sL - pL; ++i)      // 开始滑动，剔除左边，增加右边 
        {
            if (charCount[s[i] - 'a'] == 1) --dif;      // 左边为1，则dif减小，为0则dif增加，为-1则不变，右边同理
            else if (charCount[s[i] - 'a'] == 0) ++dif;
            --charCount[s[i] - 'a'];
            if (charCount[s[i + pL] - 'a'] == -1) --dif;      
            else if (charCount[s[i + pL] - 'a'] == 0) ++dif;
            ++charCount[s[i + pL] - 'a'];
            if (dif == 0) result.emplace_back(i + 1);
        }
        return result;
    }
};

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int sL = s.length(), pL = p.length();
        int[] charCount = new int[26];
        if (sL < pL) return result;
        for (int i = 0; i < pL; ++i)
        {
            --charCount[p.charAt(i) - 'a'];
            ++charCount[s.charAt(i) - 'a'];
        }
        int dif = 0;
        for (int i = 0; i < 26; ++i)
            if (charCount[i] != 0) ++dif;
        if (dif == 0) result.add(0);
        for (int i = 0; i < sL - pL; ++i)      // 开始滑动，剔除左边，增加右边 
        {
            if (charCount[s.charAt(i) - 'a'] == 1) --dif;      // 左边为1，则dif减小，为0则dif增加，为-1则不变，右边同理
            else if (charCount[s.charAt(i) - 'a'] == 0) ++dif;
            --charCount[s.charAt(i) - 'a'];
            if (charCount[s.charAt(i + pL) - 'a'] == -1) --dif;      
            else if (charCount[s.charAt(i + pL) - 'a'] == 0) ++dif;
            ++charCount[s.charAt(i + pL) - 'a'];
            if (dif == 0) result.add(i + 1);
        }
        return result;
    }
}

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        result = list()
        sL, pL = len(s), len(p)
        charCount = [0] * 26
        if (sL < pL): return result
        for i in range(pL):
            charCount[ord(p[i]) - 97] -= 1
            charCount[ord(s[i]) - 97] += 1
        differ = [c != 0 for c in charCount].count(True)

        if (differ == 0): result.append(0)
        for i in range(sL - pL):   
            if charCount[ord(s[i]) - 97] == 1: differ -= 1
            elif charCount[ord(s[i]) - 97] == 0: differ += 1
            charCount[ord(s[i]) - 97] -= 1
            if charCount[ord(s[i + pL]) - 97] == -1: differ -= 1
            elif charCount[ord(s[i + pL]) - 97] == 0: differ += 1
            charCount[ord(s[i + pL]) - 97] += 1
            if (differ == 0): result.append(i + 1)
        return result