免费网站源码下载,419黄冈分类信息网,eclipse开发网站用vue做前端,公司网站怎样添加和修改内容哈希表
哈希表可以根据键在O(1)时间内进行访问。 哈希表实际上可以看成是一个数组#xff0c;但是可以通过哈希函数计算出数组下标#xff0c;直接访问。
常用的有集合set()#xff0c;字典dict()。
有效的字母异位词 242.
#字典 给定两个字符串 s 和 t #xff0c;编写…哈希表
哈希表可以根据键在O(1)时间内进行访问。 哈希表实际上可以看成是一个数组但是可以通过哈希函数计算出数组下标直接访问。
常用的有集合set()字典dict()。
有效的字母异位词 242.
#字典 给定两个字符串 s 和 t 编写一个函数来判断 t 是否是 s 的字母异位词。
注意若 s 和 t 中每个字符出现的次数都相同则称 s 和 t 互为字母异位词。
使用数组
class Solution:def isAnagram(self, s: str, t: str) - bool:record [0] * 26for i in s:#并不需要记住字符a的ASCII只要求出一个相对数值就可以了record[ord(i) - ord(a)] 1for i in t:record[ord(i) - ord(a)] - 1return all(x False for x in record)使用字典
class Solution:def isAnagram(self, s: str, t: str) - bool:from collections import defaultdicts_dict defaultdict(int)t_dict defaultdict(int)for x in s:s_dict[x] 1for x in t:t_dict[x] 1return s_dict t_dictPython还提供了一个默认的计数器Counter效果和上面一样。
class Solution(object):def isAnagram(self, s: str, t: str) - bool:from collections import Counterreturn Counter(s) Counter(t)两个数组的交集 349.
#集合 给定两个数组 nums1 和 nums2 返回 它们的交集 。 Python 的set实现了集合运算直接转换成集合然后求交。
class Solution:def intersection(self, nums1: List[int], nums2: List[int]) - List[int]:set_1 set(nums1)set_2 set(nums2)return list(set_1 set_2)快乐数 202.
#集合 编写一个算法来判断一个数 n 是不是快乐数。
使用集合来判断n有没有出现过。
class Solution:def isHappy(self, n: int) - bool:def get_sum(num):s 0while num: s (num % 10)** 2num num // 10return svisited set()while n ! 1 and not n in visited:visited.add(n)n get_sum(n)return n 1除了正常的取余获得num各位数字还可以用字符串 n sum(int(i) ** 2 for i in str(n))两数之和 1.
#字典 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 容易想到用暴力循环来两两匹配时间复杂度为O(N^2)。但是学完字典后可以想到用字典存储出现过的数字及下标。 遍历过程中可以查看字典中是否有能组成target的数。时间复杂度为O(N)。 也可以用集合存储数字但是还需要找一次下标
class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:d dict()for i,n in enumerate(nums):if target-n in d:return i, d[target-n]else:d[n] i四数相加II 454.
#字典 给你四个整数数组 nums1、nums2、nums3 和 nums4 数组长度都是 n 请你计算有多少个元组 (i, j, k, l) 能满足
0 i, j, k, l nnums1[i] nums2[j] nums3[k] nums4[l] 0
两数相加的扩展版。 从四个数组中各取一个数和为0。 容易想到将四数相加变成两数相加。这样就将4重循环变成2重循环。 nums1 nums2 -(nums3 nums4)
class Solution:def fourSumCount(self, nums1: List[int], nums2: List[int], nums3: List[int], nums4: List[int]) - int:d defaultdict(int)for i in nums1:for j in nums2:d[ij] 1count 0 for k in nums3:for l in nums4:count d[-(kl)]return count赎金信 383.
#字典 给你两个字符串ransomNote 和 magazine 判断 ransomNote 能不能由 magazine 里面的字符构成。
和 有效的字母异位词有点像但是这里只要magazine中字符数量大于ransomNote。
class Solution:def canConstruct(self, ransomNote: str, magazine: str) - bool:d_ransomNote Counter(ransomNote)d_magazine Counter(magazine)for k,v in d_ransomNote.items():if k not in d_magazine or d_magazine[k] v:return Falsereturn True
三数之和 15.
#字典 #双指针 给你一个整数数组 nums 判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请
你返回所有和为 0 且不重复的三元组。 可以用字典做两重循环确定num[i]和nums[j]然后用字典确定是否有nums[k] -(nums[i] nums[j])。
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:d defaultdict(list)for i,n in enumerate(nums):d[n].append(i)res set()for i in range(len(nums)):for j in range(i1, len(nums)):if -(nums[i] nums[j]) in d and d[-(nums[i] nums[j])] ! [i] \and d[-(nums[i] nums[j])] ! [j] and d[-(nums[i] nums[j])] ! [i,j]:res.add(tuple(sorted([nums[i], nums[j],-(nums[i] nums[j]) ])))return [list(t) for t in res]双指针 需要先对nums排序。 固定i后用指针left和right找剩余的两个数。 这里我去重直接用了set没有像网站那样额外判断。
class Solution:def threeSum(self, nums: List[int]) - List[List[int]]:nums.sort()res set()for i in range(len(nums)):if nums[i] 0:breakif i 0 and nums[i] nums[i-1]:continueleft i1right len(nums) - 1while right left:s nums[i] nums[left] nums[right]if s 0:left 1elif s 0:right - 1else:res.add((nums[i], nums[left], nums[right]))right - 1left 1return [list(t) for t in res]四数之和 18.
#双指针 在三数之和的基础上再套一层for循环。
class Solution:def fourSum(self, nums: List[int], target: int) - List[List[int]]: nums.sort()res set()for i in range(len(nums)):for j in range(i1, len(nums)):left j1right len(nums) - 1while left right:s nums[i]nums[j] nums[left] nums[right]if s target:left 1elif s target:right - 1else:res.add((nums[i],nums[j] , nums[left] , nums[right]))left 1right - 1return [list(t) for t in res]哈希表小结
哈西表常用来判断元素是否出现过统计出现次数去重。 本章题目大多数和数组相关用到了对数组排序、双指针的方法。
