登录器显的窗口网站怎么做,做空包网站合法吗,企业如何申请网址,站内营销推广的案例题目
给定两个字符串 s 和 p#xff0c;找到 s 中所有 p 的异位词的子串#xff0c;返回这些子串的起始索引。不考虑答案输出的顺序。
异位词指由相同字母重排列形成的字符串#xff08;包括相同的字符串#xff09;。
示例 1:
输入: s cbaebabacd, 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 * 10^4s 和 p 仅包含小写字母
代码
完整代码
#include string.h
#include stdio.h
#include stdlib.h
#include stdbool.hint* findAnagrams(char * s, char * p, int* returnSize) {int len_s strlen(s);int len_p strlen(p);int* result (int*)malloc(len_s * sizeof(int));*returnSize 0;if (len_s len_p) {return result;}int hash_p[26] {0};int hash_s[26] {0};for (int i 0; i len_p; i) {hash_p[p[i] - a];hash_s[s[i] - a];}for (int i 0; i len_s - len_p; i) {if (memcmp(hash_p, hash_s, 26 * sizeof(int)) 0) {result[(*returnSize)] i;}if (i len_p len_s) {hash_s[s[i] - a]--;hash_s[s[i len_p] - a];}}return result;
}思路分析
使用滑动窗口在字符串 s 上检查长度为 len_p 的子串是否是 p 的异位词。使用两个哈希表分别记录 p 和当前窗口内的字符频率。滑动窗口每次移动时更新窗口内字符的频率并与 p 的频率进行比较。
拆解分析
初始化哈希表
首先我们需要记录 p 中每个字符的频率同时记录 s 中前 len_p 个字符的频率。
int hash_p[26] {0};
int hash_s[26] {0};for (int i 0; i len_p; i) {hash_p[p[i] - a];hash_s[s[i] - a];
}滑动窗口检查
通过比较两个哈希表来判断当前窗口是否是 p 的异位词。如果是则将当前窗口的起始索引加入结果。
for (int i 0; i len_s - len_p; i) {if (memcmp(hash_p, hash_s, 26 * sizeof(int)) 0) {result[(*returnSize)] i;}if (i len_p len_s) {hash_s[s[i] - a]--;hash_s[s[i len_p] - a];}
}窗口移动
每次移动窗口时更新窗口的字符频率然后继续比较。
if (i len_p len_s) {hash_s[s[i] - a]--;hash_s[s[i len_p] - a];
}复杂度分析
时间复杂度O(n)其中 n 是字符串 s 的长度。初始化哈希表和滑动窗口移动都只需要遍历 s 一次。空间复杂度O(1)只需要两个固定大小的哈希表来记录字符频率。
结果
一题多解
双指针法
双指针法思路分析
使用双指针来维护一个滑动窗口其中一个指针表示窗口的起始位置另一个指针表示窗口的结束位置。通过计数器来记录当前窗口内的字符频率。
具体步骤
初始化两个指针 left 和 right以及一个计数器 count。移动 right 指针扩展窗口并更新计数器。如果窗口大小等于 p 的长度则检查是否是异位词。如果窗口大小超过 p 的长度则移动 left 指针收缩窗口并更新计数器。
双指针法复杂度分析
时间复杂度O(n)每个字符最多被访问两次一次通过 right 指针一次通过 left 指针。空间复杂度O(1)只需要固定大小的哈希表和计数器。
完整代码
#include string.h
#include stdio.h
#include stdlib.h
#include stdbool.hint* findAnagrams(char * s, char * p, int* returnSize) {int len_s strlen(s);int len_p strlen(p);int* result (int*)malloc(len_s * sizeof(int));*returnSize 0;if (len_s len_p) {return result;}int hash_p[26] {0};for (int i 0; i len_p; i) {hash_p[p[i] - a];}int left 0, right 0, count len_p;while (right len_s) {if (hash_p[s[right] - a]-- 0) {count--;}if (count 0) {result[(*returnSize)] left;}if (right - left len_p hash_p[s[left] - a] 0) {count;}}return result;
}拆解分析
初始化哈希表
记录 p 中每个字符的频率。
int hash_p[26] {0};for (int i 0; i len_p; i) {hash_p[p[i] - a];
}移动右指针
移动 right 指针扩展窗口并更新计数器。
int left 0, right 0, count len_p;while (right len_s) {if (hash_p[s[right] - a]-- 0) {count--;}检查窗口
如果窗口大小等于 p 的长度则检查是否是异位词。
if (count 0) {result[(*returnSize)] left;
}移动左指针
如果窗口大小超过 p 的长度则移动 left 指针收缩窗口并更新计数器。
if (right - left len_p hash_p[s[left] - a] 0) {count;
}复杂度分析
时间复杂度O(n)每个字符最多被访问两次。空间复杂度O(1)只需要固定大小的哈希表和计数器。
结果
