系列文章目录
目录
- 系列文章目录
- 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))) {//加过集合的元素再加就为false
return 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中寻找是否有匹配的key
if (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)
