【leetCode力扣热题100(一)】适合入门·Python代码及详细解析（持续更新）
话先说在前面，我水平很差，代码无特殊标明就都是用的力扣官方题解，这里基本记录了我做题时的所有疑惑和解决办法，以及一些补充的知识点，希望可以方便跟我一样的初学者。
目录
1.两数之和
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashtable = dict()
for i, num in enumerate(nums):
if target - num in hashtable:
return [hashtable[target - num], i]
hashtable[nums[i]] = i
return []def twoSum(self, nums: List[int], target: int) -> List[int]:定义了Solution类中的一个方法twoSum，它接受一个整数列表nums和一个目标值target，并返回一个包含两个整数索引的列表。hashtable = dict()创建一个空的哈希表（字典），用于存储数值及其对应的索引。for i, num in enumerate(nums):使用enumerate函数遍历nums列表，同时获取元素的索引i和元素值num。enumerate(a)会接受一个数组a，生成一个包含索引和值的迭代器，返回当前元素的索引和元素值。
逻辑点：
- 哈希表。你可以想象为一个列表，每一行存储着一个索引和数值。在搜索时，只要给出要查找的数据，哈希函数会对这个数据进行计算，得到一个索引，然后在哈希表中查找这个索引，通过数组下标直接访问的方式得到对应项的数值。更形象地解释的话，我们可以想象哈希表是一本字典，我们查“李”这个字，一般都会直接去拼音“L”板块，而不是从第一页开始往后翻。为什么我们会下意识地找“L”呢？其实这就相当于一个哈希函数，即计算某个字的声母。我们再去L部分一页一页翻字典找到想要的字的操作就是遍历（哈希表一个索引后面可能接的是一个链表而不是单独一个数据，链表中存储具有同一特征的数据，通过遍历搜索。这种复合存储方式同时关注了速度和空间利用率）。哈希表之所以快是因为对于每一个数据我们都有哈希函数“量身定做”的索引，通过数组下标直接访问，所以时间复杂度是O（1）。
- 这段代码有一个逻辑容易模糊的地方，就是哈希表的索引位存的是数组的数值而哈希表的数值位存的是数组的索引。这是因为我们在哈希表中找某个数时是在哈希表的索引表里找，代码
这里的hashtable指的是哈希表中索引的那部分而不是哈希表中数据的那部分。因为我们是找符合条件的数，所以这里的哈希函数就是y=x，访问下表为x的数组项不为空即为找到。if target - num in hashtable: - 这里的哈希表一开始是空的而不是把数组全部存进去，是为了避免找到自己本身。不用担心漏项，对于第一个数肯定是什么都找不到的，它会被存进去，后面搜索过的每一项都会被存进去。只要存在一双配对的数，即使前面一个数在搜索时哈希表里什么都没有，后面一个数搜索时前一个数肯定已经被存进去了，所以一定会找到。
2. 字母异位词分组
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
mp = collections.defaultdict(list)
for st in strs:
key = "".join(sorted(st))
mp[key].append(st)
return list(mp.values())- def groupAnagrams(self, strs: List[str]) -> List[List[str]]: 在
Solution类中定义一个名为groupAnagrams的方法。它接受一个字符串列表strs作为输入，并返回一个字符串列表的列表。 - mp = collections.defaultdict(list): 初始化一个 defaultdict
mp，其中每个键映射到一个列表。这将用于字母异位词字符串分组在一起。 - key = “”.join(sorted(st)): 对字符串
st中的字符进行排序，并将它们重新组合成一个字符串key。 - mp[key].append(st): 用刚刚得到的key做哈希表的索引，将原始字符串
st添加到 defaultdictmp中对应排序字符串key的列表中，也就完成了分组。 - return list(mp.values()): 将 defaultdict
mp的值（即字母异位词列表）转换为一个列表并返回。
逻辑点：
- 列表。列表与链表，数组不同。列表是一种顺序存储的数据结构，元素在内存中是连续存储的。在 Python 中，列表是动态数组，可以存储不同类型的元素，支持随机访问（通过索引访问元素）。列表的插入和删除操作在最坏情况下可能需要移动大量元素，因此时间复杂度为 O(n)。
- dict（字典）。有一个误区，就是Python 中没有一种专门叫做哈希表的数据结构，我们是用字典的数据结构实现哈希表的逻辑功能的。Python 的字典（dict）实际上就是一种哈希表的实现。字典通过哈希函数将键映射到存储位置，从而实现快速查找、插入和删除操作。
- 列表不能做字典的键。 在 Python 中，字典的键必须是不可变的（如字符串、数字、元组等）。而刚刚说到列表是动态数组，因此如果想用列表的数据必须先转换成元组等格式。
- 元组（tuple），如(1, 2, 3, (4, 5))。与数组不同（数组可以动态可以静态），元组是不可变的，一旦创建了元组，里面的内容就不能被修改。元组用圆括号表示
- defaultdict(list) 与直接dict（）的区别。如果访问一个不存在的键，defaultdict会自动创建一个空列表list作为默认值。这避免了手动检查键是否存在并初始化它们的步骤。比如：
# 使用defaultdict from collections import defaultdict mp = defaultdict(int) # 每一个值初始化为int类型 mp['a'] += 1 print(mp) # 输出: defaultdict(<class 'int'>, {'a': 1}) #使用普通的dict mp = {} if 'a' not in mp: mp['a'] = 0 mp['a'] += 1 print(mp) # 输出: {'a': 1} -
为什么不能写成key = "".join(sorted(st))
这是因为key = sorted(st) 只会返回一个排序后的字符列表，而不是一个字符串。我们使用"".join() 将排序后的字符列表连接成一个字符串，这样就可以作为哈希表的索引来使用。key = sorted(st)
3.最长连续序列
# 我写的,思路是利用指针,从第二个开始,找到连续序列就后移并记录长度,直到发现第一个不连续,记录当前最大序列长度。然后指针从刚刚位置继续往后移动寻找新的连续序列,全过程只需要遍历一次
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if not nums:
return 0
nums.sort()
longest_streak = 1
current_streak = 1
i = 0
while i < len(nums) - 1:
if nums[i] == nums[i + 1]:
i += 1
continue
elif nums[i] + 1 == nums[i + 1]:
current_streak += 1
else:
longest_streak = max(longest_streak, current_streak)
current_streak = 1
i += 1
longest_streak = max(longest_streak, current_streak)
return longest_streak
这题反而感觉没什么难度，核心在于如何跳过不必要的遍历，比如如果已知有一个x,x+1,x+2,⋯,x+y 的连续序列，而我们却重新从 x+1，x+2 或者是 x+y 处开始尝试匹配，那么得到的结果肯定不会优于枚举 x 为起点的答案。我使用的方法是指针，官方题解如下：
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
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- num_set = set(nums): 将输入的列表
nums转换为集合（就是哈希表）num_set，以便于快速查找。这个哈希表的哈希函数什么的细节就不用管了，反正你理解为一个可以快速查的表就行了。
逻辑点：
- 官方题解的多余序列跳过部分就是用的遍历每一个数，通过哈希表检查是否存在num-1。存在的话就说明这个数是前面统计过的连续序列的一部分，那就可以跳过这个数了。
原文地址：https://blog.csdn.net/m0_73872643/article/details/142168758
免责声明：本站文章内容转载自网络资源，如侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！