To light up all the positions in the string that need to be lit, at least a few lights are needed

1、 subject

Given a string str, Only by X and . Two characters make up .

X Represents a wall , No lights , It doesn't need to be lit .

. Means residential area , You can put a light , It needs to be lit .

If the light is on i Location , It can make i-1,i and i+1 Three positions are lit .

Return if lit str All positions that need to be lit in the , At least a few lights .

2、 Ideas

This problem can be solved by dynamic programming , Greedy algorithm can also be used to solve . Today's headline is an upgraded version of this topic .

This paper uses greedy algorithm to solve .

Greedy strategy —— From left to right, consider whether to put lights in each position ：
  If the position i yes X, You don't have to consider , Go directly to i+1 The position depends on whether the lamp needs to be placed ;
  If the position i yes ., Discussion by situation ：
   （1） If i+1 Location is X, be i The position must be lighted , Number of lamps +1, Then jump to i+2 Consider the location ;
   （2） If i+1 Location is ., Continue to discuss i+2 Location ：
    ① If i+2 Location is X, Then the lamp can be placed i or i+1 position , In short, the number of lights +1, Then jump to i+3 Consider the location ;
    ② If i+2 Location is ., Directly in i+1 Put the light on the position , Number of lamps +1, Then jump to i+3 Consider the location .
  That is , In this case , No matter what i+2 What is the location , The number of lights should be +1, Then jump to i+3 Consider the location .

The greed of this topic is reflected in , If three consecutive positions are ., Put the lamp in the middle .

3、 Code

C++ edition

/************************************************************************* > File Name: 047. At least several lights are required to light up the position in the lighting string .cpp > Author: Maureen > Mail: [email protected] > Created Time:  Japan  7/24 00:10:17 2022 ************************************************************************/

#include <iostream>
#include <unordered_set>
#include <ctime>
using namespace std;

// Violence solution 
int process(string str, int index, unordered_set<int> &lights) {
    
    if (index == str.length()) {
    
        for (int i = 0; i < str.length(); i++) {
    
            if (str[i] != 'X') {
    
                if (!lights.count(i - 1) && !lights.count(i) && !lights.count(i + 1)) {
    
                    return INT_MAX;
                }
            }
        }

        return lights.size();
    } else {
    
        int no = process(str, index + 1, lights);
        int yes = INT_MAX;

        if (str[index] == '.') {
    
            lights.insert(index);
            yes = process(str, index + 1, lights);
            lights.erase(index);
        }

        return min(no, yes);
    }
}


int minLights1(string road) {
    
    if (road.length() == 0) 
        return 0;

    unordered_set<int> lights;
    return process(road, 0, lights);
}

// Greedy solution ： Time complexity O(N)
int minLights2(string str) {
    
    int i = 0;
    int lights = 0;

    while (i < str.length()) {
    
        if (str[i] == 'X') {
    
            i++;
        } else {
    
            lights++;
            if (i + 1 == str.length()) {
    
                break;
            } else {
    
                if (str[i + 1] == 'X') {
    
                    i = i + 2;
                } else {
    
                    i = i + 3;
                }
            }
        }
    }

    return lights;
}


//for test 
string randomString(int len) {
    
    char res[(rand() % len) + 1];

    for (int i = 0; i < strlen(res); i++) {
    
        res[i] = (rand() % 100 / (double)101) < 0.5 ? 'X' : '.';
    }

    return res;
}


int main() {
    
    srand(time(0));

    int len = 20;
    int testTimes = 100000;

    for (int i = 0; i < testTimes + 1; i++) {
    
        string test = randomString(len);
        int ans1 = minLights1(test);
        int ans2 = minLights2(test);
        if (ans1 != ans2) {
    
            cout << "Oops!" << endl;
            return 0;
        }

        if (i && i % 1000 == 0) cout << i << " cases passed!" << endl; 
    }

    cout << "Finish!" << endl;
    return 0;
}

Java edition

import java.util.HashSet;

public class Light {
    

	public static int minLight1(String road) {
    
		if (road == null || road.length() == 0) {
    
			return 0;
		}
		return process(road.toCharArray(), 0, new HashSet<>());
	}

	// str[index....] Location , Free to choose whether to put the light or not 
	// str[0..index-1] Where is the location ？ The decision has been made , Those places with lights , There is lights in 
	//  It is required to choose a light that can illuminate all . The plan , And in these effective schemes , It takes at least a few lights to return 
	public static int process(char[] str, int index, HashSet<Integer> lights) {
    
		if (index == str.length) {
     //  At the end 
			for (int i = 0; i < str.length; i++) {
    
				if (str[i] != 'X') {
     //  If the current position is a point 
					if (!lights.contains(i - 1) && !lights.contains(i) && !lights.contains(i + 1)) {
    
						return Integer.MAX_VALUE;
					}
				}
			}
			return lights.size();
		} else {
     // str Isn't over 
			// i X .
			int no = process(str, index + 1, lights);
			int yes = Integer.MAX_VALUE;
			if (str[index] == '.') {
    
				lights.add(index);
				yes = process(str, index + 1, lights);
				lights.remove(index);
			}
			return Math.min(no, yes);
		}
	}

    // Go through it in sequence ,O(n)
	public static int minLight2(String road) {
    
		char[] str = road.toCharArray();
		int i = 0;
		int light = 0;// Number of lamps 
		while (i < str.length) {
    
			if (str[i] == 'X') {
    
				i++;
			} else {
    //i Location is .  The situation of , No matter what i+1 What is it? , The city will need lights , So the number of lights will increase 
				light++;
				if (i + 1 == str.length) {
    
					break;
				} else {
     //  Yes i Location  i+ 1  This position is divided into X  and  .  The situation of 
					if (str[i + 1] == 'X') {
    
						i = i + 2;
					} else {
    
						i = i + 3;
					}
				}
			}
		}
		return light;
	}

	// for test
	public static String randomString(int len) {
    
		char[] res = new char[(int) (Math.random() * len) + 1];
		for (int i = 0; i < res.length; i++) {
    
			res[i] = Math.random() < 0.5 ? 'X' : '.';
		}
		return String.valueOf(res);
	}

	public static void main(String[] args) {
    
		int len = 20;
		int testTime = 100000;
		for (int i = 0; i < testTime; i++) {
    
			String test = randomString(len);
			int ans1 = minLight1(test);
			int ans2 = minLight2(test);
			if (ans1 != ans2) {
    
				System.out.println("oops!");
			}
		}
		System.out.println("finish!");
	}
}