题目描述
样例
输入样例1:
**********
o****o****
输出样例1:
5
输入样例2:
*o**o***o***
*o***o**o***
输出样例2:
1
算法1
(递归) $O(n)$
我之前也是递归写得磕巴,然后在油管上看了一位美女程序员推荐的The Little Schemer
就知道怎么分析递归的问题了,强烈推荐。
思路:
判断src
数组和dst
当前索引idx
上的元素是否相同,不相同的话就将src
的idx
和idx+1
上的元素交换,结果值加一。
递归出口条件:当前的索引到了元素长度-1,代表数组遍历完了。
如何逼近出口条件,将idx+1
即可
时间复杂度
因为只需要遍历一遍数组
Golang 代码
package main
import (
"fmt"
"bufio"
"strings"
"os"
)
var (
src []string
dst []string
)
func turn(src, dst []string, idx int) int {
var res int
sLen := len(src)
// 如果当前索引上的元素不相同,需要交换当前索引和下一个索引的元素
// 同时结果数量需要加1
if src[idx] != dst[idx]{
res += 1
if src[idx] == "o"{
src[idx] = "*"
}else{
src[idx] = "o"
}
if src[idx+1] == "o"{
src[idx+1] = "*"
}else{
src[idx+1] = "o"
}
}
// 出口条件
if idx == sLen -1{
return res
}
// 逼近出口条件
return res + turn(src, dst, idx+1)
}
func main() {
scanner := bufio.NewScanner(os.Stdin)
scanner.Scan()
text := scanner.Text()
for _, s := range strings.Split(text, ""){
src = append(src, s)
}
scanner.Scan()
text = scanner.Text()
for _, s := range strings.Split(text, ""){
dst = append(dst, s)
}
// 上面都是读取输入
fmt.Println(turn(src, dst, 0))
}
题外话
acwing的编辑器在Linux平台上,编辑太难用了,期待优化。当前环境manjaro