【LeetCode】 387. 字符串中的第一个唯一字符

2023-10-21 06:52

本文主要是介绍【LeetCode】 387. 字符串中的第一个唯一字符,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接

在这里插入图片描述
在这里插入图片描述

文章目录

    • Python3
      • 方法一:collections.Counter() 统计频次
      • 方法二:哈希映射 { key字符:value【首次出现的索引 or -1 出现多次】}
      • 方法三: collections.deque() 元素为 (字符,第一次出现的索引) 维护队首 + dict 记录是否重复
      • Python3 函数模块
        • collections.Counter() {键:计数}
        • collections.deque() 双端队列
    • C++
      • 方法一:哈希表 存储 频次 unordered_map
      • 方法二:哈希映射 { key字符:value【首次出现的索引 or -1 出现多次】}
        • unordered_map 并非 元素插入顺序
      • 方法三: queue 元素为 (字符,第一次出现的索引) 维护队首 + unordered_map记录是否重复
        • queue
      • 方法四: find 函数 和 rfind 函数
        • unordered_map 遍历 2种 方式

所有方法 复杂度 ( O ( n ) O(n) O(n) O ( ∣ Σ ∣ ) O(|\Sigma|) O(∣Σ∣))

Python3

方法一:collections.Counter() 统计频次

针对 s ,进行两次遍历:
第一次遍历:使用哈希映射统计出字符串中每个字符出现的次数。
第二次遍历: 只要遍历到了一个只出现一次的字符,直接返回它的索引,否则在遍历结束后返回 −1。

在这里插入图片描述

class Solution:def firstUniqChar(self, s: str) -> int:frequency = collections.Counter(s)  # 会 按照计数频次 排序,其次 出现位置前后for i, ch in enumerate(s):if frequency[ch] == 1:return i return -1

补充:

import collectionsprint(collections.Counter("leetcode"))

Counter({‘e’: 3, ‘l’: 1, ‘t’: 1, ‘c’: 1, ‘o’: 1, ‘d’: 1})

方法二:哈希映射 { key字符:value【首次出现的索引 or -1 出现多次】}

在这里插入图片描述
在这里插入图片描述

class Solution:def firstUniqChar(self, s: str) -> int:dic = {}for i in range(len(s)):  # 另一种遍历方式  for i, ch in enumerate(s):if s[i] not in dic:dic[s[i]] = i else:dic[s[i]] = -1for v in dic.values():if v != -1:  ## 找到不是 -1 的,直接返回。照理说,dic 是无序的,这里会报错,但没有。看起来dict() 默认是 元素插入顺序。return vreturn -1

补充:这里与 C++ 不同, 会按照 元素插入 顺序进行排列

在这里插入图片描述


dic = {}
s = "loveleetcode"
for i in range(len(s)):  # 另一种遍历方式  for i, ch in enumerate(s):if s[i] not in dic:dic[s[i]] = i else:dic[s[i]] = -1
print(dic)

在这里插入图片描述

set 仍是无序的

方法三: collections.deque() 元素为 (字符,第一次出现的索引) 维护队首 + dict 记录是否重复

双端队列 存储 二元组 (字符,第一次出现的索引)

队列维护技巧: 「延迟删除」
在维护队列时,即使队列中有一些字符出现了超过一次,但它只要不位于队首,那么就不会对答案造成影响,我们也就可以不用去删除它。只有当它前面的所有字符被移出队列,它成为队首时,我们才需要将它移除。

class Solution:def firstUniqChar(self, s: str) -> int:dic = {}q = collections.deque()  # 存储 (字符, 第一次出现索引)for i, ch in enumerate(s):if ch not in dic:dic[ch] = iq.append((ch, i))else: dic[ch] = -1   ## 重复  维护 dict## 重复了,核对队首的字符  【延迟删除】while q and dic[q[0][0]] == -1: ## 队首 重复了。 因为前面处理时,只针对队首。重复时只修改了 dic。这里 用while。直到找到后续 无重复的 第一个字符q.popleft()   ## 当 队首 重复,才维护return -1 if not q else q[0][1]

在这里插入图片描述

Python3 函数模块

collections.Counter() {键:计数}

官网链接https://docs.python.org/3.12/library/collections.html#collections.Counter

Counter是用于计数可哈希对象的字典子类。它是一个集合,其中元素被存储为字典键,它们的计数被存储为字典值。计数可以是任何整数值,包括0或负数计数。Counter类类似于其他语言中的bags或multiset。

元素从可迭代对象中计数或从另一个映射(或计数器)中初始化:

c = Counter()                           # a new, empty counter
c = Counter('gallahad')                 # a new counter from an iterable
c = Counter({'red': 4, 'blue': 2})      # a new counter from a mapping
c = Counter(cats=4, dogs=8)             # a new counter from keyword args
Counter('abracadabra').most_common(3)  # 返回 计数最多的前3组

[(‘a’, 5), (‘b’, 2), (‘r’, 2)]

