3. 无重复字符的最长子串
给定一个字符串 s ,请你找出其中不含有重复字符的 最长
子串的长度。
示例 1:
输入: s = "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc",所以其长度为 3。
示例 2:
输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b",所以其长度为 1。
示例 3:
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke",所以其长度为 3。
请注意,你的答案必须是 子串 的长度,"pwke" 是一个子序列,不是子串。
提示:
0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成
题解
使用滑动窗口法即可解决,关键在于如何确定如何修改窗口边界
具体代码如下:
#include <stdio.h>
#include <string.h>
int max(int a,int b){
return a>b?a:b;
}
int lengthOfLongestSubstring(char* s) {
int char_index[128];
memset(char_index, -1, sizeof(char_index)); // 初始化为 -1
// 初始化滑动窗口的左边界
int left = 0;
// 初始化最长子串的长度
int max_length = 0;
for (int right = 0; s[right] != '\0'; right++) {
// 如果字符已经在数组中,并且它的索引大于等于左边界,更新左边界
if (char_index[s[right]] >= left) {
left = char_index[s[right]] + 1;
}
// 更新字符的索引
char_index[s[right]] = right;
// 更新最长子串的长度
max_length = (right - left + 1) > max_length ? (right - left + 1) : max_length;
}
return max_length;
}
这段代码实现了求解给定字符串 s 中不含重复字符的最长子串的长度。让我详细解释一下它的思路:
滑动窗口:这个算法使用了滑动窗口的思想。滑动窗口是一个固定大小的窗口,可以在字符串上滑动,以便处理连续的子串。
字符索引数组:代码中定义了一个名为 char_index 的整数数组,用于存储每个字符在字符串中的最新索引位置。初始时,所有元素都被设置为 -1。
左指针和右指针:我们使用两个指针 left 和 right 来构建滑动窗口。初始时,left 和 right 都指向字符串的开头。
遍历字符串:我们遍历字符串 s,从左到右,处理每个字符。
更新左指针:
如果字符 s[right] 已经在 char_index 数组中,并且它的索引大于等于 left,说明窗口内有重复字符。
此时,我们将 left 更新为 char_index[s[right]] + 1,即将左指针移动到重复字符的下一个位置,以消除重复。
更新字符索引:将 char_index[s[right]] 更新为 right,表示字符 s[right] 最新出现的位置。
更新最长子串长度:计算当前窗口的长度 (right - left + 1),并将其与 max_length 比较,取较大值作为最长子串的长度。
右指针右移:将右指针 right 向右移动一位,继续处理下一个字符。
返回最长子串长度:最终返回 max_length,即不含重复字符的最长子串的长度。
这样,代码通过维护一个滑动窗口和字符索引数组,有效地找到了不含重复字符的最长子串的长度。
该代码值得学习的是用s[right]是否等于'\0'来判断是否到了数组末尾,避免了使用strlen计算数组的长度,然后使用?:来比较大小,省去了写max函数
30. 串联所有单词的子串
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
例如,如果 words = ["ab","cd","ef"], 那么 "abcdef", "abefcd","cdabef", "cdefab","efabcd", 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串,因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
示例 1:
输入:s = "barfoothefoobarman", words = ["foo","bar"]
输出:[0,9]
解释:因为 words.length == 2 同时 words[i].length == 3,连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。
示例 2:
输入:s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出:[]
解释:因为 words.length == 4 并且 words[i].length == 4,所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。
示例 3:
输入:s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出:[6,9,12]
解释:因为 words.length == 3 并且 words[i].length == 3,所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。
提示:
1 <= s.length <= 104
1 <= words.length <= 5000
1 <= words[i].length <= 30
words[i] 和 s 由小写英文字母组成
题解
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 函数功能:在字符串 s 中查找所有可以由 words 数组中的单词串联形成的子串的起始位置
// 参数说明:
// s: 输入的字符串
// words: 字符串数组,存储要匹配的单词
// wordsSize: words 数组中单词的数量
// returnSize: 输出参数,存储结果数组的大小
// 返回值:指向存储结果的整数数组的指针
int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize) {
*returnSize = 0;
if (wordsSize == 0) return NULL;
int one_word_len = strlen(words[0]);
int word_num = wordsSize;
int all_len = one_word_len * word_num;
int s_len = strlen(s);
if (s_len < all_len) return NULL;
char temp[one_word_len + 1]; // 临时存储截取的子串
int *local = (int *)malloc(sizeof(int) * s_len); // 存储结果的整数数组
int flag[wordsSize]; // 标记单词是否被查到
int i = 0, j, res, k;
while (i + all_len <= s_len) {
for (int m = 0; m < wordsSize; m++) flag[m] = 0;
// 通过滑动窗口的方式截取长度为 wordLen * wordsCount 的子串
for (j = i; j < i + all_len; j += one_word_len) {
strncpy(temp, s + j, one_word_len);
temp[one_word_len] = '\0'; // 注意:将字符数组末尾设置为 '\0'
res = 0; // 标记该单词在 words 中是否被查到
for (k = 0; k < wordsSize; k++) {
if (flag[k] == 1) continue;
if (strcmp(temp, words[k]) == 0) {
flag[k] = 1;
res = 1;
break;//找到了
}
}
-.3
31
if (res == 0) break;//没找到
}
if (res == 1) {
local[(*returnSize)++] = i; // 将子串的起始索引保存到结果数组中
}
i++;
}
return local;
}
int main() {
char s[] = "barfoothefoobarman";
char *words[] = {"foo", "bar"};
int wordsSize = 2;
int returnSize;
int *result = findSubstring(s, words, wordsSize, &returnSize);
printf("Result: ");
for (int i = 0; i < returnSize; i++) {
printf("%d ", result[i]);
}
return 0;
}