2021-03-18：给定一个字符串str，只由‘X’和‘.’两种字符构成。‘X’表示墙，不能放灯，也不需要点亮，‘.’表示居民点，可以放灯，需要点亮。如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮。返回如果点亮str中所有需要点亮的位置，至少需要几盏灯。
福大大 答案2021-03-18：
1.对连续的点计数cnt，然后累加(cnt+2)/3。
2.贪心法。
代码用golang编写，代码如下：
package main
import "fmt"
func main() {
str := ".X..XX......."
ret := minLight1(str)
fmt.Println("1.对连续的点计数：", ret)
ret = minLight2(str)
fmt.Println("2.贪心法：", ret)
}
func minLight1(road string) int {
roadLen := len(road)
i := 0
light := 0
cnt := 0
for i < roadLen {
if road[i] == 'X' {
light += (cnt + 2) / 3
cnt = 0
} else {
cnt++
}
i++
}
light += (cnt + 2) / 3
return light
}
func minLight2(road string) int {
roadLen := len(road)
i := 0
light := 0
for i < roadLen {
if road[i] == 'X' {
i++
} else {
light++
if i+1 == roadLen {
break
} else {
if road[i+1] == 'X' {
i = i + 2
} else {
i = i + 3
}
}
}
}
return light
}
执行结果如下：
在这里插入图片描述
