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