当前位置: 首页> 房产> 市场 > 个体营业执照年审怎么年审_手机当服务器建网站_百度快速排名优化技术_2021小学生新闻摘抄

个体营业执照年审怎么年审_手机当服务器建网站_百度快速排名优化技术_2021小学生新闻摘抄

时间:2025/7/9 7:32:30来源:https://blog.csdn.net/codename_cys/article/details/143279687 浏览次数:0次
个体营业执照年审怎么年审_手机当服务器建网站_百度快速排名优化技术_2021小学生新闻摘抄
  • 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= taatbatzatabtbbtzbtactbctzctaztbztzz

其中, 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=aTt

因此,这就变成一个矩阵连乘的问题了,和一般的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。

关键字:个体营业执照年审怎么年审_手机当服务器建网站_百度快速排名优化技术_2021小学生新闻摘抄

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: