网站百度不到验证码怎么办啊怎么样制作微信小程序

当前位置： 首页 > news >正文

网站百度不到验证码怎么办啊,怎么样制作微信小程序,网站跳转怎么解释,上海网站开发工程师1.问题描述 给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的 异位词的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。 示例1 输入: s cbaebabacd, p abc 输出: [0,6] 解释: 起始索引等于 0 的子串是 cba, 它是 …1.问题描述 给定两个字符串 s 和 p找到 s 中所有 p 的 异位词的子串返回这些子串的起始索引。不考虑答案输出的顺序。 示例1 输入: s cbaebabacd, p abc 输出: [0,6] 解释: 起始索引等于 0 的子串是 cba, 它是 abc 的异位词。 起始索引等于 6 的子串是 bac, 它是 abc 的异位词。 示例2  输入: s abab, p ab 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 ab, 它是 ab 的异位词。 起始索引等于 1 的子串是 ba, 它是 ab 的异位词。 起始索引等于 2 的子串是 ab, 它是 ab 的异位词。 提示 1 s.length, p.length 3 * 104s 和 p 仅包含小写字母 难度等级 中等 题目链接 找到字符串中所有字母异位词 2.解题思路 这道题要我们找出s字符串中p的所有字母异位词首先我们可以知道的就是既然是要找p的字母异位词那我们从s中找的子串长度就必须和p一样那么我们也就可以向排除一些情况那就是如果s的长度比p的长度还小那s中就不可能有p的字母异位词了。 //获取字符串的长度int sLength s.length();//窗口大小int pLength p.length();//如果s的长度小于p的长度s中不可能有p的字母异位词if(sLength pLength){return new ArrayList();} 接着因为p的长度是固定的我们要在s中寻找p长度的子串如果了解过滑动窗口的人很容易就可以想到我们可以用滑动窗口来寻找s中是p的字母异位词的子串窗口的大小就是p的长度。 由于字母异位词字符随便排序的问题我们无法通过正常的比较来判断我们找到的子串是否为p的字母异位词但是字母异位词无序但字母个数一定的这个特点给我们提供了突破口。我们可以通过比较p中各个字符出现的次数是否与我们在s中找到的子串的字符个数相等是的话我们找到的子串就是那个排序可能与p不同的字母异位词了。 解决了如何找到字母异位词的思路之后我们还有解决的一个问题就是用什么来存储字符出现个数的问题。我想大家对key-value的数据类型应该不陌生吧我们可以使用key-value的结果来存储字符出现的个数从而实现O(1)时间复杂度的增加和修改。提到key-value类型大部分人应该第一时间就能想到用hashMap来存储。但是在这道题里面可以不用hashMap来存储可以直接使用数组来存储即可。由于题目告诉我们s和p仅包含小写字母也就数说顶天了也就只有26个字符而且它们的ASCII码都是连续的所以我们可以将字符减去第一个小写字母a的ASCII码就可以将它们与数组的索引按顺序匹配起来所以我们可以只有数据就来实现26个小写字母的key-value的统计。 //初始化两个数组用于存储字母出现的次数int[] sArr new int[26];int[] pArr new int[26];创建完两个用于统计的数组之后我们就可以开始初始化这两个数组了。将p从所有出现的字符统计到pArr(统计p的数组)中,并将s中前pLength(窗口大小)个字符统计到sArr(统计s子串的字符)中这样我们就实现了两个统计数组的初始化了。我们再定义一个List集合用于存储所有的结果我们的准备工作就做完了。 //存储异位词子串起始索引ListInteger data new ArrayList();//初始化两个数组(统计p中的字符个数并且统计s的前pLength个字符的个数)for(int i 0;i pLength;i){sArr[s.charAt(i) - a];pArr[p.charAt(i) - a];} 接着我们就可以来开始遍历s字符串了因为我们已经统计了一部分字符串所以我们可以先比较当前窗口中的子串是否和p是字母异位词,比较两个数组中各个字符的数量是否相等是的话则将窗口的起始索引(当前索引-窗口大小)存入List集合中。比较完之后窗口开始向当前索引滑动减去统计数组中窗口左边界的字符次数,因为它被滑出了不在窗口之内了然后再加上当前索引的字符的次数因为窗口滑动后将它包含在内了。 //比较两个窗口中字符出现的个数是否相等是则为字母异位词if(Arrays.equals(sArr,pArr)){//i-窗口大小即为起始索引data.add(i - pLength);}//移动窗口,减去移动前左边界的字符sArr[s.charAt(i-pLength) - a]–;//加上移动后右边界的字符sArr[s.charAt(i) - a]; 不断的重复上述操作知道窗口滑到s字符串的最右边为止。 退出循环之后最后比较一下窗口中的子串是否为p的字母异位词因为最后一次滑动之后不会再进入循环所以最后一次滑动没有去判断是否为字母异位词要给它不上。 //最后再比较一次是否是字母异位词if(Arrays.equals(sArr,pArr)){data.add(sLength - pLength);} 补上最后一次判断之后就可以直接返回结果了。 3.代码展示 class Solution {public ListInteger findAnagrams(String s, String p) {//获取字符串的长度int sLength s.length();//窗口大小int pLength p.length();//如果s的长度小于p的长度s中不可能有p的字母异位词if(sLength pLength){return new ArrayList();}//初始化两个数组用于存储字母出现的次数int[] sArr new int[26];int[] pArr new int[26];//存储异位词子串起始索引ListInteger data new ArrayList();//初始化两个数组(统计p中的字符个数并且统计s的前pLength个字符的个数)for(int i 0;i pLength;i){sArr[s.charAt(i) - a];pArr[p.charAt(i) - a];} //开始遍历(从pLength开始)for(int i pLength;i sLength;i){//比较两个窗口中字符出现的个数是否相等是则为字母异位词if(Arrays.equals(sArr,pArr)){//i-窗口大小即为起始索引data.add(i - pLength);}//移动窗口,减去移动前左边界的字符sArr[s.charAt(i-pLength) - a]–;//加上移动后右边界的字符sArr[s.charAt(i) - a];}//最后再比较一次是否是字母异位词if(Arrays.equals(sArr,pArr)){data.add(sLength - pLength);}return data;}} 4.总结 这道题的难点主要在于能不能想到用字符的个数是否相等来判断是否为字母异位词至于用什么数据结构来存储字母的个数其实都可以只是用数组比直接用hashMap更加节省空间罢了直接用hashMap也可以解决这道题差别不是很大。好了今天这道题就啰嗦到这里了祝大家早日拿到offer!