<LeetCode天梯>Day017 字符串中的第一个唯一字符(哈希表+find&rfind) | 初级算法 | Python

简介: <LeetCode天梯>Day017 字符串中的第一个唯一字符(哈希表+find&rfind) | 初级算法 | Python

以下为我的天梯积分规则:


每日至少一题:一题积分+10分

若多做了一题(或多一种方法解答),则当日积分+20分(+10+10)

若做了三道以上,则从第三题开始算+20分(如:做了三道题则积分-10+10+20=40;做了四道题则积分–10+10+20+20=60)


初始分为100分

若差一天没做题,则扣积分-10分(周六、周日除外注:休息)

坚持!!!


初级算法

刷题目录

字符串


image.png

image.png

题干

给定一个字符串,找到它的第一个不重复的字符,并返回它的索引。如果不存在,则返回 -1。


示例:


s = “leetcode”

返回 0


s = “loveleetcode”

返回 2


提示:你可以假定该字符串只包含小写字母。


哈希表

分析:


本题找到不重复的字符,很明显的暗示,让我们用字典,哈希表来解题。通过字典确定每个字符的个数,然后再选出只有单次出现的字符,且选出最先出现的,返回其相对应的索引号。

class Solution:
    def firstUniqChar(self, s: str) -> int:
    # 哈希表
        hashmap = {}
        for i in s:
            if i not in hashmap:
                hashmap.update({i:s.count(i)}) # 将数字各自出现的个数存入哈希表中
        for key,value in hashmap.items():   # 遍历哈希表的键值
            if hashmap[key] == 1:
                return s.index(key)
        return -1

哈希表的速度表现还不错的!~

image.png

索引count

分析:

我们还可以将字符串取为单个字符成list后,通过count计数,看在其中的个数是多少,遍历所有项,删除多余的项,若大于1,则不返回;若仅有一个字符,则返回其对应的索引号。若不存在,则返回-1.

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # 将s中的单个字母取出来为单个字符串
        list1 = list(map(str, s))
        n = len(list1)
    temp = 0
        list2 = list(map(str, s))
        for i in list1:
            if list1.count(i) > 1:
                list2.remove(i)   # 如果有,则删除list2里的对应值
        # 判断是否存在上述情况
        for j in list1:
            if list1.count(j) == 1:
                temp += 1
        if temp > 0:
            return list1.index(list2[0])   # 查询list2中删除完
        return -1

额,勇气可嘉,超出时间限制了,感觉不应该的啊

image.png

我们再进行优化一下

将temp的判断再细化一下

不遍历所有直接读取list2的参数,看是否删除了相同的值之后还存在值,如果还有则,返回第一个,如果没有,则返回-1。

class Solution:
    def firstUniqChar(self, s: str) -> int:
        # 将s中的单个字母取出来为单个字符串
        list1 = list(map(str, s))
        n = len(list1)
    list2 = list(map(str, s))
        for i in list1:
            if list1.count(i) > 1:
                list2.remove(i)   # 如果有,则删除list2里的对应值
        # 判断是否存在上述情况
        if len(list2) > 0:
            return list1.index(list2[0])   # 查询list2中删除完
        return -1

还是太菜了,超出时间限制了

image.png

不过肯定是能用的。

咱们只用内置函数试试

class Solution:
    def firstUniqChar(self, s: str) -> int:
    for i in range(len(s)):
            if s.count(s[i]) == 1:
                return i
        return -1

image.png

实时证明,确实很慢很慢,不考虑了。

两次遍历

我们可以使用两次遍历来输出,第一次遍历,将每个数字出现的次数保存在一个list中,第二次遍历这个list,如果一遇到值为1,则输出1所在的索引值,否则,返回-1.

class Solution:
    def firstUniqChar(self, s: str) -> int:
    c1 = []
        n = len(s)
        for i in range(n):
            c1.append(s.count(s[i]))
        for j in range(n):
            if c1[j] == 1:
                return j
        return -1

勇气可嘉,怎么还是超出时间限制啊o(╥﹏╥)o

image.png

find和rfind

此法骨骼极其清奇,简直不要太妙了。一个从前查找,一个从后查找,如果下标相等,说明只出现了一次

