笔试刷题-网易2018-06-08

题目描述：

/**
小Q正在给一条长度为n的道路设计路灯安置方案。

为了让问题更简单,
小Q把道路视为n个方格,需要照亮的地方用'.'表示, 不需要照亮的障碍物格子用'X'表示。

小Q现在要在道路上设置一些路灯,
对于安置在pos位置的路灯, 这盏路灯可以照亮pos - 1, pos, pos + 1这三个位置。

小Q希望能安置尽量少的路灯照亮所有'.'区域, 希望你能帮他计算一下最少需要多少盏路灯。


输入描述:
输入的第一行包含一个正整数t(1 <= t <= 1000), 表示测试用例数
接下来每两行一个测试数据, 第一行一个正整数n(1 <= n <= 1000),表示道路的长度。
第二行一个字符串s表示道路的构造,只包含'.'和'X'。


输出描述:
对于每个测试用例, 输出一个正整数表示最少需要多少盏路灯。

输入例子1:
2
3
.X.
11
...XX....XX

输出例子1:
1
3

*/

思路如下：

/**
思路：
若i的左边没有灯可以照到i那么就在i新建一个灯

若i左边隔一个位置的刚好放了一个
若这个灯的左边不需要他照亮
那么这个灯可以向右移动一个位置

若i与其左边最近的灯相差超过1那么i要建一个灯，
参照上述贪心移动的过程其实就可以pos位置放灯可以照多少个位置不仅仅是1个位置也能类似
贪心原则：一次扫描，看是否让尽可能要照亮的地方被重复照亮即可

其实就是用two pointer记录靠近当前需要判断的点的两个等的位置
leftIdx1（已经确定的灯）<leftIdx2（可能还需要移动的等位置）
不断贪心更新leftIdx1 leftIdx2即可得到一个放最少灯的解决方案
*/

代码如下：

#include<stdio.h>
#include<iostream>

#define MAX_N 1005

using namespace std;

//最少放灯的一种方案
bool light[MAX_N];

int main()
{
    int T;
    scanf("%d", &T);
    getchar();//吃掉回车
    while(T--)
    {
        int N, numOfLights=0, lastLightPos=-1;
        scanf("%d", &N);
        getchar();//吃掉回车
        string path;
        cin>>path;
        if(path.size()!=N)
            return -1;
        for(int i=0; i<N; i++)
            light[i]=false;
        for(int i=0; i<N; i++)
        {
            if(path[i]!='.' && path[i]!='X')
                return -1;
            if(path[i]=='X')
                continue;
            else if(path[i]=='.')
            {
                if(i==0)
                {
                    //若i的左边没有灯可以照到i那么就在i新建一个灯
                    numOfLights++;
                    light[i]=true;
                    lastLightPos=i;
                }
                else if(lastLightPos+2==i && (lastLightPos==0 ||(lastLightPos>=1 && path[lastLightPos-1]=='X') || (lastLightPos>=2 && light[lastLightPos-2])))
                {
                    //若i左边隔一个位置的刚好放了一个灯
                    //若这个灯的左边不需要他照亮
                    //那么这个灯可以向右移动一个位置
                    light[lastLightPos]=false;
                    light[lastLightPos+1]=true;
                    lastLightPos=lastLightPos+1;
                }
                else if(i>lastLightPos+1)
                {
                    numOfLights++;
                    light[i]=true;
                    lastLightPos=i;
                }
            }
        }
        printf("%d\n", numOfLights);
    }
    return 0;
}