点亮字符串中所有需要点亮的位置，至少需要点几盏灯

1、题目

给定一个字符串str，只由 X 和 . 两种字符构成。

X 表示墙，不能放灯，也不需要点亮。

. 表示居民点，可以放灯，需要点亮。

如果灯放在 i 位置，可以让 i-1，i 和 i+1 三个位置被点亮。

返回如果点亮 str 中所有需要点亮的位置，至少需要几盏灯。

2、思路

本题可使用动态规划解决，也可使用贪心算法解决。今日头条原题是本题的升级版。

本文使用贪心算法求解。

贪心策略——从左往右依次考虑每个位置是否放灯：
 如果位置 i 是 X，则不用考虑，直接去 i+1 位置看是否需要放灯；
 如果位置 i 是 .，分情况讨论：
   （1）如果 i+1 位置是 X，则 i 位置必须放灯，灯的数量+1，然后跳到 i+2 位置进行考虑；
   （2）如果 i+1 位置是 .，继续讨论 i+2 位置：
    ① 如果 i+2 位置是 X，则灯可以放在 i 或 i+1 位置上，总之灯的数量+1，然后跳到 i+3 位置进行考虑；
    ② 如果 i+2 位置是 .，则直接在 i+1 位置上放灯，灯的数量+1，然后跳到 i+3 位置进行考虑。
 即是说，这种情况下，无论 i+2 位置是什么，灯的数量都要+1，然后跳到 i+3 位置进行考虑。

本题的贪心体现在，如果连续三个位置都是 .，则把灯放在中间位置。

3、代码

C++ 版

/************************************************************************* > File Name: 047.点亮字符串中需要点亮的位置至少需要几盏灯.cpp > Author: Maureen > Mail: [email protected] > Created Time: 日 7/24 00:10:17 2022 ************************************************************************/

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

//暴力解法
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);
}

//贪心解法：时间复杂度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 版

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....]位置，自由选择放灯还是不放灯
	// str[0..index-1]位置呢？已经做完决定了，那些放了灯的位置，存在lights里
	// 要求选出能照亮所有.的方案，并且在这些有效的方案中，返回最少需要几个灯
	public static int process(char[] str, int index, HashSet<Integer> lights) {
    
		if (index == str.length) {
     // 结束的时候
			for (int i = 0; i < str.length; i++) {
    
				if (str[i] != 'X') {
     // 当前位置是点的话
					if (!lights.contains(i - 1) && !lights.contains(i) && !lights.contains(i + 1)) {
    
						return Integer.MAX_VALUE;
					}
				}
			}
			return lights.size();
		} else {
     // str还没结束
			// 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);
		}
	}

    //顺序遍历一遍，O(n)
	public static int minLight2(String road) {
    
		char[] str = road.toCharArray();
		int i = 0;
		int light = 0;//灯的数量
		while (i < str.length) {
    
			if (str[i] == 'X') {
    
				i++;
			} else {
    //i位置是. 的情况，无论i+1是什么，都会需要放灯，所以灯的数量都会增加
				light++;
				if (i + 1 == str.length) {
    
					break;
				} else {
     // 有i位置 i+ 1 分为该位置为X 和 . 的情况
					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!");
	}
}