242. Valid Anagram
题目链接：https://leetcode.cn/problems/valid-anagram/
方法一 哈希思想 + 数组
1 方法思想
因为是字符串，只有26个字幕，使用长度为26得数组，存储第一个字符串中得字符出现得标志位，遍历第二个验证字符是否存在。
2 代码实现
class Solution {
public boolean isAnagram(String s, String t) {
int lenS = s.length();
int lenT = t.length();
if (lenS != lenT) return false;
int[] times = new int[26];
for (int i = 0; i < lenS; i++) {
char cur = s.charAt(i);
times[cur - 'a']++;
}
for (int i = 0; i < lenT; i++) {
char cur = t.charAt(i);
if (times[cur - 'a'] <= 0){
return false;
}
times[cur - 'a']--;
}
return true;
}
}
3 复杂度分析
时间复杂度：O(n)
空间复杂度：O(s), s = 26
4 涉及到知识点
哈希思想，字母对应得ASCII值是多少。
方法二 排序
1 方法思想
将两个字符串转成字符数组，并对字符数组进行排序，然后从头开始遍历两个字符串是否相同。
2 代码实现
3 复杂度分析
时间复杂度：O(nlogn)
空间复杂度：O(n)
4 涉及到知识点
收获和总结
1.遇到的困难？
2 收获
学习链接
https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF
349. Intersection of Two Arrays
题目链接：https://leetcode.cn/problems/intersection-of-two-arrays/
方法一 哈希思想 + 数组
1 方法思想
哈希思想加数组，和242得思想一样，这种情况适合用于数据量小得情况。
2 代码实现
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
int num1Len = nums1.length;
int num2Len = nums2.length;
int[] ans = new int[num1Len];
int[] times = new int[1001];
int len = 0;
for (int i = 0; i < num1Len; i++) {
times[nums1[i]] ++;
}
for (int i = 0; i < num2Len; i++) {
if (times[nums2[i]] >= 1){
ans[len ++] = nums2[i];
}
times[nums2[i]] = 0;
}
return Arrays.copyOfRange(ans, 0, len);
}
}
3 复杂度分析
时间复杂度：O(n/m)
空间复杂度：O(1)
4 涉及到知识点
哈希思想
方法二 HashSet
1 方法思想
2 代码实现
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> num1Set = new HashSet<>();
int[] ans = new int[nums2.length];
int len = 0;
for (int i = 0; i < nums1.length; i++) {
num1Set.add(nums1[i]);
}
for (int i = 0; i < nums2.length; i++) {
if (num1Set.contains(nums2[i])){
ans[len ++] = nums2[i];
num1Set.remove(nums2[i]);
}
}
return Arrays.copyOfRange(ans, 0, len);
}
}
3 复杂度分析
时间复杂度：O(nlogn)
空间复杂度：O(n)
4 涉及到知识点
收获和总结
1.遇到的困难？
2 收获
学习链接
https://programmercarl.com/0704.%E4%BA%8C%E5%88%86%E6%9F%A5%E6%89%BE.html#%E6%80%9D%E8%B7%AF
202. Happy Number
题目链接：https://leetcode.cn/problems/happy-number/
方法一 哈希思想 + 数组
1 方法思想
判断有没有重复出现数字，如果重复出现，则成环。
2 代码实现
class Solution {
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>();
while (n != 1 && !set.contains(n)){
set.add(n);
n = getHappyNumber(n);
}
return n == 1;
}
public int getHappyNumber(int num){
int sum = 0;
while (num > 0){
sum += Math.pow(num%10, 2);
num /= 10;
}
return sum;
}
}
3 复杂度分析
时间复杂度：O(logN)
空间复杂度：O(logN)
4 涉及到知识点
哈希思想
1. Two Sum
题目链接：https://leetcode.cn/problems/two-sum/
方法一 哈希思想 + 数组
1 方法思想
判断有没有重复出现数字，如果重复出现，则成环。
2 代码实现
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] ans = new int[2];
HashMap<Integer, Integer> hashMap = new HashMap<>();
int len = nums.length;
for (int i = 0; i < len; i++) {
if (hashMap.containsKey(target - nums[i])){
ans[0] = i;
ans[1] = hashMap.get(target - nums[i]);
return ans;
}else {
hashMap.put(nums[i], i);
}
}
return null;
}
}
|