class Solution:
    def firstUniqChar(self, s: str) -> int:
    for x in s:
            if s.find(x) == s.rfind(x):
                return s.find(x)
        return -1

image.png


相关文章
|
8天前
|
算法
刷算法Leetcode---9(二叉树篇Ⅲ)
刷算法Leetcode---9(二叉树篇Ⅲ)
11 3
|
25天前
|
算法 Java
[Java·算法·简单] LeetCode 283. 移动零
[Java·算法·简单] LeetCode 283. 移动零
22 2
|
25天前
|
算法 Java
[Java·算法·中等] LeetCode21. 合并两个有序链表
[Java·算法·中等] LeetCode21. 合并两个有序链表
18 2
|
28天前
|
算法 C++
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题-2
【数据结构与算法】:关于时间复杂度与空间复杂度的计算(C/C++篇)——含Leetcode刷题
|
1天前
|
算法 数据挖掘
MATLAB数据分析、从算法到实现
MATLAB数据分析、从算法到实现
|
7天前
|
机器学习/深度学习 算法 调度
Matlab|基于改进鲸鱼优化算法的微网系统能量优化管理matlab-源码
基于改进鲸鱼优化算法的微网系统能量管理源码实现,结合LSTM预测可再生能源和负荷,优化微网运行成本与固定成本。方法应用于冷热电联供微网,结果显示经济成本平均降低4.03%,提高经济效益。代码包括数据分段、LSTM网络定义及训练,最终展示了一系列运行结果图表。
|
7天前
|
算法
基于Dijkstra算法的最优行驶路线搜索matlab仿真,以实际城市复杂路线为例进行测试
使用MATLAB2022a实现的Dijkstra算法在城市地图上搜索最优行驶路线的仿真。用户通过鼠标点击设定起点和终点,算法规划路径并显示长度。测试显示,尽管在某些复杂情况下计算路径可能与实际有偏差,但多数场景下Dijkstra算法能找到接近最短路径。核心代码包括图的显示、用户交互及Dijkstra算法实现。算法基于图论,不断更新未访问节点的最短路径。测试结果证明其在简单路线及多数复杂城市路况下表现良好,但在交通拥堵等特殊情况下需结合其他数据提升准确性。
|
13天前
|
算法 安全 数据库
基于结点电压法的配电网状态估计算法matlab仿真
**摘要** 该程序实现了基于结点电压法的配电网状态估计算法,旨在提升数据的准确性和可靠性。在MATLAB2022a中运行,显示了状态估计过程中的电压和相位估计值,以及误差随迭代变化的图表。算法通过迭代计算雅可比矩阵,结合基尔霍夫定律解决线性方程组,估算网络节点电压。状态估计过程中应用了高斯-牛顿或莱文贝格-马夸尔特法,处理量测数据并考虑约束条件,以提高估计精度。程序结果以图形形式展示电压幅值和角度估计的比较,以及估计误差的演变,体现了算法在处理配电网状态估计问题的有效性。
|
10天前
|
数据采集 存储 算法
基于BP算法的SAR成像matlab仿真
**摘要:** 基于BP算法的SAR成像研究,利用MATLAB2022a进行仿真。SAR系统借助相对运动合成大孔径,提供高分辨率图像。BP算法执行回波数据预处理、像素投影及图像重建,实现精确成像。优点是高精度和强适应性,缺点是计算量大、内存需求高。代码示例展示了回波生成、数据处理到插值显示的全过程。
|
17天前
|
机器学习/深度学习 自然语言处理 算法
m基于深度学习的OFDM+QPSK链路信道估计和均衡算法误码率matlab仿真,对比LS,MMSE及LMMSE传统算法
**摘要:** 升级版MATLAB仿真对比了深度学习与LS、MMSE、LMMSE的OFDM信道估计算法,新增自动样本生成、复杂度分析及抗频偏性能评估。深度学习在无线通信中,尤其在OFDM的信道估计问题上展现潜力,解决了传统方法的局限。程序涉及信道估计器设计,深度学习模型通过学习导频信息估计信道响应,适应频域变化。核心代码展示了信号处理流程,包括编码、调制、信道模拟、降噪、信道估计和解调。
42 8