使用哪种算法将字符串序列排序成块，避免以某个元素开头？
使用哪种算法将字符串序列排序成块，避免以某个元素开头？
提问于 2019-09-03 04:28:52
假设有一个列表：['a', 'a', 'a', 'b', 'a', 'a', 'b', 'b', 'b']。
您可以使用哪种算法将其分类为具有2-4个元素的组？以'b'开头的组应该尽可能少。
在本例中：aa | aba | abbb
这是一个家庭作业，找到一个最优的算法。
回答 1
Stack Overflow用户
发布于 2019-09-03 09:16:18
如果允许我们更改元素的顺序，那么问题就很简单了:只要对所有的a进行分组，并尽可能在每个b后面插入三个a，就可以创建大小为4的组(如果没有足够的b，则创建更小的组)。在此之后，如果还有剩余的b，请将它们分组为大小为4的组；否则，可以根据需要对其余的a进行分组。
如果我们必须保持元素的顺序，问题就会变得更有趣，我们可以在O(n)中解决这个问题，其中n是元素的数量，使用以下递归:让f(i, j)表示从b开始直到索引i的最优集合中的组数，其中这个元素是它的组中的第j个元素。(由于j的范围从2到4，因此复杂度为O(3n) = O(n)。)然后：
f(i, j) =
if A[i - j + 1] == 'b':
return 1 + min(f(i - j, k)), for 1 < k < 5
else:
return min(f(i - j, k)), for 1 < k < 5JavaScript中简单的自上而下：
function f(A, i, j){
if (j > i + 1 || i == 0)
return Infinity
if (i == 1)
return A[0] == 'b' ? 1 : 0
let prev = Infinity
for (let k=2; k<5; k++)
prev = Math.min(f(A, i - j, k), prev)
return prev + (A[i - j + 1] == 'b' ? 1 : 0)
}
var A = "aaabaabbb"
console.log(A)
for (let j=2; j<5; j++)
console.log(`If the last char is ${j + [,,'nd','rd','th'][j]}, then optimal is ${f(A, A.length-1, j)}`)
A = "aaabaabbbb"
console.log('\n' + A)
for (let j=2; j<5; j++)
console.log(`If the last char is ${j + [,,'nd','rd','th'][j]}, then optimal is ${f(A, A.length-1, j)}`)
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/57762393
复制相关文章
相似问题
腾讯云开发者
