快速搭建网站demo,长沙优化网站方法,个人网页制作成品免费下载,网址大全浏览器app文章目录 5 哈希表5.1 【哈希表】赎金信5.2 【数学】同构字符串5.3 【数学】单词规律5.4 【哈希表】有效的字母异位词5.5 【哈希表】字母异位词分组5.6 【双指针】两数之和5.7 【数学】快乐数5.8 【哈希表】219. 存在重复元素 II5.9 【数学】最长连续序列 6 区间6.1 【数学】汇… 文章目录 5 哈希表5.1 【哈希表】赎金信5.2 【数学】同构字符串5.3 【数学】单词规律5.4 【哈希表】有效的字母异位词5.5 【哈希表】字母异位词分组5.6 【双指针】两数之和5.7 【数学】快乐数5.8 【哈希表】219. 存在重复元素 II5.9 【数学】最长连续序列 6 区间6.1 【数学】汇总区间6.2 【区间】合并区间6.3 【区间】插入区间6.4 【区间】用最少数量的箭引爆气球 5 哈希表
5.1 【哈希表】赎金信
题目地址https://leetcode.cn/problems/ransom-note/description/?envTypestudy-plan-v2envIdtop-interview-150 分别计算两个字符串中字母的出现次数然后比较 r a n s o m N o t e ransomNote ransomNote中字母出现次数在 m a g a z i n e magazine magazine中是否一样。
class Solution:def canConstruct(self, ransomNote: str, magazine: str) - bool:r_dict {}m_dict {}# hashtablefor c in ransomNote:if c in r_dict:r_dict[c] 1else:r_dict[c] 0for c in magazine:if c in m_dict:m_dict[c] 1else:m_dict[c] 0# comparafor c in r_dict:if c not in m_dict or r_dict[c] m_dict[c]:return Falsereturn True5.2 【数学】同构字符串
题目地址https://leetcode.cn/problems/isomorphic-strings/description/?envTypestudy-plan-v2envIdtop-interview-150 如果映射是唯一的那么每对有映射关系的s和t中对应的字母在各自的字符串中首次出现的小标索引也是一致的通过这个规则来判断是否为同构字符串。
class Solution:def isIsomorphic(self, s: str, t: str) - bool:for i in range(len(s)):if s.index(s[i]) ! t.index(t[i]):return Falsereturn True5.3 【数学】单词规律
题目地址https://leetcode.cn/problems/word-pattern/description/?envTypestudy-plan-v2envIdtop-interview-150 同上一题映射关系为字母与单词一一对应。
class Solution:def wordPattern(self, pattern: str, s: str) - bool:s_new s.split( )if len(pattern) ! len(s_new):return Falsefor i in range(len(pattern)):if pattern.index(pattern[i]) ! s_new.index(s_new[i]):return Falsereturn True5.4 【哈希表】有效的字母异位词
题目地址https://leetcode.cn/problems/valid-anagram/description/?envTypestudy-plan-v2envIdtop-interview-150 分别计算字符串 s s s和 t t t中字母出现次数比较是否一致即可。
class Solution:def isAnagram(self, s: str, t: str) - bool:s_dict {}t_dict {}# hashtable_buildfor c in s:if c in s_dict:s_dict[c] 1else:s_dict[c] 0for c in t:if c in t_dict:t_dict[c] 1else:t_dict[c] 0# judge_stringif len(s_dict) ! len(t_dict):return Falsefor c in s_dict:if c not in t_dict or s_dict[c] ! t_dict[c]:return Falsereturn True5.5 【哈希表】字母异位词分组
题目地址https://leetcode.cn/problems/group-anagrams/description/?envTypestudy-plan-v2envIdtop-interview-150 方法一分别计算每个单词的字母出现次数将一样的单词分为一组。 方法二每组异位词经过词内排序后都会是同一个单词根据这个规则构建哈希表。
# 方法一
class Solution:def groupAnagrams(self, strs: List[str]) - List[List[str]]:strs_dict [{} for _ in range(len(strs))]strs_visited [0]*len(strs)# hashtable_buildfor i in range(len(strs)):for c in strs[i]:if c in strs_dict[i]:strs_dict[i][c] 1else:strs_dict[i][c] 1# divideans []for i in range(len(strs)):tmp []if strs_visited[i] 0:tmp.append(strs[i])strs_visited[i] 1for j in range(i1,len(strs)):if strs_dict[j] strs_dict[i] and strs_visited[j] 0:tmp.append(strs[j])strs_visited[j] 1ans.append(tmp)return ans
# 方法二
class Solution:def groupAnagrams(self, strs: List[str]) - List[List[str]]:hash_table {}for s in strs:tmp .join(sorted(s))if tmp in hash_table:hash_table[tmp].append(s)else:hash_table[tmp] [s]return list(hash_table.values())5.6 【双指针】两数之和
题目地址https://leetcode.cn/problems/two-sum/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码。
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:tmp nums.copy()tmp.sort()left,right 0,len(nums)-1while leftright:if tmp[left]tmp[right] target:index_a nums.index(tmp[left])nums[index_a] pow(10,9)1index_b nums.index(tmp[right])return [index_a,index_b]elif tmp[left]tmp[right] target:left 1else:right - 1 5.7 【数学】快乐数
题目地址https://leetcode.cn/problems/happy-number/?envTypestudy-plan-v2envIdtop-interview-150 结果为 1 1 1就是快乐数出现循环就不是快乐数。
class Solution:def isHappy(self, n: int) - bool:cir_num []while True:if n 1:return Trueif n in cir_num:return Falsecir_num.append(n)str_num str(n)n sum(int(c)**2 for c in str_num)5.8 【哈希表】219. 存在重复元素 II
题目地址https://leetcode.cn/problems/contains-duplicate-ii/description/?envTypestudy-plan-v2envIdtop-interview-150 详见代码。
class Solution:def containsNearbyDuplicate(self, nums: List[int], k: int) - bool:idx_dict {}for i in range(len(nums)):if nums[i] in idx_dict:if i-idx_dict[nums[i]] k:return Trueidx_dict[nums[i]] ireturn False5.9 【数学】最长连续序列
题目地址https://leetcode.cn/problems/longest-consecutive-sequence/description/?envTypestudy-plan-v2envIdtop-interview-150 排序后逐一比较即可并更新最长长度。
class Solution:def longestConsecutive(self, nums: List[int]) - int:if len(nums) 0:return 0nums list(set(nums))nums.sort()max_long,tmp_long 1,1for i in range(1,len(nums)):if nums[i]-nums[i-1] 1:tmp_long 1else:max_long max(max_long,tmp_long)tmp_long 1return max(max_long,tmp_long)6 区间
6.1 【数学】汇总区间
题目地址https://leetcode.cn/problems/summary-ranges/description/?envTypestudy-plan-v2envIdtop-interview-150 逐一比较相邻元素差值是否为 1 1 1把差值为 1 1 1的元素合并到一个区间剩下的单独一个区间。
class Solution:def summaryRanges(self, nums: List[int]) - List[str]:ans []# array_len 0if len(nums) 0:return ans# array_len ! 0range_l,range_r nums[0],nums[0]for i in range(1,len(nums)):if nums[i] - nums[i-1] 1:range_r nums[i]else:rg str(range_l) - str(range_r) if range_l ! range_r else str(range_l)ans.append(rg)range_l range_r nums[i]rg str(range_l) - str(range_r) if range_l ! range_r else str(range_l)if rg not in ans:ans.append(rg)return ans6.2 【区间】合并区间
题目地址https://leetcode.cn/problems/merge-intervals/description/?envTypestudy-plan-v2envIdtop-interview-150 根据区间的第一个元素进行排序然后依次比较区间的收尾元素进行合并。
class Solution:def merge(self, intervals: List[List[int]]) - List[List[int]]:intervals.sort()l,r intervals[0][0],intervals[0][1]ans []for i in range(1,len(intervals)):if intervals[i][0] r:r max(intervals[i][1],r)else:ans.append([l,r])l,r intervals[i][0],intervals[i][1]if [l,r] not in ans:ans.append([l,r])return ans6.3 【区间】插入区间
题目地址https://leetcode.cn/problems/insert-interval/description/?envTypestudy-plan-v2envIdtop-interview-150 将新区间插入列表中然后进行排序再合并。
class Solution:def insert(self, intervals: List[List[int]], newInterval: List[int]) - List[List[int]]:intervals.append(newInterval)intervals.sort()l,r intervals[0][0],intervals[0][1]ans []for i in range(1,len(intervals)):if intervals[i][0] r:r max(intervals[i][1],r)else:ans.append([l,r])l,r intervals[i][0],intervals[i][1]if [l,r] not in ans:ans.append([l,r])return ans6.4 【区间】用最少数量的箭引爆气球
题目地址https://leetcode.cn/problems/minimum-number-of-arrows-to-burst-balloons/description/?envTypestudy-plan-v2envIdtop-interview-150 按照每个区间的第二个元素进行排序如果区间有交叉元素则需要一支箭循环时记录当前的最末尾位置如果遍历超过了这个最末尾位置则需要一支箭。
class Solution:def findMinArrowShots(self, points: List[List[int]]) - int:points.sort(key lambda x:x[1])end points[0][1]ans 1for i in range(1,len(points)):if points[i][0] end:ans 1end points[i][1]return ans
