力扣热题100刷题笔记[python]

时间:2024-05-08 12:48:37

letcode100

题录地址:
https://leetcode.cn/studyplan/top-100-liked/

注:另外有记忆精简版 [LeetCode热题100_记忆版.md](file:///D:/yingl/文件/notes_-yl/技术精品文章/编程基本功/算法资料汇总/LeetCode热题100_记忆版.md)

哈希

两数之和

思路:
0、用 hash_table ={1: 0, 2:1} 保存值与下标
1、遍历所nums,如果 target - val 不在hash_table中,将当前val和index 增加或刷新到hash_table中;如果 target - val 在hash_table中,就直接返回

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_table = defaultdict(int)
        for index, val in enumerate(nums):
            if target - val in hash_table:
                return [hash_table[target - val], index] # 如果在hash_table中就直接返回
            if val not in hash_table:
                hash_table[val] = index

49 字母异位词分组

思路:
1 使用 hash_dict = defaultdict(list) 保存hash相同的list
2 使用hash_val += hash(item)*hash(item)*hash(item) 的方式来计算hash

from collections import defaultdict

class Solution(object):
    def groupAnagrams(self, strs):
        """
        :type strs: List[str]
        :rtype: List[List[str]]
        """
        re = []
        def calHash(stri):
            hash_val = 0
            for item in stri:
                hash_val += hash(item)*hash(item)*hash(item)
            return hash_val

        hash_dict = defaultdict(list)
        for item in strs:
            hash_val = calHash(item)
            hash_dict[hash_val].append(item)

        for key, val_list in hash_dict.items():
            re.append(val_list)
        return re

128. 最长连续序列

思路:
1、遍历所有元素。以每一个元素为起点连续搜索,直到没有。搜索的时候用 key in的方式去做。可以使用hash表也可以直接使用一个set
2、去重的好处是防止重复遍历
3、此外这里使用 if num - 1 not in num_set: 来进行剪枝,这段代码的意思是判断是否为起始节点

class Solution(object):
    def longestConsecutive(self, nums):
        longest_streak = 0 # 保存当前最大的连续序列
        num_set = set(nums)

        for num in num_set:
            if num - 1 not in num_set:
                current_num = num
                current_streak = 1

                while current_num + 1 in num_set:
                    current_num += 1
                    current_streak += 1 # 保存当前的最大连续序列长度

                longest_streak = max(longest_streak, current_streak)

        return longest_streak

双指针

移动零(简单题)

思路:
1、此题有点像插入排序。左指针维护一个非零的队列,右指针维护一个0的队列
2、

class Solution:
    def moveZeroes(self, nums):
        """
        :type nums: List[int]
        :rtype: None Do not return anything, modify nums in-place instead.
        """
        left = 0 # 第一个指针,left
        for right in range(len(nums)):  # 第二个指针,right,在for循环中实现移动
            # 核心的交换步骤:如果当前right不为0,则交换到左侧,把非0数往左侧移动就对了
            if nums[right]: 
                nums[left], nums[right] = nums[right], nums[left]
                left += 1 # 交换后也移动left

作者:庸才程序员
链接:https://leetcode.cn/problems/move-zeroes/solutions/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

乘最多水的容器

  1. 盛最多水的容器
    我的思路:(但我觉得还是不严谨)
    1 如果将两个指针放在两端,那么 width 只能减少,但问题是左右指针怎么移动
    2 左右指针的移动目标就是朝着 height 增大的方向去移动,所有选择移动其中小的指针

具体算法
构建一个搜索路径,保证搜索的单向性,使用排除法
收尾两个指针,向中间移动,永远移动小指针,直到收尾指针重合

这篇题解和我的思路一模一样:
https://leetcode.cn/problems/container-with-most-water/solutions/11491/container-with-most-water-shuang-zhi-zhen-fa-yi-do

class Solution(object):
    def maxArea(self, height):
        """
        :type height: List[int]
        :rtype: int
        """
        left = 0
        right = len(height) -1
        global_area  = 0
        while left < right and right < len(height):
            currrnt_area = min(height[left], height[right]) * (right - left)
            global_area = max(global_area, currrnt_area)
            if height[left] < height[right]:
                left = left+1
            else:
                right = right - 1
        return global_area

if __name__ == '__main__':
    slution = Solution()
    re = slution.maxArea([1,1])
    print(re)

三数之和

使用双指针
1 首先排序
2 不重复第一个元素(第一个指针) 保证第一个元素不重复
3 不重复的遍历第二个元素(第二个指针,从第一个指针往后), 找到第三个元素
注:其实我觉得 if cur + nums[l] + nums[r] > 0 之后 r可以连续走的

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) < 3: return []
        nums, res = sorted(nums), []
        for i in range(len(nums) - 2):
            cur, l, r = nums[i], i + 1, len(nums) - 1
            if res != [] and res[-1][0] == cur: continue # Drop duplicates for the first time.

            while l < r:
                if cur + nums[l] + nums[r] == 0:
                    res.append([cur, nums[l], nums[r]])
                    while l < r - 1 and nums[l] == nums[l + 1]:
                        l += 1
                    while r > l + 1 and nums[r] == nums[r - 1]:
                        r -= 1
                if cur + nums[l] + nums[r] > 0: # 注:这里为什么不连续接着走呢,其实我觉得是可以的
                    r -= 1
                else:
                    l += 1
        return res

