当前位置:网站首页>【LeetCode】Day96-第一个唯一字符&赎金信&字母异位词
【LeetCode】Day96-第一个唯一字符&赎金信&字母异位词
2022-07-06 05:48:00 【倒过来是圈圈】
1.字符串中的第一个唯一字符
题解
使用哈希表存储频数,这里哈希表用HashMap
class Solution {
public int firstUniqChar(String s) {
Map<Character,Integer>hashMap=new HashMap<>();
for(int i=0;i<s.length();i++){
char c=s.charAt(i);
if(hashMap.containsKey(c)){
int count=hashMap.get(c);
hashMap.put(c,count+1);
}
else
hashMap.put(c,1);
}
for(int i=0;i<s.length();i++){
if(hashMap.get(s.charAt(i))==1)
return i;
}
return -1;
}
}
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( ∣ Σ ∣ ) O(∣Σ∣) O(∣Σ∣),其中 Σ \Sigma Σ 是字符集
2.赎金信
题解
使用哈希表存储频数,这里哈希表用数组,运行时间更短
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
int[] cnt=new int[26];
for(int i=0;i<magazine.length();i++){
cnt[magazine.charAt(i)-'a']++;
}
for(int i=0;i<ransomNote.length();i++){
char c=ransomNote.charAt(i);
if(cnt[c-'a']<=0)
return false;
cnt[c-'a']--;
}
return true;
}
}
时间复杂度: O ( m + n ) O(m+n) O(m+n)
空间复杂度: O ( ∣ Σ ∣ ) O(∣Σ∣) O(∣Σ∣),其中 Σ \Sigma Σ 是字符集
3.有效的字母异位词
题解
哈希表
class Solution {
public boolean isAnagram(String s, String t) {
int m=s.length(),n=t.length();
if(m!=n)
return false;
int[] snt=new int[26];
for(int i=0;i<m;i++)
snt[s.charAt(i)-'a']++;
for(int i=0;i<n;i++){
snt[t.charAt(i)-'a']--;
if(snt[t.charAt(i)-'a']<0)
return false;
}
return true;
}
}
注意:在进阶中提到“如果输入字符串包含 unicode 字符怎么办”?
这种情况就不可以用数组表示哈希表了,而只能用HashMap!
时间复杂度: O ( n ) O(n) O(n)
空间复杂度: O ( ∣ Σ ∣ ) O(∣Σ∣) O(∣Σ∣),其中 Σ \Sigma Σ 是字符集
排序
t 是 s 的异位词等价于「两个字符串排序后相等」。因此我们可以对字符串 s 和 t 分别排序,看排序后的字符串是否相等即可判断。
重点记一下字符串转数组、排序、判等的操作API
class Solution {
public boolean isAnagram(String s, String t) {
int m=s.length(),n=t.length();
if(m!=n)
return false;
char[] str1=s.toCharArray();
char[] str2=t.toCharArray();
Arrays.sort(str1);
Arrays.sort(str2);
return Arrays.equals(str1,str2);
}
}
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn),排序所需
空间复杂度: O ( l o g n ) O(logn) O(logn),排序所需
边栏推荐
- Station B, Master Liu Er - dataset and data loading
- 【经验】win11上安装visio
- Node 之 nvm 下载、安装、使用,以及node 、nrm 的相关使用
- [Baiwen smart home] first day of the course_ Learn Embedded and understand the development mode of bare metal and RTOS
- 清除浮动的方式
- 养了只小猫咪
- Station B Liu Erden softmx classifier and MNIST implementation -structure 9
- CoDeSys note 2: set coil and reset coil
- ArcGIS应用基础4 专题图的制作
- After the project is released, index Html is cached
猜你喜欢
Mysql database master-slave cluster construction
The difference and usage between continue and break
Embedded interview questions (IV. common algorithms)
26file filter anonymous inner class and lambda optimization
Migrate Infones to stm32
continue和break的区别与用法
YYGH-11-定时统计
[SQL Server Express Way] - authentification et création et gestion de comptes utilisateurs
[SQL Server fast track] - authentication and establishment and management of user accounts
Clear floating mode
随机推荐
H3C firewall rbm+vrrp networking configuration
Go language -- language constants
Zoom through the mouse wheel
B站刘二大人-Softmx分类器及MNIST实现-Lecture 9
Processes and threads
Web Security (V) what is a session? Why do I need a session?
H3C S5820V2_ Upgrade method after stacking IRF2 of 5830v2 switch
关于 PHP 启动 MongoDb 找不到指定模块问题
Grant Yu, build a web page you want from 0
局域网同一个网段通信过程
Redis message queue
Pytorch代码注意的细节,容易敲错的地方
How to use PHP string query function
查詢生產訂單中某個(些)工作中心對應的標准文本碼
RustDesk 搭建一个自己的远程桌面中继服务器
Yunxiaoduo software internal test distribution test platform description document
Redis6 cluster setup
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
As3013 fire endurance test of cable distribution system
[imgui] unity MenuItem shortcut key