贪心算法--给定一个只包含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 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); int ans3 = minLight3(test); if (ans1 != ans2 || ans2 != ans3) { System.out.println("oops!"); } } System.out.println("finish!"); } }