字符串构造求助,单一操作下log2n复杂度 增加一种操作如何解
  • 板块学术版
  • 楼主guanwangzhensao1
  • 当前回复1
  • 已保存回复1
  • 发布时间2024/12/23 21:25
  • 上次更新2024/12/24 15:00:51
查看原帖
字符串构造求助,单一操作下log2n复杂度 增加一种操作如何解
1626083
guanwangzhensao1楼主2024/12/23 21:25

题目

m个长度为len的字符串,每个字符串都由0,1组成,目标是构成一个只由1组成的字符串。两个字符串可以进行操作1生成新的字符串(原字符串仍然存在,可以重复使用)。操作1:新的字符串由字符串a的[0,l)的子串和字符串b的[l,len)的子串拼接而成(a,b顺序可以互换)。

已知条件:对于[0, len)的每个位置,至少存在一个字符串在该位置为1.

我的思路:从m个字符串中找到一个字符串集,使得集合内的字符串满足已知条件并且连续1的片段数量之和最小。将连续1的片段按照开始位置排序,进行归并,产生一颗二叉平衡树,时间复杂度log2n(n为连续1的片段数量之和)

logo

增加操作2:新字符串由字符串a的[0,l)、字符串b的[l,r],字符串a的(r, len)组成(a,b顺序可以互换)。在操作1和操作2都存在的情况下,如何最快构造目标字符串呢。(操作2的效果类似于2次操作1)

2024/12/23 21:25
加载中...