day15
第一题
1419. 数青蛙
本题主要是采用模拟的解题思路，用一个croak来模拟青蛙的叫声，在一堆字符串中来找到几个croak，并判断这是由几个青蛙叫的；
首先我们使用数组来模拟hash表，其次我们使用hash表来映射青蛙叫的字符中的每一个元素x（x，x在数组中所对应的下标）；
接下来就是来分析解题思路：
步骤一：
首先把青蛙的叫的字符串放在hash表中，其次使用指针来遍历给出的一串字符中有多少个青蛙叫；
步骤二：
当我们指针所指字符串中的元素指的是青蛙叫的第一个元素时（c），首先判断数组数组中的最后一位（k）是否为1，（当k为1时，表示青蛙此前已经完整的叫了一声音，此时开始从新叫），所以当前k位置的数字-1；c位置的数字加一；如果当前的k为0，说明当前的青蛙是第一次叫，所以，只需要进行c所在位置的数字加一操作；
当我们的指针指向青蛙叫的非第一个元素的时候，判断数组中该元素位置的前一位元素是否为1，如果是，则青蛙叫继续，前一位元素在数组中的位置进行-1操作，当前元素在数组中的位置进行+1操作，（我们是通过hash表来通过元素来查找数组中该元素的位置）；如果该元素在数组中的前一个位置的元素数字不为1，则该字符串不是青蛙所能叫的，所以直接返回-1；
步骤三：
上述操作完成后，判断数组中1的位置，1只能出现在数组的最后一个位置，如果其他的位置上还有1，则直接返回-1；
代码如下所示：
class Solution {public int minNumberOfFrogs(String c) {char[] croakOfFrogs = c.toCharArray();String t = "croak";int n = t.length();int[] hash = new int[n]; // 数组模拟哈希表Map<Character, Integer> index = new HashMap<>(); // [x, x这个字符对应的下标for(int i = 0; i < n; i++)index.put(t.charAt(i), i);for(char ch : croakOfFrogs){if(ch == t.charAt(0)){if(hash[n - 1] != 0) hash[n - 1]--;hash[0]++;} else{int i = index.get(ch);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];} }
第二题
首先举例子来分析：
本题我们采用模拟和双指针的方法来解决：
如下图所示，右指针右移，直到所遇到的数和前一个不一样时，记录该数的个数，right-left，同时将左指针移到右指针的位置，开始进行新的一轮判断；
注意事项，同时题目给的额数为n，我们只需要进行n-1次循环遍历可以；
class Solution{public String countAndSay(int n) {String ret = "1";for(int i = 1; i < n; i++) // 解释 n - 1 次 ret 即可{StringBuilder tmp = new StringBuilder();int len = ret.length();for(int left = 0, right = 0; right < len; ){while(right < len && ret.charAt(left) == ret.charAt(right)) right++;tmp.append(Integer.toString(right - left));tmp.append(ret.charAt(left));left = right;}ret = tmp.toString();}return ret;} }
ps：本次的内容就到这里了，如果大家感兴趣的话，就请一键三连哦！！！