系列文章目录
目录
- 系列文章目录
- 242.有效的字母异位词
- 349. 两个数组的交集
- ①使用HashSet
- ②使用Hash数组
- 202. 快乐数
- 1. 两数之和
- ①暴力解法（时间复杂度不符合要求）
- ②使用HashMap法
242.有效的字母异位词
这道题是数组在哈希表中的典型应用。
因为只有26个小写字母，且这26个元素是连续的，所以采用数组这种数据结构。将字符串的字母减去字母a得到的就是从0到25这26个字母的下标索引。数组的值就是元素出现的次数，也就是遍历到这个元素，对应的数组值就++。这样就记录了第一个字符串中每个元素出现的次数。再遍历第二个字符串，让数组值--，最后判断数组值是否全为0即可。
class Solution {public boolean isAnagram(String s, String t) {int[] record = new int[26];for (int i = 0; i < s.length(); i++) {record[s.charAt(i) - 'a']++;// 并不需要记住字符a的ASCII，只要求出一个相对数值就可以了}for (int i = 0; i < t.length(); i++) {record[t.charAt(i) - 'a']--;}for (Integer i : record) {if(i!=0){// record数组如果有的元素不为零0，说明字符串s和t 一定是谁多了字符或者谁少了字符。return false;}}return true; // record数组所有元素都为零0，说明字符串s和t是字母异位词}
}
349. 两个数组的交集
①使用HashSet
将第一个数组放到Set中，然后看第二个数组的值有没有在里面出现，出现的话就记录。
剪枝：在已知不符合条件的情况下，剪枝避免做无效判断。因为遍历本质是在决策，决策是为了求得结果，已知结果的决策就没有必要进行了。
//判断条件if(nums1==null||nums1.length==0||nums2==null||nums2.length==0){return new int[0];}
import java.util.HashSet;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int[] intersection(int[] nums1, int[] nums2) {//判断条件if(nums1==null||nums1.length==0||nums2==null||nums2.length==0){return new int[0];}HashSet<Integer> set1 = new HashSet<>();HashSet<Integer> set2 = new HashSet<>();//遍历数组1
/* for (int i = 0; i < nums1.length; i++) {set1.add(nums1[i]);}*/for (int i : nums1) {set1.add(i);}//遍历数组2的过程中判断哈希表中是否存在该元素// ①如果加不进去，则说明该元素在第一个数组中存在// ②直接使用contains方法来查看集合中是否有该元素
/* for (int i = 0; i < nums2.length; i++) {if (!set1.add(nums2[i])) {//①如果加不进去，则说明该元素在第一个数组中出现过set2.add(nums2[i]);}*/for (int i : nums2) {if (set1.contains(i)) {//②直接使用contains方法来查看集合中是否有该元素set2.add(i);}}
/* //方法1：将结果集合转为数组return set2.stream().mapToInt(x -> x).toArray();*///方法2：另外申请一个数组存放setRes中的元素,最后返回数组int[] arr = new int[set2.size()];int i = 0;for (Integer setnum : set2) {arr[i++] = setnum;}return arr;}
}
Set 的常用方法：add：添加单个元素；size：获取元素个数。contains：查找元素是否存在；也可再次加入元素看能否加进去来判断元素是否存在。需要注意的是，Set 有toArray的方法，该方法是重写接口Collection的方法。可返回包含此集合中所有元素的数组。
但是转换成数组的元素类型是object，所以还是建议重新创建一个数组来存放Set集合中的值。
//方法1：将结果集合转为数组return set2.stream().mapToInt(x -> x).toArray();
//方法2：另外申请一个数组存放setRes中的元素,最后返回数组int[] arr = new int[set2.size()];int i = 0;for (Integer setnum : set2) {arr[i++] = setnum;}return arr;
②使用Hash数组
class Solution { public int[] intersection(int[] nums1, int[] nums2) { int[] hash1 = new int[1003]; int[] hash2 = new int[1003]; //nums1中出现的字母在hash1数组中做记录 for (int i = 0; i < nums1.length; i++) { hash1[nums1[i]]++; } //nums2中出现的字母在hash2数组中做记录 for (int i = 0; i < nums2.length; i++) { hash2[nums2[i]]++; } //创建一个实现List集合的实现类来存相同元素， // ArrayList效率比Vector高，改查效率比LinkedList高 ArrayList<Integer> resList = new ArrayList<>(); for (int i = 0; i < hash1.length; i++) { if (hash1[i] > 0 && hash2[i] > 0) {//如果相同下标位置值都大于0，说明元素有交集 resList.add(i); } } //方法1：将结果集合转为数组 //return resList.stream().mapToInt(x -> x).toArray();//方法2：另外申请一个数组存放setRes中的元素,最后返回数组 int[] arr = new int[resList.size()]; int index = 0; for (Integer i : resList) { arr[index++] = i; } return arr; }
因toArray方法是重写接口Collection的方法，故ArrayList也能调用toArray方法。
//方法1：将结果集合转为数组 return resList.stream().mapToInt(x -> x).toArray();
//方法2：另外申请一个数组存放setRes中的元素,最后返回数组 int[] arr = new int[resList.size()]; int index = 0; for (Integer i : resList) { arr[index++] = i; } return arr;
202. 快乐数
①当不知道一个数是几位数时，求各个位上的平方和的方法要记住。就取这个数的个位（模，即%10），然后将这个数/10，再求个位，while循环，判断的条件是这个数>0。
int sum = 0;while (n > 0) {int temp = n % 10;//得到末位数sum += temp * temp;n = n / 10;//缩小一位}
②主方法isHappy中退出循环需要两个条件①n为1。②集合中已有该元素。故最后在返回值时需return n == 1;来判断当退出循环时是否是满足第①条件退出的。
class Solution {public boolean isHappy(int n) {HashSet<Integer> set = new HashSet<>();/* while (n != 1) {if (!(set.add(n))) {//加过集合的元素再加就为falsereturn false;}n = getNextNumber(n);}return true;*///退出该循环有两个条件：①n为1②集合中已有该元素while (n != 1 && !set.contains(n)) {set.add(n);n = getNextNumber(n);}return n == 1;}private int getNextNumber(int n) {int sum = 0;while (n > 0) {int temp = n % 10;//得到末位数sum += temp * temp;n = n / 10;//缩小一位}return sum;}
}
1. 两数之和
①暴力解法（时间复杂度不符合要求）
class Solution {public int[] twoSum(int[] nums, int target) {//暴力解法for (int i = 0; i < nums.length; i++) {for (int j = i+1; j < nums.length; j++) {if(nums[i]==target-nums[j]){return new int[]{i,j};}}}return new int[0];}
}
②使用HashMap法
Map的key值有没有出现过的判断方法：containsKey()。
剪枝（自己没写），若数组为null或者长度为0则直接返回退出：
//剪枝(自己没写）if (nums == null || nums.length == 0) {return res;}
import java.util.HashMap;//leetcode submit region begin(Prohibit modification and deletion)
class Solution {public int[] twoSum(int[] nums, int target) {//使用HashMap法int[] res = new int[2];//只创建一个数组(自己创建了两个数组)//剪枝(自己没写）if (nums == null || nums.length == 0) {return res;}HashMap<Integer, Integer> map = new HashMap<>();for (int i = 0; i < nums.length; i++) {int temp = target - nums[i];// 遍历当前元素，并在map中寻找是否有匹配的keyif (map.containsKey(temp)) {//return new int[]{i, map.get(temp)};res[0] = i;res[1] = map.get(temp);return res;}map.put(nums[i], i); // 如果没找到匹配对，就把访问过的元素和下标加入到map中}//return new int[0];return res;}
}
//leetcode submit region end(Prohibit modification and deletion)
