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

ops/2024/10/18 9:17:08/

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. 盛最多水的容器
    我的思路:(但我觉得还是不严谨)
    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的子数组 ( 前缀和)

  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而不是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/

http://www.ppmy.cn/ops/37284.html

相关文章

整体安全保障服务方案包括哪些方面?

整体安全保障服务方案是一套综合性的措施&#xff0c;旨在保护企业的网络、数据和资源免受各种威胁。主要包含检测、加固、应急保障、安全运营、攻防演练等多项核心能力与服务。 ​安全狗通过专业团队、工具以及专业运营流程&#xff0c;提出了新一代整体安全保障思路&#xff…

Linux——mysql运维篇

回顾基本语句&#xff1a; 数据定义语言 ( DDL ) 。这类语言用于定义和修改数据库的结构&#xff0c;包括创建、删除和修改数据库、表、视图和索引等对象。主要的语句关键字包括 CREATE 、 DROP 、 ALTER 、 RENAME 、 TRUNCATE 等。 create database 数据库 &…

提供 DISC性格测试报告的全新 API接口,带给你惊喜的发现!

简介 DISC个性测验由24组描述个性特质的形容词构成&#xff0c;每组包含四个形容词&#xff0c;这些形容词是根据支配性&#xff08;D&#xff09;、影响性&#xff08;I&#xff09;、服从性&#xff08;C&#xff09;、 稳定性&#xff08;S&#xff09;和四个测量维度以及一…

简要介绍MATLAB的背景和重要性,以及它在数据分析与可视化领域的广泛应用

**标题**&#xff1a;MATLAB在数据分析与可视化中的应用 **引言**&#xff08;约200字&#xff09; 简要介绍MATLAB的背景和重要性&#xff0c;以及它在数据分析与可视化领域的广泛应用。强调本文旨在探讨MATLAB在这两个领域的具体应用案例、技术特点和发展趋势。 **一、MAT…

你对氟橡胶油封的基本知识了解多少?

在机械和工程领域&#xff0c;氟橡胶油封在确保平稳运行和防止泄漏方面发挥着至关重要的作用。了解这些密封件的基本知识对于任何参与制造、维护或维修过程的人来说都是至关重要的。 1.组成与结构&#xff1a; 氟橡胶油封主要由氟、碳和氢原子组成&#xff0c;因此得名氟弹性…

第六代移动通信介绍、无线网络类型、白皮书

关于6G 即第六代移动通信的介绍&#xff0c; 图解通信原理与案例分析-30&#xff1a;6G-天地互联、陆海空一体、全空间覆盖的超宽带移动通信系统_6g原理-CSDN博客文章浏览阅读1.7w次&#xff0c;点赞34次&#xff0c;收藏165次。6G 即第六代移动通信&#xff0c;6G 将在5G 的基…

分布式锁概述

什么是分布式锁 分布式锁是一种在分布式计算环境中用于同步访问共享资源的机制。它的主要目的是在一个分布式系统中&#xff0c;当多个进程或服务需要同时访问同一个资源时&#xff0c;确保任一时刻只有一个进程或服务能够执行涉及该资源的关键操作。这类似于传统单体应用中的…

去中心化金融与Web3:科技驱动的金融革命

随着区块链技术的发展和普及&#xff0c;去中心化金融&#xff08;DeFi&#xff09;作为其重要应用之一&#xff0c;正在成为金融领域的一场革命。结合Web3技术&#xff0c;去中心化金融正在以前所未有的方式重新定义着金融服务和产品的交付方式&#xff0c;推动着金融领域的创…