【贪心算法】——力扣763. 划分字母区间

🕗 发布于 2024-11-13 06:28 贪心算法 leetcode 算法

763. 划分字母区间

一、题目难度

中等

二、相关标签与相关企业

[相关标签]
[相关企业]

三、题目描述

给你一个字符串 s。我们要把这个字符串划分为尽可能多的片段，同一字母最多出现在一个片段中。

注意，划分结果需要满足：将所有划分结果按顺序连接，得到的字符串仍然是 s。

返回一个表示每个字符串片段的长度的列表。

四、示例

示例1

输入：s = "ababcbacadefegdehijhklij"
输出：[9, 7, 8]
解释：
划分结果为“ababcbaca”、“defegde”、“hijhklij”，每个字母最多出现在一个片段中。
像“ababcbacadefegde”，“hijhklij”这样的划分是错误的，因为划分的片段数较少。

示例2

输入：s = "eccbbbbdec"
输出：[10]

五、提示

1 <= s.length <= 500
s 仅由小写英文字母组成

贪心算法

思路：
- 首先，我们先遍历一次字符串，用字典last_s = { }记录每个字母最后出现的位置。
- 然后，我们再次从头遍历字符串，设定一个当前片段起start末end位置，后续不断更新维护该片段。
  - 起start末end都初始化为0
  - 遍历过程中，对于每个字符，更新end为当前字符最后出现位置的最大字符
  - 当遍历到i位置等于end时，说明当前片段已经包含了所有出现过的字母
  - 将当前片段的长度end - start +1添加到结果列表中
  - 更新start为i + 1，开始下一个片段的划分

——————————————————————————————————————————————
如何实现用字典和enumerate（）函数记录最后出现的位置？？

1. `enumerate`函数**

功能：
- enumerate 是 Python 中的一个内置函数，它用于在遍历可迭代对象（如列表、字符串等）时，同时返回元素的索引和元素本身。它的基本语法是 enumerate(iterable, start=0)，其中iterable是要遍历的可迭代对象，start 是可选参数，用于指定索引的起始值，默认是 0。
用法：
- 当执行for i, char in enumerate(s): 时，对于字符串 s 中的每个字符char和i,enumerate 会依次获取到该字符在字符串中的索引（从 0 开始，因为默认 start=0），而 char 则获取到对应的字符本身。例如，如果 s = "abc"，那么第一次循环时，i 会是 0，char 会是 a；第二次循环时，i 会是 1，char 会是 b；第三次循环时，i 会是 2，char 会是 c。

以下是对这段代码中字典 last_index 以及 enumerate 函数相关操作的详细解释：

2. 字典 `last_index`

注意字典写入方法：
- last_index={} # 创建字典
- last_index[a] = 1 # 写入键值对
- ——>
- last_index = {'a' : 1}
功能及初始化：
- 字典是Python中的一种数据结构，它以键值对的形式存储数据，其中键是唯一的，通过键可以快速访问到对应的值。在这里，last_index 字典被初始化为一个空字典 {}，它的作用是用于记录每个字母在字符串 s 中最后出现的位置。
记录最后出现位置的原理：
- 在循环 for i, char in enumerate(s): 中，每次遍历到一个字符 char 时，我们就将这个字符作为键，将它当前的索引 i 作为值，存入 last_index 字典中。关键在于，由于我们是按照字符串的顺序依次遍历的，所以当遇到同一个字母多次出现时，后面出现的位置索引会覆盖前面的记录。这样，当整个字符串遍历完成后，字典 last_index 中每个字母对应的键值对中，值就是该字母在字符串中最后出现的位置。
写入后字典的形式示例：
- 假设字符串 s = "ababcbacadefegdehijhklij"，经过上述循环遍历后，last_index 字典的形式可能如下：

{
    'a': 8,
    'b': 5,
    'c': 7,
    'd': 14,
    'e': 15,
    'f': 11,
    'g': 13,
    'h': 19,
    'i': 22,
    'j': 23,
    'k': 20,
    'l': 21
}

