leetcode242.有效的字母异位词
进入哈希表章节
思路:首先数组本身就是一个简单的哈希表,我们可以利用一个数组来记录元素出现的次数,字母一共有26个,我们可以定义一个长度为26的数组,数组下标依次对应记录a~z,因为要比较s和t两个字符串的元素出现次数。我们可以设置 当s出现了则数组对应的元素则+1,T中出现则-1;最后每个元素所记录的就是出现次数,当某一个元素!=0,则不满足字母异位。
class Solution {
public boolean isAnagram(String s, String t) {
int[] record=new int[26]; //定义一个长度为26的数组
if(s.length()!=t.length()){ //首先判断是否长度相等 不相等 直接不满足条件
return false;
}
for(int i=0;i<s.length();i++){ // 遍历s和t的字符
record[s.charAt(i)-'a']++; //s.charAt(i)-'a'对应着a~z由0到25的下标
record[t.charAt(i)-'a']--; // s ++ t 则--
}
for(int count:record){ //最后遍历record数组元素 如果有不等于0则 不满足
if(count!=0){
return false;
}
}
return true;
}
}
leetcode349
本题如果输入的数组元素的范围比较小的话,可以和上题的思路一样,使用数组来记录,但如果范围太大,显然浪费了存储空间。
所以这题使用哈希法来做
unordered_set:使用unordered_set 读写效率是最高的,并不需要对数据进行排序,而且还不要让数据重复,所以选择unordered_set。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1.length==0||nums2.length==0){
return new int[0];
}
Set<Integer> set1=new HashSet<>();
Set<Integer> reset=new HashSet<>();
for(int num:nums1){ //遍历数组1 把所有元素存入
set1.add(num);
}
for(int num:nums2){ //遍历数组2 找出和数组1中相等的元素 放入reset中
if(set1.contains(num)){
reset.add(num);
}
}
return reset.stream().mapToInt(x -> x).toArray();
}
}
leetcode 1两数之和
首先寻找两个数的和思路是:遍历数组每个数 ,根据 target 减去当前遍历的数,得到的就是所需要的另一个数,也就是把问题转换成了:查询一个数是否出现过,这个时候就可以想到使用哈希表来解决问题,
,而又要返回的是值的数组下标,所以我们可以用hashmap 按数组的顺序,在遍历数组的同时,把元素放入数组中, 当hashmap中找到目标元素时,返回其下标就是数组所对应的下标,所以使用hashmap而不是set,并且查询的是数组元素的值,直接拿来做判断是否符合条件,所以key放的是 num[i]
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer,Integer> map=new HashMap<>();
int[] res=new int[2];
for(int i=0;i<nums.length;i++){ //遍历数组
int temp=target-nums[i]; // temp 就是要找的目标
if(map.containsKey(temp)){ //如果存在 放入res
res[0]=i;
res[1]=map.get(temp);
}
map.put(nums[i],i);
}
return res;
}
}
leetcode 202 快乐数
首先 一个最重要的 是 如果 sum重复出现 也就是陷入了无线循环,所以要判断一个元素是否重复出现,使用哈希法。
我们只需要知道是否有这个值,不需要下标什么的,所以使用hashset即可
class Solution {
public boolean isHappy(int n) {
Set<Integer> set=new HashSet<>();
int sum=n;
while(sum!=1&&!set.contains(sum)){ //如果sum==1 或者sum重复出现了(出现循环) 跳出循环过程
set.add(sum);
sum=getSum(sum);
}
return sum==1;
}
public int getSum(int n){
int sum_num=0; //输入的数值 不能确定是几位数, 从0位开始求平方
while(n>0){
int temp=n%10;
sum_num+=temp*temp;
n/=10;
}
return sum_num;
}
}
标签:set,int,sum,day06,num,数组,new
From: https://www.cnblogs.com/wdnmdp/p/16732691.html