中行软开 11.3编程测评第4题 题解

题干：给定一串小写字符，每一个字符都可以转换成字母表中相邻的其他字符，但是a、z之间无法直接转换，求最少转换次数，使该字符串不存在两个辅音字母相邻

思路：读完题定下的基本认知是，元音字母将字符串分割为多个全为辅音字母的字符串，每一个辅音字符串的转换都是互不相干的独立问题，所以问题简化成，对一个全为辅音字母的字符串，求最少转换次数，使该字符串不存在两个辅音字母相邻

首先想到的思路就是动态规划，但是因为前三题过于简单，所以考虑寻找更简单的解法，尝试了135...246...这种交替转换，提交上去a了50%，想到对于"zbbz"的样例，应该是2、3位直接转换成a是最优解，交替转换的思路不可取，于是重新思考动规解法。

状态定义：

dp1：在第n位转换成元音字母的情况下，前n个字符组成的字符串，满足无连续辅音字母所需转换的最少次数

dp2：前n个字符组成的字符串，满足无连续辅音所需转换的最少次数

dp2就是待求的问题。

状态转移方程：

对于dp1，如果第n位变成了元音字母，那么问题就等价于求前n-1个辅音字符串，满足无连续辅音所需转换的最少次数，恰好是dp2[n-1]，则dp1=dp2[n-1]+count(n)

对于dp2，

情况1：如果最优解中第n-1位变成了元音字母，则最优解中第n位一定无需转换，最优解就是dp1[n-1]

情况2：如果最优解中第n-1位不变且第n-2位变成了元音字母，则最优解中第n位一定需要转换，最优解是dp1[n-2]+count(n)

情况3：最优解中第n-1位不变，且第n-2位不变，这种情况显然不存在，因为出现了连续两个辅音字母

状态转移方程如下：

// count(n) 是第n个辅音字母转换成元音字母所需转换的最小次数
dp1[n] = dp2[n-1] + count(n)
dp2[n] = min(dp1[n-1], dp1[n-2]+count(n))

状态初始化：

dp1[0] = count(0), dp1[1] = count(1)
dp2[0] = 0, dp2[1] = min(dp1[0], dp1[1])

代码实现：

def get_distances() -> dict[str: int]:
    """求每一个辅音字母转换为元音字母所需的最小转换次数，常数级时间复杂度"""
    distances = dict()
    for c in 'abcdefghijklmnopqrstuvwxyz':
        if c in vowel:
            continue
        distances[c] = 26
        for v in vowel:
            distances[c] = min(distances[c], abs(ord(v) - ord(c)))
    return distances


vowel = {'a', 'e', 'i', 'o', 'u'}
dis = get_distances()


def main(s: str) -> int:
    res = 0
    seg = ''
    # 分割出每一个连续的辅音字符串，独立求解，加和得到最终结果
    for c in s:
        if c in vowel:
            if len(seg) >= 2:
                res += count(seg)
            seg = ''
            continue
        seg += c
    
    if len(seg) >= 2:
        return res + count(seg)
    return res


def count(s: str) -> int:
    dp1 = [0] * len(s)
    dp2 = [0] * len(s)
    dp1[0] = dis[s[0]]
    dp1[1] = dis[s[1]]
    dp2[1] = min(dp1[0], dp1[1])
    for i in range(2, len(s)):
        # 以下是状态转移方程，可以进行存储优化
        dp1[i] = dp2[i-1] + dis[s[i]]
        dp2[i] = min(dp1[i-1], dp1[i-2] + dis[s[i]])

    return dp2[-1]


# def count(s: str) -> int:
#     """存储优化版本"""
#     a, b = dis[s[0]], dis[s[1]]
#     c = min(a, b)
#     for i in range(2, len(s)):
#         c_new = min(b, a + dis[s[i]])
#         a, b = b, c + dis[s[i]]
#         c = c_new
#     return c


print(main('azbbzabcdabbb'))

复杂度：

时间复杂度：O(n)

空间复杂度：O(n)，存储优化版本的复杂度是O(1)