牛客网算法教程-中级篇-第一章_牛客网算法题

学习目标：

牛客网中级算法题 第一章

---

学习内容：

1.旋转词-模拟
2.旋转矩阵-模拟
3.数轴覆盖-贪心
4.1 完整字符串1（括号字符串的有效性）-栈
4.2 完整字符串2（缺失的括号）-栈
4.3 完整字符串3（最长合法括号子串）-栈
5.打包机器人-贪心
6.1容器装水-贪心
6.2地形盛水-贪心
7.牛牛找工作-有序表
8.安置路灯-贪心

---

学习时间：

2022.3.1-2022.3.6

学习产出：

1.旋转词-模拟

牛客网题目连接
如果一个字符串为str，把字符串的前面任意部分挪到后面形成的字符串叫str的旋转词。比如str=“12345”，str的旋转串有“12345”、“45123”等等。给定两个字符串，判断是否为旋转词。



解析：

1.备注时间复杂度和空间复杂度为O（N），这就表示，我们不能用暴力法去求解了。
2.我们通过仔细阅读题目，不难发现，如果旋转词的长度和原来串的长度不一致，那么肯定是NO
3.我们使用的方法是，扩大串。将str= str + str

4.所以我们的算法的难度来到了KMP，这是一个经典的判断字串的算法

using System;

namespace test{
    class test{
        static void Main(string[] args){
            string lengthIn=Console.ReadLine();
            string[] lengthSplit=lengthIn.Split(' ');
            int length1=Convert.ToInt32(lengthSplit[0]);
            int length2=Convert.ToInt32(lengthSplit[1]);
				
            if(length1!=length2){
                Console.WriteLine("NO");
                return;
            }
                
            
            string l1=Console.ReadLine();
            string l2=Console.ReadLine();  //第二个字符串
            
            //让字符串扩大两倍
            string big=l1+l1;
            
            
            for(int i=0;i<big.Length;i++){
                if(big[i]==l2[0]){
                    if(IsChild(i,big,l2)){
                        Console.WriteLine("YES");
                        return;
                    }
                        
                }
            }
            Console.WriteLine("NO");
            
        }
        
