珍佰农 商城网站建设,网络推广培训哪个好,广东建设工程信息网官网证书查询,微商城网站建设合同下载目录 1、1576. 替换所有的问号
2、 495. 提莫攻击
3、6. Z 字形变换
4、38. 外观数列
5、 1419. 数青蛙 1、1576. 替换所有的问号 思路#xff1a;分情况讨论 ?zs#xff1a;左边没有元素#xff0c;则仅需保证替换元素与右侧不相等#xff1b;z?s#xff1a;左右都…目录 1、1576. 替换所有的问号
2、 495. 提莫攻击
3、6. Z 字形变换
4、38. 外观数列
5、 1419. 数青蛙 1、1576. 替换所有的问号 思路分情况讨论 ?zs左边没有元素则仅需保证替换元素与右侧不相等z?s左右都有元素则问号两侧都需要保证替换元素与其不相等zs? 右边没有元素则仅需保证替换元素与左侧不相等。 class Solution {
public:string modifyString(string s) {int n s.size();for (int i 0; i n; i) {if (s[i] ?) {for (char ch a; ch z; ch) {if ((i 0 || ch ! s[i - 1]) (i n - 1 || ch ! s[i 1])) {s[i] ch;break;}}}}return s;}
};
2、 495. 提莫攻击 思路分情况讨论 相邻两次受到攻击的时间差与中毒持续时间进行比较时间差大于等于中毒持续时间则可以收到完整中毒时长否则只能接受到时间差的中毒时长。 class Solution {
public:int findPoisonedDuration(vectorint timeSeries, int duration) {int sum 0;for (int i 1; i timeSeries.size(); i) {int x timeSeries[i] - timeSeries[i - 1];if (x duration)sum duration;elsesum x;}return sum duration;}
};
3、6. Z 字形变换 思路画图找规律 示例解释 以 PAYPALISHIRING 为例numRows 3 时周期 d 4。 第一行字符P0A4H8N12第二行字符A1P3L5S7I9I11G13第三行字符Y2I6R10 按行读取这些字符后得到的新字符串是 PAHNAPLSIIGYIR。 特殊情况处理如果 numRows 为 1则不需要进行任何变换直接返回原字符串 s。 周期计算整个 Z 字形排列的一个循环周期 d 是 2 * numRows - 2。这个周期是由于从上到下再到上的一个完整循环所包含的字符数量。例如当 numRows 为 3 时d 为 4。 第一行的字符添加第一行的字符在原字符串中的位置就是周期 d 的倍数即 0, d, 2d, ...。 中间行的字符添加 对于中间的每一行每个周期内都有两个字符需要被添加到结果字符串中。第一个字符的位置是周期起始位置加行数第二个字符的位置是周期结束位置减行数。具体来说对于行 k从 0 开始计数在周期 i 中第一个字符的位置是 i k第二个字符的位置是 i d - k。注意每次添加第二个字符时需要检查其位置是否超出了原字符串的长度。 最后一行的字符添加最后一行的字符在原字符串中的位置是周期起始位置加 numRows - 1即 numRows - 1, numRows - 1 d, numRows - 1 2d, ...。 返回结果按照上述规则将所有行的字符依次添加到结果字符串 ret 中后返回 ret。 class Solution {
public:string convert(string s, int numRows) {if (numRows 1)return s;string ret;int d 2 * numRows - 2;int n s.size();for (int i 0; i n; i d) {ret s[i];}for (int k 1; k numRows - 1; k) {for (int i k, j d - k; i n || j n; i d, j d) {ret s[i];if (j n)ret s[j];}}for (int i numRows - 1; i n; i d) {ret s[i];}return ret;}
};
4、38. 外观数列 思路外层遍历数组元素内层使用双指针寻找相同字符区间区间相减就是相同字符的个数区间左端点就是字符。 class Solution {
public:string countAndSay(int n) {string ret 1;for (int i 1; i n; i) {string tmp;int n ret.size();for (int left 0, right 0; right n;) {while (right n ret[left] ret[right])right;tmp to_string(right - left) ret[left];left right;}ret tmp;}return ret;}
};
5、 1419. 数青蛙 思路 计数逻辑通过追踪每个 croak 中字符的状态确保蛙鸣声的顺序正确无误。顺序检测确保每个蛙鸣声都是按照正确的顺序 croak 发出的。 初始化变量 s croak定义了一个青蛙蛙鸣的顺序。n s.size()蛙鸣声 croak 的长度这里是5。hash一个大小为5的向量数组用于追踪 croak 中每个字母的状态。index一个哈希表unordered_map用于映射每个字符到它在 croak 中的索引。 处理字符串 遍历输入的 croakOfFrogs 字符串中的每个字符。如果字符是 c表示一个新的蛙鸣声开始。如果在 hash 的最后一个位置对应 k 字符的位置有计数表示有一个青蛙完成了蛙鸣可以开始新的蛙鸣因此减少 k 的计数并增加 c 的计数。对于 r, o, a, k 之外的 c需要检查前一个字符是否已经存在即前一个状态的计数是否大于0。如果是将前一个字符的计数减1当前字符的计数加1。如果不是表示蛙鸣声的顺序被打断了返回 -1。 验证和返回结果 遍历 hash 向量检查 c, r, o, a 的计数是否都为0。如果这些位置的计数不为0表示有蛙鸣声没有完成返回 -1。如果所有 c, r, o, a 的计数都为0最后返回 k 的计数即为所需的最少青蛙数量。 class Solution {
public:int minNumberOfFrogs(string croakOfFrogs) {string s croak;int n s.size();vectorint hash(n);unordered_mapchar, int index;for (int i 0; i n; i)index[s[i]] i;for (auto c : croakOfFrogs) {if (c c) {if (hash[n - 1] ! 0)hash[n - 1]--;hash[0];} else {int i index[c];if (hash[i - 1] 0)return -1;hash[i - 1]--;hash[i];}}for (int i 0; i n - 1; i) {if (hash[i] ! 0)return -1;}return hash[n - 1];}
};
