安置路灯

算法思路

遍历路灯字符串，遇见“.”，就给计数器+1，然后往后挪三个位置。如果遇到“X”，就直接往后挪一个位置。

编程思路

if __name__ == '__main__':
    count = int(input())  # 测试用例的个数
    n = []
    lantern = []
    for i in range(count):
        n_tmp = int(input())  # 路灯个数
        n.append(n_tmp)
        lantern_tmp = input()  # 路灯分布字符串
        lantern.append(lantern_tmp)
    lantern_count = [0 for i in range(count)]  # 存储最终结果的数组
    for i in range(len(lantern)):  # 循环路灯数
        j = 0
        while (j < len(lantern[i])):  # 循环对应路灯排列字符串
            if lantern[i][j] == '.':
                j += 3
                lantern_count[i] += 1
            else:
                j += 1
    print(lantern_count[0])
    for i in range(len(lantern_count) - 1):
        print(lantern_count[i + 1])

#include <bits/stdc++.h>
using namespace std;
int main() {
    int m; cin >> m;
    while (m--) {
        int n; cin >> n; string s; cin >> s;
        int ans = 0;
        for (int i=0; i<s.length(); i++) {
            if (s[i] == '.') {
                i+=2;
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

本套8道题全部pass的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)
牛客网上的其他题目解答也在持续更新。

#include <iostream>
using namespace std;
int main()
{
    int t; cin >> t;
    for (int i = 0; i < t; i++) {
        int n; cin >> n;
        int j = 0, count = 0;
        while (j++ < n) {
            char ch; cin >> ch;
            if (ch == '.') {
                count++;
                if (j++ < n) cin >> ch;
                if (j++ < n) cin >> ch;
            }
        }
        cout << count << endl;
    }
    return 0;
}

t = int(input())
for i in range(t):
    n = int(input())
    s = input()
    ans = 0
    j = 0
    while j < n:
        if s[j] == '.':
            ans += 1
            j += 3
        else:
            j += 1
    print(ans)

#include <iostream>
#include <algorithm>
using namespace std;
char s[1005];
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        cin>>n;
        cin>>s;
        int ans=0;
        for(int i=0;i<n;++i)
            if(s[i]=='.')
            {
                int cnt=0;
                for(int j=i;j<n;++j)
                    if(s[j]=='X')
                        break;
                    else cnt++;
                int res=(cnt+2)/3;
                ans+=res;
                for(int j=i;j<i+res*3&&j<n;++j)
                    s[j]='X';
            }
        cout<<ans<<endl;

    }
}

	

import java.util.*;
//贪心算法求解：1.当遇到第一个'.'时，表示该位置需要被照亮，此时不安装路灯，在它的下一个位置安装路灯，即sum+1;
//因为该路灯位置的下一个位置已经被照亮了，因此下标+2
//遇到‘X’时跳过，因为不需要安装
public class Main{
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        for(int i = 0; i < t; i++){
            int n = sc.nextInt();
            String s = sc.next();
            int sum = 0;
            for(int j = 0; j < n; j++){
                if(s.charAt(j) == '.'){
                    sum++;
                    j = j + 2;
                }
            }
            System.out.println(sum);
        }
    }
}

#include<iostream>
#include<cstring>
using namespace std;
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        int n;
        bool flag = true;
        cin>>n;
        string str;
        cin>>str;
        int count = 0;  //方格的数量
        int lampcount = 0;  //路灯数量
        for(int i=0;i<n;i++)
        {
            if(flag==true && str[i]=='X')  //开头是X，就可以略过
                continue;
            if(flag==false && str[i]=='X')  //X不在开头，那就要把它当作要照亮的区域
            {
                count++;
            }
            if(str[i] == '.')  //在一开始的时候加上路灯，之后就不需要判断
            {
                count++;
                if(true == flag)
                lampcount++;
                flag = false;
            }
            if(3 == count)  //满3格清0
            {
                count = 0;
                flag = true;
            }           
        }
         cout<<lampcount<<endl;
    }
}

