【基础算法总结】模拟篇

一，算法介绍

   模拟算法本质就是"依葫芦画瓢"，就是在题目中已经告诉了我们该如何操作，我们只要把题目中的过程转化成代码即可。特点是思路简单，难点黑白常考验代码功底。
  二，算法原理和代码实现

1576.替换全部的问号

算法原理：
   没有那么多弯弯绕绕，就是从前今后遍历字符串，如果出现 ‘?’，就用26个字母判断一个 ‘?’ 字符的前一个和后一个字符，保证不出现前后两个连续相同的字符，再把 ‘?’ 替换即可。
  细节题目：
   要注意边界情况的判断，就是当 ‘?’ 出现在第一个位置和最后一个位置的处理。
  代码实现：

1. class Solution
2. {
3. public:
4.     string modifyString(string s)
5.     {
6.         int n = s.size();
7.         for(int i = 0; i < n; i++)
8.         {
9.             if(s[i] == '?')
10.             {
11.                 for(char ch = 'a'; ch <= 'z'; ch++)
12.                 {
13.                     if((i == 0 || s[i-1] != ch) && (i == n-1 || s[i+1] != ch))
14.                     {
15.                         s[i] = ch;
16.                         break;
17.                     }
18.                 }
19.             }
20.         }
21.         return s;
22.     }
23. };

复制代码

495.提莫攻击

算法原理：
   根据示例，可以得到下面的规律：

  代码实现：

1. class Solution {
2. public:
3.     int findPoisonedDuration(vector<int>& timeSeries, int duration) {
4.         int n = timeSeries.size();
5.         int ret = 0;
6.         for(int i = 1; i <= n-1; i++)
7.         {
8.             int x = timeSeries[i] - timeSeries[i-1];
9.             if(x >= duration)
10.                 ret += duration;
11.             else
12.                 ret += x;
13.         }
14.         return ret + duration;
15.     }
16. };

复制代码

6.Z字形变更

算法原理：
   我们不直接把字符举行Z变更，把每个字符的下标抽象出来：

然后在表中找出下标的规律，直接在字符串中根据找出的下标取字符：

  细节题目：
   当给定行数为 1 行时，盘算的公差 d == 0，会造成死循环。所以要特殊处理，此时直接返回原字符串即可。
  代码实现：

1. class Solution
2. {
3. public:
4.     string convert(string s, int numRows)
5.     {
6.         // 处理特殊情况
7.         if(numRows == 1) return s;
8.         
9.         int d = 2 * numRows - 2, n = s.size();
10.         string ret;
12.         // 处理第一行的字符
13.         for(int i = 0; i < n; i += d)
14.             ret += s[i];
15.         
16.         // 出来中间行的字符
17.         for(int k = 1; k < numRows-1; k++) // 枚举中间的每一行
18.         {
19.             for(int i = k, j = d - k; i < n || j < n; i += d, j += d)
20.             {
21.                 if(i < n) ret += s[i];
22.                 if(j < n) ret += s[j];
23.             }
24.         }
26.         // 处理最后一行字符
27.         for(int i = numRows-1; i < n; i += d)
28.             ret += s[i];
29.         
30.         return ret;
31.     }
32. };

复制代码

38.外观数列

算法原理：
   本题使用：模拟+双指针
这里的双指针的作用就是从前今后遍历相同字符的地区，盘算出相同字符的个数。

  代码实现：

1. class Solution
2. {
3. public:
4.     string countAndSay(int n)
5.     {
6.         if(n == 1) return to_string(1);
7.         string ret;
8.         string tmp = to_string(1);
10.         for(int i = 0; i < n-1; i++)
11.         {
12.             ret = "";
13.             int left = 0, right = 0, len = tmp.size();
14.             while(right < len)
15.             {
16.                 while(right < len && tmp[right] == tmp[left]) right++;
17.                 ret += to_string(right - left) + tmp[left];
18.                 left = right;
19.             }
20.             tmp = ret;
21.         }
22.         return tmp;
23.     }
24. };

复制代码

1419.数青蛙

算法原理：
   这道题在模拟算法中是一道比力难的题。
使用：模拟+哈希表。
遍历所给的字符串，与啼声字符串举行对比映射：

通过模拟，可以举行总结：

  细节处理：
   (1) 两个哈希表的作用：
第一个哈希表用数组模拟，目的是统计字符出现的个数，但不是用字符举行映射统计的，而是根据啼声字符串 "croak"的下标。
第二个哈希表用 hash< char, int > 实现，表现的是啼声字符串"croak"的每个字符，和每个字符对应的下标。
(2) 当遍历完整个 croakOfFrogs 字符串后，还必要把第一个哈希表遍历检查一下。
  代码实现：
   根据上面的总结，实今世码有多种方式，下面的实现方式是一种通用的，由于可能有些题目给的啼声字符串不是只有五个字符的"croak"，而是其他更长的。

1. class Solution
2. {
3. public:
4.     int minNumberOfFrogs(string croakOfFrogs)
5.     {
6.         string t = "croak";
7.         int n = t.size();
8.         vector<int> hash(n); // 用数组模拟哈希
10.         unordered_map<char, int> index; // [x,x这个字符的下标]
11.         for(int i = 0; i < n; i++)
12.             index[t[i]] = i;
13.         
14.         for(auto ch : croakOfFrogs)
15.         {
16.             if(ch == 'c')
17.             {
18.                 // 判断最后一个字符是否存在
19.                 if(hash[n-1] != 0) hash[n-1]--;
20.                 hash[0]++;
21.             }
22.             else
23.             {
24.                 int i = index[ch]; // 找到字符的下标
25.                 if(hash[i-1] == 0) return -1;
26.                 else hash[i-1]--, hash[i]++;
27.             }
28.         }
30.         // 除了最后一个字符'k'外，其他字符如果还有出现，直接返回-1
31.         for(int i = 0; i < n-1; i++)
32.             if(hash[i] != 0) return -1;
34.         return hash[n-1];
35.     }
36. };

复制代码

三，算法总结

   解决有关模拟类的题型，最重要的就是根据题目写代码。有些模拟题可能正面做困难，举行优化时一样平常都是"找规律"举行转换。

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