C语言 | Leetcode C语言题解之第30题串联所有单词的子串

题目:

题解:

typedef struct {
    char key[32];
    int val;
    UT_hash_handle hh;
} HashItem;

int* findSubstring(char * s, char ** words, int wordsSize, int* returnSize){    
    int m = wordsSize, n = strlen(words[0]), ls = strlen(s);
    int *res = (int *)malloc(sizeof(int) * ls);
    int pos = 0;
    for (int i = 0; i < n; i++) {
        if (i + m * n > ls) {
            break;
        }
        HashItem *diff = NULL;
        char word[32] = {0};
        for (int j = 0; j < m; j++) {
            snprintf(word, n + 1, "%s", s + i + j * n);
            HashItem * pEntry = NULL;
            HASH_FIND_STR(diff, word, pEntry);
            if (NULL == pEntry) {
                pEntry = (HashItem *)malloc(sizeof(HashItem));
                strcpy(pEntry->key, word);
                pEntry->val = 0;
                HASH_ADD_STR(diff, key, pEntry);
            } 
            pEntry->val++;            
        }
        for (int j = 0; j < m; j++) {
            HashItem * pEntry = NULL;
            HASH_FIND_STR(diff, words[j], pEntry);
            if (NULL == pEntry) {
                pEntry = (HashItem *)malloc(sizeof(HashItem));
                strcpy(pEntry->key, words[j]);
                pEntry->val = 0;
                HASH_ADD_STR(diff, key, pEntry);
            } 
            pEntry->val--;
            if (pEntry->val == 0) {
                HASH_DEL(diff, pEntry);
                free(pEntry);
            }
        }
        for (int start = i; start < ls - m * n + 1; start += n) {
            if (start != i) {
                char word[32];
                snprintf(word, n + 1, "%s", s + start + (m - 1) * n);
                HashItem * pEntry = NULL;
                HASH_FIND_STR(diff, word, pEntry);
                if (NULL == pEntry) {
                    pEntry = (HashItem *)malloc(sizeof(HashItem));
                    strcpy(pEntry->key, word);
                    pEntry->val = 0;
                    HASH_ADD_STR(diff, key, pEntry);
                } 
                pEntry->val++;
                if (pEntry->val == 0) {
                    HASH_DEL(diff, pEntry);
                    free(pEntry);
                }
                snprintf(word, n + 1, "%s", s + start - n);
                pEntry = NULL;
                HASH_FIND_STR(diff, word, pEntry);
                if (NULL == pEntry) {
                    pEntry = (HashItem *)malloc(sizeof(HashItem));
                    strcpy(pEntry->key, word);
                    pEntry->val = 0;
                    HASH_ADD_STR(diff, key, pEntry);
                } 
                pEntry->val--;
                if (pEntry->val == 0) {
                    HASH_DEL(diff, pEntry);
                    free(pEntry);
                }
            }
            if (HASH_COUNT(diff) == 0) {
                res[pos++] = start;
            }
        }
        HashItem *curr, *tmp;
        HASH_ITER(hh, diff, curr, tmp) {
            HASH_DEL(diff, curr);  
            free(curr);      
        }
    }
    *returnSize = pos;
    return res;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/547305.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【测试开发学习历程】python常用的模块(中)

目录 5 time模块 5.1、Python中的四种格式的时间&#xff1a; 5.2、time模块中的常用函数 6 I/O流操作 6.1 创建文件 6.2 读取一个文件存入到另外一个文件 6.3 with open as 结构 6.4 open和with open as的区别 7 Excel的操作模块-openpyxl 7.1、新建Excel文件进行读…

11.范式与反范式设计

范式 1.问题 MySQL的库表设计&#xff0c;在很多时候我们都是率性而为&#xff0c;往往在前期的设计中考虑不全面&#xff0c;同时对于库表结构的划分也并不明确&#xff0c;所以很多时候在开发过程中&#xff0c;代码敲着敲着会去重构某张表结构&#xff0c;甚至大面积重构多…

bestvike 资料 --Spring Boot 2.5.0

Spring Boot 2.5.0 SSM环境搭建 springspringmvcmybatisspring springmvc mybatis # 项目 - 需求分析 概要设计(库表设计) 详细设计(验证库表正确性) 编码(环境搭建业务代码) 测试 部署上线# 员工添加 查询所有功能 SSM - 库表 库: ssm 数据库:mysql 表: id na…

spring-cloud微服务gateway

核心部分&#xff1a;routes(路由)&#xff0c; predicates(断言)&#xff0c;filters(过滤器) id&#xff1a;可以理解为是这组配置的一个id值&#xff0c;请保证他的唯一的&#xff0c;可以设置为和服务名一致 uri&#xff1a;可以理解为是通过条件匹配之后需要路由到&…

RabbbitMQ基本使用及其五种工作模型

初识MQ 同步通讯和异步通讯 什么是同步通讯呢&#xff1f;举个例子&#xff0c;你认识了一个小姐姐&#xff0c;聊的很火热&#xff0c;于是你们慢慢开始打电话&#xff0c;视频聊天&#xff0c;这种方式就成为同步通讯&#xff0c;那什么是一部通讯呢&#xff0c;同样的&…

gitlab(docker)安装及使用

GitLab GitLab 是一个用于仓库管理系统的开源项目&#xff0c;使用Git作为代码管理工具&#xff0c;并在此基础上搭建起来的Web服务。 下载(docker) 查询docker镜像gitlab-ce gitlab-ce是它的社区版 [rootlocalhost ~]# docker search gitlab-ce NAME …

OpenCV基本图像处理操作(六)——直方图与模版匹配

直方图 cv2.calcHist(images,channels,mask,histSize,ranges) images: 原图像图像格式为 uint8 或 float32。当传入函数时应 用中括号 [] 括来例如[img]channels: 同样用中括号括来它会告函数我们统幅图 像的直方图。如果入图像是灰度图它的值就是 [0]如果是彩色图像 的传入的…

SETR——Rethinking系列工作,展示使用纯transformer在语义分割任务上是可行的,但需要很强的训练技巧

题目:Rethinking Semantic Segmentation from a Sequence-to-Sequence Perspective with Transformers 作者: 开源:https://fudan-zvg.github.io/SETR 1.研究背景 1.1 为什么要研究这个问题? 自[ 36 ]的开创性工作以来,现有的语义分割模型主要是**基于全卷积网络( FCN )的…

ubuntu20.04安装+ros-noetic安装+内网穿透frp

刷机后的系统安装 ubuntu20.04安装安装ros-noetic安装各种必要的插件安装vscode内网穿透连接实验室主机配置frpc和frps文件运行完成自动化部署免密登录linux的免密登录windows上的免密登录 内网穿透的参考链接&#xff1a;如何优雅地访问远程主机&#xff1f;SSH与frp内网穿透配…

Python学习笔记 - 正则表达式

前言 正则表达式&#xff08;Regular Expression&#xff0c;在代码中常简写为 regex、regexp、RE 或 re&#xff09;是预先定义好的一个“规则字符串”&#xff0c;通过这个“规则字符串”可以匹配、查找、替换那些符合“规则”的文本&#xff0c;也就是说正则表达式针对的目标…

MSTP/RSTP的保护功能

目录 原理概述 实验目的 实验内容 实验拓扑 1.配置RSTP/MSTP 2.配置BPDU保护 3.配置根保护 4.配置环路保护 5.配置TC-BPDU保护 原理概述 在RSTP或MSTP交换网络中&#xff0c;为了防止恶意攻击或临时环路的产生&#xff0c;可配置保护功能来增强网络的健壮性和安全性。…

C++vector类(个人笔记)

vector类 1.熟悉vector接口以及使用1.1vector的定义1.2vector迭代器使用1.3vector空间增长1.4vector增删查改1.5vector迭代器失效问题&#xff08;重点&#xff09; 2.vector的一些笔试题3.模拟实现vector 1.熟悉vector接口以及使用 vector的C官网文档 1.1vector的定义 (con…

用python快速读取大文件几个GB以上的csv数据文件

用python快速读取大文件几个GB以上的csv数据文件 遇到几个GB的csv大文件,用python读取时,可以通过next()函数一行行来读取以提高效率,然后分批量进行处理。 1、文件格式例图 其中第一、第二行是数据行数、列数汇总。 2、流程 1、把csv第一、第二行的数据说明,先读取出来…

Windows远程桌面连接虚拟机Linux

Windows远程桌面连接虚拟机Linux 需要先打开虚拟机的启用VNC连接使用VNC客户端进行连接 yum install -y tigervnc-server #安装tigervnc-server vncserver #启动一个vnc进程 #第一次启动会要求设置密码 #如果需要更改密码可以使用vncpasswd进行更改密码 vncserver -list #查看…

ASUS华硕ROG幻13笔记本电脑GV301R工厂模式原厂OEM预装Windows11系统,恢复出厂开箱状态

适用于型号&#xff1a;GV301RC、GV301RE、GV301RA 工厂模式安装包&#xff1a;https://pan.baidu.com/s/1gLme1VqidpUjCLocgm5ajQ?pwddnbk 提取码&#xff1a;dnbk 工厂模式Win11安装包带有ASUS RECOVERY恢复功能、自带所有驱动、出厂主题壁纸、系统属性专属联机支持标志…

java算法day55 | 动态规划part16 ● 583. 两个字符串的删除操作 ● 72. 编辑距离

583. 两个字符串的删除操作 思路&#xff1a; 和1143.最长公共子序列这道题思路相同&#xff0c;只不过需要对return的数据做一些操作。 class Solution {public int minDistance(String word1, String word2) {int[][] dpnew int[word1.length()1][word2.length()1];for(int …

06_定时器中断

72分频 72MHz 72000000 经过72分频 1000000

【攻防世界】ics-07

<?php session_start();if (!isset($_GET[page])) {show_source(__FILE__);die(); }if (isset($_GET[page]) && $_GET[page] ! index.php) {include(flag.php); }else {header(Location: ?pageflag.php); } <?phpif ($_SESSION[admin]) {$con $_POST[con];$…

可溶性PFA材质三角漏斗耐腐蚀进口聚四氟乙烯漏斗低溶出析出

PFA全名为可溶性聚四氟乙烯、全氟烷氧基树脂&#xff0c;成品外观透明可视&#xff0c;便于观察&#xff0c;有着良好的化学稳定性、耐温性&#xff0c;耐受强酸强碱以及各种有机溶剂&#xff0c;且PFA原料本身较为洁净&#xff0c;金属离子溶出析出少&#xff0c;经过清洗后可…

OpenCV——SUSAN边缘检测

目录 一、SUSAN算法二、代码实现三、结果展示 OpenCV——SUSAN边缘检测由CSDN点云侠原创&#xff0c;爬虫自重。如果你不是在点云侠的博客中看到该文章&#xff0c;那么此处便是不要脸的爬虫。 一、SUSAN算法 Susan边缘检测是一种经典的边缘检测算&#xff0c;它由Susan Smith…