C语言 | Leetcode C语言题解之第336题回文对
题目:

题解:
#define SIZE 9470
#define N 168000
#define P 13331typedef unsigned long long ULL;
ULL p[301];//p[i]存储P^ivoid init()//初始化p进制次幂数组
{int i;p[0]=1;for(i=1;i<300;i++){p[i]=p[i-1]*P;}
}int** palindromePairs(char**words, int wordsSize, int* returnSize, int** returnColumnSizes){int **re=(int **)malloc(sizeof(int *)*N);*returnColumnSizes=(int *)malloc(sizeof(int)*N);int i,j,k;int index=0;int len;int l,r;int hash[SIZE];//存储某字符串hash值在words中的对应下标ULL key[SIZE];//存储字符串hash值,可近似认为字符串与hash值之间是一一对应的ULL t;ULL pre[301];//存储前缀字符串hash值,pre下标从1开始(即pre[i]存储某字符串前i个子字符串的哈希值),注意下标转换char *word=NULL;init();//初始化p数组memset(hash,-1,sizeof(hash));for(i=0;i<wordsSize;i++){t=0;word=words[i];for(j=strlen(word)-1;j>=0;j--)//倒序遍历计算哈希值t{t=t*P+word[j];}//第二层哈希,将hash值及对应下标存入哈希表j=t%SIZE;while(hash[j]!=-1){j=(j+1)%SIZE;}hash[j]=i;key[j]=t;}for(i=0;i<wordsSize;i++){word=words[i];len=strlen(word);pre[0]=0;for(j=0;j<len;j++)//计算前缀哈希值数组{pre[j+1]=pre[j]*P+word[j];}for(j=-1;j<len;j++)//正向查找回文串{for(l=0,r=j;l<r;l++,r--){if(word[l]!=word[r]){break;}}if(l>=r)//下标0-j是一个回文串,查找原字符串数组中是否存在j+1-末尾的翻转字符串{t=pre[len]-pre[j+1]*p[len-j-1];//j+1-末尾子字符串的哈希值k=t%SIZE;while(hash[k]!=-1&&key[k]!=t){k=(k+1)%SIZE;}if(hash[k]>=0&&hash[k]!=i)//找到了且不是自身{re[index]=(int *)malloc(sizeof(int)*2);re[index][0]=hash[k];re[index][1]=i;returnColumnSizes[0][index++]=2;if(words[hash[k]][0]==0)//空字符串,特处{re[index]=(int *)malloc(sizeof(int)*2);re[index][0]=i;re[index][1]=hash[k];returnColumnSizes[0][index++]=2;}}}}for(j=len-1;j>0;j--)//反向查找回文串{for(l=j,r=len-1;l<r;l++,r--){if(word[l]!=word[r]){break;}}if(l>=r)//下标j-末尾子字符串是回文串{t=pre[j];//前j-1个子字符串的hash值k=t%SIZE;while(hash[k]!=-1&&key[k]!=t){k=(k+1)%SIZE;}if(hash[k]>=0&&hash[k]!=i)//找到了且不是自身{re[index]=(int *)malloc(sizeof(int)*2);re[index][0]=i;re[index][1]=hash[k];returnColumnSizes[0][index++]=2;}}}}*returnSize=index;return re;
}相关文章:
C语言 | Leetcode C语言题解之第336题回文对
题目: 题解: #define SIZE 9470 #define N 168000 #define P 13331typedef unsigned long long ULL; ULL p[301];//p[i]存储P^ivoid init()//初始化p进制次幂数组 {int i;p[0]1;for(i1;i<300;i){p[i]p[i-1]*P;} }int** palindromePairs(char**words,…...
【SQL】仅出现一次的最大数据
目录 题目 分析 代码 题目 MyNumbers 表: ------------------- | Column Name | Type | ------------------- | num | int | ------------------- 该表可能包含重复项(换句话说,在SQL中,该表没有主键)。…...
MySQL 数据类型详解及SQL语言分类-DDL篇
在数据库开发中,选择合适的数据类型和理解SQL语言的分类是非常重要的。今天详细介绍MySQL中的数据类型,包括数值类型、字符串类型和日期类型,并解释SQL语言的四大分类:DDL、DML、DQL和DCL。 1.MySQL 数据类型 SQL语言是不区分大…...
Leet Code 128-最长连续序列【Java】【哈希法】
给定一个未排序的整数数组 nums ,找出数字连续的最长序列(不要求序列元素在原数组中连续)的长度。 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 示例 1: 输入:nums [100,4,200,1,3,2] 输出:4 …...
网络协议(概念版)
通讯:首先要得知对方的IP地址。 最终是根据MAC地址(网卡地址),输送数据到网卡,被网卡接收。 如果网卡发现数据的目标MAC地址是自己,就会将数据传递给上一层进行处理;如果目标MAC地址不是自己,…...
Pulsar官方文档学习笔记——消息机制
pulsar 基于3.x最新官方文档学习记录 概念与架构 典型的推送订阅模式。生产者发送消息,消费者订阅topic消费信息并回应ACK。订阅创建后,Pulsar会保留所有消息。仅消息被所有订阅 成功消费了才会丢弃(可以配置消息保留机制保留一定量&#…...
PyTorch--残差网络(ResNet)在CIFAR-10数据集进行图像分类
完整代码 import torch import torch.nn as nn import torchvision import torchvision.transforms as transforms# Device configuration device torch.device(cuda if torch.cuda.is_available() else cpu)# Hyper-parameters num_epochs 80 batch_size 100 learning_rate…...
ETAS工具链自动化实战指南<一>
----自动化不仅是一种技术,更是一种思维方式,它将帮助我们在快节奏的工作环境中保持领先! 目录 往期推荐 场景一:SWC 之间 port自动连接 命令示例 参数说明 场景二:SWC与ECU 自动映射 命令示例 参数说明 场景三&…...
疫情期间我面试了13家企业软件测试岗位,一些面试题整理
项目的测试流程 拿到需求文档后,写测试用例 审核测试用例 等待开发包 部署测试环境 冒烟测试(网页架构图) 页面初始化测试(查看数据库中的数据内容和页面展示的内容是否一致,并且是否按照某些顺序排列)…...
PINCE——Linux 原生游戏内存修改器,一款替代 Cheat Engine 的强大游戏修改器,Linux 游戏玩家必备神器!
PINCE——Linux 原生游戏内存修改器,一款替代 Cheat Engine 的强大游戏修改器,Linux 游戏玩家必备神器! PINCE 是 GNU Project Debugger(GDB) 的前端/反向工程工具,常用作程序调试器,主要用于游戏领域,修改…...
为IntelliJ IDEA安装插件
安装插件 插件是开发工具的扩展程序,通常由第三方提供,当安装了插件后,原开发工作的菜单、按钮等开发环境可能会发生变化,例如出现了新的菜单项,或出现了新的按钮,甚至一些全新的编码方式,通常…...
ES6 Promise
ES6 Promise 对象 一、概述 是异步编程的一种解决方案。 从语法上说,Promise 是一个对象,从它可以获取异步操作的消息。 Promise 状态 状态的特点 Promise 异步操作有三种状态:pending(进行中)、fulfilled(…...
html+css 实现hover 凹陷按钮
前言:哈喽,大家好,今天给大家分享html+css 绚丽效果!并提供具体代码帮助大家深入理解,彻底掌握!创作不易,如果能帮助到大家或者给大家一些灵感和启发,欢迎收藏+关注哦 💕 目录 📚一、效果📚二、原理解析💡1.这是一个,hover时凹陷的效果。每个按钮是一个button…...
什么是负载均衡?负载均衡器如何运作?
往期文章 负载均衡器:LVS、Nginx、HAproxy如何选择? 目录 往期文章什么是负载均衡?为什么需要负载均衡?负载均衡工作原理?静态负载均衡算法动态负载均衡算法 参考 什么是负载均衡? 负载均衡是一种网络技术…...
(Arxiv-2023)潜在一致性模型:通过少步推理合成高分辨率图像
潜在一致性模型:通过少步推理合成高分辨率图像 Paper Title: Latent Consistency Models: Synthesizing High-Resolution Images with Few-Step Inference Paper是清华发表在Arxiv 2023的工作 Paper地址 Code地址 ABSTRACT 潜在扩散模型 (LDM) 在合成高分辨率图像方…...
Unity与UE,哪种游戏引擎适合你?
PlayStation vs Xbox,Mario vs Sonic,Unreal vs Unity?无论是游戏主机、角色还是游戏引擎,人们总是热衷于捍卫他们在游戏行业中的偏爱。 专注于游戏引擎,Unity和Unreal Engine(简称UE4)是目前市…...
这五本大模型书籍,把大模型讲的非常详细,收藏我这一篇就够了
当然可以。在当前的大模型时代,随着自然语言处理(NLP)技术的迅速发展,出现了许多优秀的书籍来帮助读者理解这些复杂的技术。以下是几本值得推荐的大模型书籍,它们涵盖了从基础理论到高级实践的内容,可以帮助…...
伊朗通过 ChatGPT 试图影响美国大选, OpenAI 封禁多个账户|TodayAI
OpenAI 近日宣布,他们已经封禁了一系列与伊朗影响行动有关的 ChatGPT 账户,这些账户涉嫌利用该 AI 工具生成并传播与美国总统选举、以色列 – 哈马斯战争以及奥运会等相关的内容。 OpenAI 表示,这些账户与一个名为 “Storm-2035” 的秘密伊朗…...
windows系统如何走后面之windows系统隐藏账户
系统隐藏账户是一种最为简单有效的权限维持方式,其做法就是让攻击者创建一个新的具有管理员权限的隐藏账户,因为是隐藏账户,所以防守方是无法通过控制面板或命令行看到这个账户的。 自然我们需要一些前提条件,比如说有一个网站&am…...
Elasticsearch(ES)(版本7.x)数据更新后刷新策略RefreshPolicy
Elasticsearch(ES)(版本7.x)数据更新后刷新策略RefreshPolicy 介绍 ES数据写入后,默认1s后才会被搜索到(refresh_interval为1); 这样可能是考虑到性能问题,毕竟实时IO 消耗较多资源 造成的问题 例如一个索引现在有…...
wordpress后台更新后 前端没变化的解决方法
使用siteground主机的wordpress网站,会出现更新了网站内容和修改了php模板文件、js文件、css文件、图片文件后,网站没有变化的情况。 不熟悉siteground主机的新手,遇到这个问题,就很抓狂,明明是哪都没操作错误&#x…...
Vim 调用外部命令学习笔记
Vim 外部命令集成完全指南 文章目录 Vim 外部命令集成完全指南核心概念理解命令语法解析语法对比 常用外部命令详解文本排序与去重文本筛选与搜索高级 grep 搜索技巧文本替换与编辑字符处理高级文本处理编程语言处理其他实用命令 范围操作示例指定行范围处理复合命令示例 实用技…...
对WWDC 2025 Keynote 内容的预测
借助我们以往对苹果公司发展路径的深入研究经验,以及大语言模型的分析能力,我们系统梳理了多年来苹果 WWDC 主题演讲的规律。在 WWDC 2025 即将揭幕之际,我们让 ChatGPT 对今年的 Keynote 内容进行了一个初步预测,聊作存档。等到明…...
【配置 YOLOX 用于按目录分类的图片数据集】
现在的图标点选越来越多,如何一步解决,采用 YOLOX 目标检测模式则可以轻松解决 要在 YOLOX 中使用按目录分类的图片数据集(每个目录代表一个类别,目录下是该类别的所有图片),你需要进行以下配置步骤&#x…...
PL0语法,分析器实现!
简介 PL/0 是一种简单的编程语言,通常用于教学编译原理。它的语法结构清晰,功能包括常量定义、变量声明、过程(子程序)定义以及基本的控制结构(如条件语句和循环语句)。 PL/0 语法规范 PL/0 是一种教学用的小型编程语言,由 Niklaus Wirth 设计,用于展示编译原理的核…...
在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?
uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件,用于在原生应用中加载 HTML 页面: 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
算法笔记2
1.字符串拼接最好用StringBuilder,不用String 2.创建List<>类型的数组并创建内存 List arr[] new ArrayList[26]; Arrays.setAll(arr, i -> new ArrayList<>()); 3.去掉首尾空格...
【Java学习笔记】BigInteger 和 BigDecimal 类
BigInteger 和 BigDecimal 类 二者共有的常见方法 方法功能add加subtract减multiply乘divide除 注意点:传参类型必须是类对象 一、BigInteger 1. 作用:适合保存比较大的整型数 2. 使用说明 创建BigInteger对象 传入字符串 3. 代码示例 import j…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...
