算法训练第六天

242.有效的字母异位词

思路：

如果是python写的话，会很简单，只需要判断sorted返回的两个字符串是否相等即可，如果使用哈希的思想去解决的话，就开一个字典记录每个字符出现的次数，然后遍历一遍字典看每个字符出现的次数是否一致即可。

代码：

class Solution(object):def isAnagram(self, s, t):""":type s: str:type t: str:rtype: bool"""if sorted(s)==sorted(t):return Trueelse:return False

349. 两个数组的交集

思路：

这里可以使用set的交函数。

代码：

class Solution(object):def intersection(self, nums1, nums2):""":type nums1: List[int]:type nums2: List[int]:rtype: List[int]"""set1 = set(nums1)set2 = set(nums2)return list(set1 & set2)

202. 快乐数

思路：

我们需要开一个数组或者哈希表，只需要查看当前的数是否被计算过即可。

代码：

class Solution(object):def calculate(self,n):sum = 0while n:sum += (n%10)*(n%10)n//=10return sumdef isHappy(self, n):""":type n: int:rtype: bool"""hash_map = {}while n!=1:res = hash_map.get(n,-1)if res>0:return Falsehash_map[n]=1n = self.calculate(n)return True

1. 两数之和

思路：

这道题可以使用暴力搜索，时间复杂度为O(n^2)，但是如果使用哈希表，可以将时间复杂度降为O(n)，那在此我们使用哈希的方式。

代码：

class Solution(object):def twoSum(self, nums, target):""":type nums: List[int]:type target: int:rtype: List[int]"""hash_map = {}for i in range(len(nums)):if hash_map.get(nums[i]):hash_map[nums[i]].append(i)else:hash_map[nums[i]]=[i]for k in hash_map.keys():key = target-kif key == k:if len(hash_map.get(key))>1:return hash_map.get(key)else:continueres = hash_map.get(key,-1)if res==-1:continue      else:second = res[0]first = hash_map.get(k)[0]return [first,second]