赎金信(easy)
做题过程
哈希表已经easy至极了。
算法概述
原题
本题要求为第二参数字符串是否包含第一个字符串中所有出现的字符。用 哈希表 存了频次然后删就行。
- 时间复杂度为O(m+n)
- 空间复杂度为O(m)：只需要存储可用字符串的字符出现频次
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
char[] r=ransomNote.toCharArray();
char[] m=magazine.toCharArray();
Map<Character,Integer> map=new HashMap<>();
for(char c:m){
map.put(c,map.getOrDefault(c,0)+1);
}
for(char c:r){
if(map.getOrDefault(c,0)==0) return false;
map.put(c, map.get(c) - 1);
}
return true;
}
}
|
总结
也可以用原生数组，直接cnt[c-'a']++这样就可以了。
同构字符串(easy)
做题过程
没想到怎么构建键值关系。
算法概述
原题
本题要求为判断两个字符串之间是否存在映射的关系。需要使用 两个哈希表 分别记录映射，通过是否有冲突判断。
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> s2t = new HashMap<Character, Character>();
Map<Character, Character> t2s = new HashMap<Character, Character>();
int len = s.length();
for (int i = 0; i < len; ++i) {
char x = s.charAt(i), y = t.charAt(i);
if ((s2t.containsKey(x) && s2t.get(x) != y) || (t2s.containsKey(y) && t2s.get(y) != x)) {
return false;
}
s2t.put(x, y);
t2s.put(y, x);
}
return true;
}
}
|
总结
没有想到可以运用多个哈希表存储信息，思路局限在了哈希表只是被用于作为一个辅助工具上。
单词规律
做题过程
和上一题完全一样的思路，但是不熟悉相关方法。
算法概述
原题
本体要求为给定一种组词规律和一系列单词，判断是否符合前者（规律）。依然使用 两个哈希表 。
- 时间复杂度为O(m+n)
- 空间复杂度为O(m+n)
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| import java.util.*;
class Solution {
public boolean wordPattern(String pattern, String s) {
Map<Character, String> map1 = new HashMap<>();
Map<String, Character> map2 = new HashMap<>();
String[] words = s.split(" ");
if (words.length != pattern.length()) {
return false;
}
for (int i = 0; i < pattern.length(); i++) {
char pChar = pattern.charAt(i);
String word = words[i];
if (map1.containsKey(pChar) && !map1.get(pChar).equals(word)) {
return false;
}
if (map2.containsKey(word) && !map2.get(word).equals(pChar)) {
return false;
}
map1.put(pChar, word);
map2.put(word, pChar);
}
return true;
}
}
|
重要实例方法及属性
String[] words = s.split(" ");：通过方法快速划分单词，无需遍历
!map1.get(pChar).equals(word)： 必须 使用equals()，因为是引用类型，而不是基本类型，如果使用!=不会比较值，而只会比较内容！！！
总结
还是用的GPT的版本，虽然稍显冗长，但是清晰很多。
有效的字母异位词(easy)
做题过程
没问题。
算法概述
原题
本题要求为判断两个输入字符串是否为字母异位词（换个位置就可以变来变去）。
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean isAnagram(String s, String t) {
int[] cnt=new int[26];
int[] ctr=new int[26];
for(int i=0;i!=s.length();++i){
cnt[s.charAt(i)-'a']++;
}
for(int i=0;i!=t.length();++i){
if(cnt[t.charAt(i)-'a']--==0) return false;
}
return Arrays.equals(cnt,ctr);
}
}
|
总结
easy❇️。
快乐数(easy)
做题过程
不会。
算法概述
原题
本题要求为判断一个数是否为快乐数（不断取各数位的平方和再加和最终得到1）。
- 时间复杂度为O(logn)：数字的位数由logn给定
- 空间复杂度为O(logn)：每个都要存
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class Solution {
private int getNext(int n) {
int totalSum = 0;
while (n > 0) {
int d = n % 10;
n = n / 10;
totalSum += d * d;
}
return totalSum;
}
public boolean isHappy(int n) {
Set<Integer> seen = new HashSet<>();
while (n != 1 && !seen.contains(n)) {
seen.add(n);
n = getNext(n);
}
return n == 1;
}
}
|
总结
必须要做分离。
还可以使用的方法如下：
存在重复元素 II
做题过程
方法还是有点问题，不是很掌握。
算法概述
原题
本题要求为不仅要检查重复元素是否存在，还要计算重复元素距离的范围是否符合给定值以内。
JAVA
1
2
3
4
5
6
7
8
9
10
11
12
| class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
Map<Integer,Integer> map=new HashMap<>();
for(int i=0;i!=nums.length;++i){
if(map.containsKey(nums[i])&&Math.abs(map.get(nums[i])-i)<=k){
return true;
}
map.put(nums[i],i);
}
return false;
}
}
|
重要实例方法及属性(java)
map.containsKey()：必须要用这个api，不能用getOrDefault，后者不仅进行查询操作，还进行更新。
总结
easy。
