代码随想录算法训练营第六天 | 242-有效的字母异位词、349-两个数组的交集、202-快乐数、1-两数之和
LeetCode242 有效的字母异位词
题目链接：https://leetcode.cn/problems/valid-anagram/
文章讲解：https://programmercarl.com/0242.有效的字母异位词.html
视频讲解：https://www.bilibili.com/video/BV1YG411p7BA/?vd_source=b989f2b109eb3b17e8178154a7de7a51
一拿到题目，首先是想构建一个Map，然后发现题目所给字符串只包含小写字母，那其实一个26大小的char数组就够用
解题思路是建立一个大小为26的char数组作为hash表，先遍历字符串s，把出现的字母在数组对应的数值加一，然后再遍历字符串t，把出现的字母在数组对应的数值减一。最后再遍历一遍hash表，若有非零，则说明s和t不是字母异位词
class Solution {public boolean isAnagram(String s, String t) {char[] dict = new char[26];for(int i = 0;i < s.length();i++){dict[s.charAt(i) - 'a']++;}for(int i = 0;i < t.length();i++){dict[t.charAt(i) - 'a']--;}for(int i = 0;i < 26;i++){if(dict[i] != 0){return false;}}return true;}
}
LeetCode349 两个数组的交集
题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/solutions/
文章讲解：https://programmercarl.com/0349.两个数组的交集.html
视频讲解：https://www.bilibili.com/video/BV1ba411S7wu/?spm_id_from=333.1391.0.0&vd_source=b989f2b109eb3b17e8178154a7de7a51
一拿到题目，发现还是用一个hash数组就可以解决：先遍历nums1数组，将nums1中出现的元素在hash数组对应位置进行标记，然后再遍历nums2数组，将nums2命中hash表被标记位置的元素，记录在HashSet里，最后再从HashSet输出成int数组提交即可
class Solution {public int[] intersection(int[] nums1, int[] nums2) {int[] hash = new int[1001];for(int i = 0;i < nums1.length;i++){hash[nums1[i]] = 1;}HashSet<Integer> dict = new HashSet<Integer>();for(int i = 0;i < nums2.length;i++){if(hash[nums2[i]] == 1){dict.add(nums2[i]);}}int[] result = new int[dict.size()];int cnt = 0;for(Integer i : dict){result[cnt] = i;cnt++;}return result;}
}
LeetCode202 快乐数
题目链接：https://leetcode.cn/problems/happy-number/description/
文章讲解：https://programmercarl.com/0202.快乐数.html
这题的难点主要在发现不是快乐数的数会陷入循环，且不会越来越大直到无穷大
利用HashSet来记录得到过的数，若再次出现则说明陷入了循环，即不是快乐数
class Solution {public boolean isHappy(int n) {String str = ((Integer)n).toString();HashSet<Integer> dict = new HashSet<Integer>();while(true){int num = 0;for(int i = 0;i < str.length();i++){num += Math.pow(str.charAt(i) - '0', 2);}if(num == 1){return true;}if(dict.contains(num)){return false;}else{dict.add(num);str = ((Integer)num).toString();}}}
}
看了题解之后发现，还可以用快慢指针来检测是否存在循环，快指针一次移动两个阶段，慢指针一次移动一个阶段，则会出现两种情况：
- 快指针先到1，说明所给数是快乐数
- 慢指针与快指针相遇，说明存在循环，不是快乐数
class Solution {private int getNext(int n){int num = 0;while(n > 0){int d = n % 10;num += d * d;n /= 10;}return num;}public boolean isHappy(int n) {int fast = getNext(n);int slow = n;while(fast != 1 && fast != slow){fast = getNext(getNext(fast));slow = getNext(slow);}return fast == 1;}
}
LeetCode1 两数之和
题目链接：https://leetcode.cn/problems/two-sum/description/
文章讲解：https://programmercarl.com/0001.两数之和.html
视频讲解：https://www.bilibili.com/video/BV1aT41177mK/?vd_source=b989f2b109eb3b17e8178154a7de7a51
首先用的是两层for循环暴力求解，因为数据集没那么大所以侥幸通过，但还得再继续优化优化，对于这题O(n^2)还是不够优雅
class Solution {public int[] twoSum(int[] nums, int target) {int[] result = new int[2];for(int i = 0;i < nums.length;i++){for(int j = i + 1;j < nums.length;j++){if(nums[i] + nums[j] == target){result[0] = i;result[1] = j;return result;}}}return result;}
}
听了Carl哥的讲解，发现用HashMap存已遍历的数和对应下标，for循环遍历到一个新的元素nums[i]，就在HashMap里找有没有 target-nums[i] ，这样用一层for循环就做完了之前两层for循环的事，很妙呀
class Solution {public int[] twoSum(int[] nums, int target) {HashMap<Integer,Integer> dict = new HashMap<Integer,Integer>();int[] result = new int[2];for(int i = 0;i < nums.length;i++){if(dict.containsKey(target-nums[i])){result[0] = dict.get(target-nums[i]);result[1] = i;return result;}else{dict.put(nums[i],i);}}return result;}
}