发布时间：2025-06-24 20:04:02  作者：北方职教升学中心  阅读量：464

数青蛙

---

1、

目录

1、

总结：

1、替换所有问号

 3、

class Solution {public:    string convert(string s, int numRows)     {        if(numRows == 1) return s;        // 1.将数据存入字符串数组        vector<string> vs(numRows);        int i = 0,flag = -1;        for(auto& x: s)        {            vs[i] += x; // 刚进循环,第一个数据flag是-1            if(i == 0 || i == numRows-1) // 第一/最后一行是转折点                flag = -flag; // 用flag控制存储的方向,位置            i += flag;        }        // 2.将字符串数组中所有字符串按行号顺序接合起来        string str;        for(string& rows: vs)            str += rows;        return str;    }};

方法二：找规律：

 第1/numRows行，隔2*numRows-2是一个元素。模拟算法简介

模拟算法是一种基本的算法设计方法，它的核心思想是按照问题描述的规则，逐步模拟问题的发展过程，从而得到问题的解决方案。

但因为我们要找的是最少的青蛙数，青蛙在叫完完整一次“croak”后可以紧接着继续蛙鸣，所以，当读到【c】时还有一种情况是先查看哈希表中对应的【k】叫声个数，如果不是0，说明有青蛙可以重新开始一轮蛙鸣，对应我们的操作就是把记录到的【k】叫声个数-1，给【c】叫声个数+1。r o a k  --->  查看前序字符是否在哈希表中存储个数

（1）存在：前驱个数--，当前个数++

（2）不存在：返回-1

2、后续【o】...叫声与上面演示的【r】的处理方式类似。外观数列

6、模拟算法简介

2、这种算法通常不依赖于复杂的数学公式或高级的数据结构，而是通过直接模拟现实世界中的操作或规则来解决问题。

class Solution {public:    string countAndSay(int n) {        // 模拟 + 双指针        string ret = "1"; // 初始值        for (int i = 1;i < n; i++) // 模拟n-1次,因为第一次就是1        {            string tmp;            int len = ret.size(); // 限定区域是在ret内            for(int left = 0,right = 0;right < len;)            {                while (right < len && ret[left] == ret[right]) right++;// 确定重复次数                tmp += to_string(right - left); // 重复次数                tmp += ret[left]; // 对应字符                left = right; // 重置指针            }            ret = tmp; // 更换新字符串        }        return ret;    }};

6、

 中间行，两组数据从(k,d-k)开始，每次隔2*numRows-2是一组数据，可能最后会有一个数据越界。

遍历字符串s时：用 flag 来做索引标记，到达Z字形转折点时的时候 (第一行 / 最后一行)，执行反向 (flag = -flag) 。数青蛙

. - 力扣（LeetCode）

方法：模拟 + 分情况讨论

用哈希表模拟寻找青蛙叫声的过程，开始时，青蛙开始发出叫声【c】，在哈希表中映射记录一次【c】叫声，假设紧接着发出【r】时，就要先在哈希表中找【r】的前驱字符【c】是否已经记录过叫，如果有记录就把这个记录传承下来，前驱【c】的叫声次数-1，当前【r】的叫声+1次；如果没有记录，就说明此时字符串记录的叫声是不完整的，不是有效组合。Z字形变换

6. Z 字形变换

方法一：用字符串数组vector<string>模拟Z字形存入数据，再将字符串数组中的字符串按行号顺序连接。

class Solution {public:    string convert(string s, int numRows)     {        // 边界情况        if(numRows == 1) return s;        // 找规律：第1/numRows行,隔2*numRows-2是一个元素        // 中间行,两组数据从(k,d-k)开始,每次隔2*numRows-2是一组数据,        // 可能最后会有一个数据越界        string str;        int d = 2 * numRows - 2; // 计算步长        int n = s.size();                // 处理第一行,从s[0]开始        for(int i = 0;i < n;i += d)            str += s[i];        // 处理中间行的每一行,从(s[k],s[d-k])开始        for(int k = 1;k < numRows-1;k++)        {            for(int i = k,j = d-k;(i < n || j < n);i += d,j += d)            {                if(i < n) str += s[i];                if(j < n) str += s[j];            }        }        // 处理最后一行,从s[numRows-1]开始        for(int i = numRows-1;i < n;i += d)            str += s[i];        return str;    }};

5、提莫攻击

4、提莫攻击

495. 提莫攻击

class Solution {public:    int findPoisonedDuration(vector<int>& timeSeries, int duration)     {        int T = 0;        for(int i = 1;i < timeSeries.size();i++)        {   // 计算两次中毒的时间间隔            int time = timeSeries[i] - timeSeries[i-1];            // 间隔大于标准中毒时间,按标准计时             if(time > duration) T += duration;            // 否则,计时会重置，所以只记录间隔时间            else T += time;        }        // 别忘了最后一次中毒        T += duration;        return T;    }};

4、外观数列

. - 力扣（LeetCode）

模拟 + 双指针，双指针用来模拟顺序读取下字符的连续次数。c --->  找最后一个字符 k 在哈希表中是否存储

（1）存在：k字符个数--，c字符个数++

（2）不存在：c字符个数++

class Solution {public:    int minNumberOfFrogs(string croakOfFrogs)     { // 用哈希表模拟        string str = "croak"; // 先把叫声存储起来        int n = str.size();        vector<int> hash(n); // 数组模拟哈希表，用下表对应存储str的每个字符(‘c’对应0...)        unordered_map<char,int> index(n);         // 存储 [x,x对应的下标] 方便寻找前驱字符(通过下标)        for(int i = 0;i < n; i++)            index[str[i]] = i;                for(auto ch : croakOfFrogs)        {            if(ch == 'c')            {                if(hash[n - 1] != 0) hash[n - 1]--;                hash[0]++;            }            else            {                int prev = index[ch] - 1; // 找到前驱字符的下标                if(hash[prev] == 0) return -1;                hash[prev]--;                hash[index[ch]]++;            }        }        for(int i = 0;i < n - 1;i++)            if(hash[i] != 0) return -1;        return hash[n - 1];    }};

class Solution {public:    int minNumberOfFrogs(string croakOfFrogs)     {        unordered_map<char,int> vv;        for(auto e : "croak")        {            vv[e] = 0;        }        int cur = 0,len = croakOfFrogs.size();        while(cur < len)        {            if(croakOfFrogs[cur] == 'r')            {                if(vv['c'] > 0)                 {                    vv['c']--;                    vv['r']++;                }                 else return -1;            }            else if(croakOfFrogs[cur] == 'o')            {                if(vv['r'] > 0)                 {                    vv['r']--;                    vv['o']++;                }                 else return -1;            }            else if(croakOfFrogs[cur] == 'a')            {                if(vv['o'] > 0)                 {                    vv['o']--;                    vv['a']++;                }                 else return -1;            }            else if(croakOfFrogs[cur] == 'k')            {                if(vv['a'] > 0)                 {                    vv['a']--;                    vv['k']++;                }                 else return -1;            }            else if(croakOfFrogs[cur] == 'c')            {                if(vv['k'] > 0)                {                    vv['k']--;                    vv['c']++;                }                else vv['c']++;            }            cur++;        }        for(auto e: "croa")        {            if(vv[e] > 0) return -1;        }        return vv['k'];    }};