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
}

执行结果如下:
在这里插入图片描述