华为OD机试 - 增强的strstr - 滑动窗口（Python/JS/C/C++ 2024 E卷 200分）

2024-09-06 09:20
文章标签 python c++ 200 js 华为 2024 窗口 滑动 增强 strstr od 机试

本文主要是介绍华为OD机试 - 增强的strstr - 滑动窗口（Python/JS/C/C++ 2024 E卷 200分），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

在这里插入图片描述

华为OD机试 2024E卷题库疯狂收录中，刷题点这里

专栏导读

本专栏收录于《华为OD机试真题（Python/JS/C/C++）》。

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

一、题目描述

C语言有一个库函数Q：char *strstr(const char *haystack, const char *needle)，实现在字符串haystack中查找第一次出现字符串needle的位置，如果未找到则返回null。

现要求实现一个fsrstr的增强函数，可以使用带可选字符的字符串来模糊查询，与strstr一样返回首次查找到的字符串位置。
可选段使用中括号[]标识，表示该位置可以选取其中任意一个字符即可满足匹配条件。例如"a[bc]“表示可以匹配"ab"或"ac”。

注意目标字符串中可选段可能出现多个。

二、输入描述

与strstr函数Q一样，输入参数是两个字符指针，分别是源字符串和目标字符串。

三、输出描述

与strstr函数Q不同，返回的是源字符串中，匹配子字符串相对于源字符串地址的偏移（从0开始算），如果没有匹配返回-1。

补充说明： 源字符串中也不会出现[]，目标字符串中[]是成对出现的且非空，且不会出现嵌套。
输入的字符串长度在[1, 100]之间。

四、测试用例

测试用例1：

1、输入

abcd
b[cd]

2、输出

1

3、说明

相当于是在源字符串中查找bc或者bd，bc子字符串相对于abcd的偏移是1。

测试用例2：

1、输入

abcdefg
h[ij]

2、输出

-1

3、说明

目标字符串 tar 是 h[ij]，表示匹配以字符 ‘h’ 开头，接着是字符 ‘i’ 或 ‘j’ 的字符串。

在源字符串 “abcdefg” 中，没有子字符串以字符 ‘h’ 开头。

滑动窗口从源字符串的第一个字符开始滑动，检查长度为 2 的子串，未找到符合条件的子串。

因此，输出结果是 -1，表示目标字符串不在源字符串中。

测试用例3：

1、输入

xyzabc
yza[bc]

2、输出

1

3、说明

目标字符串 tar 是 yza[bc]，表示匹配以字符 ‘y’、‘z’、‘a’ 开头，接着是字符 ‘b’ 或 ‘c’ 的字符串。

在源字符串 “xyzabc” 中，子字符串 “yzab” 从索引 1 开始。

滑动窗口从源字符串的第一个字符开始滑动，检查长度为 5 的子串：

  1. 第一个窗口子串 “xyzab”：不完全匹配目标模式，因为第二个字符 ‘x’ 不符合。
  2. 第二个窗口子串 “yzabc”：完全匹配目标模式。

因此，输出结果是 1。

五、解题思路

1、滑动窗口

滑动窗口（Sliding Window）是一种常见的算法技巧，主要用于在一个列表或数组中找到满足某种条件的子列表或子数组。其核心思想是使用两个指针（通常称为窗口的左端和右端）来定义一个子区间，随着指针的移动，这个区间会“滑动”或“扩展”，从而高效地遍历并处理列表或数组中的元素。

滑动窗口适用于那些要求在连续子数组、子字符串、子区间中进行高效查找、匹配或计算的场景。滑动窗口算法通过避免重复计算，将时间复杂度降低到 O(n) 的量级。

滑动窗口适用哪些场景？

滑动窗口算法适用于以下几类问题：

字符串匹配与查找：如查找一个字符串中的所有异位词、找出最长的无重复子串、实现正则表达式的匹配。

数组的子区间问题：如找到满足某种条件的连续子数组，最大/最小和子数组问题。

固定窗口大小的子数组问题：如在一个数组中查找固定长度的子数组，使其满足某些条件（最大、最小、和等）。

动态窗口调整问题：如找到数组中最短的子数组，其和大于等于给定值。

2、为什么采用滑动窗口？

在本题中，滑动窗口是一个自然的选择，因为我们需要在源字符串 (src) 中找到目标字符串 (tar) 的第一次匹配位置，并且目标字符串可能包含可选字符段（[]内的字符）。