可以看到，每个字母作为键，其最后出现的位置作为值被准确地记录在了字典中。这样，在后续处理划分字母区间的过程中，我们就可以方便地通过查询这个字典来获取每个字母的最后出现位置信息，以便确定每个片段的范围。

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 1. 统计每个字符最后出现的位置(用到enumerate迭代器，返回字符串的索引和字符)
          # 初始化字典last_index
        last_index = {}
          # 从头遍历每个字符char出现的位置，由于从头向后遍历，后面的位置会覆盖前面的,
        for i, char in enumerate(s):
            last_index[char] = i

        # 2. 从头遍历字符串s的字符char，
          # 初始化起末位置
          start = 0
          end = 0
          # 初始化结果列表
          res = []
          # 再次遍历，对于每个字符char,索引i
        for i, char in enumerate(s):
            # 更新end，为当前字符char最后出现的位置（字典中存着）
            end = last_index[char]
            if i == end:
                res.append(end- start + 1)
        return res
————————————————————————————————————————————
执行出错
0 / 118 个通过的测试用例
IndentationError: unindent does not match any outer indentation level
             ^
    start = 0
Line 12  (Solution.py)

以上代码错误，是我顺着之前的算法步骤写的！
问题出在哪？
太粗心了呀!!!

首先，i碰到一次end，需要更新start位置为i+1

    if i == end:
        res.append(end- start + 1)
        start = i + 1

一个很关键的点，下面来详细解释一下为什么是 end = max(end, last_index[char]) 而不是直接 end = last_index[char]：

理解需求

我们的目标是划分字符串 s 为尽可能多的片段，使得同一字母最多出现在一个片段中。在遍历字符串的过程中，要确定每个片段的结束位置 end，这个位置应该是当前片段内所有字母最后可能出现的最远位置。

直接赋值的问题（`end = last_index[char]`）

如果按照 end = last_index[char] 来更新 end，那么每次遇到一个字符 char，就会直接将 end 设置为该字符在字典中记录的最后出现位置。这样做会导致一个问题，就是可能会把 end 的值设置得过小，无法包含当前片段内其他字母后续可能出现的位置。

例如，对于字符串 s = "ababcbacadefegdehijhklij"，假设我们已经开始划分第一个片段，初始时 end = 0。当我们遍历到字符 a 时，如果按照直接赋值的方式，end 就会被设置为 a 的最后出现位置，也就是 8。但此时，在后续的字符串中，还有其他字母（如 b、c 等）在这个片段内也会出现，并且它们的最后出现位置可能比 8 更远。如果就这样把 end 固定为 8，那么就无法正确划分出满足条件的片段，可能会导致某些字母被错误地划分到了下一个片段中，违背了“同一字母最多出现在一个片段中”的要求。

取最大值的好处（`end = max(end, last_index[char])`）

而使用 end = max(end, last_index[char]) 来更新 end，就可以避免上述问题。每次遇到一个字符 char，我们会比较当前的 end 值和该字符 char 的最后出现位置（last_index[char]）。

如果 last_index[char] 大于当前 end 值，说明该字符的最后出现位置更远，那么就需要把 end 更新为这个更远的位置，以确保 end 能够包含该字符以及可能后续出现的其他字母的最远位置。
如果 last_index[char] 小于等于当前 end 值，说明当前 end 的值已经能够涵盖该字符后续可能出现的位置了，不需要对 end 进行更新。

继续以上面的字符串为例，初始时 end = 0，当遍历到字符 a 时，假设 a 的最后出现位置是 8，此时 end = max(0, 8)，end 就会被更新为 8。接着当遍历到字符 b 时，假设 b 的最后出现位置是 5，因为 5 小于当前的 end（也就是 8），所以 end 保持不变，还是 8。但当遍历到字符 c 时，假设 c 的最后出现位置是 7，此时 end = max(8, 7)，end 依然保持为 8。这样，通过不断地取最大值来更新 end，就能保证 end 始终是当前片段内所有字母最后可能出现的最远位置，从而正确地划分出满足条件的片段。

所以，不能简单地为每一个 char 都直接赋予 end，而是要通过取最大值的方式来更新 end，以确保划分片段的正确性。

修改了代码：

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 1. 统计每个字符最后出现的位置(用到enumerate迭代器，返回字符串的索引和字符)
          # 初始化字典last_index
        last_index = {}
          # 从头遍历每个字符char出现的位置，由于从头向后遍历，后面的位置会覆盖前面的,
        for i, char in enumerate(s):
            last_index[char] = i

        # 2. 从头遍历字符串s的字符char，
          # 初始化起末位置
          start = 0
          end = 0
          # 初始化结果列表
          res = []
          # 再次遍历，对于每个字符char,索引i
        for i, char in enumerate(s):
            # 更新end，为当前字符char最后出现的位置（字典中存着）
            # 错：end = last_index[char]
            # 改：
            end = max(last_index[char], end)
            if i == end:
                res.append(end- start + 1)
                # 错，加：
                start = i + 1 
        return res
