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 }
执行结果如下: