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

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
}

执行结果如下：

在这里插入图片描述

评论

有疑问加站长微信联系（非本文作者）