《LeetCode 热题 100》
《LeetCode 热题 100》持续更新
- 一、hash表
- 1.两数之和
- 49.字母异位词分组
- 128.最长连续序列
一、hash表
1.两数之和
【题解】遍历nums数组，判断target-num是否在hash表中，如果不在就把当前遍历的数字和其下表加入到hash表中，如果在则返回hash表中数字的下标以及当前数字下标。
当然也可以使用暴力求解，第二层遍历看target-num是否在数组nums中。
【代码】
class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""hashmap=dict()for i,num in enumerate(nums):if target-num in hashmap:return [hashmap[target-num],i]hashmap[nums[i]]=i
49.字母异位词分组
【题解】对字符串数组中每个单词进行排序，使得其按正序排序。接着遍历排序过的字符串数组，并把排列相同的单词放入到hash表中，key为字母排序，值为字符串数组中的单词。
【代码】
strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
res = dict()
sortedStrs = [''.join(sorted(list(s))) for s in strs]
for i in range(len(sortedStrs)):if sortedStrs[i] not in res.keys():res[sortedStrs[i]] = [strs[i]]else:res[sortedStrs[i]].append(strs[i])
print( list(res.values()))
128.最长连续序列
【题解】用一个set存储list，然后遍历这个set，看当前数的前一个数在不在set中，如果在就下一个，如果不在一直循环直到下一个数不在。为什么要查看当前数的前一个数在不在，是因为避免重复循环，就是要找到第一个循环的数（即最小的数）。
class Solution:def longestConsecutive(self, nums: List[int]) -> int:max_len=0num_set =set(nums)for num in num_set:if (num-1) not in num_set:seq_len=1while (num+1) in num_set:seq_len+=1num+=1max_len = max(max_len,seq_len)return max_len