LeetCode热题100(哈希篇)
题目出自Leetcode热题100：Leetcode热题100
文章目录
- 1. 两数之和
- 思路
- 代码
- C++
- Java
- Python
- 49. 字母异位词分组
- 思路
- 代码
- C++
- Java
- Python
- 128. 最长连续序列
- 思路
- 代码
- C++
- Java
- Python
- 总结
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
思路
所谓两数之和，因为目标值的存在是可以相互转化的。
如：a+b = tar
那么a = a b = tar-a。
所以我们可以遍历一遍数组，把数组元素全部存入哈希表，然后再遍历一个数组通过哈希表来判断是否存在满足题意得另一个元素。
解题步骤：
1.定义一个哈希表。
2.遍历数组，将数组元素存入哈希表中，数组元素为key，下标为value。
3.再次遍历数组，通过哈希表判断当前元素是否满足题意。注意不能使用两次相同的元素。
4.返回结果。
代码
C++
Java
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ans = new int[2];
HashMap<Integer,Integer> cnt = new HashMap<Integer,Integer>();
for(int i = 0;i<nums.length;++i)
{
cnt.put(nums[i],i);
}
for(int i = 0;i<nums.length;++i)
{
if(cnt.containsKey(target-nums[i])&&cnt.get(target-nums[i])!=i)
{
ans[0] = i;
ans[1] = cnt.get(target-nums[i]);
break;
}
}
return ans;
}
}
Python
class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
cnt = dict()
for i in range(0,len(nums)):
cnt[nums[i]] = i
nums.sort()
l = 0
r = len(nums)-1
while l<r:
if(nums[l]+nums[r]==target):
return cnt[nums[l]],cnt[nums[r]]
elif nums[l]+nums[r]>target:
r-=1
else:
l+=1
return -1,-1
49. 字母异位词分组
给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
思路
观察题目要求，我们需要把由相同字母的组成的不同单词组合给存放到一个数组中。第一个想法肯定就是哈希表，因为尽管单词的字母排列不同，但是单词的组成字母相同，这就可以让它成为key，然后我能把符合key的字母加入到哈希表当中。
那么这题的关键步骤也就出来了，只要知道这个key怎么求得。
对应key的求法，我想了3个思路，第3个最优。
版本1
开始我想到是，利用状态压缩把字母根据字母顺序存放到相应的比特位上，可是直到运行时才发现错误，毕竟字母会出现多次…。所以这是个错误版本
版本2
然后我又想到，既然版本1是因为无法记录字母的数目而错的，那么这次我把数字加上不就可以了吗。我想到是是我创建一个哈希数组来记录一个单词中每个字母出现的次数，然后再遍历这个哈希数组把这个单词的各个字母和字母出现的次数合起来当key，比如【“apple”】的key就是【“a1p2l1e1”】，这样就可以达成题目要求了，运行也通过了。但是效率还是低了。
版本3
最后我想到记录字母虽然可以满足题目要求，但是效率还是被拉慢了，还能不能优化。我想到还可以对数组排序啊，排序后的相同字母的组合单词一定相同，而且效率更高。
代码
C++
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> cnt;
for(string&s:strs)
{
string tmp(s);
sort(tmp.begin(),tmp.end());
if(cnt.find(tmp)==cnt.end())
{
cnt[tmp] = vector<string>();
}
cnt[tmp].push_back(s);
}
vector<vector<string>> ans;
for(const auto&[key,value]:cnt)
{
ans.push_back(value);
}
return ans;
}
};
Java
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
HashMap<String,List<String>> cnt = new HashMap<String,List<String>>();
for(String s:strs){
char[] arr = s.toCharArray();
Arrays.sort(arr);
String tmp = new String(arr);
if(!cnt.containsKey(tmp)){
cnt.put(tmp,new ArrayList<>());
}
cnt.get(tmp).add(s);
}
List<List<String>> ans = new ArrayList<>();
Iterator<List<String>> it = cnt.values().iterator();
for(List<String> group:cnt.values()){
ans.add(group);
}
return ans;
}
}
Python
class Solution:
def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
ans = defaultdict(list)
for s in strs:
key = "".join(sorted(s))
ans[key].append(s)
return list(ans.values())
128. 最长连续序列
给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。
请你设计并实现时间复杂度为 O(n) 的算法解决此问题。
思路
假设题目没有要O(n)的时间复杂度的话，肯定就是先将数组排序后在遍历数组计算最长的连续序列。
那么该如何只用O(n)的时间复杂度来完成这道题呢?
排序的目的是为了让连续的数字在物理层面紧挨在一起，不排序的话，现在让它们逻辑上挨在一起就行了。我们可以利用哈希表来实现数字在逻辑方面挨在一起。哈希表的key就是数字，value则为包含key的最长连续序列的长度。
那么现在的问题就变成的如何用value表示包含key的最长连续序列的长度。
遍历数组，将第i位元素num插入哈希表，就存在3种情况：
仅num在哈希表中。
num-1或者num+1也在哈希表中。
num-1和num+1都在哈希表中。
因为哈希表的value存的是长度，当有新数字插入时，与其相邻的数字长度也需要改变。但是我们不需要把这个连续序列全部都修改，只需要修改这个连续序列的边缘数字，因为连续序列内的数字改变没有意义，我们不会把数字插入到连续序列内
在代码实现中，可以把上面三种情况同一实现，具体看代码。
代码
C++
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
int ans = 0;
unordered_map<int,int> cnt;
for(int& num : nums)
{
int prev = cnt.find(num-1)==cnt.end()?0:cnt[num-1];
int suf = cnt.find(num+1)==cnt.end()?0:cnt[num+1];
if(cnt.find(num)==cnt.end())
{
cnt[num]+=(prev+suf+1);
cnt[num-prev] = cnt[num];
cnt[num+suf] = cnt[num];
}
}
for(auto&x:cnt)
{
ans = max(ans,x.second);
}
return ans;
}
};
Java
class Solution {
public int longestConsecutive(int[] nums) {
HashMap<Integer,Integer> cnt = new HashMap<>();
for(int num:nums){
int prev = cnt.containsKey(num-1)?cnt.get(num-1):0;
int suf = cnt.containsKey(num+1)?cnt.get(num+1):0;
if(!cnt.containsKey(num)){
cnt.put(num,suf+prev+1);
cnt.put(num-prev,cnt.get(num));
cnt.put(num+suf,cnt.get(num));
}
}
int ans = 0;
for(int val:cnt.values()){
ans = Math.max(ans,val);
}
return ans;
}
}
Python
class Solution:
def longestConsecutive(self, nums: List[int]) -> int:
if len(nums) == 0:
return 0
cnt = dict()
for num in nums:
prev = cnt[num-1] if num-1 in cnt else 0
suf = cnt[num+1] if num+1 in cnt else 0
if not num in cnt:
cnt[num] = prev+suf+1;
cnt[num-prev] = cnt[num]
cnt[num+suf] = cnt[num]
ans = max(cnt.values())
return ans
总结
Leetcode的热题100还是比较有代表性的。
此篇章记录我的刷图历程