2.代码实现
2.1 使用HashSet实现
class Solution { public int[] intersection(int[] nums1, int[] nums2) { if(nums1.length==0 || nums1==null ||nums2.length ==0 ||nums2 == null ) { return new int[0]; } Set<Integer> set1 = new HashSet<>(); Set<Integer> set2 = new HashSet<>(); for(int i = 0;i<nums1.length;i++) { set1.add(nums1[i]); } for(int i = 0;i<nums2.length;i++) { if(set1.contains(nums2[i])) { set2.add(nums2[i]); } } int[] arr = new int[set2.size()]; int j = 0; for(int i:set2) { arr[j++] = i; } return arr; } }
2.2 使用Hash数组实现
class Solution { public int[] intersection(int[] nums1, int[] nums2) { int[] hash1 = new int[1002]; int[] hash2 = new int[1002]; for(int i : nums1) hash1[i]++; for(int i : nums2) hash2[i]++; List<Integer> resList = new ArrayList<>(); for(int i = 0; i < 1002; i++) if(hash1[i] > 0 && hash2[i] > 0) resList.add(i); int index = 0; int res[] = new int[resList.size()]; for(int i : resList) res[index++] = i; return res; } }
LeetCode T202 快乐数
今天一点也不快乐!!!
1.题目思路
这题我们仍然可以使用HashSet来帮助我们判断一个元素是否出现过,所以在判断元素是否出现过的题目都可以使用哈希法.
首先我们先创建一个HashSet set,只要目前的n不是1并且HashSet没有包含这个数字就代表没有陷入循环,也没有满足快乐数的条件,这就是循环继续的条件,循环中我们只要把这个n加入我们的set中,并获取新的n即可,所以我们写一个get函数返回值是一个n.
题目要求每一位的平方相加得到新n,这里我们就采用取模再平方的方法实现,在循环外定义一个sum作为函数的返回值,取模一次n取到n的各位,再将个位的平方除以10,依次往复,直到<0为止.
2.代码实现
class Solution { public boolean isHappy(int n) { Set<Integer> set = new HashSet<>(); while(n != 1 && !set.contains(n)) { set.add(n); n = get(n); } return n==1; } int get(int n) { int sum = 0; while(n>0) { int tmp = n%10; sum += tmp*tmp; n/=10; } return sum; } }
3.方法2:快慢指针法
快指针每次走两步,慢指针每次走一步,slow==fast为一个循环周期,判断是否为1引起的循环周期即可,是1就是快乐数,不是1就不是快乐数.
4.代码实现
class Solution { public boolean isHappy(int n) { int slow = n,fast = n; do{ fast = get(get(fast)); slow = get(slow); }while(slow != fast); return fast==1; } int get(int n) { int sum = 0; while(n>0) { int tmp = n%10; sum += tmp*tmp; n/=10; } return sum; } }
LeetCode T1 两数之和
题目链接:力扣（LeetCode）官网 - 全球极客挚爱的技术成长平台
1.思路分析
首先我么可以想到,两数之和,如果这里给定一个数,那么另一个数就是target-第一个数,因为最后要返回两个数下标形成的数组,所以首先我们先创建一个两个元素的数组res,然后这道题我们使用Map来完成,key是值,value是下标,先判断nums是否是空指针或者是空数组,
如果是就直接返回res数组,
如果不是我们就进行这样一个逻辑:用i遍历nums数组,创建变量
tmp = target-nums[i],然后判断我们的map中是否有一个值为tmp的键值对,没有就把这个键值对加入到map中,然后照这个逻辑循环.直到找到了,就将res数组的第一个元素赋值为i的下标,另一个元素则在map中寻找到tmp再找到他的下标,最后返回res数组.
2.代码实现
class Solution { public int[] twoSum(int[] nums, int target) { int[] res = new int[2]; if(nums == null || nums.length == 0) { return res; } Map<Integer,Integer> map = new HashMap<>(); for(int i=0;i<nums.length;i++) { int tmp = target-nums[i]; if(map.containsKey(tmp)) { res[0] = i; res[1] = map.get(tmp); } map.put(nums[i],i); } return res; } }
总结
在一个集合中查找某个元素是否存在就可以使用哈希表,当元素个数确定时,可以考虑使用哈希数组实现,当元素个数不确定时,可以考虑哈希表的其他实现类的结构,注意牢记哈希表的api方法.
