瓜子网网站建设策划书,洛阳市河阳建设工程有限公司网站,快速开发平台,网站建设成功案例方案leetcode-hot100-hash表 1. 两数之和49. 字母异位次分组128. 最长连续序列 hash表主要功能是#xff1a;记录#xff0c;当做查找表#xff0c;时间换空间的一种策略。
1. 两数之和
nums [2,7,11,15], target 9 输出#xff1a;[0,1] **解释#xff1a;因为 nums[0] … leetcode-hot100-hash表 1. 两数之和49. 字母异位次分组128. 最长连续序列 hash表主要功能是记录当做查找表时间换空间的一种策略。
1. 两数之和
nums [2,7,11,15], target 9 输出[0,1] **解释因为 nums[0] nums[1] 9 返回 [0, 1] 。
你可以假设每种输入只会对应一个答案。 第一思路双层循环第一层循环 i in [0, N], 第二层循环 j in [i1, N], 依次计算nums[i] nums[j]判断是否等于target如果相等返回下标ij否则继续遍历直到循环结束返回[-1, -1]表示不存在这组解。 for i in range(0, N):for j in range(i1, N):temp nums[i] nums[j]if temp target:return [i, j]return [-1, -1]存在的问题时间复杂度过高。 因为是一个查找问题所以想到用hash表。
如果我们先过一遍数组将数值和下标的对应关系存储在hash表中。然后再过一遍数组判断target - nums[i]是否在hash表中如果在说明知道了返回即可如果没找到遍历下一个元素。 另外我们可以将hash表存储和数组遍历合并到一次遍历中。
hash_table {}for i in range(0, N):if target - nums[i] in hash_table:return [hash_table[target-nums[i]], i]hash_table[nums[i]] ireturn [-1, -1] # 没找到class Solution:def twoSum(self, nums: List[int], target: int) - List[int]:table {}for i in range(len(nums)):if target - nums[i] in table:return [table[target-nums[i]], i]table[nums[i]] ireturn [-1, -1]49. 字母异位次分组
输入: strs [eat, tea, tan, ate, nat, bat] 输出: output[ [“bat”],[“nat”,“tan”],[“ate”,“eat”,“tea”] ]
对数组中的每一项进行排序这样异位词排序后顺序一致我们可以把顺序一致的字符串合并遍历结束后返回即可。
hash_table defaultdict(list)for st in strs:key .join(sorted(st))hash_table[key].append(st)return hash_table.values()异位次的统一化可以通过数据统计实现将异位次转换成统计信息如a3表示a出现了3次。 因为是字母我们可以用26个英文字符进行统计。
128. 最长连续序列
示例 1
**输入nums [100,4,200,1,3,2] 输出4 解释最长数字连续序列是 [1, 2, 3, 4]。它的长度为 4。
示例 2
**输入nums [0,3,7,2,5,8,4,6,0,1] 输出9
采用集合记录数组中的每个元素然后查找连续序列最后再多个连续序列中查找最长序列。 如何查找连续序列以当前元素为第一个元素向后查找如果找到了继续找连续序列因为连续序列所以当前元素-1应该不在hash表或集合中。直到找不到说明找到了以当前元素为第一个元素的连续序列然后以下一个元素为起点查找新的序列。
hs set(nums)longest 0
for num in nums:if nums-1 not in hs:cur_len 1cur_num numswhile cur_num1 in hs:cur_len 1cur_num 1longest max(longest, cur_len)return longestclass Solution:def longestConsecutive(self, nums: List[int]) - int:longest_streak 0num_set set(nums)for num in num_set:if num - 1 not in num_set:current_num numcurrent_streak 1while current_num 1 in num_set:current_num 1current_streak 1longest_streak max(longest_streak, current_streak)return longest_streakclass Solution {
public:int longestConsecutive(vectorint nums) {unordered_setint hash;for (auto x : nums)hash.insert(x);int longestSteak 0;for (auto x: hash) {if (!hash.count(x-1)){int curNum x, curSteak 1;while (hash.count(curNum1)) {curNum 1;curSteak 1;}longestSteak max(longestSteak, curSteak);}}return longestSteak;}
};hash表主要功能是记录当做查找表时间换空间的一种策略。
