2021-03-18：給定一個(gè)字符串str，只由‘X’和‘.’兩種字符構(gòu)成活尊×バ＃‘X’表示墻，不能放燈蛹锰，也不需要點(diǎn)亮深胳，‘.’表示居民點(diǎn)，可以放燈铜犬，需要點(diǎn)亮舞终。如果燈放在i位置，可以讓i-1癣猾，i和i+1三個(gè)位置被點(diǎn)亮敛劝。返回如果點(diǎn)亮str中所有需要點(diǎn)亮的位置，至少需要幾盞燈纷宇。
福大大 答案2021-03-18：
1.對(duì)連續(xù)的點(diǎn)計(jì)數(shù)cnt夸盟，然后累加(cnt+2)/3。
2.貪心法像捶。
代碼用golang編寫(xiě)上陕，代碼如下：
package main
import "fmt"
func main() {
str := ".X..XX......."
ret := minLight1(str)
fmt.Println("1.對(duì)連續(xù)的點(diǎn)計(jì)數(shù)：", 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
}
執(zhí)行結(jié)果如下：
在這里插入圖片描述
