我要评论
c代码：滑动窗口、字符串异位段
// 此题是 字母异位词 的进阶题；字符串异位段
// 1、创建words的哈希表，记录word、次数、下标idx（对比438，相当于是判断哈希数组相等！）
// 2、类比判断哈希数组相等的条件：遍历每一个str，str出现在words中，次数相等，窗口的长度与words所有串的长度相等！
// 3、str不出现在words中，l右移一个step，清空hash，重新开始；
// 4、hash[idx] > cnt 滑动窗口左移；
typedef struct {
char *str;
int cnt;
int idx;
ut_hash_handle hh;
} hashtable;
hashtable* addhash(char **words, int wordssize) {
hashtable* head = null;
hashtable* out = null;
for (int r = 0; r < wordssize; r++) {
hash_find_str(head, words[r], out);
if(null == out) {
out = (hashtable*)malloc(sizeof(hashtable));
out->str = words[r];
out->cnt = 1;
out->idx = r;
hash_add_str(head, str, out);
} else {
out->cnt++;
}
}
return head;
}
int* findsubstring(char * s, char** words, int wordssize, int* returnsize){
int step = strlen(words[0]); // words的字符串长度相等
int lenhash = step * wordssize;
int lens = strlen(s);
int* arr = (int *)malloc(sizeof(int) * lens);
int* hash = (int*)malloc(sizeof(int) * wordssize);
int k = 0;
hashtable* head = addhash(words, wordssize); // 构造哈希
hashtable* out = null;
for (int i = 0; i < step; ++i) { // 窗口左侧步进是一个step，所以要遍历一个step里面的左右起点
int l = i;
memset(hash, 0, sizeof(int) * wordssize);
for (int r = i; r < lens; r += step) { // 窗口右侧一个步进、一个步进前进
char str[step + 1];
str[0] = '\0';
strncat(str, s + r, step); // 截取一个step的字符串、查找
hash_find_str(head, str, out);
if(null == out) { // 未找到，就得重新归零、重新开始，移至下一个元素开头
memset(hash, 0, sizeof(int) * wordssize); // 用hash数组代替uthash的增删；
l = r + step; // hash数组：滑动窗口中个字符串出现的次数!
} else { // 窗口中的截取串str在words中出现了，窗口内左侧的子串一定是出现在words里面的！
int idx = out->idx;
int cnt = out->cnt;
hash[idx]++; // 统计str出现的次数，hash为words的字符串各自出现在窗口中的次数；
while(hash[idx] > cnt) { // 在满足条件的结果中：一个word的次数少了，必定导致另外一个word的次数多了
char str1[step + 1];
str1[0] = '\0';
strncat(str1, s + l, step);
hash_find_str(head, str1, out);
hash[out->idx]--;
l += step;
}
if (r - l + step == lenhash) { // 窗口匹配后、窗口左侧右移一个step，并hash[idx]--;
arr[k++] = l; // 记录ans结果
char str1[step + 1];
str1[0] = '\0';
strncat(str1, s + l, step);
hash_find_str(head, str1, out);
hash[out->idx]--;
l += step;
}
}
}
}
*returnsize = k;
return arr;
}
c代码：失败案例：哈希表保存重复出现
typedef struct {
char *str;
int cnt;
int idx;
ut_hash_handle hh;
} hashtable;
hashtable* addhash(char **words, int wordssize) {
hashtable* head = null;
hashtable* out = null;
for (int r = 0; r < wordssize; r++) {
hash_find_str(head, words[r], out);
if(null == out) {
out = (hashtable*)malloc(sizeof(hashtable));
out->str = words[r];
out->cnt = 1;
out->idx = r;
hash_add_str(head, str, out);
} else {
out->cnt++;
}
}
return head;
}
int* findsubstring(char * s, char** words, int wordssize, int* returnsize){
int step = strlen(words[0]);
int lenhash = step * wordssize;
int lens = strlen(s);
int* arr = (int *)malloc(sizeof(int) * lens);
int* hash = (int*)malloc(sizeof(int) * wordssize);
int k = 0;
hashtable* head = addhash(words, wordssize);
hashtable* out = null;
for (int i = 0; i < step; ++i) { // 遍历初始节点
int l = i;
memset(hash, 0, sizeof(int) * wordssize);
for (int r = i; r < lens; r += step) { // 从初始节点开始，一段一段遍历
char str[step + 1];
strncpy(str, s + r, step);
hash_find_str(head, str, out);
if(null == out) { // 未找到，就得重新归零、重新开始，移至下一个元素开头
memset(hash, 0, sizeof(int) * wordssize); // 用hash数组代替uthash的增删；
l = r + step; // hash数组：滑动窗口中个字符串出现的次数!
} else {
int idx = out->idx;
int cnt = out->cnt;
hash[idx]++; // 下标出现过、hash[idx]次数
while(hash[idx] > cnt) { // 经典的滑动窗口套路，滑动窗口中个字符串出现的次数 > uthash中该字符串出现的次数
char str1[step + 1]; // 窗口就应该收缩左边！直到窗口中字符串次数满足uthash的
strncpy(str1, s + l, step);
hash_find_str(head, str1, out);
hash[out->idx]--;
l += step;
}
if (r + step - l == lenhash) { // 窗口匹配后、l右移1个step，并hash[idx]--;
arr[k++] = l; // 记录结果，l并左移一个step；
char str1[step + 1];
strncpy(str1, s + l, step);
hash_find_str(head, str1, out);
hash[out->idx]--;
l += step;
}
}
}
}
*returnsize = k;
return arr;
}
发表评论