        //KMP
        static bool IsChild(int begin,string father,string child){
            int childindex=0;
            for(int i=begin;i<father.Length;i++){
                if(father[i]!=child[childindex]){
                    return false;
                }
                childindex++;
                if(childindex>=child.Length)return true;
            }
            return true;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

总结：这里我们采用基地址的方法，以每个基地址作为处理对象，通过将每个基地址的情况进行计算，得到最优的答案。
局部->最优

2.旋转矩阵-模拟

牛客网链接
有一个NxN整数矩阵，请编写一个算法，将矩阵顺时针旋转90度。

给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵。

解析：

1.其实我们可以创新一个新的矩阵，然后将旧矩阵旋转之后，赋值给新矩阵，只需要找到对应点旋转后的关系即可。
2.但是，进阶要求是要我们去实现空间复杂度为O（1），意思就是不创建新的矩阵，就在原来的矩阵里面进行旋转
3.我们采取剥洋葱的方法，一层一层的去实现旋转。首先是最外面一层，我们的发现他们的规律，红色的组一，就是四个顶点，他们旋转的位置很容易发现规律。我们只需要用一个去覆盖另外一个即可。然后紧跟着的绿色组二，和组一位置的关系很紧密，看下面写的for循环就可以理解了。
4.for循环的一次循环，代表完成一组。比如i=0，执行完后，组1完成旋转。比如i=1，执行完成后，组2完成选择。所以，一个for循环，就可以解决一圈的数据
5.我们只需要让abcd的值，不断往里面缩。下一个圈，就是a+1，b+1，c-1，d-1
6.直到a>c了，就是都完成了

using System;
class Solution
{   
    public int[][] rotateMatrix(int[][] mat, int n)
    {
        int a=0;
        int b=0;
        int c=n-1;
        int d=n-1;
        while(a<c){
            RotateOne(mat,a++,b++,c--,d--);
        }
        PrintMat(mat,n);
        return mat;
    }
    
    public static void RotateOne(int[][] mat,int a,int b,int c,int d){
        for(int i=0;i<d-b;i++){
            int temp=mat[a][b+i];
            mat[a][b+i]=mat[c-i][b];
            mat[c-i][b]=mat[c][d-i];
            mat[c][d-i]=mat[a+i][d];
            mat[a+i][d]=temp;
        }
    }
    
    
    public static void PrintMat(int[][] mat,int n){
        Console.Write('[');
        for(int i=0;i<n;i++){
            Console.Write('[');
            for(int j=0;j<n;j++){
                Console.Write(mat[i][j]);
                Console.Write(',');
            }
            Console.Write(']');
        }
        Console.Write(']');
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

总结：
这道题我们应该舍弃局部，而是从整体来进行处理。以整体去推局部，如果纠结于某个局部的值怎么样去转换， 那会很难！
如果我们分析整体，发现客观规律，那我们就可以轻松应对。
将局部代入整体

3.数轴覆盖-贪心

牛客网链接


分析：

1.这里使用的是3方法，滑动窗口法。以Left作为窗口左边，Right作为窗口右边。Right试着往右边无限扩大窗口，直到无法扩大，即让Left往前移动一格。每一次右边无法扩大的时候，即是Left位置窗口的最大值。此时应该刷新Max。

using System;
namespace test{
    class test{
        static void Main(){
            string[] putin=Console.ReadLine().Split(' ');
            int pointCount=Convert.ToInt32(putin[0]);
            int Length=Convert.ToInt32(putin[1]);
            
            string[] PointArrayIn=Console.ReadLine().Split(' ');
            int[] PointArray=new int[PointArrayIn.Length];
            for(int i=0;i<PointArrayIn.Length;i++){
                PointArray[i]=Convert.ToInt32(PointArrayIn[i]);
            }

            int Left=0;
            int Right=0;
            int Max=0;
            
            //滑动窗口，开始滑动，窗口左边不越界
            while(Left<pointCount){
                //窗口右边无限右扩，直到长度大于了绳子长度
                while(Right<pointCount && PointArray[Right]-PointArray[Left]<Length){
                    Right++;
                }
                //右边已经扩到顶了，所以让更新Max，然后左边往右移一格
                Max=GetMax(Max,Right-Left);
                Left++;
            }
            Console.WriteLine(Max);
            
        }
        
        static int GetMax(int a,int b){
            if(a>b){
                return a;
            }else{
                return b;
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

总结：
这道题有三种解题方法，分别是基地址法o(N2)，基地址加二分查找O（NlogN），滑动窗口O（N）

4.1 完整字符串1（括号字符串的有效性）-栈

牛客网链接

分析：我们如何判断括号是否匹配？

1.首先，我们应该从括号的数量下手。我们定义一个变量，Count。如果此时字符为 ‘(’ 我们应该让Count++。如果此时字符为 ‘)’ ，我们应该让Count–
2.那怎么判断呢？第一：任何时候，只要Count<0，就代表无法匹配了。为什么？因为Count<0就代表当前位置的 ‘)’ 比 '('要多，而多出来的 ')'此时已经无法进行匹配了。
例如(()))( 第三个 ‘)’ 是无法找到一个 ‘(’ 去和它匹配的
3.第二：如果结束的时候Count！=0，此时就说明，Count>0，即 '('比 ‘)’ 要多，自然不匹配。

using System;
namespace test{
    class test{
        static void Main(){
            string str=Console.ReadLine();
            int Count=0;
            for(int i=0;i<str.Length;i++){
                if(str[i]=='(')Count++;
                if(str[i]==')')Count--;
                if(Count<0)
                {
                    break;
                }
            }
            if(Count==0)Console.WriteLine("YES");
            else Console.WriteLine("NO");
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

总结：
我们应该通过对用例的分析来发现规律，匹配即左括号和右括号数目一样，并且右括号不能单独出现

4.2 完整字符串2（缺失的括号）-栈

牛客网链接
解析：

1.我们这里和4.1有区别的点就是在于，我们字符串本身就是不匹配的，需要让我们找出需要添加的括号数量，那么这里就有几种情况。一：需要添加左括号 二：需要添加右括号 三：两者都需要添加
2.我们定义一个变量，Count。如果此时字符为 ‘(’ 我们应该让Count++。如果此时字符为 ‘)’ ，我们应该让Count–
2.我们如何来确定是否需要添加左括号？我们定义一个变量为Need，如果Count==-1的时候，就是出现了 ‘)’ ，需要 ‘(’ 来对齐。那么这个时候，我们让Need++，相当于补充了一个 ‘(’ ，那么此时Count=0
3.最后，输出Need+Count，即代表，需要的左括号数目加上需要的右括号数目，为总的需要的数目。

using System;
namespace test{
    class test{
        static void Main(){
            string str=Console.ReadLine();
            int Count=0;
            int Need=0;
            for(int i=0;i<str.Length;i++){
                if(str[i]=='(')Count++;
                if(str[i]==')'){
                    Count--;
                    if(Count==-1){
                    Need++;
                    Count=0; 
                    }
                } 
            }
            
            Console.WriteLine(Need+Count );


        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

4.3 完整字符串3（最长合法括号子串）-栈

牛客网链接

分析：

1.对于字串问题，我们采用基地址的核心思想，以基地址去判断，以局部求最优
2.dp指的是当前位置的最长字串长度，对于每个基地址的dp值，我们应该考虑之前的相邻的dp值。

using System;
namespace test{
    class test{
        static void Main(){
            string str=Console.ReadLine();
            
            //用于往前找'('的指针
            int pre=0;
            //记录索引位置最长的字串
            int[] dp=new int[str.Length];
            //最长
            int max=0;
            
            //从前往后遍历每一个点
            for(int i=1;i<str.Length;i++){
                if(str[i]=='(')continue;
                //只有遇到了')'我们才进行判断
                //前面的'('的指针的位置，应该是根据i-1位置的dp值
                //如果i-1位置不存在dp值，即i-1位置就是pre指向的位置
                //如果i-1位置存在dp值，即i-1位置也是')',那么pre指向的位置一定在i-dp[i-1]-1位置
                pre=i-dp[i-1]-1;
                //没有越界，并且pre指向的位置是'('，才能构成字串
                if(pre>=0&&str[pre]=='('){
                    //如果构成字串了，那么i位置的dp值应该更新
                    dp[i]=dp[i-1]+2+(pre>0?dp[pre-1]:0);
                }
                //更新最大值
                max=max>dp[i]?max:dp[i];
            }
            Console.WriteLine(max);
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

5.打包机器人-贪心

牛客网连接

解析：
1.我们对单独某个i进行分析，对其左边和右边进行分析，就可以得到以下结论

2.为什么？为什么要选出最大值作为最佳轮数？因为我们这里是求解出每个位置需要的轮数。当我们解决了最痛点的时候，自然其他点也会被解决

6.1容器装水-贪心

牛客网链接

分析：

1.容器装水问题，有三种解决方式：1.求每个波谷，计算复杂 2.根据i求每个格子的水，然后累加起来。这里只需要求i左边最大高度，和i右边最大高度，然后两个最大高度与i的高度进行比较，就可以求出i的水量了 3.双指针法
2.双指针法就是利用左指针在左边，右指针在右边，然后一个Lmax表示左边最大的高度，Rmax表示右边最大的高度。我们每次只需要进行判断Lmax和Rmax谁大谁小，我们就去结算哪一边指针指向格子的水量。

using System;
namespace test{
    class test{
        static void Main(){
            string lengthin=Console.ReadLine();
            int length=Convert.ToInt32(lengthin);
            string[] arrayin=Console.ReadLine().Split(' ');
            
            //长度小于3，无法装水
            if(arrayin.Length<3){
                Console.Write(0);
                return;
            }
            //初始化我们的数组
            int[] Array=new int[arrayin.Length];
            for(int i=0;i<arrayin.Length;i++){
                Array[i]=Convert.ToInt32(arrayin[i]);
            }
            
            
            
            int Lmax=Array[0];
            int Rmax=Array[Array.Length-1];
            int Lindex=1;
            int Rindex=Array.Length-2;
            
            long Water=0;
            //我们左边指针不能大于右边指针
            while(Lindex<=Rindex){
                //如果左边比较小，则结算左边，同时要更新左边最大值
                if(Lmax<=Rmax){
                    Lmax=Math.Max(Lmax, Array[Lindex]);
                    Water+=Math.Max(0,Lmax-Array[Lindex]);
                    Lindex++;
                //如果右边比较小，则结算右边，同时要更新右边最大值
                }else{
                    Rmax=Math.Max(Rmax, Array[Rindex]);
                    Water+=Math.Max(0,Rmax-Array[Rindex]);
                    Rindex--;
                }
            }
            
            Console.WriteLine(Water);
            
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

6.2地形盛水-贪心

牛客网链接

分析：
1.我们构造一个小根堆，都先将旁边一圈全部放入，用红色下划线表示
2.我们弹出最小的值，是3，然后我们更新max为3，即，我们盛水最大容量为3。然后我们试着将3上下左右四个点都放入，在放入时，产生水。比如3旁边的2，产生一格水。
3.然后弹出最小值，是2，无法更新max，我们将2旁边的3和1全部塞入，只有1产生水。产生两格水。
4.然后弹出最小值，是1，无法更新max，我们将1旁边的9和4塞入，发现无法产生水。
5.弹出最小值3，弹出最小值4，更新max为4
6.弹出最小值，右边的5，更新max为5，然后将5旁边的2放入。此时产生3格水。
7.弹出最小值，是2，无法更新max，然后将2旁边的3和0放入，产生2+5格水。
8.弹出0，弹出3，弹出5，都无法产生水，直到全部弹出，处理完毕！

using System;
using System.Collections.Generic;
namespace test{
    class test{
        
        
        public struct Node{
            public int Value;
            public int Row;
            public int Line;
        }
        static void Main(){
            
            string[] linein=Console.ReadLine().Split(' ');
            int R=Convert.ToInt32(linein[0]) ;
            int L=Convert.ToInt32(linein[1]) ;
            
            int[,] Map=new int[R,L];  //格子二维数组
            bool[,] IsIn=new bool[R,L];  //标记是否进入的二维数组
            for(int i=0;i<R;i++){
                for(int j=0;j<L;j++){
                    IsIn[i,j]=false;
                }
            }
            
            //初始化格子
            for(int i=0;i<R;i++){
                string[] line=Console.ReadLine().Split(' ');
                for(int j=0;j<L;j++){
                    Map[i,j]=Convert.ToInt32(line[j]);
                }
            }
            
            
            List<Node> Sorted=new List<Node>(); //小根堆
            
            //四个For循环完成将边框全部的都放入
            for(int i=0;i<L;i++){
                //第一行
                Sorted=InsertByMin(Sorted,Map[0,i],0,i);
                IsIn[0,i]=true;
                //最后一行
                Sorted=InsertByMin(Sorted,Map[R-1,i],R-1,i);
                IsIn[R-1,i]=true;
            }
            
            for(int i=0;i<R;i++){
                //第一列
                Sorted=InsertByMin(Sorted,Map[i,0],i,0);
                IsIn[i,0]=true;
                //最后一列
                Sorted=InsertByMin(Sorted,Map[i,L-1],i,L-1);
                IsIn[i,L-1]=true;
            }
            
            int Water=0;
            int Max=0;
            //然后开始弹出 判断
            while(Sorted.Count!=0){
                //取出最小的格子
                Node node =Sorted[0];
                Sorted.RemoveAt(0);
                Max=Math.Max(Max,node.Value);
                
                int nodeR=node.Row;
                int nodeL=node.Line;
                
                //遍历弹出来格子的边上四个，上下左右， 因为上下左右会围成一个圈，可以装水
                //上 存在上面的格子并且没有进入过
                if(nodeR>0&&IsIn[nodeR-1,nodeL]==false){
                    //将格子创建为Node，然后放入堆
                    Node nodeIn=CreateNode(Map[nodeR-1,nodeL],nodeR-1,nodeL);
                    IsIn[nodeR-1,nodeL]=true;
                    Water+=Math.Max(0,Max-nodeIn.Value);
                    Sorted=InsertByMin(Sorted,Map[nodeR-1,nodeL],nodeR-1,nodeL);
                }
                //下 存在下面的格子并且没有进入过
                if(nodeR<R-1&&IsIn[nodeR+1,nodeL]==false){
                    //将格子创建为Node，然后放入堆
                    Node nodeIn=CreateNode(Map[nodeR+1,nodeL],nodeR+1,nodeL);
                    IsIn[nodeR+1,nodeL]=true;
                    Water+=Math.Max(0,Max-nodeIn.Value);
                    Sorted=InsertByMin(Sorted,Map[nodeR+1,nodeL],nodeR+1,nodeL);
                }
                //左 存在左边的格子并且没有进入过
                if(nodeL>0&&IsIn[nodeR,nodeL-1]==false){
                    //将格子创建为Node，然后放入堆
                    Node nodeIn=CreateNode(Map[nodeR,nodeL-1],nodeR,nodeL-1);
                    IsIn[nodeR,nodeL-1]=true;
                    Water+=Math.Max(0,Max-nodeIn.Value);
                    Sorted=InsertByMin(Sorted,Map[nodeR,nodeL-1],nodeR,nodeL-1);
                }
                //右 存在右边的格子并且没有进入过
                if(nodeL<L-1&&IsIn[nodeR,nodeL+1]==false){
                    //将格子创建为Node，然后放入堆
                    Node nodeIn=CreateNode(Map[nodeR,nodeL+1],nodeR,nodeL+1);
                    IsIn[nodeR,nodeL+1]=true;
                    Water+=Math.Max(0,Max-nodeIn.Value);
                    Sorted=InsertByMin(Sorted,Map[nodeR,nodeL+1],nodeR,nodeL+1);
                }
            }
            Console.WriteLine(Water);
            
        }
        
        //构造小根堆
        public static List<Node> InsertByMin(List<Node> Sorted,int n,int R,int L){
            Node node=CreateNode(n,R,L);

            if(Sorted.Count==0){
                Sorted.Add(node);
                return Sorted;
            }
                
            for(int i=0;i<Sorted.Count;i++){
                if(Sorted[i].Value>node.Value){
                    Sorted.Insert(i, node);
                    return Sorted;
                }else if(i==Sorted.Count-1){
                    Sorted.Add(node);
                    return Sorted;
                }
            }
            return Sorted;
        }
        
        //创建新节点
        public static Node CreateNode(int n,int R,int L){
            Node node=new Node();
            node.Value=n;
            node.Row=R;
            node.Line=L;
            return node;
        }
        
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137

7.牛牛找工作-贪心

牛客网链接

分析：
使用有序表就能在规定时间内完成

TreeMap<Integer, Integer> map = new TreeMap<>();
1

但是在C#中没有JAVA里面的TreeMap，所以实现起来比较繁琐，这里我是将List进行修改，达到同样的效果。但是，超时了！

1.首先我们要清楚的知道，同一岗位要求，只需要留下薪水最高的就行了。
2.其次，如果岗位要求增加，薪水没有增加，则不需要考虑该岗位
3.将其按岗位要求排好序，然后看员工满足的岗位要求，即是最大报酬！

using System;
using System.Collections;
using System.Collections.Generic;
namespace test
{
    class test
    {
        public struct Job
        {
            public int Di;
            public int Pi;
        }
        static void Main()
        {
            //工作的集合
            List<Job> JobList = new List<Job>();
                
            string[] putin = Console.ReadLine().Split(' ');
            int JobCount = Convert.ToInt32(putin[0]);
            int ManCount = Convert.ToInt32(putin[1]);
            
            //将工作全部插入集合
            for (int i = 0; i < JobCount; i++)
            {
                string[] put = Console.ReadLine().Split(' ');
                Job job = new Job { Di = Convert.ToInt32(put[0]), Pi = Convert.ToInt32(put[1]) };
                JobList = InsertByMin(JobList, job);
            }
            
            //将工作能力大反而报酬小的工作去掉
            JobList = SortList(JobList);
            
            //for循环尝试每个工作
            string[] lastin = Console.ReadLine().Split(' ');
            for (int i = 0; i < ManCount; i++)
            {
                int temp = Convert.ToInt32(lastin[i]);
                int Big = 0;
                for (int j = JobList.Count-1; j >=0; j--)
                {
                    if (temp >= JobList[j].Di)
                    {
                        Big =JobList[j].Pi;
                        break;
                    }
                }
                Console.WriteLine(Big);
            }

        }
        //构造小根堆
        public static List<Job> InsertByMin(List<Job> Sorted, Job job)
        {
            if (Sorted.Count == 0)
            {
                Sorted.Add(job);
                return Sorted;
            }
            
            for (int i = 0; i < Sorted.Count; i++)
            {
                //如果要求相同，则换报酬高的
                if (Sorted[i].Di == job.Di)
                {
                    Job newjob = Sorted[i];
                    newjob.Pi = Math.Max(Sorted[i].Pi, job.Pi);
                    Sorted.RemoveAt(i);
                    Sorted.Insert(i, newjob);
                    return Sorted;
                }//按从小到大的顺序排序
                else if (Sorted[i].Di > job.Di)
                {

                    Sorted.Insert(i, job);
                    return Sorted;

                }
                else if (i == Sorted.Count - 1)
                {
                    Sorted.Add(job);
                    return Sorted;
                }
            }
            return Sorted;
        }

        //构造小根堆
        public static List<Job> SortList(List<Job> Sorted)
        {
            for (int i = 0; i< Sorted.Count; i++)
            {
                if(i+1== Sorted.Count) return Sorted;
                
                //如果能力大反而报酬少，则删除
                if (Sorted[i].Di < Sorted[i +1].Di&& Sorted[i].Pi > Sorted[i + 1].Pi)
                {
                    Sorted.RemoveAt(i+1);
                    i--;
                }
            }
            return Sorted;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

8.安置路灯-贪心

牛客网链接


分析：

1.路灯只能照亮自己和旁边的两个格子，所以，我们可以在草稿纸上将各种情况绘制出来。
2.如果i是’.’，i+1是’X’，则我们应该意识到，只能在i位置放一盏灯，然后i+2，跳过’X’
3.如果i是’.’，i+1是’.’，则我们应该意识到，放一盏灯在i+1然后，i+3
4.如果i是’X’，则i++，不放灯

using System;
namespace test{
    class test{
        static void Main(){
            int count=Convert.ToInt32(Console.ReadLine());
            string array=Console.ReadLine();
            
            int index=0;
            int light=0;
            while(index<array.Length){
                
                if(array[index]=='.'){
                    light++;
                    if(index+1==array.Length)break;
                    
                    if(array[index+1]=='X'){
                        index+=2;
                    }else{
                        index+=3;
                    }
                }else{
                    index++;
                }
            }
            Console.WriteLine(light);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28