2021-03-18：给定一个字符串str，只由‘X’和‘.’两种字符构成。‘X’表示墙，不能放灯，

2021-03-18：给定一个字符串str，只由‘X’和‘.’两种字符构成。‘X’表示墙，不能放灯，也不需要点亮，‘.’表示居民点，可以放灯，需要点亮。如果灯放在i位置，可以让i-1，i和i+1三个位置被点亮。返回如果点亮str中所有需要点亮的位置，至少需要几盏灯。

福大大 答案2021-03-18：

1.对连续的点计数cnt，然后累加(cnt+2)/3。
2.贪心法。

代码用golang编写，代码如下：

package mainimport "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}

执行结果如下：

评论