数组 – 给定一串红色和蓝色的球,找到最少数量的互换,以一起分色

我们得到一个形式的字符串:RBBR,其中R – 红色和B – 蓝色.

我们需要找到为了将颜色一起分配所需的最小交换数量.在上述情况下,答案将为1获得RRBB或BBRR.

我觉得像排序一个部分排序的数组的算法在这里是有用的,因为一个简单的排序将给我们的交换数量,但我们想要最小的交换数量.

有任何想法吗?

据说这是根据this的微软采访问题.

取一个字符串,并计数红色数(#R)和蓝调数(#B).然后计算第一#R球(#r)中的红色数量和第一#B球(#b)中的蓝色球数. (#R – #r)和(#B – #b)中的较小者将是所需的最小交换数.
相关文章
相关标签/搜索