算法练习|Leetcode49字母异位词分词 ，Leetcode128最长连续序列，Leetcode3无重复字符的最长子串，sql总结

一、Leetcode49字母异位词分词

题目描述

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

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

题目链接：力扣题目链接

解题思路

• 看到小写字母，想到使用哈希ord
• 将前面出现过的放在字典，再次出现相同的就append

方法:哈希

• 要用两次循环做哈希，找到每个单层对应的哈希特征
• 加入字典
• 打印字典value

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        mp = defaultdict(list)

        for i in strs:
            # 把每个单词特征存好
            pre = [0] * 26
            for j in i:
                pre[ord(j) - ord("a")] += 1
            # 找之前是否出现过
            mp[tuple(pre)].append(i)

        return list(mp.values())
           
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结

• 新建字典：mp = defaultdict(list)，添加value时默认值是[]
• 字典的key要唯一，数组作为key要变成元组tuple
• 最终输出字典的所有value：list(mp.values())

---

二、Leetcode128最长连续序列

题目描述

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

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

题目链接：力扣题目链接

解题思路

• 去重
• 排序
• 看下一位是不是当前位+1
• 更新最大长度

方法:

• 先用list(set())去重，sort()排序
• 看下一位是不是当前位+1
• 更新最大长度
• 反之，长度变回1

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        if not nums:
            return 0
            
        nums = list(set(nums))  # 去除重复元素
        nums.sort()
        l = 1
        res = 1
        for i in range(len(nums)):
            cur = nums[i] 
            if (i+1)<len(nums) and nums[i+1] == cur+1:
                l += 1
                res = max(res, l)
            else:
                l = 1

        return res
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结

• 思考要不要排序，排序前要不要去重
• 去除重复元素再排序！！list(set())，.sort()
• 注意i+1不要超限！！

---

三、Leetcode3无重复字符的最长子串

题目描述

给定一个字符串 s ，请你找出其中不含有重复字符的 最长
子串的长度。

题目链接：力扣题目链接

解题思路

• 双指针
• 每走一步，用字典记录字符和下标
• 出现重复的，移动left，更新right

方法:双指针法

• 每走一步记录 字符：下标
• 遇到重复的，left移动到之前记录的重复位置+1
• 更新当前right位置的字典
• 更新length
• right += 1

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        left, right = 0, 0
        length = 0
        dic = {}
        while right < len(s):
            if s[right] in dic and dic[s[right]] >= left:
                left = dic[s[right]] + 1
            dic[s[right]] = right
            length = max(length, right - left + 1)
            right += 1

        return length
        
1
2
3
4
5
6
7
8
9
10
11
12
13
14

总结

• left的移动：
  字典中先判断有重复元素
  并且重复元素之前出现的位置在left右边
  移动到重复元素的右边一个位置

---

sql总结

• 所有情况都满足才返回
  (当一个产品所有发布时间都要在时间范围内才返回id)
  用count检测：having count(x between ’ ’ and ’ ') = count(*)
  
  

心得：积累算法还是要多刷题，在进步了！~