作者:代码随想录
链接:https://leetcode.cn/problems/3sum/solutions/1670261/dai-ma-sui-xiang-lu-dai-ni-gao-ding-ha-x-jzkx/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

滑动窗口

无重复最长子串

题解:
用一个滑窗和hash
具体算法
1、while循环(左窗口<=窗口 and 右窗口小于字符串长度),判断右窗口指向的元素是否重复,如果不在更新最大值,右窗口++。否则左窗口++,窗口内的元素–
注:
先判断再加进滑窗,不要每次循环都加
先想好伪代码,再开始写代码

from collections import defaultdict
class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        left, right = 0, 0
        hashmap = defaultdict(int)
        res = 0
        if len(s) == 0:
            return 0
        while left <= right and right < len(s):
            if hashmap[s[right]] > 0:
                hashmap[s[left]] -=1
                left += 1
            else:
                hashmap[s[right]] += 1  # 注:先判断再加,不要先加再判断
                res = max(res, right - left +1)
                right += 1
        return res


438. 找到字符串中所有字母异位词(有技巧性)

题解:
用一个滑窗和hash(hash使用26个字母的编号)
具体算法
1、滑窗长度固定,慢慢平移。每滑动一格重新计算滑窗的编码判断是否相等

注:本题最关键的点在于如何让设计hash,注26个编码的实现方法,使用一个26个字母的list,
或者使用dict但是需要提前把所有的值都赋值好,不能动态增加

class Solution(object):
    def findAnagrams(self, s, p):
        """
        :type s: str
        :type p: str
        :rtype: List[int]
        """
        def get_hash(strp):
            '''
            返回26个字母的编码
            :param s:
            :return:
            '''
            re_hash = [0]*26
            for i in range(0, len(strp)):
                re_hash[ord(strp[i])-ord('a')] += 1
            return re_hash
        re = []
        p_hash = get_hash(p)
        left = 0
        right = len(p)-1
        s_hash = get_hash(s[left:right+1])
        while right < len(s):
            if left > 0:
                s_hash[ord(s[right])-ord('a')] += 1
            if s_hash == p_hash:
                re.append(left)
            s_hash[ord(s[left])-ord('a')] -= 1
            right += 1
            left += 1
        return re

子串

和为k的子数组 ( 前缀和)

  1. 和为 K 的子数组
    题解:
    1、先求解前缀和 : pre_sum_list[i] = pre_sum_list[i-1] + nums[i-1]
    2、最后就变成了在前缀和序列中求解两数之差为k的数量 ps:区间和:pre_sum_list[j]-pre_sum_list[i] = [i, j)

