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

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 defaultdictclass Solution(object):def groupAnagrams(self, strs):""":type strs: List[str]:rtype: List[List[str]]"""re = []def calHash(stri):hash_val = 0for item in stri:hash_val += hash(item)*hash(item)*hash(item)return hash_valhash_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 = numcurrent_streak = 1while current_num + 1 in num_set:current_num += 1current_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 # 第一个指针，leftfor 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 如果将两个指针放在两端,那么 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 = 0right = len(height) -1global_area  = 0while 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+1else:right = right - 1return global_areaif __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) - 1if 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 += 1while r > l + 1 and nums[r] == nums[r - 1]:r -= 1if cur + nums[l] + nums[r] > 0: # 注：这里为什么不连续接着走呢，其实我觉得是可以的r -= 1else:l += 1return 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, 0hashmap = defaultdict(int)res = 0if len(s) == 0:return 0while left <= right and right < len(s):if hashmap[s[right]] > 0:hashmap[s[left]] -=1left += 1else:hashmap[s[right]] += 1  # 注：先判断再加，不要先加再判断res = max(res, right - left +1)right += 1return 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]*26for i in range(0, len(strp)):re_hash[ord(strp[i])-ord('a')] += 1return re_hashre = []p_hash = get_hash(p)left = 0right = len(p)-1s_hash = get_hash(s[left:right+1])while right < len(s):if left > 0:s_hash[ord(s[right])-ord('a')] += 1if s_hash == p_hash:re.append(left)s_hash[ord(s[left])-ord('a')] -= 1right += 1left += 1return re

子串

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

和为 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而不是setfor i in range(0, len(pre_sum_list)):target = pre_sum_list[i] - kre_sum += pre_sum_map[target] pre_sum_map[pre_sum_list[i]] += 1return re_sum

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

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

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

from collections import dequeclass 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: # 刚开始滑窗大小未到kans.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 Counterclass Solution:def minWindow(self, s: str, t: str) -> str:ans_left, ans_right = -1, len(s)left = 0cnt_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 Counterclass 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], 1for i in nums:sum = sum * ipre.append(sum)# 后缀乘积suf, sum = [1], 1for 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] += 1for i in range(1,len(nums)+1):if s[i] == 0:return ireturn 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] * nfor 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]: # 如果在目标行或者目标列，就置为0matrix[i][j] = 0作者：YingL
链接：https://leetcode.cn/