【算法】模仿

【ps】本篇有 5 道 leetcode OJ。 
  目录
一、算法简介
二、相关例图
1）替换所有的问号
 .1- 题目分析
.2- 代码编写
2）提莫攻击
 .1- 题目分析
.2- 代码编写
3）Z 字形变动
 .1- 题目分析
.2- 代码编写
4）表面数列
 .1- 题目分析
.2- 代码编写
5）数田鸡
 .1- 题目分析
.2- 代码编写

---

一、算法简介

        模仿算法是指，根据题目表述进行筛选提取关键要素，按需求书写代码办理实际题目，换句话说其实就是“依葫芦画瓢”，但很考察对数据布局、容器和一些特殊数学方法的掌握水平。
        模仿算法一般是一些很基础的题目，只要按题目要求来写代码就能解开题目。不过，模仿题也有相对困难的题目，而它们大部门的优化思绪都是找规律。

二、相关例图

1）替换所有的问号

1576. 替换所有的问号
   

   
 .1- 题目分析

        “？”在字符串中心，需要考虑“？”两侧的字符；“？”在字符串两端，就只需要考虑“？”一侧的字符。
   

           由此，对于“？”如何替换，就有了以后判断条件：

• “？”的左侧没有字符，则“？”的左侧无须判断与替换的字符是否相当。
  
• “？”的左侧有字符，则需判断与替换的字符字符是否相当。
  
• “？”的右侧没有字符，则“？”的右侧无须判断与替换的字符是否相当。
  
• “？”的右侧有字符，则需判断与替换的字符字符是否相当。
  

.2- 代码编写

1. class Solution {
2. public:
3.     string modifyString(string s) {
4.         int n=s.size();
5.         for(int i=0;i<n;i++)
6.         {   
7.             //遇到“？”就替换字符
8.             if(s[i]=='?')
9.             {
10.                 //遍历26个字符，找到合适的替换字符
11.                 for(char ch='a';ch<='z';ch++)
12.                 {
13.                     //需判断“？”的左侧和右侧
14.                     if((i==0||ch!=s[i-1])&&(i==n-1||ch!=s[i+1]))
15.                     {
16.                         s[i]=ch;
17.                         break;
18.                     }
19.                 }
20.             }
21.         }
22.         return s;
23.     }
24. };

复制代码

 
2）提莫攻击

495. 提莫攻击
   

   
 .1- 题目分析

        设 a、b、c 为 timeSeries 数组中的元素，含义为中毒的时候，x 为相邻两元素的差值，d 即为中毒时间 duration，则存在以下规律：
   

          所谓题目中的中毒连续时间会重置，其实就是 x 时间内又遭受了提莫攻击，且 x 时间小于 d 中毒时间，此时新的中毒时候与上一次中毒时候之间的差值 x，即为实际的中毒时间。
        因此，当 x < d 时，中毒时间实际为 x，而当 x >= d时，中毒时间则为 d。
 
.2- 代码编写

1. class Solution {
2. public:
3.     int findPoisonedDuration(vector<int>& timeSeries, int duration) {
4.         int ret=0;
5.         for(int i=1;i<timeSeries.size();i++)
6.         {
7.             int x=timeSeries[i]-timeSeries[i-1];
8.             //当 x < d 时，中毒时间实际为 x，而当 x >= d时，中毒时间则为 d。
9.             if(x>=duration)ret+=duration;
10.             else ret+=x;
11.         }
12.         return ret+duration; //最后一个时刻也遭受了中毒攻击，也需算上中毒时间
13.     }
14. };

复制代码

 
3）Z 字形变动

6. Z 字形变动
   

   
 .1- 题目分析

        由示例 1，一个字符串进行 Z 字变动后，形式如下：
   

          我们可以把这个变动后的字符串当作是在一个二维矩阵中，由此 Z 字变动可以在一个二维矩阵中进行。设一个字符串为“abcdefg...”，且行数 n = 4，则可以得到以下二维矩阵：
   

          但这样的话，代码的时间复杂度和空间复杂度都来到了O(字符串长度*n)，是非常高的。因此，还需要对这样的思绪进行优化，而优化的方式就是找规律。
        假如填入的不是字符，而是字符在字符串数组中的下标，则可以得到以下二维矩阵：
   

           不难发现，对于一行中的下标，它们之间的隔断都雷同。设一行中相邻两元素下标的公差为 d，则：

• 对于第 0 行，第 0 行的下标依此为 0、0 + d、0 + 2d...0 + k*d。
  
• 对于第 i 行（第 1、2行），以第 i 行相邻的两字符为一组，它们的下标依此为 ( i，d - i )、( i + d，d - i + d)、( i + 2d，d - i + 2d)...( i + k*d，d - i + k*d)。
  
• 对于 n - 1 行（第 3 行），第 n - 1 行的下标依此为 n - 1、n - 1 + d、n - 1 + 2d...n - 1 + k*d。
  

        当 n = 3 时，该规律仍正确：
   

   
.2- 代码编写

1. class Solution {
2. public:
3.     string convert(string s, int numRows) {
4.         if(numRows==1)return s; //处理边界情况
5.         string ret;
6.         int d=2*numRows-2,n=s.size();
7.         //先处理第0行
8.         for(int i=0;i<n;i+=d)
9.             ret+=s[i];
10.         //处理第i行
11.         for(int k=1;k<numRows-1;k++)//先枚举行数
12.         {
13.             for(int i=k,j=d-k;i<n||j<n;i+=d,j+=d)//再枚举列
14.             {
15.                 //以第 i 行相邻的两字符为一组，i表示前一个字符，j表示后一个字符
16.                 if(i<n)ret+=s[i];
17.                 if(j<n)ret+=s[j];
18.             }
19.         }
20.         //处理第n-1行
21.         for(int i=numRows-1;i<n;i+=d)
22.             ret+=s[i];
23.         return ret;
24.     }
25. };

