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
}

执行结果如下:

评论

本文来自:简书

感谢作者:福大大架构师每日一题

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

• 编辑
• 预览