开封做网站优化,vi视觉设计案例,wordpress商店主题,营销网络图1. 两数之和
题目描述 给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一个元素在答案里不能重复出现思路…1. 两数之和
题目描述 给定一个整数数组 nums 和一个整数目标值 target请你在该数组中找出 和为目标值 target 的那 两个 整数并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是数组中同一个元素在答案里不能重复出现思路 通过哈希表保存每个数字nums[i]对应的下标并查找target-nums[i]是否在哈希表中这样可以通过一次遍历就完成 时间复杂度: O(N)空间复杂度: O(N)代码class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:n len(nums)if n 2:return []dic {}for i in range(n):if target - nums[i] in dic:return [dic[target - nums[i]], i]dic[nums[i]] i2. 字母异位词分组 题目描述 给你一个字符串数组请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。 字母异位词 是由重新排列源单词的所有字母得到的一个新单词。 示例 1: 输入: strs [eat, tea, tan, ate, nat, bat]输出: [[bat],[nat,tan],[ate,eat,tea]]思路 提到字母异位词要联想到两点(1) 字母异位词的字母计数的哈希表是相同的 2字母异位词按照字母序排序后的字符串是相同的 本道题就是要将字母异位词进行聚类判断方式无非上面两种由于我们通过字典存储聚类字母异位词而字典是不可哈希的无法作为字典的key因此就将排序后的字母异位词作为key 时间复杂度O(nklogk)其中 n是 strs 中的字符串的数量k是 strs 中的字符串的的最大长度。 空间复杂度O(nk) 代码 class Solution:def groupAnagrams(self, strs: List[str]) - List[List[str]]:n len(strs)if n 0:return []dic {}for i in range(n):s strs[i]s_sorted .join(sorted(s))if s_sorted not in dic:dic[s_sorted] [s]else:dic[s_sorted].append(s)return [value for value in dic.values()]如果想通过字母计数哈希表的方式来实现则不能用字典来计数需要用列表然后再转成tuple可以作为dict的key: class Solution:def groupAnagrams(self, strs: List[str]) - List[List[str]]:mp collections.defaultdict(list)for st in strs:counts [0] * 26for ch in st:counts[ord(ch) - ord(a)] 1# 需要将 list 转换成 tuple 才能进行哈希mp[tuple(counts)].append(st)return list(mp.values())3. 最长连续序列 题目描述 给定一个未排序的整数数组 nums 找出数字连续的最长序列不要求序列元素在原数组中连续的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1 输入nums [100,4,200,1,3,2]输出4解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。思路 由于序列是无序的而题目要求O(n)的解法那么想到用哈希表实现注意哈希表题目有的用字典方便有的用数组方便有的用集合方便集合set是一个无序的不重复元素序列。本题就是用set比较合适因为我们只要方便查找哪些元素是否出现即可不需要用到其他信息 首先将所有元素放入set中遍历set中的元素num如果num-1在set中说明num并不是一个连续序列的起点如果num是一个连续序列的起点那么依次判断num1num2是不是在set中即可获取以num为起点的连续序列的长度 时间复杂度O(N)因为每个元素只会被遍历一次因此数组中的每个数只会进入内层循环一次 空间复杂度O(N) 代码 class Solution:def longestConsecutive(self, nums: List[int]) - int:n len(nums)if n 0:return 0nums_set set(nums)res 1for i in nums_set:if i - 1 not in nums_set:cur_l 1cur_num iwhile cur_num 1 in nums_set:cur_num 1cur_l 1res max(res, cur_l)return res
