leetcode做题笔记87扰乱字符串
使用下面描述的算法可以扰乱字符串 s 得到字符串 t :
- 如果字符串的长度为 1 ,算法停止
- 如果字符串的长度 > 1 ,执行下述步骤:
- 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串
s,则可以将其分成两个子字符串x和y,且满足s = x + y。 - 随机 决定是要「交换两个子字符串」还是要「保持这两个子字符串的顺序不变」。即,在执行这一步骤之后,
s可能是s = x + y或者s = y + x。 - 在
x和y这两个子字符串上继续从步骤 1 开始递归执行此算法。
- 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串
给你两个 长度相等 的字符串 s1 和 s2,判断 s2 是否是 s1 的扰乱字符串。如果是,返回 true ;否则,返回 false 。
思路一:模拟题意
bool check(char *s1,char *s2,int len)
{char ss1[26]={0};char ss2[26]={0};char i=0;for (i=0;i<len;i++){ss1[s1[i]-'a']++;ss2[s2[i]-'a']++;}for(i=0;i<26;i++){if(ss1[i]!=ss2[i]) return false;}return true;
}
char mem[30][30][31];
bool complie(char *s1,char *s2,int len,int s1begin,int s2begin)
{if(mem[s1begin][s2begin][len]==1) return true;if(mem[s1begin][s2begin][len]==2) return false;if(len==0) return true;if(len==1) {mem[s1begin][s2begin][len]=1;return *s1==*s2;}if(!check(s1,s2,len)) {mem[s1begin][s2begin][len]=2;return false;}int i=0;for(i=1;i<len;i++){if(complie(s1,s2,i,s1begin,s2begin) && complie(s1+i,s2+i,len-i,s1begin+i,s2begin+i)) {mem[s1begin][s2begin][len]=1;return true;}if(complie(s1,s2+len-i,i,s1begin,s2begin+len-i) && complie(s1+i,s2,len-i,s1begin+i,s2begin)) {mem[s1begin][s2begin][len]=1;return true;}}mem[s1begin][s2begin][len]=2;return false;
}
bool isScramble(char * s1, char * s2){int len1=0;int len2=0;memset(mem,0,sizeof(mem));while(s1[len1]!=0){len1++;}while(s2[len2]!=0){len2++;}if(len1!=len2) return false;return complie(s1,s2,len1,0,0);
}
分析:
本题扰乱字符串满足交换两个子字符串或保持这两个子字符串的顺序不变,转换为complie(s1,s2,i,s1begin,s2begin) && complie(s1+i,s2+i,len-i,s1begin+i,s2begin+i)和complie(s1,s2+len-i,i,s1begin,s2begin+len-i) && complie(s1+i,s2,len-i,s1begin+i,s2begin),通过complie函数递归找到答案,同时两个字符串长度首先要相等,先判断两个字符串长度是否相等再进行递归返回答案
总结:
本题考察递归的应用,利用递归交换两个子字符串或保持这两个子字符串的顺序不变判断是否为扰乱字符串
相关文章:
leetcode做题笔记87扰乱字符串
使用下面描述的算法可以扰乱字符串 s 得到字符串 t : 如果字符串的长度为 1 ,算法停止如果字符串的长度 > 1 ,执行下述步骤: 在一个随机下标处将字符串分割成两个非空的子字符串。即,如果已知字符串 s ,…...
第一章 初识Linux(含VMware安装Ubuntu、CentOS、Windows、FinalShell、快照)
目录 一、 课程的介绍 1.为什么要学习Linux 2.课程的安排 3.如何学习Linux 二、操作系统概述 1.学习目标 2.计算机的硬件和软件 3.什么是操作系统 4.常见的操作系统 5.本小节的总结 三、初识Linux 1.学习目标 2.Linux的诞生 3.Linux的内核 …...
MATLAB算法实战应用案例精讲-【图像处理】OCR识别方法-CRNN
目录 OCR综述 什么是OCR OCR发展历程 OCR 常用检测方法 基于回归的方法 1) box回归...
无涯教程-PHP - preg_grep()函数
preg_grep() - 语法 array preg_grep ( string $pattern, array $input [, int $flags] ); 返回由与给定模式匹配的输入数组元素组成的数组。 如果将flag设置为PREG_GREP_INVERT,则此函数返回输入数组中与给定模式不匹配的元素。 preg_grep() - 返回值 返回使用…...
【Linux】Nginx解决跨域问题
文章目录 一、跨域问题二、解决跨域问题三、结尾 一、跨域问题 在前后端分离的项目中,前端通常运行在一个域名或端口上,而后端运行在另一个域名或端口上。当浏览器发起跨域请求时,即前端页面向后端发送请求的域名、端口或协议与当前页面的域…...
无涯教程-PHP - preg_split()函数
preg_split() - 语法 array preg_split (string pattern, string string [, int limit [, int flags]]); preg_split()函数的操作与split()完全相同,只不过正则表达式被接受为pattern的输入参数。 如果指定了可选的输入参数limit,则仅返回子字符串的限…...
B. Spreadsheets
Problem - B - Codeforces 问题描述:excel有两种情况, Rr_nCc_n:R行数C列数ZZZ(列数)行数。 对这两个进行相互转换。 细节: 准确判断这两种情况 string str; cin>>str; auto posR str.find("R"), posC st…...
matlab面向对象
一、面向对象编程 1.1 面向过程与面向对象 区别: 面向过程的核心是一系列函数,执行过程是依次使用每个函数面向对象的核心是对象(类)及其属性、方法,每个对象根据需求执行自己的方法以解决问题 对象:单个…...
01、Cannot resolve MVC View ‘xxxxx前端页面‘
Cannot resolve MVC View ‘xxxxx前端页面’ 没有找到对应的mvc的前端页面。 代码:前端这里引入了 thymeleaf 模板 解决: 需要添加 thymeleaf 的依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>s…...
时空智友企业流程化管控系统文件上传漏洞复现
0x01 产品简介 时空智友企业流程化管控系统是一个功能丰富、灵活可定制的企业管理工具。通过该系统,企业能够实现流程的自动化、协同的提升、数据的洞察和决策的优化,从而提高工作效率、管理水平和企业竞争力。 0x02 漏洞概述 时空智友企业流程化管控系…...
【已解决】Authenticator:无法添加账户请验证激活代码是否正确以及您的设备是否已为此应用启用推送通知
问题: 小米手机的Authenticator添加微软账户扫描QR码提示:无法添加账户请验证激活代码是否正确以及您的设备是否已为此应用启用推送通知 解决办法: 1、在通知管理中允许Authenticator所有通知。 2、在手机设置-账户与同步里找到谷歌基础服…...
聊聊springboot tomcat的maxHttpFormPostSize
序 本文主要研究一下spring boot tomcat的maxHttpFormPostSize参数 parseParameters tomcat-embed-core-9.0.37-sources.jar!/org/apache/catalina/connector/Request.java /*** Parse request parameters.*/protected void parseParameters() {parametersParsed true;Para…...
java并发:synchronized锁详解
背景: 在java多线程当中,我们总有遇到过多个线程操作一个共享数据时,而这个最后的代码执行结果并没有按照我们的预期一样得到正确的结果。此时我们就需要让代码执行在操作共享变量时,要等一个线程操作完毕时,另一个线程…...
Unity 之NavMeshAgent 组件(导航和路径寻找的组件)
文章目录 **作用**:**属性和方法**:**用途**:**注意事项**: NavMeshAgent 是Unity引擎中用于导航和路径寻找的组件。它可以使游戏对象在场景中自动找到可行走的路径,并在避免障碍物的情况下移动到目标位置。 以下是关于…...
装箱和拆箱
1. 概念 装箱 将值类型转换成等价的引用类型 装箱的步骤 拆箱 将一个已装箱的引用类型转换为值类型,拆箱操作需要声明拆箱后转换的类型 拆箱的步骤 1)获取已装箱的对象的地址 2)将值从堆上的对象中复制到堆栈上的值变量中 2. 总结 装箱和拆箱…...
等保测评--安全通信网络--测评方法
安全子类--安全架构 a)应保证网络设备的业务处理能力满足业务高峰期需要; 一、测评对象 路由器、交换机、无线接入设备和防火墙等提供网络通信功能的设备或相关组件 二、测评实施 1) 应核查业务高峰时期一段时间内主要网络设备(一般包括核心交换机、汇聚交换机、边界路…...
统计学补充概念11-tsne
概念 t-SNE(t-distributed Stochastic Neighbor Embedding)是一种非线性降维技术,用于可视化高维数据在低维空间中的分布。与主成分分析(PCA)等线性降维方法不同,t-SNE专注于保留数据点之间的局部相似性关…...
Linux_11_系统启动和内核管理
目录 1 C entOS 6 的启动管理1.1 Linux 组成1.2 内核设计流派1.3 CentOS 6启动流程1.3.1 CentOs 6 启动流程1.3.1 硬件启动POST1.3.2 bootloader 启动/引导加载器1.3.2.1 grub 功能和组成1.3.2.2 CentOS 6 grub 安装1.3.2.3 grub legacy 管理 1.3.3 加载 kernel1.3.4 init 初始…...
【从零学习python 】65. Python正则表达式修饰符及其应用详解
文章目录 正则表达式修饰符进阶案例 正则表达式修饰符 修饰符描述re.I使匹配对大小写不敏感re.M多行匹配,影响 ^ 和 $re.S使 . 匹配包括换行在内的所有字符 示例代码如下: import reprint(re.search(rL, hello)) # None# 不区分大小写,可…...
QA2
1. import shutil 是什么意思? 在 Python 中,import shutil 是导入标准库 shutil 的语句。shutil 提供了一些用于复制文件和文件夹、移动文件和文件夹、以及执行其他文件操作的函数。 通过导入 shutil,你可以使用其中的函数来处理文件和文件…...
智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...
sqlserver 根据指定字符 解析拼接字符串
DECLARE LotNo NVARCHAR(50)A,B,C DECLARE xml XML ( SELECT <x> REPLACE(LotNo, ,, </x><x>) </x> ) DECLARE ErrorCode NVARCHAR(50) -- 提取 XML 中的值 SELECT value x.value(., VARCHAR(MAX))…...
04-初识css
一、css样式引入 1.1.内部样式 <div style"width: 100px;"></div>1.2.外部样式 1.2.1.外部样式1 <style>.aa {width: 100px;} </style> <div class"aa"></div>1.2.2.外部样式2 <!-- rel内表面引入的是style样…...
【Java_EE】Spring MVC
目录 Spring Web MVC 编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 编辑参数重命名 RequestParam 编辑编辑传递集合 RequestParam 传递JSON数据 编辑RequestBody …...
深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南
🚀 C extern 关键字深度解析:跨文件编程的终极指南 📅 更新时间:2025年6月5日 🏷️ 标签:C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言🔥一、extern 是什么?&…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
HarmonyOS运动开发:如何用mpchart绘制运动配速图表
##鸿蒙核心技术##运动开发##Sensor Service Kit(传感器服务)# 前言 在运动类应用中,运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据,如配速、距离、卡路里消耗等,用户可以更清晰…...
【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制
使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下,限制某个 IP 的访问频率是非常重要的,可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案,使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...
【Veristand】Veristand环境安装教程-Linux RT / Windows
首先声明,此教程是针对Simulink编译模型并导入Veristand中编写的,同时需要注意的是老用户编译可能用的是Veristand Model Framework,那个是历史版本,且NI不会再维护,新版本编译支持为VeriStand Model Generation Suppo…...
沙箱虚拟化技术虚拟机容器之间的关系详解
问题 沙箱、虚拟化、容器三者分开一一介绍的话我知道他们各自都是什么东西,但是如果把三者放在一起,它们之间到底什么关系?又有什么联系呢?我不是很明白!!! 就比如说: 沙箱&#…...
