网站设计预算,WordPress女人网模板,莱州网站制作,软件类专业有哪些目录
前言#xff1a;
Z字形变换
题目解析
算法原理
算法编写
数青蛙
题目解析
算法原理
算法编写 前言#xff1a;
本文的主题是模拟#xff0c;通过两道题目讲解#xff0c;一道是Z字形变化#xff0c;一道是数青蛙。 链接分别为#xff1a;
1419. 数青蛙…目录
前言
Z字形变换
题目解析
算法原理
算法编写
数青蛙
题目解析
算法原理
算法编写 前言
本文的主题是模拟通过两道题目讲解一道是Z字形变化一道是数青蛙。 链接分别为
1419. 数青蛙 - 力扣LeetCode
6. Z 字形变换 - 力扣LeetCode 题目分为三个部分讲解一是题目解析二是算法原理三是算法编写那么话不多说直接进行主题咯。 Z字形变换
题目解析 该题目的要求相当于让我们将字符串分成一个一个的字符串进行Z字形排列只需要让我们创建一个n * col的矩阵可是col是多少我们并不知道。但是不影响。
题目要求我们转换字符串之后将字符串从左到右依次读取字符串最后返回即可。
这就是题目解析部分我们进入到算法原理部分。
算法原理
因为是一道典型的模拟题目所以我们只需要模拟一下这个过程就可以了 解法一的话直接就老老实实的模拟呗不过这种方法的时间复杂度和空间复杂度都是比较高的就拿创建的矩阵来说我们都不知道矩阵的长究竟有多长保险的创建方式就是让长等于length毕竟N是有可能等于1的。
但是第一种方式在leetcode里面还真的是可以跑过去的只是效率方面来说确实没有那么好而已。
接下来我们介绍一种优化方式其实也是模拟大多数题目的一种优化方式就找规律嘛找规律之前我们应该是否可以让所谓的字符变成一个一个的下标呢当然是可以的。 就像是这样转换成了下标之后我们找规律就可以了从第一行开始发现是从0到6也就是公差为6此时的n是2那么公差d是等于2 * n - 2的其他n的取值也是这种情况这里就不验证了。
那么第一行的规律我们找到了那么最后一行一样的无非开始的部分变成了n - 1而已对于中间来说稍微是有一点麻烦的因为有两个数字嘛。
同样的找规律我们拿1举例后面依旧是1 7 13也是满足加d的这个规律的对于5 11来说我们拿1 5举例1 5等于公差对吧所以第二个数的取值就是d - i所以对于中间两个的取值我们只需要i d - i就可以了。
不过我们还需要处理一下特殊情况如果n 1的话那么我们就不需要变化了并且n 1的时候公差d是等于0的。我们直接返回字符串就行了。
算法编写
class Solution
{
public:string convert(string s, int numRows) {// 处理边界情况if(numRows 1) return s;// 开始解释string ret;int d 2 * numRows - 2;// 处理第一行for (int i 0; i s.size(); i d)ret s[i];// 处理中间行for (int i 1; i numRows - 1; i){for (int m i, n d - m; m s.size() || n s.size(); m d, n d){if(m s.size()) ret s[m];if(n s.size()) ret s[n];}}// 处理最后一行for(int i numRows - 1; i s.size(); i d)ret s[i];return ret;}
}; 数青蛙
题目解析 数青蛙这道题目青蛙的输出顺序是croak每只青蛙都是一个一个的输出的让我们在一个输出序列里面找到最少需要多少只青蛙才可能输出对应的输出序列。
那么要求是最少的青蛙找到返回就可以了。
算法原理
对于这道题目来说是不是和提莫攻击这道题目有点类似因为都是模拟一个序列提莫攻击模拟的是提莫的攻击对于这道题目来说模拟的是青蛙的蛙鸣行为。
那么总共的输出序列是croak可能一只青蛙在叫的时候另一只青蛙穿插着叫了。
但是这并不影响青蛙的叫声是非常死板的死板到只能从croak这个字符串序列里面输出也就是青蛙叫r的时候需要看前面是否存在c如果存在c的话它才能从r继续。
那么
当我们遍历这个序列的时候用一个哈希数组来映射当遍历到某个元素判断前面是否存在元素如果存在那么前面的元素--当前元素代表青蛙叫到了哪个位置。
其中比较特殊的是当我们遍历到了c那么我们应该是从k里面找是否存在青蛙空闲下来了如果空闲了那么K--C即可因为我们是要找最少的青蛙个数。
所以现在一个哈希表是肯定要的那么映射的时候我们需要一种映射关系是吧所以我们可以使用unordered_map映射字符和下标的关系即可。
这里的唯一作用就是遍历的时候判断前面的字符而已。
算法编写
class Solution
{
public:int minNumberOfFrogs(string croakOfFrogs) {string s croak;int len s.size();vectorint hash(len);unordered_mapchar, int index;for (int i 0; i len; i)index[s[i]] i;for (auto ch : croakOfFrogs) {if (ch c) {if (hash[len - 1] ! 0)hash[len - 1]--;hash[0];} else {int i index[ch];if (hash[i - 1] 0)return -1;hash[i - 1]--;hash[i];}}for (int i 0; i len - 1; i)if (hash[i] ! 0)return -1;return hash[len - 1];}
}; 感谢阅读
