Leetcode 3337. Total Characters in String After Transformations II
- Leetcode 3337. Total Characters in String After Transformations II
- 1. 解题思路
- 2. 代码实现
- 题目链接:3337. Total Characters in String After Transformations II
1. 解题思路
这一题是这次最有意思的一道题目,可惜我也没有自力搞定,看了题目才恍然大悟的……
这一题就是一道纯·数学问题,我们可以给定的变化用一个转移矩阵进行表示:
T = [ t a a t a b t a c ⋯ t a z t b a t b b t b c ⋯ t b z ⋮ ⋮ ⋮ ⋱ ⋮ t z a t z b t z c ⋯ t z z ] T = \begin{bmatrix} t_{aa} & t_{ab} & t_{ac} & \cdots & t_{az} \\ t_{ba} & t_{bb} & t_{bc} & \cdots & t_{bz} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ t_{za} & t_{zb} & t_{zc} & \cdots & t_{zz} \end{bmatrix} T= taatba⋮tzatabtbb⋮tzbtactbc⋮tzc⋯⋯⋱⋯taztbz⋮tzz
其中, t i j t_{ij} tij表示字符 i i i经过一次变换之后产生的字符 j j j的个数。
我们使用数组 a = ( n a , n b , n c , ⋯ , n z ) a = ({n_a, n_b, n_c, \cdots, n_z}) a=(na,nb,nc,⋯,nz)表示原始字符串当中字符 a a a到 z z z各自出现的次数,那么,不难写出,经过 t t t次操作之后最终得到的字符串当中各个字符的个数即为:
o = a ⋅ T t o = a \cdot T^{t} o=a⋅Tt
因此,这就变成一个矩阵连乘的问题了,和一般的n次方问题完全一样了,直接二分求解即可。
2. 代码实现
给出python代码实现如下:
MOD = 10**9+7class Solution:def lengthAfterTransformations(self, s: str, t: int, nums: List[int]) -> int:def mat_mul(A, B):assert(len(A[0]) == len(B))n, m, l = len(A), len(A[0]), len(B[0])out = [[0 for _ in range(l)] for _ in range(n)]for i in range(n):for j in range(l):for k in range(m):out[i][j] = (out[i][j] + A[i][k] * B[k][j]) % MODreturn outmat = [[0 for _ in range(26)] for _ in range(26)]for i, j in enumerate(nums):for k in range(1, j+1):mat[i][(i+k) % 26] = 1@lru_cache(None)def mat_pow(n):if n == 1:return matreturn mat_mul(mat_pow(n//2), mat_pow(n-n//2))mat = mat_pow(t)cnt = [0 for _ in range(26)]for ch in s:cnt[ord(ch) - ord('a')] += 1out = [0 for _ in range(26)]for j in range(26):for i in range(26):out[j] = (out[j] + cnt[i] * mat[i][j]) % MODreturn sum(out) % MOD
提交代码评测得到:耗时3719ms,占用内存25.3MB。