贪心算法-点灯问题

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

2、解题思路
这题我们可以用谈心思想 分情况来去讨论：
（1）i 位置是 'X’，不管，来到 i + 1位置
（2）i 位置是 ‘.’ ，i + 1是 'X’，i 位置需要放灯，来到 i + 2位置
（3）i 位置是 ‘.’ ，i + 1是 ‘.’，i + 2是 ‘.’，i + 1 位置需要放灯，来到 i + 3位置（此步即是贪心）
（4）i 位置是 ‘.’ ，i + 1是 ‘.’，i + 2是 'X’，i 或 i + 1 位置需要放灯，来到 i + 3位置

代码实现：

	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 {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;}