注:前缀和
pre_sum_list[0] 为 0
pre_sum_list[1] 为 num[0]
pre_sum_list[2] 为 num[0] + num[1]
pre_sum_list[5] 为 num[0] num[1] num[2] num[3] num[4]

区间和:pre_sum_list[j]-pre_sum_list[i] = [i, j)

class Solution(object):
    def subarraySum(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: int
        """
        re_sum = 0

        # 获取前缀和 pre_sum_list[1] = pre_sum_list[0] + nums[0]
        pre_sum_list = [0]*(len(nums)+1)
        for i in range(1, len(pre_sum_list)):
            pre_sum_list[i] = pre_sum_list[i-1] + nums[i-1]

        # 获取两数之和 pre_sum_list[j]-pre_sum_list[i] = [i, j)
        pre_sum_map = defaultdict(int) # 使用dict而不是set
        for i in range(0, len(pre_sum_list)):
            target = pre_sum_list[i] - k
            re_sum += pre_sum_map[target] 
            pre_sum_map[pre_sum_list[i]] += 1
        return re_sum

滑动窗口最大值(困难 单调队列 双端队列)

使用:单调队列
参考资料:https://www.bilibili.com/video/BV1bM411X72E/?vd_source=d8ef884ad74a2afc063f9ca90338ca3c
题解:
这里的单调队列有一个特点,只有后来的且比他小的才能加进去。因为前面这些值一定不是解

1、遍历nums,每遍历一个元素,将队列中比它小的全从尾部弹出来,将该元素入队
2、将超出k的左边部分出队,小于k时不需要出队
3、队首就是解。将队首加入结果数组

from collections import deque


class Solution(object):
    def maxSlidingWindow(self, nums, k):
        """
        :type nums: List[int]
        :type k: int
        :rtype: List[int]
        """
        ans = []
        q = deque()
        for i, x in enumerate(nums):
            
            #右入 将比当前小的元素都弹出来,右边弹出
            while q and nums[q[-1]] <= x:
                q.pop()
            q.append(i)

            # 左出
            if i-q[0]>=k:  # 将超出滑窗范围的元素弹出,这种做法是因为小于k时不需要出队
                q.popleft() # 左边弹出
            if i >= k-1: # 刚开始滑窗大小未到k
                ans.append(nums[q[0]]) # 将当前
        return ans

最小覆盖子串(困难 )

参考这个题解
https://leetcode.cn/problems/minimum-window-substring/solutions/258513/tong-su-qie-xiang-xi-de-miao-shu-hua-dong-chuang-k

题解:
1、不断增加j使滑动窗口增大,直到窗口包含了T的所有元素
2、不断增加i使滑动窗口缩小,因为是要求最小字串,所以将不必要的元素排除在外,使长度减小,直到碰到一个必须包含的元素,这个时候不能再扔了,再扔就不满足条件了,记录此时滑动窗口的长度,并保存最小值
3 让i再增加一个位置,这个时候滑动窗口肯定不满足条件了,那么继续从步骤一开始执行,寻找新的满足条件的滑动窗口,如此反复,直到j超出了字符串S范围。

from collections import Counter

class Solution:
    def minWindow(self, s: str, t: str) -> str:
        ans_left, ans_right = -1, len(s)
        left = 0
        cnt_s = Counter()  # s 子串字母的出现次数,初始化方法
        cnt_t = Counter(t)  # t 中字母的出现次数
        for right, c in enumerate(s):  # 移动子串右端点
            cnt_s[c] += 1  # 右端点字母移入子串
            while cnt_s >= cnt_t:  # 涵盖
                if right - left < ans_right - ans_left:  # 找到更短的子串
                    ans_left, ans_right = left, right  # 记录此时的左右端点
                cnt_s[s[left]] -= 1  # 左端点字母移出子串
                left += 1  # 移动子串左端点
        return "" if ans_left < 0 else s[ans_left: ans_right + 1]

普通数组

53. 最大子数组和

动态规划
核心公式:dp[i] = max(nums[i], dp[i-1]+nums[i])

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dp = [0] * len(nums)
        dp[0] = nums[0]
        max_sum = nums[0]
        for i in range(1, len(nums)):
            dp[i] = max(nums[i], dp[i-1]+nums[i])
            max_sum = max(max_sum, dp[i])
        return  max_sum

作者:YingL
链接:https://leetcode.cn/problems/maximum-subarray/solutions/2676294/53-zui-da-zi-shu-zu-he-by-user5776-6kds/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

合并区间

题解:
1、排序
2、依次加入数组,加入之前和最后一个元素进行对比。如果有交叉就合并然后加入数组

class Solution(object):
    def merge(self, intervals):
        if len(intervals) == 0:
            return []

        intervals.sort()
        re = []
        re.append(intervals[0])
        for i, item in enumerate(intervals):
            if item[0] <= re[-1][1]:
                last = re.pop()
                re.append([last[0], max(last[1], item[1])]) # 合并然后加入数组
            else:
                re.append(item)
        return re

轮转数组

题解:
1、保存前面的的n-k个元素
2、删除前面的n-k个元素, 只剩下k个元素了

注意:不能使用 nums = last_k 这样无法修改nums中的内容

import copy
from collections import Counter

class Solution:
    def rotate(self, nums, k):
        k = k % len(nums)
        retote = nums[:len(nums)-k] #  保存前面的的n-k个元素
        last_k = nums[len(nums)-k:] #  保存前面的的n-k个元素
        last_k.extend(retote)
        nums[:] = last_k # 注意:不能使用 nums =  last_k

238. 除自身以外数组的乘积

使用前缀乘积和后缀乘积。
题解:
1、 提前将从左到右的所有乘积和从右到左的所有乘积保存下来,然后进行相乘。

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # 前缀乘积
        pre, sum = [1], 1
        for i in nums:
            sum = sum * i
            pre.append(sum)
        # 后缀乘积
        suf, sum = [1], 1
        for i in range(len(nums)):
            sum = sum * nums[len(nums) - i - 1]
            suf.append(sum)
        # 求解
        ans = []
        for i in range(len(nums)):
            total = pre[i] * suf[len(nums) - i - 1]
            ans.append(total)
        return ans

作者:Nebula
链接:https://leetcode.cn/problems/product-of-array-except-self/solutions/1820552/238-by-nebula-a0-c06n/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。


作者:YingL
链接:https://leetcode.cn/problems/product-of-array-except-self/solutions/2676286/238-chu-zi-shen-yi-wai-shu-zu-de-cheng-j-1pnp/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

缺失的第一个正整数(困难-我感觉很简单)

数组长度定了,正整数就定了,所以就可以从小到大遍历正整数,看看哪个最先不在原数组中。具体而言,假设我的数组长度为5,那么就应该出现12345,遍历12345,看哪个不在数组中,如果都在就是满足条件,返回6
题解;
1、遍历一遍数组,使用hash_table 保存所有出现过值,用于判断该值是否存在
2、从1数到len(num) 看哪个值不存在

class Solution(object):
    def firstMissingPositive(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        s = defaultdict(int)
        for item in nums:
            s[item] += 1

        for i in range(1,len(nums)+1):
            if s[i] == 0:
                return i
        return len(nums)+1

作者:YingL
链接:https://leetcode.cn/problems/first-missing-positive/solutions/2678840/que-shi-de-di-yi-ge-zheng-shu-by-user577-vmna/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

矩阵

矩阵置零

题解:
1、遍历一遍矩阵,记录有0的行与列
2、将相关行与列全部置为0

class Solution:
    def setZeroes(self, matrix):
        m, n = len(matrix), len(matrix[0])
        row, col = [False] * m, [False] * n

        for i in range(m):
            for j in range(n):
                if matrix[i][j] == 0:
                    row[i] = col[j] = True
        
        # 一次遍历即可
        for i in range(m):
            for j in range(n):
                if row[i] or col[j]: # 如果在目标行或者目标列,就置为0
                    matrix[i][j] = 0

作者:YingL
链接:https://leetcode.cn/