贪心算法

概述

贪心算法是一种在每一步选择中都采取当前看起来最优的选择（贪心选择）的算法。它在每一步做出局部最优解，期望通过这些局部最优解最终得到全局最优解。贪心算法通常用于解决优化问题。

特点

• 局部最优性：在每一步做选择时，总是选择当前状态下最优的方案。
• 可行性：所选择的方案需满足问题的约束条件。
• 无后效性：选择的结果不会影响后续的选择过程。

常见应用

• 最小生成树：如Kruskal算法和Prim算法。
• 活动选择问题：选择不重叠的活动。
• 霍夫曼编码：用于数据压缩。

优缺点

• 优点：实现简单，通常效率高，适用于某些特定类型的问题。
• 缺点：并非所有问题都可以使用贪心算法获得全局最优解，需要具备贪心选择性质和最优子结构性质。

字符串处理

概述

字符串处理涉及对字符串（即字符的序列）的各种操作和算法。字符串是计算机科学中一种基本的数据结构，字符串处理在文本处理、搜索、匹配等领域具有广泛的应用。

常见操作

• 查找：在字符串中查找子串，例如KMP算法、Boyer-Moore算法等。
• 匹配：确定一个字符串是否包含另一个字符串。
• 替换：替换字符串中的某些部分。
• 排序：按照特定规则对字符串进行排序。

常见算法

• KMP（Knuth-Morris-Pratt）算法：用于字符串匹配，时间复杂度为O(n + m)，其中n是主串长度，m是模式串长度。
• Trie（字典树）：一种高效的字符串检索结构，适合用于前缀匹配等场景。
• Sufix Tree：是一种压缩后的后缀树，主要用于处理后缀相关问题。

应用场景

• 文本检索引擎
• DNA序列分析
• 编程语言的解析与编译

总结

贪心算法和字符串处理是数据结构与算法中两个非常重要的领域。贪心算法侧重于问题的最优解选择，对于某些特定问题十分有效；而字符串处理则是计算机科学基础之一，涉及众多字符串操作和应用方法。掌握这两个领域能够有效提升编程和解决问题的能力。

OK，话不多说，直接看题：

2734.执行子串操作后的字典序最小字符串【中等】

题目：

给你一个仅由小写英文字母组成的字符串 s 。在一步操作中，你可以完成以下行为：

• 选择 s 的任一非空子字符串，可能是整个字符串，接着将字符串中的每一个字符替换为英文字母表中的前一个字符。例如，'b' 用 'a' 替换，'a' 用 'z' 替换。

返回执行上述操作 恰好一次 后可以获得的 字典序最小 的字符串。

子字符串 是字符串中的一个连续字符序列。

现有长度相同的两个字符串 x 和 字符串 y ，在满足 x[i] != y[i] 的第一个位置 i 上，如果  x[i] 在字母表中先于 y[i] 出现，则认为字符串 x 比字符串 y 字典序更小 。

示例 1：

输入：s = "cbabc"
输出："baabc"
解释：我们选择从下标 0 开始、到下标 1 结束的子字符串执行操作。 
可以证明最终得到的字符串是字典序最小的。

示例 2：

输入：s = "acbbc"
输出："abaab"
解释：我们选择从下标 1 开始、到下标 4 结束的子字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

示例 3：

输入：s = "leetcode"
输出："kddsbncd"
解释：我们选择整个字符串执行操作。
可以证明最终得到的字符串是字典序最小的。

提示：

• 1 <= s.length <= 3 * 10**5
• s 仅由小写英文字母组成