c.total()                       # total of all counts
c.clear()                       # reset all counts
list(c)                         # list unique elements
set(c)                          # convert to a set
dict(c)                         # convert to a regular dictionary
c.items()                       # convert to a list of (elem, cnt) pairs
Counter(dict(list_of_pairs))    # convert from a list of (elem, cnt) pairs
########    
c.most_common()[:-n-1:-1]       # n least common elements
+c                              # remove zero and negative counts
c = Counter(a=2, b=-4)
+c   # Counter({'a': 2})
-c   #  Counter({'b': 4})
collections.deque() 双端队列

官方文档链接

Deques = stacks + queues

the name is pronounced “deck” and is short for “double-ended queue”
双端队列
append(x) # 默认 右添加
appendleft(x)
clear()
copy()
count(x)
extend(iterable)
extendleft(iterable)
index(x[, start[, stop]])
insert(i, x)
pop() ## 会返回 值
popleft()
remove(value)
reverse()
maxlen

rotate(n=1)

  • Rotate the deque n steps to the right. If n is negative, rotate to the left.

C++

方法一:哈希表 存储 频次 unordered_map

针对 s ,进行两次遍历:
第一次遍历:使用哈希映射统计出字符串中每个字符出现的次数。
第二次遍历: 只要遍历到了一个只出现一次的字符,直接返回它的索引,否则在遍历结束后返回 −1。

