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

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

}

执行结果如下：

评论

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