当前位置:网站首页>Leetcode daily question: the first unique character in the string
Leetcode daily question: the first unique character in the string
2022-07-05 17:48:00 【Sharp blade CC】
link : The first unique character in the string
( notes : The prompt string of this question only contains lowercase letters )
Conventional thinking : Each character is traversed once , Find out whether there are the same letters in the string .( But in the worst case, the time complexity is O(n^2), So... Is not recommended here )
Code :
class Solution {
public:
int firstUniqChar(string s) {
// Conventional thinking : Each time, we iterate to find whether there are equal , Time complexity O(n^2), Not recommended
for(size_t i = 0; i < s.size(); i++)
{
// use flag Mark with , If it becomes 0 The description has the same
int flag = 1;
for(size_t j = 0; j < s.size(); j++)
{
// If the subscripts are the same, no comparison is required
if(j == i)
continue;
if(s[j] != s[i])
continue;
else
{
flag = 0;
break;
}
}
if(flag == 1)
return i;
}
return -1;
}
};
Another way to think about it : Using the idea of counting and sorting , Count the number of occurrences of each letter in the string , Then add the first count array as 1 Letter return of .
notes : The time complexity of this idea is O(N).
Code :
class Solution {
public:
int firstUniqChar(string s) {
// The time complexity is O(n)
// Using the idea of counting and sorting , First count the number of times each letter appears
int arr[26] = {
0};
for(size_t i = 0; i < s.size(); i++)
{
arr[s[i] - 'a']++;
}
// lookup s In the corresponding arr Whether the number of occurrences is once
for(size_t i = 0; i < s.size(); i++)
{
if(arr[s[i] - 'a'] == 1)
return i;
}
return -1;
}
};
边栏推荐
- Thesis reading_ Chinese NLP_ LTP
- Simple query cost estimation
- VBA drives SAP GUI to realize office automation (II): judge whether elements exist
- Knowledge points of MySQL (7)
- Seven Devops practices to improve application performance
- 一文读懂简单查询代价估算
- Tita performance treasure: how to prepare for the mid year examination?
- GFS分布式文件系统
- 论文阅读_医疗NLP模型_ EMBERT
- EPM相关
猜你喜欢
统计php程序运行时间及设置PHP最长运行时间
Knowledge points of MySQL (7)
Ten top automation and orchestration tools
統計php程序運行時間及設置PHP最長運行時間
Matlab reference
GFS分布式文件系统
flask接口响应中的中文乱码(unicode)处理
Zabbix
Beijing internal promotion | the machine learning group of Microsoft Research Asia recruits full-time researchers in nlp/ speech synthesis and other directions
哈趣K1和哈趣H1哪个性价比更高?谁更值得入手?
随机推荐
Ten capabilities that cyber threat analysts should have
How to save the trained neural network model (pytorch version)
如何修改mysql字段为自增长字段
2022 information system management engineer examination outline
統計php程序運行時間及設置PHP最長運行時間
Zabbix
The five most difficult programming languages in the world
Complete solution instance of Oracle shrink table space
leetcode每日一题:字符串中的第一个唯一字符
Disabling and enabling inspections pycharm
Winedt common shortcut key modify shortcut key latex compile button
EPM related
Cmake tutorial Step2 (add Library)
ICML 2022 | Meta提出魯棒的多目標貝葉斯優化方法,有效應對輸入噪聲
Operation before or after Teamcenter message registration
The comprehensive competitiveness of Huawei cloud native containers ranks first in China!
Read the history of it development in one breath
Domain name resolution, reverse domain name resolution nbtstat
Disorganized series
Data access - entityframework integration