LeetCode刷题实战438:找到字符串中所有字母异位词
2023-03-15 23:22:32 时间
算法的重要性,我就不多说了吧,想去大厂,就必须要经过基础知识和业务逻辑面试+算法面试。所以,为了提高大家的算法能力,这个公众号后续每天带大家做一道算法题,题目就从LeetCode上面选 !
今天和大家聊的问题叫做 找到字符串中所有字母异位词,我们先来看题面:
https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/
Given two strings s and p, return an array of all the start indices of p's anagrams in s. You may return the answer in any order. An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.
给定两个字符串 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" 的异位词。
解题
class Solution {
public List<Integer> findAnagrams(String s, String p) {
char[] arrS = s.toCharArray();
char[] arrP = p.toCharArray();
// 接收最后返回的结果
List<Integer> ans = new ArrayList<>();
// 定义一个 needs 数组来看 arrP 中包含元素的个数
int[] needs = new int[26];
// 定义一个 window 数组来看滑动窗口中是否有 arrP 中的元素,并记录出现的个数
int[] window = new int[26];
// 先将 arrP 中的元素保存到 needs 数组中
for (int i = 0; i < arrP.length; i++) {
needs[arrP[i] - 'a'] += 1;
}
// 定义滑动窗口的两端
int left = 0;
int right = 0;
// 右窗口开始不断向右移动
while (right < arrS.length) {
int curR = arrS[right] - 'a';
right++;
// 将右窗口当前访问到的元素 curR 个数加 1
window[curR] += 1;
// 当 window 数组中 curR 比 needs 数组中对应元素的个数要多的时候就该移动左窗口指针
while (window[curR] > needs[curR]) {
int curL = arrS[left] - 'a';
left++;
// 将左窗口当前访问到的元素 curL 个数减 1
window[curL] -= 1;
}
// 这里将所有符合要求的左窗口索引放入到了接收结果的 List 中
if (right - left == arrP.length) {
ans.add(left);
}
}
return ans;
}
}
好了,今天的文章就到这里,如果觉得有所收获,请顺手点个在看或者转发吧,你们的支持是我最大的动力 。
相关文章
- 从本体论开始说起——运营商关系图谱的构建及应用
- 如何成为一名数据科学家?
- 从未见过的堂兄杀了人,你的DNA是关键证据
- 20个安全可靠的免费数据源,各领域数据任你挑
- 20个安全可靠的免费数据源,各领域数据任你挑
- 阿里云李飞飞:All in Cloud时代,云原生数据库优势明显
- 基于Hadoop生态系统的一高性能数据存储格式CarbonData(性能篇)
- 大数据告诉你:10年漫威,到底有多少角色
- TigerGraph:实时图数据库助力金融风控升级
- Splunk利用Splunk Connected Experiences和Splunk Business Flow 扩大数据访问
- 大数据开发常见的9种数据分析手段
- 以免在景区看人,我爬了5W条全国景点门票数据...
- 【实战解析】基于HBase的大数据存储在京东的应用场景
- 数据科学家告诉你哪些计算机科学书籍是你应该看的
- Kafka作为大数据的核心技术,你了解多少?
- Spring Boot 整合 Redis 实现缓存操作
- 大数据学习必须掌握的五大核心技术有哪些?
- 基于Antlr在Apache Flink中实现监控规则DSL化的探索实践
- 甲骨文再次被Gartner评为分析型数据管理解决方案魔力象限领导者
- 爬取吴亦凡微博102118条转发数据,扒一扒流量的真假