3、具体步骤：

  1. 解析目标字符串：
    • 首先，将目标字符串 tar 解析为多个字符层次（levels），每个层次是一个字符集合（HashSet）。
    • 普通字符直接放入一个单字符集合中。
    • 当遇到一个 [ 时，表示开始一个可选字符段，读取所有在 [] 中的字符，直到遇到 ] 结束，将这些字符放入一个集合中。
  2. 构建模式层次结构：
    • 遍历目标字符串 tar，构建一个字符集合的列表（levels）。这个列表的每个元素是一个字符集合，表示在源字符串 src 中这个位置可以匹配的字符。
    • 例如，对于目标字符串 b[cd]，会被解析为 [[‘b’], [‘c’, ‘d’]]，表示第一位必须是 ‘b’，第二位可以是 ‘c’ 或 ‘d’。
  3. 滑动窗口匹配：
    • 使用滑动窗口的方法在源字符串 src 中查找目标模式。
    • 滑动窗口的长度与目标模式的长度相同，逐步移动窗口并检查每个窗口的子字符串是否与目标模式匹配。
    • 对于每一个窗口位置，我们依次检查源字符串的字符是否在对应的目标字符集合中。
  4. 返回结果：
    • 如果找到匹配，则返回匹配的起始索引。
    • 如果遍历完整个源字符串仍未找到匹配，则返回 -1。

六、Python算法源码

def find_pattern_index(source_string, target_pattern):"""查找目标模式在源字符串中的起始索引。:param source_string: 源字符串:param target_pattern: 包含可选字符的目标模式:return: 目标模式首次匹配的起始索引，如果未找到则返回-1"""# 将目标模式解析为多个字符层次结构，每个层次存储可能匹配的字符集合pattern_levels = []# 当前字符集合用于存储[]中的字符current_set = set()is_within_brackets = False# 解析目标模式for current_char in target_pattern:if current_char == '[':is_within_brackets = True  # 开始读取可选字符段elif current_char == ']':is_within_brackets = False  # 结束读取可选字符段pattern_levels.append(current_set)current_set = set()  # 重置集合else:if is_within_brackets:current_set.add(current_char)  # 添加到当前可选字符集合else:single_char_set = {current_char}pattern_levels.append(single_char_set)  # 添加单个字符作为集合# 调用辅助方法查找匹配索引return find_first_match_index(source_string, pattern_levels)def find_first_match_index(source_string, pattern_levels):"""查找源字符串中首次匹配的索引:param source_string: 源字符串:param pattern_levels: 目标模式解析后的字符集合列表:return: 匹配的起始索引，如果未找到则返回-1"""# 遍历源字符串，使用滑动窗口法查找匹配for i in range(len(source_string) - len(pattern_levels) + 1):is_match_found = True# 检查每一个层次的字符是否匹配for j in range(len(pattern_levels)):if source_string[i + j] not in pattern_levels[j]:is_match_found = Falsebreak  # 如果字符不匹配，退出检查if is_match_found:return i  # 返回匹配的起始索引# 如果未找到匹配，返回-1return -1if __name__ == "__main__":# 使用input读取输入source_string = input("请输入源字符串：")target_pattern = input("请输入目标模式字符串：")# 输出匹配结果result = find_pattern_index(source_string, target_pattern)print(result)

七、JavaScript算法源码

