当前位置:网站首页>[leetcode] day96 - the first unique character & ransom letter & letter ectopic word
[leetcode] day96 - the first unique character & ransom letter & letter ectopic word
2022-07-06 05:57:00 【Upside down, it's a circle】
1. The first unique character in the string
387. The first unique character in the string 【 Simple 】
Answer key
Storage frequency using hash table , Here the hash table is used 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;
}
}
Time complexity : O ( n ) O(n) O(n)
Spatial complexity : O ( ∣ Σ ∣ ) O(∣Σ∣) O(∣Σ∣), among Σ \Sigma Σ It's a character set.
2. Ransom letter
Answer key
Storage frequency using hash table , Here the hash table is used Array , Less time to run
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;
}
}
Time complexity : O ( m + n ) O(m+n) O(m+n)
Spatial complexity : O ( ∣ Σ ∣ ) O(∣Σ∣) O(∣Σ∣), among Σ \Sigma Σ It's a character set.
3. Effective alphabetic words
242. Effective alphabetic words 【 Simple 】
Answer key
Hashtable
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;
}
}
Be careful : Mentioned in the advanced “ If the input string contains unicode character What do I do ”?
In this case, the hash table cannot be represented by an array , and Only use HashMap!
Time complexity : O ( n ) O(n) O(n)
Spatial complexity : O ( ∣ Σ ∣ ) O(∣Σ∣) O(∣Σ∣), among Σ \Sigma Σ It's a character set.
Sort
t yes s The heterotopic words of are equivalent to 「 Two strings are sorted equal 」. So we can do string s and t Sort them separately , You can judge whether the sorted strings are equal .
Just remember String to array 、 Sort 、 Sentence etc. The operation of 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);
}
}
Time complexity : O ( n l o g n ) O(nlogn) O(nlogn), Sort required
Spatial complexity : O ( l o g n ) O(logn) O(logn), Sort required
边栏推荐
- Hongliao Technology: Liu qiangdong's "heavy hand"
- Network protocol model
- Wib3.0 leapfrogging, in leapfrogging (ง • ̀_•́) ง
- Leetcode 701 insertion operation in binary search tree -- recursive method and iterative method
- Web服务连接器:Servlet
- Bit operation rules
- H3C防火墙RBM+VRRP 组网配置
- Processes and threads
- 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
- A master in the field of software architecture -- Reading Notes of the beauty of Architecture
猜你喜欢
[paper reading] nflowjs: synthetic negative data intensive anomaly detection based on robust learning
Classes and objects (I) detailed explanation of this pointer
What preparations should be made for website server migration?
MIT6.s081-2020 Lab2 System Calls
华为路由器如何配置静态路由
wib3.0 跨越,在跨越(ง •̀_•́)ง
Cannot build artifact 'test Web: War expanded' because it is included into a circular depend solution
First knowledge database
- [email protected]树莓派"/>
[email protected]树莓派
- [email protected] raspberry pie"/>
[email protected] raspberry pie
随机推荐
Summary of data sets in intrusion detection field
类和对象(一)this指针详解
华为路由器忘记密码怎么恢复
如何在业务代码中使用 ThinkPHP5.1 封装的容器内反射方法
My 2021
Demander le Code de texte standard correspondant à un centre de travail dans l'ordre de production
SQLMAP使用教程(三)实战技巧二
Application Security Series 37: log injection
AUTOSAR从入门到精通番外篇(十)-嵌入式S19文件解析
入侵检测领域数据集总结
H3C V7版本交换机配置IRF
Redis message queue
[Jiudu OJ 07] folding basket
[experience] when ultralso makes a startup disk, there is an error: the disk / image capacity is too small
Database: ODBC remote access SQL Server2008 in oracel
Redis6 cluster setup
What is independent IP and how about independent IP host?
Luogu [Beginner Level 4] array p1427 number game of small fish
授予渔,从0开始搭建一个自己想要的网页
Clear floating mode