蓝桥杯---数青蛙（leetcode第1419题）

1.题目重述

这个题目算是模拟这个专题里面的一类比较难的题目了，他主要是使用crock这个单词作为一个整体，让我们确定：给你一个字符串，至少需要多少个青蛙进行完成鸣叫的过程，这个地方强调的是最少的青蛙的数量，为什么强调最少，通过下面对于例子的分析，你就会理解里面的原因；

2.例子分析

示例一算是一个比较完整的例子：croak算是一个完整的过程，这个时候这个青蛙叫完之后，可以继续去叫下一个croak,因此这个输入的字符串最少需要一个青蛙，这个青蛙叫两遍就可以了；

为什么会强调是最少的数量，这个例子就可以体现，因为我们可以让一个青蛙叫前面的croak，让第二个青蛙叫第二组croak，这个时候可以是两个青蛙，但是因为题目要求是最少的青蛙的数量，因此使用一个就可以了；

示例二强调的是交叉进行这个情况，就是对于一个青蛙而言，他叫的这个顺序必须是croak,因此这个示例里面标注了第一个青蛙叫的内容和第二个青蛙叫的内容，都是croak，这个时候和上面不同的地方就是这个croak不是连续的了；

这个示例里面至少就是两个青蛙，一个就不可以了，假设第一个青蛙叫：c,r,到达第三个字符c的时候，他就不可以叫了，因为上面说了，这个叫的顺序必须是croak,这个时候他本来交了cr，再出来一个c不可能再是他叫的，这个时候需要第二个青蛙；

示例三就是无法完成的一个情况，因为这个第一个青蛙叫完croak,他再去叫cro，这个时候发现下一个是o，显然不符合这个croak的顺序，因此这个就无法完成，所以返回异常值-1；

3.思路分析

下面，我是用可视化的方式展示一下这个题目的思路分析过程：

这个题目的整体的思路是使用的数组模拟哈希表，值记录的是这个字符出现的次数：刚开始的时候，指向c，因此这个数组里面的c对应的值就是1；

下面的这一步很重要，就是下一个字符是r,这个时候我们就去找c，因为一个青蛙想要叫r，前提是他必须叫c，这个时候我们上一步前面就是c，所以我们可以看下面的这个图：就是1挪到了r的这个位置；

上面的这个理解下，下面就好搞了，我们发现，走到一个非开头元素的时候，我们就要看这个数组里面是不是存在他前面的这个位置的元素：

下一个元素是c，是croak里面的开头元素，这个时候他的前面没有元素，因为他自己就是第一个，所以这个时候需要另外的一个青蛙，我们在这个对应位置填上1；

下面的元素是o。我们找croak里面o前面的元素是r，在这个数组里面是存在的，挪动一下即可；

下面的这个元素是a,在croak里面，a前面的元素是o，正好存在，所以就是挪一下即可；

接下来的元素是k，我们找的是o，存在，进行挪动，发现这个到达k了，也就是鸣叫的最后一个字符，这个时候他的一次就完成了，如果后续需要，它可以继续重复，因为他的这一次完整的过程结束了；

接下来就是r元素，我们找的是c元素，存在进行挪动，以此类推（下面的这个过程我省略了，因为接下来的元素分别是roak，都是连着顺序的，这个原理是一样的，所以我就直接划到了k，这个时候相当于两个青蛙完成了鸣叫，我们发现剩下的正好是croak一个完整的鸣叫，这个时候我们从两个两个完成鸣叫的青蛙里面任意进行选择一个完成下面的过程即可，因此这个最少数量就是2个；

4.思路总结

下面的这个就是基于上面的过程总结：

我们分为是不是第一个元素，如果是c，我们就要看看是不是有已经叫完了的青蛙，否则就需要一个新的；如果有的话，k对应的位置–，我们的c对应的位置++就可以了；

如果不是第一个元素(roak之类的）,我们找前驱元素，例如，指向k的时候，我们看看是不是有青蛙叫到了a，如果有，按照上面的过程挪动就可以了（该位置++，前面的位置–，这个就是挪动涉及到的变化），如果没有就返回-1，证明这个过程无法完成，类似于示例里面的第三个情况；

5.代码解释

1）字符串转换为字符数组，tocharArray方法转换；

2）hash数组模拟上面提到的croak这个过程，挪动设计到的下标的变化；

3）HashMap是主要方便去找前驱节点，因为总结里面说了，前驱节点存在，需要前驱节点–，该位置++，HashMap里面的键值对分别表示字符t.charAt获取字符（键），对应下标（值）就是代码里面的i；

4）index就是把这个字符和他的下标绑定在一起，方便我们使用；

5）遍历这个ret字符数组，根据我们的总结里面的内容进行操作：

如果对应的是c，我们去找这个k对应的位置是不是0，也就是代码里面的n-1下标，如果不是0，这个时候n-1位置的数值–，否则我们的0下标就++；

如果对应的是roak里面的字符，也就说不是第一个，我们需要做的就是找i前面的一个元素位置的值是不是存在，存在的话，就是前驱–，该位置++；

前面的元素不存在，直接返回-1，证明字符不完整，无法鸣叫；

6）最后的for讲的是遍历croak里面的前面的四个位置对应的值是不是都是0，如果有一个不是，证明有落单的，这个就无法完成，如果出了k之外的元素对应位置都是0，说明每一个青蛙都是完成了croak的鸣叫，没有中途停留的，我们返回的就是k下标对应的值（表示的最少的青蛙的数量）；