Given a string STR, it consists of only ‘X’ and ‘. ‘characters. ‘X’ means wall, no lights, no need to be lit, ‘. ‘means residential area, can be lit, need to be lit. If the light is on -2021-03-18

2021-03-18: Given a string STR, it consists of only ‘X’ and ‘. ‘characters. ‘X’ means wall, no lights, no need to be lit, ‘. ‘means residential area, can be lit, need to be lit. If the lamp is placed at I, it can be lit at i-1, I and I +1. Returns at least a few lights needed to light all the positions in STR that need to be lit.

Answer 2021-03-18:

1. Count CNT for consecutive points and add (CNT +2)/3. 2. Greedy method.

The code is written in Golang, and the code is as follows:

package main

import "fmt"

func main(a) {
    str := ".X.. XX......."
    ret := minLight1(str)
    fmt.Println("1. Count consecutive points:", ret)
    ret = minLight2(str)
    fmt.Println(2. Greedy Method:, 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
}
Copy the code

The result is as follows:

comments