中行软开 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)
#中国银行##编程测评##题解#