代码随想录第六天
- Leetcode 242 有效的字母异位词
- Leetcode 349 两个数组的交集
- Leetcode 202 快乐数
- Leetcode 1 两数之和
Leetcode 242 有效的字母异位词
题目链接: 有效的字母异位词
自己的思路:自己没想到,多练!
正确思路:定义一个长度为26的数组res,用于存放每个字符出现的次数,因为字符串s和t里面都是小写字母,所以长度是26。首先如果两个字符串长度不相等的话,字符串出现的次数一定不同,所以返回false;当长度相同的时候,遍历字符串s和t,s字符串用于字符个数的++,t字符串用于字符个数的–,然后再遍历数组res,如果有某个字符的个数不等于0,则返回false,因为如果字符个数相等的话,最后一定是一个全0的数组,如果没有返回false,则返回true,代表字符个数相等。
代码:
class Solution {
public boolean isAnagram(String s, String t) {
//如果两个字符串长度不相等的话,直接返回false
if (s.length()!=t.length()) return false;
//因为都为小写字母,所以我们定义一个长度为26的字母来存放每个字符出现的次数
int[] res = new int[26];
//遍历两个字符串,s字符串用于++,t字符串用于--
for (int i = 0;i<s.length();i++){
res[s.charAt(i)-'a']++;
res[t.charAt(i)-'a']--;
}
//遍历结果数组,如果有某个字符最后对应的值不等于0,说明某个字符出现的次数不相同
for (int i = 0;i<26;i++){
if (res[i]!=0) return false;
}
return true;
}
}
复杂度分析:
时间复杂度:
O
(
n
)
\mathcal{O}(n)
O(n)
空间复杂度:
O
(
1
)
\mathcal{O}(1)
O(1)
Leetcode 349 两个数组的交集
题目链接: 两个数组的交集
自己的思路:没想到,多练!!
正确思路:因为最后存放的数据是唯一,首先一定要想到Set来处理;因为要求两个数组的交集,而且唯一,那么最后的数据首先用一个Set来处理,可以先定义两个Set:set和resset,set用于遍历nums1,存放nums1中的数(不重复),然后再遍历nums2,如果说nums2中某个数在set中存在,那么加入到resset中,那么最后resset中存在的就是两个数组的交集(不重复)。最后再把Set转化成数组即可,方法二必须掌握,方法一根据时间来掌握。
代码:
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
//如果有某个为空,则直接返回空数组
if (nums1==null||nums2==null) return new int[0];
//定义两个Set,一个用于存放nums1里面的数(不重复)
//另一个存放结果数组
Set<Integer> set = new HashSet<>();
Set<Integer> resset = new HashSet<>();
for (int num1:nums1){
set.add(num1);
}
//如果set里面包括num2,则加入到结果Set中
for (int num2:nums2){
if (set.contains(num2)){
resset.add(num2);
}
}
//转换为数组
//方法一:
return resset.stream().mapToInt(x -> x).toArray();
//方法二:
// int index = 0;
// int[] res = new int[resset.size()];
// for (int num:resset){
// res[index] = num;
// index++;
// }
// return res;
}
}
复杂度分析:
时间复杂度:
O
(
m
+
n
)
\mathcal{O}(m+n)
O(m+n)
空间复杂度:
O
(
m
+
n
)
\mathcal{O}(m+n)
O(m+n)
Leetcode 202 快乐数
题目链接: 快乐数
自己的思路:分析问题本质。快乐数是重复将该数替换为它每个位置上的数字的平方和,如果说中间存在了重复的元素,那么一定不是快乐数,因为会一直循环下去;如果说出现了,则为快乐数!
正确思路:哈希表
代码:
class Solution {
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
//定义一个临时变量作为getsum的输入参数
int m;
//定义一个flag,如果flag为false则说明出现了重复的数
boolean flag;
while(true){
m = n;
n = getsum(m);
//如果n之前存在于set中,则flag为flase,否则为true
flag = set.add(n);
if (!flag) return false;
//如果包含1,则返回true
if (set.contains(1)) return true;
}
}
//计算每个位置的平方和
public int getsum(int n){
int sum = 0;
while(n!=0){
sum += (n%10)*(n%10);
n /= 10;
}
return sum;
}
}
复杂度分析:
不知道怎么算时间复杂度
空间复杂度:
O
(
1
)
\mathcal{O}(1)
O(1)
Leetcode 1 两数之和
题目链接: 两数之和
自己的思路:这道题目的是为了找出和为target的两个数,我们可以遍历整个数组,使用一个Map来存放之前遍历过的数组的值和索引,当遍历到nums[i]的时候,去Map中寻找有没有target-nums[i]的值,如果有的话,直接返回两个索引即可,如果没有,则把当前的值nums[i]和i放入Map中,直到找到和为target的两个数为止。
正确思路:哈希表
代码:
class Solution {
public int[] twoSum(int[] nums, int target) {
//定义一个map,key用于存放数组中的值,value用于存放数组中的值的索引
Map<Integer,Integer> map = new HashMap<>();
for (int i =0;i<nums.length;i++){
//如果map包含target-nums[i],因为target-nums[i]+nums[i]=target
//直接返回索引数组
if (map.containsKey(target-nums[i])) return new int[]{map.get(target-nums[i]),i};
else{
//如果不包含的话把这对entry加入到map中
map.put(nums[i],i);
}
}
//随便返回一个数组
return new int[2];
}
}
复杂度分析:
时间复杂度:
O
(
n
)
\mathcal{O}(n)
O(n)
空间复杂度:
O
(
n
)
\mathcal{O}(n)
O(n)