leetcode 第 405 场算法比赛

零、背景

没参加比赛，最后一题比较有难度。

A: 子串拼接。
B: DFS。
C: 动态规划。
D: 字符串hash+动态规划。

排名：无
代码地址： https://github.com/tiankonguse/leetcode-solutions/tree/master/contest/4/405

一、找出加密后的字符串

题意：字符串循环左移 K 次。

思路：K 为分界线，后缀放前面，前缀放后面。

二、生成不含相邻零的二进制字符串

题意：生成长度为 n 的 01 字符串，不能有连续 0。

思路：DFS 生成字符串，判断最后两个是否都是 0 即可。

三、统计 X 和 Y 频数相等的子矩阵数量

题意：统计左上角为顶点的子矩阵中，有多少包含相同个数的 X 和 Y。

思路：动态规划统计每个子矩阵出现的 X 和 Y 的个数，判断是否相等。

四、最小代价构造字符串

题意：给 n 个字符串和代价，问组成字符串 w 的最小代价。

思路：动态规划。

状态：dp(i) 前缀 i 的最小代价。
方程： dp(i) = dp(j) + min(cost[i,j])
分析：枚举所有字符串，更新状态。
复杂度：O(n^2)

优化：题目强调 n 个字符串的长度和不大于 L=10^5。
意味着字符串的长度集合不大于 sqrt(L)。

枚举字符串长度而不是字符串即可。
复杂度：O(n sqrt(L))

五、最后

这次比赛最后一题枚举字符串长度可以水过去，正规的做法是后缀数组和AC自动机，后面有计划分别介绍一下。

《完》

-EOF-

本文公众号：天空的代码世界
个人微信号：tiankonguse
公众号ID：tiankonguse-code