算法刷题记录-两个数组的交集
两个数组的交集
给定两个数组 nums1 和 nums2 ，返回 它们的交集 。输出结果中的每个元素一定是 唯一 的。我们可以 不考虑输出结果的顺序 。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2]
示例 2：
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[9,4]
解释：[4,9] 也是可通过的
思路：用两个set一个存储第一个数组的所有元素，第二个存结果
public int[] intersection(int[] nums1, int[] nums2) {
if(nums1.length==0)return null;
if(nums2.length==0)return null;
Set<Integer> set1=new HashSet<>();
Set<Integer> set2=new HashSet<>();
for(int i:nums1){
set1.add(i);
}
for(int i:nums2){
if(set1.contains(i))
set2.add(i);
}
int[] res=new int[set2.size()];
int index=0;
for(Integer i:set2){
res[index]=i;
index++;
}
return res;
}
两个数组的交集二
给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。
示例 1：
输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]
示例 2:
输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]
思路：三个map，两个存数组的值即次数，最后一个得到结果
public int[] intersect(int[] nums1, int[] nums2) {
if(nums1.length==0)return null;
if(nums2.length==0)return null;
HashMap<Integer,Integer> map1=new HashMap<>();
HashMap<Integer,Integer> map2=new HashMap<>();
HashMap<Integer,Integer> map3=new HashMap<>();
for(int i:nums1){
if(!map1.containsKey(i))map1.put(i,1);
else map1.put(i,map1.get(i)+1);
}
for(int i:nums2){
if(!map2.containsKey(i))map2.put(i,1);
else map2.put(i,map2.get(i)+1);
}
for(Integer i:map1.keySet()){
if(map2.containsKey(i)) {
int temp = map1.get(i)>map2.get(i)?map1.get(i):map2.get(i);
map3.put(i, temp);
}
}
int len=0;
for (Integer i:map3.keySet()){
len+=map3.get(i);
}
int[] res=new int[len];
int index=0;
for (Integer i:map3.keySet()){
for (int j = 0; j < map3.get(i); j++) {
res[index]=i;
index++;
}
}
return res;
}
快乐数
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」 定义为：
- 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
- 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
- 如果这个过程 结果为 1，那么这个数就是快乐数。
如果 n 是 快乐数 就返回 true ；不是，则返回 false 。
示例 1：
输入：n = 19
输出：true
解释：
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2：
输入：n = 2
输出：false
思路：非快乐数会重复递归
public boolean isHappy(int n) {
if(n==1)return true;
Set res=new HashSet<>();
String num=String.valueOf(n);
int[] list=new int[num.length()];
for (int i = 0; i < num.length(); i++) {
list[i]=(int)num.charAt(i)-(int)('0');
}
int result=0;
for(int i:list){
result+=i*i;
}
if(result==1)return true;
else {
while (result!=1) {
res.add(result);
num=String.valueOf(result);
list=new int[num.length()];
for (int i = 0; i < num.length(); i++) {
list[i]=(int)num.charAt(i)-(int)('0');
}
result=0;
for(int i:list){
result+=i*i;
}
if(res.contains(result))return false;
}
}
return true;
}
两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
思路：暴力解法，两个for循环解决
public int[] twoSum(int[] nums, int target) {
int[] res=new int[2];
for (int i = 0; i < nums.length-1; i++) {
for (int j = i+1; j < nums.length; j++) {
if(nums[i]+nums[j]==target){
res[0]=i;
res[1]=j;
return res;
}
}
}
return res;
}
思路二：用一个集合存储数组，每次判断当前位置是否正确在循环
public int[] twoSum(int[] nums, int target) {
int[] res=new int[2];
Set set=new HashSet<>();
for(int i:nums){
set.add(i);
}
for (int i = 0; i < nums.length-1; i++) {
if(set.contains(target-nums[i])){
res[0]=i;
for (int j = i+1; j <nums.length ; j++) {
if(nums[j]==target-nums[i]){
res[1]=j;
return res;
}
}
}
}
return res;
}