代码随想录day6| 242.有效的字母异位词 、349. 两个数组的交集、 202. 快乐数 、 1. 两数之和

242.有效的字母异位词

思路

• 使用暴力解法时间复杂度为O(n^2)
• 这道题需要判断字母之前是否出现过，所以使用哈希法
• 由于字符使用asc||可以找出连续的规律（a=97）,故可以使用数组来存放字母出现过的次数

步骤

• 先判断两个字符串长度是否相同，不同直接返回false；
• 创建一个长度为26的数组，来存放26个字母出现的次数
• 遍历字符串长度，第一个字符串出现的字母对应的位置每次加一；另一个字符串字母出现的位置每次减一
• 最后遍历数组，如果有位置不等于0，则返回false
• 数组中都为0，则返回true;

class Solution {public boolean isAnagram(String s, String t) {if(s.length() != t.length()){return false;}int[] arr = new int[26];for(int i = 0 ; i < s.length() ; i++){// System.out.print(s.charAt(i) - 97 + " ");arr[s.charAt(i) - 97]++;arr[t.charAt(i) - 97]--;}for(int i = 0 ; i < arr.length ; i++){System.out.print(arr[i] + " ");if(arr[i] != 0){return false;}}return true;}
}

349. 两个数组的交集

思路

• 改题目需要去重（交集结果中不能有重复数字），且返回不考虑输出结果的顺序，所以可以使用哈希法中的set集合

步骤

• 新建两个set集合，一个用来给nums1数组去重，另一个收集两个数组的交集
• 遍历nums1去重,收集在set1中
• 遍历nums2，如果set1中包含在元素，添加到resSet集合中
• 最后将收集的resSet转换为数组返回

class Solution {public int[] intersection(int[] nums1, int[] nums2) {Set<Integer> set1 = new HashSet<>();Set<Integer> resSet = new HashSet<>();//遍历数组1for (int i : nums1) {set1.add(i);}//遍历数组2的过程中判断哈希表中是否存在该元素for (int i : nums2) {if (set1.contains(i)) {resSet.add(i);}}return resSet.stream().mapToInt(x -> x).toArray();}}

202. 快乐数

思路

• 题目中说了会 无限循环，那么也就是说求和的过程中，sum会重复出现,这是无限循环结束的条件
• 判断是否重复出现可以使用set集合
• 具体思路

步骤

• 创建一个set集合判断是否重复
• 用while循环来寻找是否有符合的值，当n!=1并且n没有重复时就一直循环。
• 进入循环将n加入到set中，开始判断是否时快乐书操作，并且并且更新n的值。
• 循环结束判断n是否为1（是否为快乐数）

class Solution {public boolean isHappy(int n) {Set<Integer> record = new HashSet<>();while (n != 1 && !record.contains(n)) {record.add(n);n = getNextNumber(n);}return n == 1;}private int getNextNumber(int n) {int res = 0;while (n > 0) {int temp = n % 10;res += temp * temp;n = n / 10;}return res;}
}

1. 两数之和

思路

图文思路

步骤

• 创建一个map集合，key存放可能会被匹配的数，value中方这个数在数组中的位置。
• 用for循环来遍历数组，如果当前元素的能够匹配的数不在集合map中，则把该数放到map中，供其他数匹配
• 如果在map中找到能够匹配的数，则把这两个数的位置放到数组中返回

class Solution {public int[] twoSum(int[] nums, int target) {Map<Integer, Integer> map = new HashMap();int[] arr = new int[2];for(int i = 0 ; i < nums.length ; i++){if(map.containsKey(target-nums[i])){arr[0] = i;arr[1] = map.get(target-nums[i]);break;}map.put(nums[i],i);}return arr;}
}