贪心算法--给定一个只包含X和.字符串

给定一个字符串str, 只有 ‘X’和’.'两种字符构成。
'X’表示墙，不能放灯，也不需要点亮。
'.'表示居民点,可以放灯,需要点亮。
如果灯放在i位置,可以让 i-1，和i和i+1三个位置被点亮.
返回如果点亮str中所有需要点亮的位置,至少需要几盏灯。

import java.util.HashSet;public class Light {public static int minLight1(String road) {if (road == null || road.length() == 0) {return 0;}return process(road, 0, new HashSet<>());}public static int process(String road, int i,  HashSet<Integer> lights){if(i == road.length()){for (int j = 0; j < road.length(); j++) {if(road.charAt(j) != 'X'){if(!lights.contains(j-1) && !lights.contains(j) && !lights.contains(j+1)){return Integer.MAX_VALUE;}}}return lights.size();}else {int y = Integer.MAX_VALUE;//int n = Integer.MAX_VALUE;if(road.charAt(i) != 'X') {lights.add(i);y = process(road, i + 1, lights);lights.remove(i);}int n = process(road, i + 1, lights);return Math.min(y, n);}}public static int minLight2(String road) {if(road == null || road.length() == 0){return 0;}int light = 0;int i = 0;int len = road.length();while (i < len){if(road.charAt(i) == 'X'){i++;}else{light++;if(i+1 == len){break;}else if(road.charAt(i+1) == 'X'){i = i + 2;}else{i = i + 3;}}}return light;}public static int minLight3(String road) {char[] str = road.toCharArray();int cur = 0;int light = 0;for (char c : str) {if (c == 'X') {light += (cur + 2) / 3;cur = 0;} else {cur++;}}light += (cur + 2) / 3;return light;}// for testpublic 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);int ans3 = minLight3(test);if (ans1 != ans2 || ans2 != ans3) {System.out.println("oops!");}}System.out.println("finish!");}
}