class Solution {
public:int firstUniqChar(string s) {unordered_map<int, int> frequency;  // 按照语法应该是 <char, int>, 但这里不会报错,会强制转换。这里不需要输出,影响不大。用整型快点???不理解for (char ch : s){++frequency[ch];}for (int i = 0; i < s.size(); ++i){if (frequency[s[i]] == 1){return i;}}return -1;}
};

方法二:哈希映射 { key字符:value【首次出现的索引 or -1 出现多次】}

unordered_map函数文档

官方解法的 字典遍历方式在 IDE 里无法运行

class Solution {
public:int firstUniqChar(string s) {unordered_map<int, int> dic; // 这里 用 char 或 int 都可以?int n = s.size();for (int i = 0; i < n; ++i) {if (dic.count(s[i])) {dic[s[i]] = -1;}else {dic[s[i]] = i;}}int first = n; // 字典 中的元素 不是 按照 元素插入顺序 排列,要处理for (auto [_, pos]: dic) {if (pos != -1 && pos < first) {first = pos;}}if (first == n) {// 遍历完毕 , 无 不重复的first = -1;}return first;}
};

遍历方式 2

class Solution {
public:int firstUniqChar(string s) {unordered_map<int, int> dic; // 这里 用 char 或 int 都可以?int n = s.size();for (int i = 0; i < n; ++i) {if (dic.count(s[i])) {// 重复了dic[s[i]] = -1;}else {dic[s[i]] = i;}}int first = n; // 字典 中的元素 不是 按照 元素插入顺序 排列,要处理for (const auto& c: dic) {  // 遍历方式 2if (c.second != -1 &&c.second < first) {first = c.second;}}if (first == n) {// 遍历完毕 , 无 不重复的first = -1;}return first;}
};

遍历方式 3

class Solution {
public:int firstUniqChar(string s) {unordered_map<int, int> dic; // 这里 用 char 或 int 都可以?int n = s.size();for (int i = 0; i < n; ++i) {if (dic.count(s[i])) {// 重复了dic[s[i]] = -1;}else {dic[s[i]] = i;}}int first = n; // 字典 中的元素 不是 按照 元素插入顺序 排列,要处理for (unordered_map<int, int>::const_iterator it = dic.begin(); it != dic.end(); ++it) {  // 遍历方式 3if (it->second != -1 && it->second < first) {first = it->second ;}}if (first == n) {// 遍历完毕 , 无 不重复的first = -1;}return first;}
};
unordered_map 并非 元素插入顺序
#include <unordered_map>
#include <iostream>
using namespace std;
int main()
{unordered_map<char, int> position;string s = "loveleetcode";int n = s.size();for (int i = 0; i < n; ++i) {if (position.count(s[i])) {position[s[i]] = -1;}else {position[s[i]] = i;}}for (unordered_map<char, int> ::const_iterator it = position.begin();it != position.end(); ++it)std::cout << " [" << it->first << ", " << it->second << "]";std::cout << std::endl;}

并非 元素插入的顺序
在这里插入图片描述
s = “leetcode”
在这里插入图片描述

方法三: queue 元素为 (字符,第一次出现的索引) 维护队首 + unordered_map记录是否重复

class Solution {
public:int firstUniqChar(string s) {unordered_map<char, int> dic;queue<pair<char, int>> q; // 队列 维护 字母 和 第一次出现的索引for (int i = 0; i < s.size(); ++i){if (!dic.count(s[i])){dic[s[i]] = i;q.emplace(s[i], i);  // 默认 右边 添加}else{dic[s[i]] = -1;while (!q.empty() && dic[q.front().first] == -1){q.pop(); // 弹出 左端 元素}}}return q.empty() ? -1 : q.front().second;}
};
queue

queue 文档
在这里插入图片描述

方法四: find 函数 和 rfind 函数

s.find(s[i]) : 返回字符串s中 从左向右 查找s[i]第一次出现的位置; s.rfind(s[i]) : 返回字符串s中 从右向左 查找s[i]第一次出现的位置;

class Solution {
public:int firstUniqChar(string s) {for (int i = 0; i < s.size(); ++i){if (s.find(s[i]) == s.rfind(s[i])) // 该字符第一次出现的位置和最后一次出现的位置一样,就证明不重复。return i;}return -1;}
};
unordered_map 遍历 2种 方式

整理自 unordered_map函数文档

#include<unordered_map>
#include<iostream>
using namespace std;int main(){unordered_map<int, char> c5({ { 5, 'g' }, { 6, 'h' }, { 7, 'i' }, { 8, 'j' } });for (const auto& c : c5) {cout << " [" << c.first << ", " << c.second << "]";}cout << endl;return 0;
}

在这里插入图片描述

#include <unordered_map>
#include <iostream>
using namespace std;int main()
{unordered_map<int, char> dic({ { 5, 'g' }, { 6, 'h' }, { 7, 'i' }, { 8, 'j' } });for (unordered_map<int, char>::const_iterator it = dic.begin();  it != dic.end(); ++it)std::cout << " [" << it->first << ", " << it->second << "]";std::cout << std::endl; // 只能通过  ->  取值return 0;
}

在这里插入图片描述

这篇关于【LeetCode】 387. 字符串中的第一个唯一字符的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/252676

相关文章

C#数据结构之字符串(string)详解

《C#数据结构之字符串(string)详解》:本文主要介绍C#数据结构之字符串(string),具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录转义字符序列字符串的创建字符串的声明null字符串与空字符串重复单字符字符串的构造字符串的属性和常用方法属性常用方法总结摘

Java实现时间与字符串互相转换详解

《Java实现时间与字符串互相转换详解》这篇文章主要为大家详细介绍了Java中实现时间与字符串互相转换的相关方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 目录一、日期格式化为字符串(一)使用预定义格式(二)自定义格式二、字符串解析为日期(一)解析ISO格式字符串(二)解析自定义

python中字符串拼接的几种方法及优缺点对比详解

《python中字符串拼接的几种方法及优缺点对比详解》在Python中,字符串拼接是常见的操作,Python提供了多种方法来拼接字符串,每种方法有其优缺点和适用场景,以下是几种常见的字符串拼接方法,需... 目录1. 使用 + 运算符示例:优缺点:2. 使用&nbsjsp;join() 方法示例:优缺点:3

java字符串数字补齐位数详解

《java字符串数字补齐位数详解》:本文主要介绍java字符串数字补齐位数,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录Java字符串数字补齐位数一、使用String.format()方法二、Apache Commons Lang库方法三、Java 11+的St

C++字符串提取和分割的多种方法

《C++字符串提取和分割的多种方法》在C++编程中,字符串处理是一个常见的任务,尤其是在需要从字符串中提取特定数据时,本文将详细探讨如何使用C++标准库中的工具来提取和分割字符串,并分析不同方法的适用... 目录1. 字符串提取的基本方法1.1 使用 std::istringstream 和 >> 操作符示

SpringBoot项目使用MDC给日志增加唯一标识的实现步骤

《SpringBoot项目使用MDC给日志增加唯一标识的实现步骤》本文介绍了如何在SpringBoot项目中使用MDC(MappedDiagnosticContext)为日志增加唯一标识,以便于日... 目录【Java】SpringBoot项目使用MDC给日志增加唯一标识,方便日志追踪1.日志效果2.实现步

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java反转字符串的五种方法总结

《Java反转字符串的五种方法总结》:本文主要介绍五种在Java中反转字符串的方法,包括使用StringBuilder的reverse()方法、字符数组、自定义StringBuilder方法、直接... 目录前言方法一:使用StringBuilder的reverse()方法方法二:使用字符数组方法三:使用自

Golang中拼接字符串的6种方式性能对比

《Golang中拼接字符串的6种方式性能对比》golang的string类型是不可修改的,对于拼接字符串来说,本质上还是创建一个新的对象将数据放进去,主要有6种拼接方式,下面小编就来为大家详细讲讲吧... 目录拼接方式介绍性能对比测试代码测试结果源码分析golang的string类型是不可修改的,对于拼接字

Java对象和JSON字符串之间的转换方法(全网最清晰)

《Java对象和JSON字符串之间的转换方法(全网最清晰)》:本文主要介绍如何在Java中使用Jackson库将对象转换为JSON字符串,并提供了一个简单的工具类示例,该工具类支持基本的转换功能,... 目录前言1. 引入 Jackson 依赖2. 创建 jsON 工具类3. 使用示例转换 Java 对象为