2021-05-05：一个数组中只有两种字符‘G‘和‘B‘，可以让所有的G都放在左侧
原创2021-05-05：一个数组中只有两种字符‘G‘和‘B‘，可以让所有的G都放在左侧
原创
福大大架构师每日一题
修改于 2021-05-06 10:26:09
修改于 2021-05-06 10:26:09
2021-05-05：一个数组中只有两种字符'G'和'B'，可以让所有的G都放在左侧，所有的B都放在右侧。或者可以让所有的G都放在右侧，所有的B都放在左侧。但是只能在相邻字符之间进行交换操作。返回至少需要交换几次。
福大大 答案2021-05-05：
自然智慧即可。
所有G和所有B的相对顺序不变，交换次数一定是最少的。
相邻交换，类似于冒泡排序，而冒泡排序是稳定的。
把G全部移动到左边，记录次数step1；把B全部移动到左边，记录次数step2。返回值取step1和step2的最小值。
代码用golang编写。代码如下：
package main
import "fmt"
func main() {
s := "BBGGB"
ret := minSteps1(s)
fmt.Println(ret)
ret = minSteps2(s)
fmt.Println(ret)
}
// 一个数组中只有两种字符'G'和'B'，
// 可以让所有的G都放在左侧，所有的B都放在右侧
// 或者可以让所有的G都放在右侧，所有的B都放在左侧
// 但是只能在相邻字符之间进行交换操作，请问请问至少需要交换几次，
func minSteps1(s string) int {
if len(s) == 0 {
return 0
}
step1 := 0
gi := 0
for i := 0; i < len(s); i++ {
if s[i] == 'G' {
step1 += i - gi
gi++
}
}
step2 := 0
bi := 0
for i := 0; i < len(s); i++ {
if s[i] == 'B' {
step2 += i - (bi)
bi++
}
}
return getMin(step1, step2)
}
// 可以让G在左，或者在右
func minSteps2(s string) int {
if len(s) == 0 {
return 0
}
step1 := 0
step2 := 0
gi := 0
bi := 0
for i := 0; i < len(s); i++ {
if s[i] == 'G' { // 当前的G，去左边 方案1
step1 += i - gi
gi++
} else { // 当前的B，去左边 方案2
step2 += i - bi
bi++
}
}
return getMin(step1, step2)
}
func getMin(a int, b int) int {
if a < b {
return a
} else {
return b
}
}执行结果如下：
图片
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读