点灯问题_贪心

本文主要是介绍点灯问题_贪心，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

问题描述：

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

way：遍历str，如果遇到的是X字符，不需要点亮直接走到下一个字符，如果遇到的是.字符，那么先让lights++表示先在该处点上一盏灯，然后判断i+1位置，如果i+1位置是X，那么在i位置点的灯照亮i位置自己就够了，让i=i+2, 而如果i+1位置是.，说明其实应该把灯放在i+1位置，这样i位置和i+2位置都可以被照亮，然后lights我们已经加过了，让i=i+3;

#include<iostream>
#include<string>
using namespace std;int minLights(string road)
{int i=0, n=road.size();int lights=0;while(i<n){if(road[i]=='X'){i++;}else{lights++;if(i+1 == n){break;}if(road[i+1] == 'X'){i=i+2;}else{i=i+3;}}}return lights;
}int main()
{system("pause");return 0;  
}

这篇关于点灯问题_贪心的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---