免費做ppt的網(wǎng)站有哪些濟寧seo公司
題目
給定兩個字符串 s
和 p
,找到 s
中所有 p
的異位詞的子串,返回這些子串的起始索引。不考慮答案輸出的順序。
異位詞指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 1:
- 輸入:
s = "cbaebabacd"
,p = "abc"
- 輸出:
[0, 6]
- 解釋:
- 起始索引等于 0 的子串是
"cba"
,它是"abc"
的異位詞。 - 起始索引等于 6 的子串是
"bac"
,它是"abc"
的異位詞。
- 起始索引等于 0 的子串是
示例 2:
- 輸入:
s = "abab"
,p = "ab"
- 輸出:
[0, 1, 2]
- 解釋:
- 起始索引等于 0 的子串是
"ab"
,它是"ab"
的異位詞。 - 起始索引等于 1 的子串是
"ba"
,它是"ab"
的異位詞。 - 起始索引等于 2 的子串是
"ab"
,它是"ab"
的異位詞。
- 起始索引等于 0 的子串是
提示:
1 <= s.length, p.length <= 3 * 10^4
s
和p
僅包含小寫字母
代碼
完整代碼
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int* 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']++;}
}
窗口移動
每次移動窗口時,更新窗口的字符頻率,然后繼續(xù)比較。
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)
,只需要兩個固定大小的哈希表來記錄字符頻率。
結果
一題多解
雙指針法
雙指針法思路分析
使用雙指針來維護一個滑動窗口,其中一個指針表示窗口的起始位置,另一個指針表示窗口的結束位置。通過計數(shù)器來記錄當前窗口內的字符頻率。
具體步驟:
- 初始化兩個指針
left
和right
,以及一個計數(shù)器count
。 - 移動
right
指針擴展窗口,并更新計數(shù)器。 - 如果窗口大小等于
p
的長度,則檢查是否是異位詞。 - 如果窗口大小超過
p
的長度,則移動left
指針收縮窗口,并更新計數(shù)器。
雙指針法復雜度分析
- 時間復雜度:
O(n)
,每個字符最多被訪問兩次(一次通過right
指針,一次通過left
指針)。 - 空間復雜度:
O(1)
,只需要固定大小的哈希表和計數(shù)器。
完整代碼
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>int* 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
指針擴展窗口,并更新計數(shù)器。
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
指針收縮窗口,并更新計數(shù)器。
if (right - left == len_p && hash_p[s[left++] - 'a']++ >= 0) {count++;
}
復雜度分析
- 時間復雜度:
O(n)
,每個字符最多被訪問兩次。 - 空間復雜度:
O(1)
,只需要固定大小的哈希表和計數(shù)器。