分析问题：

        读题意，可以知道这道题就是在从前往后遍历把每个非a的字母都变成它之前的小写字母，这里可以用ASCLL码进行实现，并且只能选择一个子序列。什么意思呢？ 就是只能选择在两个a中间夹着的一个子序列，或者是一个a前面的子序列，如果前面的子序列为空字符串，那么就是a后面的子序列。

        需要注意的是，这里必须要操作一次，也就是说如果s全是a的话，也必须要执行一次操作，那么当然是选最后的一个a将其变成z是字典序最小的情况。

        思路很简单，总的来说就是把字符串以‘a’为标志分隔，取最前面一个不空的字符串作为我们选择的子字符串来修改。

        这种思路虽然是正确的，但是复杂度太高，代码太复杂，需要处理的细节很多。所以我们可以对该代码进一步优化。

优化思路如下：

1. 首先获取输入字符串 s 的长度 n ，并初始化一个索引 i 为 0 。
2. 通过一个 while 循环，从字符串的开头开始，找到第一个不是 'a' 的字符的位置 i 。
3. 如果整个字符串都是 'a' （即 i == n ），那么将字符串的最后一个字符改为 'z' 并返回。
4. 然后初始化另一个索引 j = i ，通过另一个 while 循环，从位置 i 开始找到第一个 'a' 的位置 j 。
5. 对于从位置 i 到位置 j 的这部分子串，将每个字符的 ASCII 值减 1 ，得到新的子串。
6. 最后将原始字符串的前 i 个字符、新生成的子串和位置 j 之后的字符拼接起来返回。

代码实现：

优化前：

class Solution:
    def smallestString(self, s: str) -> str:
        # 如果字符串中没有 'a'
        if s.count('a')==0:
            # 将字符串转换为列表以便修改元素
            s,v = list(s),''
            # 遍历列表，将每个字符的 ASCII 值减 1
            for i in range(len(s)):
                s[i] = chr(ord(s[i]) - 1) 
            # 将修改后的列表元素重新组合成字符串
            for l in s: 
                v += l
        else:
            # 计算字符串中 'a' 的个数
            n = s.count('a')
            # 按 'a' 分割字符串并转换为列表
            ls = list(s.split('a'))
            key = ''
            b = ''
            # 找到第一个非空的子串
            for k in ls:
                if k!= '':
                    key = k
                    b = k
                    break
            # 如果没有找到非空子串
            if key == '': 
                return s[:-1] + 'z'
            # 将非空子串转换为列表
            key = list(key)
            # 遍历非空子串列表，将每个字符的 ASCII 值减 1
            for j in range(len(key)):
                key[j] = chr(ord(key[j]) - 1)
            p = ''
            # 将修改后的非空子串列表元素重新组合成字符串
            for l in key: 
                p += l
            # 将修改后的非空子串放回原列表中
            ls[ls.index(b)] = p
            v = ''
            # 重新组合处理后的列表为字符串，并在适当位置插入 'a'
            for j in ls:
                if j == '' and n > 0:
                    v += 'a'
                    n -= 1
                else: 
                    v += j
                    if n > 0:
                        v += 'a'
                        n -= 1
        # 如果处理后的字符串与原始字符串不同
        if v!= s:
            return v
        # 如果处理后的字符串与原始字符串相同，将最后一个字符改为 'z' 并返回
        return v[:-1] + 'z'

​

优化后： 

class Solution:
    def smallestString(self, s: str) -> str:
        n = len(s)
        i = 0
        while i < n and s[i] =='a':
            i +=1
        if i == n:
            return s[:-1] + "z"
        j = i
        while j< n and s[j] != 'a':
            j+=1
        return s[:i] + "".join(chr(ord(c) - 1) for c in s[i:j]) + s[j:]

​​

​

总结：

考点：

1. 字符串的遍历和索引操作。
2. 条件判断（while 循环的条件）。
3. 字符的 ASCII 值操作（通过 ord 和 chr 函数）。

收获：

1. 加深了对字符串处理的理解，包括如何遍历和根据条件提取子串。
2. 学会了使用 ord 和 chr 函数来操作字符的 ASCII 值，实现对字符的修改。
3. 掌握了通过多个索引和循环来处理字符串中特定部分的技巧。
4. 提高了在处理复杂字符串问题时的逻辑思维和代码实现能力。