————————————————————————————————————————————————————————
IndentationError: unindent does not match any outer indentation level
             ^
    start = 0
Line 12  (Solution.py)

检查半天原来是缩进问题，缩进是python的特色。

class Solution:
    def partitionLabels(self, s: str) -> List[int]:
        # 1. 统计每个字符最后出现的位置(用到enumerate迭代器，返回字符串的索引和字符)
          # 初始化字典last_index
        last_index = {}
          # 从头遍历每个字符char出现的位置，由于从头向后遍历，后面的位置会覆盖前面的,
        for i, char in enumerate(s):
            last_index[char] = i

        # 2. 从头遍历字符串s的字符char，
          # 初始化起末位置
        start = 0
        end = 0
        # 初始化结果列表
        res = []
        # 再次遍历，对于每个字符char,索引i
        for i, char in enumerate(s):
            # 更新end，为当前字符char最后出现的位置（字典中存着）
            # 错：end = last_index[char]
            # 改：
            end = max(last_index[char], end)
            if i == end:
                res.append(end- start + 1)
                # 错，加：
                start = i + 1 
        return res
————————————————————————————
通过

原文地址：https://blog.csdn.net/weixin_47868976/article/details/143725782

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：性能测试|JMeter接口与性能测试项目
下一篇：HTML文本标签学习记录

GOLANG笔记第四周
原本的本地函数放到另一个服务器上运行，但是引入了很多新问题Call 的id映射序列化和反序列化网络传输。
阅读更多2024-11-16
redis集群主备模式的快速搭建
redis主备集群可以有效的实现节点的冗余备份，提高redis的负载压力的同时，又有效的实现了故障切换。
阅读更多2024-11-16
Python实现贪吃蛇经典解压小游戏！附源码
大家应该都玩过诺基亚上面的贪吃蛇吧，那是一段美好的童年回忆，本文将带你一步步用python语言实现一个snake小游戏！版本：Python3●系统：Windows●相关模块：pygamepip ins
阅读更多2024-11-16
Unity中HDRP设置抗锯齿
在Unity的高清渲染管线（HDRP）中，Post Anti-Aliasing（后期抗锯齿）提供了几种不同的抗锯齿选项，以减少图像中的锯齿效果并提升视觉质量。FXAA是一种基于像素的抗锯齿方法，通过模
阅读更多2024-11-16
嘎嘎快充php版服务端部署配置注意玉阳软件
6、需要移除PHP禁用函数：proc_open、pcntl_alarm、pcntl_fork、pcntl_wait、pcntl_signal、pcntl_signal_dispatch。7、不需要cd
阅读更多2024-11-16
Docker 容器常见故障排查及处理
Docker 容器常见故障排查及处理。
阅读更多2024-11-16
Python实现人脸识别算法并封装为类库（续）
本文将介绍如何使用Python实现一个人脸识别系统，并将其封装为一个类库。我们将逐步扩展和完善这个类库，增加代码优化、人脸照片存储到数据库、对特殊场景（如戴口罩、眼镜）的优化，以及灵活的识别距离设置。
阅读更多2024-11-16
CentOS虚拟机使用记录
1.安装 Vmtool ,重启后可显示U盘2.安装minicomcentOs 安装使用yum minicom ,没有apt-get 命令通过ssh网口root 2440ssh root@192.16
阅读更多2024-11-16
MATLAB中的绘图技巧
综上所述，MATLAB凭借其强大的绘图功能，为用户提供了丰富多样的可视化选择。从基础的二维图形到复杂的三维动画，MATLAB都能够胜任。掌握这些绘图技巧，不仅能够提升数据分析的可读性，也能够增强报告和
阅读更多2024-11-16
Win11 终端执行 python xxx.py 没反应
在 Win11 上写了一段 Python 代码来分析日志文件，发现执行没反应。是在 VSCode 里的终端中执行的。, 是 PowerShell；也尝试了 cmd，情况一样。WindowsApps
阅读更多2024-11-16