// 主函数
function main() {const readline = require('readline');const rl = readline.createInterface({input: process.stdin,output: process.stdout});rl.question("请输入源字符串：", function(sourceString) {rl.question("请输入目标模式字符串：", function(targetPattern) {// 输出匹配结果const result = findPatternIndex(sourceString, targetPattern);console.log(result);rl.close();});});
}/*** 查找目标模式在源字符串中的起始索引。** @param {string} sourceString - 源字符串* @param {string} targetPattern - 包含可选字符的目标模式* @return {number} 目标模式首次匹配的起始索引，如果未找到则返回-1*/
function findPatternIndex(sourceString, targetPattern) {// 将目标模式解析为多个字符层次结构，每个层次存储可能匹配的字符集合const patternLevels = [];// 当前字符集合用于存储[]中的字符let currentSet = new Set();let isWithinBrackets = false;// 解析目标模式for (let i = 0; i < targetPattern.length; i++) {const currentChar = targetPattern[i];if (currentChar === '[') {isWithinBrackets = true;  // 开始读取可选字符段} else if (currentChar === ']') {isWithinBrackets = false;  // 结束读取可选字符段patternLevels.push(currentSet);currentSet = new Set();  // 重置集合} else {if (isWithinBrackets) {currentSet.add(currentChar);  // 添加到当前可选字符集合} else {const singleCharSet = new Set([currentChar]);patternLevels.push(singleCharSet);  // 添加单个字符作为集合}}}// 调用辅助方法查找匹配索引return findFirstMatchIndex(sourceString, patternLevels);
}/*** 查找源字符串中首次匹配的索引** @param {string} sourceString - 源字符串* @param {Array<Set>} patternLevels - 目标模式解析后的字符集合列表* @return {number} 匹配的起始索引，如果未找到则返回-1*/
function findFirstMatchIndex(sourceString, patternLevels) {// 遍历源字符串，使用滑动窗口法查找匹配for (let i = 0; i <= sourceString.length - patternLevels.length; i++) {let isMatchFound = true;// 检查每一个层次的字符是否匹配for (let j = 0; j < patternLevels.length; j++) {if (!patternLevels[j].has(sourceString[i + j])) {isMatchFound = false;break;  // 如果字符不匹配，退出检查}}if (isMatchFound) {return i;  // 返回匹配的起始索引}}// 如果未找到匹配，返回-1return -1;
}// 调用主函数
main();

八、C算法源码

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <stdbool.h>// 定义最大字符串长度
#define MAX_LEN 101// 函数声明
int findPatternIndex(const char* sourceString, const char* targetPattern);
int findFirstMatchIndex(const char* sourceString, char** patternLevels, int levelCount);
void freePatternLevels(char** patternLevels, int levelCount);int main() {// 定义源字符串和目标字符串char sourceString[MAX_LEN];char targetPattern[MAX_LEN];// 输入源字符串和目标字符串printf("请输入源字符串：");fgets(sourceString, MAX_LEN, stdin);sourceString[strcspn(sourceString, "\n")] = '\0';  // 去除换行符printf("请输入目标模式字符串：");fgets(targetPattern, MAX_LEN, stdin);targetPattern[strcspn(targetPattern, "\n")] = '\0';  // 去除换行符// 查找匹配结果int result = findPatternIndex(sourceString, targetPattern);printf("%d\n", result);return 0;
}/*** 查找目标模式在源字符串中的起始索引。** @param sourceString 源字符串* @param targetPattern 包含可选字符的目标模式* @return 目标模式首次匹配的起始索引，如果未找到则返回-1*/
int findPatternIndex(const char* sourceString, const char* targetPattern) {// 用于存储解析后的字符集合char* patternLevels[MAX_LEN];int levelCount = 0;char currentSet[MAX_LEN] = {0};int currentIndex = 0;bool isWithinBrackets = false;// 解析目标模式for (int i = 0; i < strlen(targetPattern); i++) {char currentChar = targetPattern[i];if (currentChar == '[') {isWithinBrackets = true;  // 开始读取可选字符段currentIndex = 0;  // 重置当前集合索引memset(currentSet, 0, sizeof(currentSet));  // 清空当前集合} else if (currentChar == ']') {isWithinBrackets = false;  // 结束读取可选字符段patternLevels[levelCount] = (char*)malloc((currentIndex + 1) * sizeof(char));strcpy(patternLevels[levelCount], currentSet);  // 保存当前集合levelCount++;} else {if (isWithinBrackets) {currentSet[currentIndex++] = currentChar;  // 添加到当前可选字符集合} else {patternLevels[levelCount] = (char*)malloc(2 * sizeof(char));patternLevels[levelCount][0] = currentChar;patternLevels[levelCount][1] = '\0';  // 添加单个字符作为集合levelCount++;}}}// 查找匹配索引int result = findFirstMatchIndex(sourceString, patternLevels, levelCount);// 释放动态分配的内存freePatternLevels(patternLevels, levelCount);return result;
}/*** 查找源字符串中首次匹配的索引** @param sourceString 源字符串* @param patternLevels 目标模式解析后的字符集合列表* @param levelCount 目标模式解析后的字符集合数量* @return 匹配的起始索引，如果未找到则返回-1*/
int findFirstMatchIndex(const char* sourceString, char** patternLevels, int levelCount) {int sourceLen = strlen(sourceString);// 遍历源字符串，使用滑动窗口法查找匹配for (int i = 0; i <= sourceLen - levelCount; i++) {bool isMatchFound = true;// 检查每一个层次的字符是否匹配for (int j = 0; j < levelCount; j++) {if (strchr(patternLevels[j], sourceString[i + j]) == NULL) {isMatchFound = false;break;  // 如果字符不匹配，退出检查}}if (isMatchFound) {return i;  // 返回匹配的起始索引}}// 如果未找到匹配，返回-1return -1;
}/*** 释放动态分配的内存** @param patternLevels 目标模式解析后的字符集合列表* @param levelCount 目标模式解析后的字符集合数量*/
void freePatternLevels(char** patternLevels, int levelCount) {for (int i = 0; i < levelCount; i++) {free(patternLevels[i]);}
}

九、C++算法源码

#include <iostream>
#include <vector>
#include <set>
#include <string>using namespace std;/*** 查找目标模式在源字符串中的起始索引。** @param sourceString 源字符串* @param targetPattern 包含可选字符的目标模式* @return 目标模式首次匹配的起始索引，如果未找到则返回-1*/
int findPatternIndex(const string& sourceString, const string& targetPattern) {// 用于存储解析后的字符集合vector<set<char>> patternLevels;set<char> currentSet;bool isWithinBrackets = false;// 解析目标模式for (char currentChar : targetPattern) {if (currentChar == '[') {isWithinBrackets = true;  // 开始读取可选字符段currentSet.clear();  // 清空当前集合} else if (currentChar == ']') {isWithinBrackets = false;  // 结束读取可选字符段patternLevels.push_back(currentSet);  // 保存当前集合} else {if (isWithinBrackets) {currentSet.insert(currentChar);  // 添加到当前可选字符集合} else {set<char> singleCharSet = { currentChar };patternLevels.push_back(singleCharSet);  // 添加单个字符作为集合}}}// 调用辅助方法查找匹配索引return findFirstMatchIndex(sourceString, patternLevels);
}/*** 查找源字符串中首次匹配的索引** @param sourceString 源字符串* @param patternLevels 目标模式解析后的字符集合列表* @return 匹配的起始索引，如果未找到则返回-1*/
int findFirstMatchIndex(const string& sourceString, const vector<set<char>>& patternLevels) {int sourceLen = sourceString.length();// 遍历源字符串，使用滑动窗口法查找匹配for (int i = 0; i <= sourceLen - patternLevels.size(); i++) {bool isMatchFound = true;// 检查每一个层次的字符是否匹配for (int j = 0; j < patternLevels.size(); j++) {if (patternLevels[j].find(sourceString[i + j]) == patternLevels[j].end()) {isMatchFound = false;break;  // 如果字符不匹配，退出检查}}if (isMatchFound) {return i;  // 返回匹配的起始索引}}// 如果未找到匹配，返回-1return -1;
}int main() {// 定义源字符串和目标字符串string sourceString;string targetPattern;// 输入源字符串和目标字符串cout << "请输入源字符串：" << endl;getline(cin, sourceString);cout << "请输入目标模式字符串：" << endl;getline(cin, targetPattern);// 查找匹配结果int result = findPatternIndex(sourceString, targetPattern);cout << result << endl;return 0;
}

🏆下一篇：华为OD机试真题 - 简易内存池（Python/JS/C/C++ 2024 E卷 200分）

🏆本文收录于，华为OD机试真题（Python/JS/C/C++）

刷的越多，抽中的概率越大，私信哪吒，备注华为OD，加入华为OD刷题交流群，每一题都有详细的答题思路、详细的代码注释、3个测试用例、为什么这道题采用XX算法、XX算法的适用场景，发现新题目，随时更新，全天CSDN在线答疑。

在这里插入图片描述

这篇关于华为OD机试 - 增强的strstr - 滑动窗口（Python/JS/C/C++ 2024 E卷 200分）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！


http://www.chinasem.cn/article/1141623。

相关文章

JS常用组件收集

JS常用组件收集

收集了一些平时遇到的前端比较优秀的组件，方便以后开发的时候查找！！！ 函数工具： Lodash 页面固定： stickUp、jQuery.Pin 轮播： unslider、swiper 开关: switch 复选框： icheck 气泡： grumble 隐藏元素： Headroom
阅读更多...
python: 多模块(.py)中全局变量的导入

python: 多模块(.py)中全局变量的导入

文章目录 global关键字可变类型和不可变类型数据的内存地址单模块(单个py文件)的全局变量示例总结 多模块(多个py文件)的全局变量from x import x导入全局变量示例 import x导入全局变量示例 总结 global关键字 global 的作用范围是模块(.py)级别： 当你在一个模块（文件）中使用 global 声明变量时，这个变量只在该模块的全局命名空
阅读更多...
【C++ Primer Plus习题】13.4

【C++ Primer Plus习题】13.4

大家好,这里是国中之林! ❥前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站。有兴趣的可以点点进去看看← 问题: 解答: main.cpp #include <iostream>#include "port.h"int main() {Port p1;Port p2("Abc", "Bcc", 30);std::cout <<
阅读更多...
C++包装器

C++包装器

包装器 在 C++ 中，“包装器”通常指的是一种设计模式或编程技巧，用于封装其他代码或对象，使其更易于使用、管理或扩展。包装器的概念在编程中非常普遍，可以用于函数、类、库等多个方面。下面是几个常见的 “包装器” 类型： 1. 函数包装器 函数包装器用于封装一个或多个函数，使其接口更统一或更便于调用。例如，std::function 是一个通用的函数包装器，它可以存储任意可调用对象（函数、函数
阅读更多...
2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题

题库来源：安全生产模拟考试一点通公众号小程序 2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题是由安全生产模拟考试一点通提供，流动式起重机司机证模拟考试题库是根据流动式起重机司机最新版教材，流动式起重机司机大纲整理而成（含2024年流动式起重机司机证模拟考试题库及流动式起重机司机理论考试试题参考答案和部分工种参考解析），掌握本资料和学校方法，考试容易。流动式起重机司机考试技
阅读更多...
C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

C++11第三弹：lambda表达式 | 新的类功能 | 模板的可变参数

🌈个人主页： 南桥几晴秋 🌈C++专栏： 南桥谈C++ 🌈C语言专栏： C语言学习系列 🌈Linux学习专栏： 南桥谈Linux 🌈数据结构学习专栏： 数据结构杂谈 🌈数据库学习专栏： 南桥谈MySQL 🌈Qt学习专栏： 南桥谈Qt 🌈菜鸡代码练习： 练习随想记录 🌈git学习： 南桥谈Git 🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈🌈�
阅读更多...
【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

【专题】2024飞行汽车技术全景报告合集PDF分享（附原数据表）

原文链接： https://tecdat.cn/?p=37628 6月16日，小鹏汇天旅航者X2在北京大兴国际机场临空经济区完成首飞，这也是小鹏汇天的产品在京津冀地区进行的首次飞行。小鹏汇天方面还表示，公司准备量产，并计划今年四季度开启预售小鹏汇天分体式飞行汽车，探索分体式飞行汽车城际通勤。阅读原文，获取专题报告合集全文，解锁文末271份飞行汽车相关行业研究报告。 据悉，业内人士对飞行汽车行业
阅读更多...
【C++】_list常用方法解析及模拟实现

【C++】_list常用方法解析及模拟实现

相信自己的力量，只要对自己始终保持信心，尽自己最大努力去完成任何事，就算事情最终结果是失败了，努力了也不留遗憾。💓💓💓 目录   ✨说在前面 🍋知识点一：什么是list？ •🌰1.list的定义 •🌰2.list的基本特性 •🌰3.常用接口介绍 🍋知识点二：list常用接口 •🌰1.默认成员函数 🔥构造函数（⭐） 🔥析构函数 •🌰2.list对象
阅读更多...
高效录音转文字：2024年四大工具精选！

高效录音转文字：2024年四大工具精选！

在快节奏的工作生活中，能够快速将录音转换成文字是一项非常实用的能力。特别是在需要记录会议纪要、讲座内容或者是采访素材的时候，一款优秀的在线录音转文字工具能派上大用场。以下推荐几个好用的录音转文字工具！ 365在线转文字 直达链接：https://www.pdf365.cn/ 365在线转文字是一款提供在线录音转文字服务的工具，它以其高效、便捷的特点受到用户的青睐。用户无需下载安装任何软件，只
阅读更多...
【Python编程】Linux创建虚拟环境并配置与notebook相连接

【Python编程】Linux创建虚拟环境并配置与notebook相连接

1.创建 使用 venv 创建虚拟环境。例如，在当前目录下创建一个名为 myenv 的虚拟环境： python3 -m venv myenv 2.激活 激活虚拟环境使其成为当前终端会话的活动环境。运行： source myenv/bin/activate 3.与notebook连接 在虚拟环境中，使用 pip 安装 Jupyter 和 ipykernel： pip instal
阅读更多...

Copyright China编程 23002807@qq.com

沪ICP备2023033072号-2