Python Hot100 学习笔记

这篇是我刷 Hot100 的总览页。
我会把每道题单独存到此篇笔记目录下的 .py 文件，并由页面自动读取展示。

代码

1. 两数之和

class Solution(object):
    def twoSum(self, nums, target):
        l = len(nums)
        hashtable = dict()
        
        for i in range(l):
            if target - nums[i] in hashtable:
                return [hashtable[target - nums[i]], i]

            hashtable[nums[i]] = i

        return []

49. 字母异位词分组

class Solution(object):
    def groupAnagrams(self, strs):
        mp = dict()

        for s in strs:
            key = "".join(sorted(s))
            if key not in mp:
                mp[key] = []
            mp[key].append(s)

        return list(mp.values())

128. 最长连续序列

class Solution:
    def longestConsecutive(self, nums: List[int]) -> int:
        hashset = set(nums)
        maxlen = 0

        for num in nums :
            if num-1 not in hashset :
                nowlen = 1
                nex = num+1

                while nex in hashset :
                    nex += 1
                    nowlen += 1

                maxlen = max(nowlen,maxlen)
                
        return maxlen

283. 移动零

class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        length = len(nums)
        putindex = 0

        # 将非零元素依次放在前面
        for i in range(length):
            while putindex < length and nums[putindex] == 0:
                putindex += 1

            if putindex == length:
                nums[i] = 0
            else:
                nums[i] = nums[putindex]
                putindex += 1

11. 盛最多水的容器

class Solution:
    def maxArea(self, height: List[int]) -> int:
        left = 0
        right = len(height)-1
        maxArea = 0

        while left < right :
            area = (right-left) * min(height[right] , height[left])
            maxArea = max( maxArea , area)

            if height[right] < height[left] :
                right -= 1
            else :
                left += 1

        return maxArea

15. 三数之和

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        # 双重for + set找need 有重复
        # 应该使用排序 + 双指针
        l = len(nums)
        nums.sort()
        ans = []
        for i in range(l) :
            if i > 0 and nums[i] == nums[i-1] :
                continue
            need = -nums[i]
            left = i+1
            right = l-1
            while left < right :
                if nums[left]+nums[right] > need : 
                    right -= 1
                elif nums[left]+nums[right] < need :
                    left += 1
                else :
                    ans.append([-need , nums[left] , nums[right]])
                    while left < right and nums[left] == nums[left + 1]: left += 1
                    while left < right and nums[right] == nums[right - 1]: right -= 1
                    left += 1
                    right -= 1
    
        return ans

42. 接雨水

class Solution:
    def trap(self, height: List[int]) -> int:
        l = len(height)
        pre = 0
        preheight = [0]*l

        for i in range(l) :
            pre = max(height[i],pre)
            preheight[i] = pre

        ans = 0
        nex = 0
        for j in range(l-1 , -1, -1) :
            nex = max(height[j],nex)
            ans += min(nex,preheight[j])-height[j]
        
        return ans

3. 无重复字符的最长子串

class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        if not s :
            return 0
        mp = {}
        star , l = 0 , 1
        # map中存在即重复 新的star = key+1
        for i in range(len(s)) :
            c = s[i]
            if c not in mp or mp[c] < star :
                l = max(l , i-star+1)
                mp[c] = i
            else :
                star = mp[c]+1
                mp[c] = i

        return l

438. 找到字符串中所有字母异位词

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        sl,pl = len(s),len(p)
        if sl < pl :
            return [] 

        sMap,pMap = [0]*26 , [0]*26
        ans = []
        for i in range(pl) :
            sMap[ ord(s[i]) - ord('a') ] += 1
            pMap[ ord(p[i]) - ord('a') ] += 1

        if sMap == pMap :
                ans.append(0)

        for i in range(0 , sl-pl) :
            sMap[ ord(s[i])-ord('a') ] -= 1
            sMap[ord(s[i+pl])-ord('a')] +=1

            if sMap == pMap :
                ans.append(i+1)

        return ans

560. 和为 K 的子数组

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans , nowsum = 0, 0
        mp = {}
        mp[0] = 1
        for num in nums :
            nowsum += num
            need = nowsum - k
            if need in mp :
                ans += mp[need]
            mp[nowsum] = mp.get(nowsum , 0) +1 
        return ans

239. 滑动窗口最大值

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        l = len(nums)
        if k > l :
            return []
        left = 0
        heap = []
        ans = []
        for i in range(l) :
            # 存当前的元素
            heapq.heappush(heap , (-nums[i] , i))
            if i >= k-1 :
                # 满了 存 拿 移动left
                while heap[0][1] < left :
                    heapq.heappop(heap)
                ans.append(-heap[0][0])
                left += 1       
        return ans
        #也可以存递减的下标

76. 最小覆盖子串

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        if len(t) > len(s) :
            return ""

        tmap ={}
        for tchar in t :
            tmap[tchar] = tmap.get(tchar, 0) + 1
        needchar = len(tmap)
        left , star = 0 , -1
        minLength = len(s) + 1
        for right in range(len(s)) :
            addchar = s[right]
            if addchar in tmap:
                tmap[addchar] -= 1
                if tmap[addchar] == 0 : needchar -= 1
            while needchar == 0 :
                # 移除前面的无用字母 
                if s[left] not in tmap :
                    left += 1
                # 以及多余字母
                elif tmap[s[left]] < 0 :
                    tmap[s[left]] += 1
                    left += 1
                # 当前最短有效
                else :
                    if right-left+1 < minLength :
                        minLength = right-left+1
                        star = left
                    # 记录后 删除第一个有效字母
                    tmap[s[left]] += 1
                    needchar += 1
                    left += 1
        if star == -1 : return ""
        return s[star : star+minLength]

53. 最大子数组和

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        maxsum,nowsum = nums[0],0
    
        for right in range(len(nums)) :
            nowsum += nums[right]
            # 更新最大值
            maxsum = max(maxsum,nowsum)
            # 如果当前和小于0 就丢弃之前的和 从下一个开始
            if nowsum < 0:
                nowsum = 0

        return maxsum

56. 合并区间

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        pq = []
        ans = []
        for interval in intervals :
            heapq.heappush(pq,interval)
        while pq :
            interval = heapq.heappop(pq)
            while pq and pq[0][0] <= interval[1] :
                add = heapq.heappop(pq)
                interval[1] = max (interval[1],add[1])
            ans.append(interval)
        return ans

记录方式

将道题结果 .py 文件存入hoot100笔记统计目录下，扫描全部py文件自动添加显示
代码都是 leetcode 过了提交测试的，但是思路并不一定是最佳思路，仅为自己过程记录
如果你发现了某个代码有问题，可以在背地里偷偷笑我，因为我的博客里没有添加评论功能

Python_Hot100

学习 Python 顺遍刷 Hot100 的过程记录

Python Hot100 学习笔记

目录

代码

1. 两数之和

49. 字母异位词分组

128. 最长连续序列

283. 移动零

11. 盛最多水的容器

15. 三数之和

42. 接雨水

3. 无重复字符的最长子串

438. 找到字符串中所有字母异位词

560. 和为 K 的子数组

239. 滑动窗口最大值

76. 最小覆盖子串

53. 最大子数组和

56. 合并区间

记录方式