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 如果将两个指针放在两端,那么 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的子数组 ( 前缀和)
- 和为 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/