"""
一盏路灯照亮3个格子
当遇到'.'且cnt3为0，ans计数，点亮一盏路灯flag
当'X'且当前没有路灯是cnt3保持0，其他情况cnt3自增1
当超过3格，flag、cnt3重置
"""
import sys

if __name__ == "__main__":
    # sys.stdin = open('input.txt', 'r')
    t = int(input().strip())
    while t:
        n = int(input().strip())
        s = input().strip()
        ans, flag, cnt3 = 0, 0, 0
        for i in range(len(s)):
            if s[i] == '.':
                if cnt3 == 0:
                    flag = 1
                    ans += 1
                cnt3 += 1
            elif flag == 1:
                cnt3 += 1
            if cnt3 == 3:
                flag = 0
                cnt3 = 0
        print(ans)
        t -= 1

	

import java.util.Scanner;

/*
 * 有点类似智力题
 * */
public class LayLamp {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNext()) {
            int n = scanner.nextInt();
            while (n-- > 0) {
                int len = scanner.nextInt();
                String line = scanner.next();
                int count = 0;
//                在需要防止路灯位置的右边放置路灯
                for (int i = 0; i < len; i++) {
                    if (line.charAt(i) == 'X') {
                        continue;
                    }
                    count++;
                    i += 2;
                }
                System.out.println(count);
            }
        }
    }
}

	#include<iostream>



	#include<string>



	usingnamespacestd;



	intmain(){



	    intt;



	    while(cin>>t){



	        for(inti =0;i<t;i++){



	            intn;



	            string str;



	            cin>>n>>str;



	         



	            intnum=0;



	            for(inti = 0;i<str.size();){



	                if(str[i]=='.'){



	                    num++;



	                    i+=3;



	                }



	                else



	                    i++;



	            }



	            cout<<num<<endl;



	        }



	    }



	    system("pause");



	    return0;



	}

for i in range(int(input())):
    b,c,j,p = int(input()),input(),0,0
    while j < b:
        if c[j] == '.':
            p,j = p + 1,j + 2
        j += 1
    print(p)

# 一盏路灯可以照亮当前位置和相邻位置
# 首先，假设没有障碍物，则x个位置需要最少多少盏路灯⌈x/3⌉，即x除以三向上取整
# 现在中间夹杂着一些不需要照亮的位置，这些位置不是必须照亮，但是可以被照亮，也可以安置路灯
# 从左向右，贪心算法，第一盏灯最多照亮3个位置（不管需不需要被照亮），除非位置不够
# 前面的位置都被遍历过了，当前位置是'X'不需要照亮就跳过，寻找下一个'.'

n = int(input())
target = []
for i in range(n):
    length = int(input())
    s = input()
    j, result = 0, 0
    while j < length:
        if s[j] == '.':
            result += 1
            j += 3
        else:
            j += 1
    target.append(result)
for e in target:
    print(e)

import java.util.Scanner;
public class Main {
    //思路：小贪心，假如第一个遇到`.`反正都要花费一个灯来照亮，所以就把这个灯安装到下一个位置
    //然后来到第4个格子，同时也说明新来到的格子不能依靠前面的灯来把自己照亮
    public static int light(String road) {
        if(road == null || road.length() == 0) {
            return 0;
        }
        int n = road.length();
        int ans = 0;
        //for循环中的变量i:
        //若遇到'.'则向后移3位，
        //若遇到'X'则向后移1位
        for(int i = 0; i < n; i++) {
            if(road.charAt(i) == '.') {
                ans++;
                i += 2;
            }
        }

        return ans;
    }

    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        int n = Integer.valueOf(s.nextLine());
        for(int i = 0; i < n; i++) {
            s.nextLine();
            System.out.println(light(s.nextLine()));
        }
    }
}