复制代码

 
4）表面数列

38. 表面数列
   

   
 .1- 题目分析

        若 n = 5，则 countAndSay(1) 到 countAndSay(5) 分别为：
   

          以“33341111554”为例，最终应压缩为“3314412514”，不难发现这个过程其实是对一段连续的数字进行计数， 然后描述这个数有多少个，比方压缩后的“3314412514”中的“33”，含义为“3 个 3”，而可以或许得到“3 个 3”，其实是由于对数组从左往后数出了 3 个 3。
        由此，我们可以使用双指针来遍历数组，找出连续雷同的数字构成的区间，并对数字的个数进行计数，以此完成字符串的压缩。
   

   
.2- 代码编写

1. class Solution {
2. public:
3.     string countAndSay(int n) {
4.         string ret="1";
5.         //进行n-1次压缩
6.         for(int i=1;i<n;i++)
7.         {
8.             string tmp;         //保存本次压缩的结果
9.             int len=ret.size(); //求压缩前的字符串长度
10.             //双指针寻找连续相同的数字区间
11.             for(int left=0,right=0;right<len;)
12.             {
13.                 //找到连续区间后第一个不同的数字
14.                 while(ret[left]==ret[right]&&right<len)
15.                     right++;
16.                 //保存本次压缩的结果
17.                 tmp+=to_string(right-left)+ret[left];
18.                 //继续下一次压缩
19.                 left=right;
20.             }
21.             ret=tmp;
22.         }
23.         return ret;
24.     }
25. };

复制代码

5）数田鸡

1419. 数田鸡
   

   
 .1- 题目分析

        "coark"完备的为一声蛙叫。以示例 2 为例，当遍历字符串时，遍历至第一个“r”，只需“r”前面相应地存在一个“c”，就分析当前还可以构成一次蛙叫，可以继续遍历下去。；同理，遍历至第一个“o”，只需“o”前面相应地存在一个“r”。
        由此，我们需要一个哈希表来对字符出现的情况进行标识。
   

          每统计一遍完备的"coark"，字符“k”在哈希表中对应的频次都将 + 1，直到遍历完字符串后，假如除k以外的字符在哈希表中的值全为 0，则可以返回字符“k”对应的出现频次，此时即返回了蛙叫的次数。

.2- 代码编写

1. //版本1
2. class Solution {
3. public:
4.     int minNumberOfFrogs(string croakOfFrogs) {
5.         // int c = 0, r = 0, o = 0, a = 0, k = 0;
6.         vector<int> arr(6, 0); // 用下标1到5分别映射五个字母
7.         for(auto& e : croakOfFrogs)
8.         {
9.             if(e == 'c')
10.             {
11.                 if(arr[5] > 0)
12.                     --arr[5];
13.                 ++arr[1];
14.             }
15.             if(e == 'r')
16.             {
17.                 if(arr[1] > 0)
18.                     --arr[1];
19.                 else
20.                     return -1;
21.                 ++arr[2];
22.             }
23.             if(e == 'o')
24.             {
25.                 if(arr[2] > 0)
26.                     --arr[2];
27.                 else return -1;
28.                 ++arr[3];
29.             }
30.             if(e == 'a')
31.             {
32.                 if(arr[3] > 0)
33.                     --arr[3];
34.                 else  return -1;
35.                 ++arr[4];
36.             }
37.             if(e == 'k')
38.             {
39.                 if(arr[4] > 0)
40.                     --arr[4];
41.                 else return -1;
42.                 ++arr[5];
43.             }
44.         }
45.         if(arr[1] > 0 || arr[5] == 0)
46.             return -1;
47.         return arr[5];
48.     }
49. };

复制代码

1. //版本2
2. class Solution {
3. public:
4.     int minNumberOfFrogs(string croakOfFrogs) {
5.         //前期准备
6.         string t="croak";
7.         int n=t.size();
8.         vector<int> hash(n);           //hash标识字符的出现频次
9.         unordered_map<char,int> index; //index映射字符的下标，方便统一处理o、a、r、k
10.         for(int i=0;i<n;i++)
11.             index[t[i]]=i;             //初始化 index
12.         //统计蛙叫
13.         for(auto ch:croakOfFrogs)
14.         {
15.             //遇到c
16.             if(ch=='c')
17.             {
18.                 if(hash[n-1]) //若最后一个字符k在哈希表中存在
19.                     hash[n-1]--;
20.                 hash[0]++;
21.             }
22.             //遇到o、a、r、k
23.             else
24.             {
25.                 int i=index[ch];
26.                 if(hash[i-1]==0) //若前驱字符不存在
27.                     return -1;
28.                 hash[i-1]--;
29.                 hash[i]++;
30.             }
31.         }
32.         //检验hash，若除k以外的字符对应频次为0，则结果有效
33.         for(int i=0;i<n-1;i++)
34.         {
35.             if(hash[i])
36.                 return -1;
37.         }
38.         //结果有效，则返回k对应的频次
39.         return hash[n-1];
40.     }
41. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。