文章目录

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

学习目标：

牛客网中级算法题 第一章

学习内容：

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; }    }}

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

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(']');    }}

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

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;     } }    }}

总结：
这道题有三种解题方法，分别是基地址法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"); }    }}

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

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 ); }    }}

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); }    }}

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);      }    }}

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; }     }}

7.牛牛找工作-贪心

牛客网链接

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

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

但是在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; }    }}

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); }    }}

组词诗歌网