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
}
           

執行結果如下：

評論