廊坊论坛网站建设,网页期末大作业,国内十大4a广告公司,asp网站设置1、题目描述 给定一个字符串str#xff0c;只由 ‘X’ 和 ‘.’ 两种字符构成。‘X’ 表示墙#xff0c;不能放灯#xff0c;点亮不点亮都可#xff1b;’.’ 表示居民点#xff0c;可以放灯#xff0c;需要点亮。如果灯放在i位置#xff0c;可以让 i-1#xff0c;i 和…1、题目描述 给定一个字符串str只由 ‘X’ 和 ‘.’ 两种字符构成。‘X’ 表示墙不能放灯点亮不点亮都可’.’ 表示居民点可以放灯需要点亮。如果灯放在i位置可以让 i-1i 和 i1 三个位置被点亮。返回如果点亮str中所有需要点亮的位置至少需要几盏灯。
2、解题思路 这题我们可以用谈心思想 分情况来去讨论 1i 位置是 X’不管来到 i 1位置 2i 位置是 ‘.’ i 1是 X’i 位置需要放灯来到 i 2位置 3i 位置是 ‘.’ i 1是 ‘.’i 2是 ‘.’i 1 位置需要放灯来到 i 3位置此步即是贪心 4i 位置是 ‘.’ 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;}
