有效的字母异位词
思路:
数组作为一个简单的哈希表,可以用来记录字符串中每个字符出现的次数。
可以设置一个数组,第一轮遍历s中的字符,字符每出现一次,在数组对应位置+1。第二轮遍历t中的字符,字符每出现一次,在数组对应位置-1。最后遍历作为哈希表的数组,如果都为0,则说明每个字符出现的次数相同,否则不满足题目要求。
代码:
class Solution {
public boolean isAnagram(String s, String t) {
//声明大小为26的数组。
int[] record = new int[26];
//第一轮遍历,出现的字符在对应位置+1
for(int i = 0; i < s.length(); i++){
record[s.charAt(i) - 'a']++;//只需要求出对应位置即可
}
//第二轮遍历,出现的字符在对应位置-1
for(int i = 0; i < t.length(); i++){
record[t.charAt(i) - 'a']--;
}
//只要有一个不为0.则不符合要求
for(int i = 0; i < record.length; i++){
if(record[i] != 0){
return false;
}
}
return true;
}
}
两个数组的交集
数组法
用数组来做哈希表,前提条件:给定的两个数组大小要是确定的。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int[] hash1 = new int[1005];
int[] hash2 = new int[1005];
//遍历第一个数组的所有元素,将出现的元素在hash1对应的位置+1
for(int i:nums1){
hash1[i]++;
}
//遍历第二个数组的所有元素,将出现的元素hash2对应的位置+1
for(int i:nums2){
hash2[i]++;
}
List<Integer> resList = new ArrayList<>();
//如果hash1与hash2中同一位置元素个数大于1,说明在两个数组中都有存在,加入到list中
for(int i = 0; i < 1005; i++){
if(hash1[i] > 0 && hash2[i] > 0){
resList.add(i);
}
}
int[] res = new int[resList.size()];
int index = 0;
for(int i: resList){
res[index++] = i;
}
return res;
}
}
hashset
根据题目要求,交集中的元素是不重复且没有顺序要求的,因此可以使用hashset来作为哈希表。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1 == null || nums1.length == 0 || nums2 == null || nums2.length == 0){
return new int[0];
}
Set<Integer> set1 = new HashSet<>();
Set<Integer> resSet = new HashSet<>();
//遍历nums1数组中的每一个元素,加入到hashset的哈希表中
for(int i : nums1){
set1.add(i);
}
//遍历nums2数组中的每一个元素,判断hashset中是否存在对应元素,存在就加入的resSet中
for(int i : nums2){
if(set1.contains(i)){
resSet.add(i);
}
}
//声明一个新数组,将resSet中的元素复制到该数组并输出
int[] arr = new int[resSet.size()];
int index = 0;
for(int i : resSet){
arr[index++] = i;
}
return arr;
}
}
快乐数
题目中提示,可能是无限循环,也就是说平方和的数字会重复出现,重复出现时,说明得不到结果。也就是说,快速判断某个数是否出现在集合中,考虑哈希法。
class Solution {
public boolean isHappy(int n) {
Set<Integer> resSet = new HashSet<>();
//判断n是否符合条件,是否已经出现过
while(n != 1 && !resSet.contains(n)){
resSet.add(n);
n = getNextNumber(n);
}
//如果n=1,则说明n是快乐数,返回true。如果n!=1,则说明已经进入了无限循环,不可能再得到1的结果,返回false。
return n == 1;
}
//获取下一个平方和
private int getNextNumber(int n){
int res = 0;
while(n > 0){
int temp = n % 10;
res += temp * temp;
n /= 10;
}
return res;
}
}
标签:遍历,哈希,int,随想录,++,算法,resSet,数组,new
From: https://www.cnblogs.com/forest-pan/p/18318291