当前位置: 首页 > news >正文

leetcode日记(74)扰乱字符串

很有难度的一题,一开始真的绕了很多思维上的弯路。

最开始的想法是递归,看到题目的时候想到动态规划但是完全没有思路应该怎么用,结果确实是递归+动态规划。

最开始的想法是构建树,每一层包含这一步划分的方法(实际会很复杂,时间绝对超限,于是就放弃了)。

然后用贴近动态规划的思维思考,想要构建一个二(三)维表格,先对角线存放每一个字母,然后一层层推出两两结合的可能性……(怎么比第一种还要复杂啊啊啊啊)

最后还是看了答案,答案的动态规划+递归+剪枝思路还是很巧妙的。

动态规划其实是构建了这么一个数组:memo[i1][i2][len],其中i1、i2表示分别从两个字符串的i1i2起,各取len个字母,这两个取出来的字符串是否为扰乱字符串。

一开始i1、i2取0,len取最大长度(就是直接塞入题目的问题),然后开始层层递归。

递归时建立一个循环,将i1后移,i2后移(如果不交换)或从最末端前移(如果交换),len就随之变化。

以上只是最基础的思路。

既然是动态规划,那么数组肯定还可以重复使用,保存的数组就是为了这个操作:if(memo[i1][i2][len]!=0) return memo[i1][i2][len]==1;

注意这里,memo有三种状态,-1(不是扰乱字符串)、1(是扰乱字符串)、0(未计算)。

这里这样做可以重复使用之前的数据,节省很多复杂度。

为了进一步降低时间复杂度,还得进行剪枝。

方法是再建立一个判断”是否可能为扰乱字符串“的判断,如果其中有某个字母,在两个字符串中出现的频次不等,那么就不可能是扰乱字符串。

我原以为写这个会有些复杂,没想到可以用map写:

bool peace(string s1, string s2){unordered_map<char, int> freq;for(int i=0;i<s1.length();i++){freq[s1[i]]++;}for(int i=0;i<s2.length();i++){freq[s2[i]]--;}if(any_of(freq.begin(),freq.end(),[](auto& n){return n.second!=0;})) return 0;else return 1;}

使用unorder_map,记录第一个字符串中出现的单词频率,再遍历第二个字符串,将出现的单词减一,如果最后存在个数不为0的单词,即不可能为扰乱字符串。

最后代码:

class Solution {string s1,s2;int memo[30][30][31];
public:bool peace(string s1, string s2){unordered_map<char, int> freq;for(int i=0;i<s1.length();i++){freq[s1[i]]++;}for(int i=0;i<s2.length();i++){freq[s2[i]]--;}if(any_of(freq.begin(),freq.end(),[](auto& n){return n.second!=0;})) return 0;else return 1;}bool dfs(int i1, int i2, int len){if(memo[i1][i2][len]!=0) return memo[i1][i2][len]==1;if(s1.substr(i1,len)==s2.substr(i2,len)) {memo[i1][i2][len]=1;return 1;}if(peace(s1.substr(i1,len), s2.substr(i2,len))==0) {memo[i1][i2][len]=0;return 0;}for(int i=1;i<len;i++){if(dfs(i1,i2,i)&&dfs(i1+i,i2+i,len-i)){memo[i1][i2][len] = 1;return 1;}if(dfs(i1,i2+len-i,i)&&dfs(i1+i,i2,len-i)){memo[i1][i2][len] = 1;return 1;}}memo[i1][i2][len]=-1;return 0;}bool isScramble(string s1, string s2) {memset(memo,0,sizeof(memo));this->s1=s1;this->s2=s2;return dfs(0,0,s1.length());        }
};

(基本是照着答案写的真的很抱歉)

相关文章:

leetcode日记(74)扰乱字符串

很有难度的一题&#xff0c;一开始真的绕了很多思维上的弯路。 最开始的想法是递归&#xff0c;看到题目的时候想到动态规划但是完全没有思路应该怎么用&#xff0c;结果确实是递归动态规划。 最开始的想法是构建树&#xff0c;每一层包含这一步划分的方法&#xff08;实际会…...

RV1126的OSD模块和SDL_TTF结合输出H264文件

目录 一.RV1126多线程处理输出OSD字符叠加图层的流程 1.1. VI模块的初始化 1.2. 初始化VENC模块&#xff1a; 1.3. 初始化RGN模块&#xff1a; 1.4. 绑定VI模块和VENC模块&#xff0c;伪代码如下 1.5. 创建多线程进行OSD字库的叠加&#xff1a; 1.6. 获取每一帧处理过后的…...

GEE:计算长时间序列NPP与NDVI之间的相关系数

GEE中内置了计算相关系数的函数&#xff0c;可以分析两个变量之间的相关性&#xff0c;比如要分析两个波段之间的相关性&#xff0c;主要用到ee.Reducer.pearsonsCorrelation()函数。 ee.Reducer.pearsonsCorrelation() 内容&#xff1a;创建一个双输入归约器&#xff0c;用于…...

水仙花数(华为OD)

题目描述 所谓水仙花数&#xff0c;是指一个n位的正整数&#xff0c;其各位数字的n次方和等于该数本身。 例如153是水仙花数&#xff0c;153是一个3位数&#xff0c;并且153 13 53 33。 输入描述 第一行输入一个整数n&#xff0c;表示一个n位的正整数。n在3到7之间&#x…...

【对话状态跟踪】关心整个对话过程用户完整意图变化

对话状态管理器 核心逻辑是解决键冲突和验证范围有效性&#xff0c; 但需依赖外部输入的正确性。在实际应用中&#xff0c; 可能需要结合用户提示或自动修正逻辑以提高鲁棒性。 NLU 槽 值 对儿 NLU的目的是把自然语言解析成结构化语义。结构化语义有多种表示方式&#xff0c…...

【分享】网间数据摆渡系统,如何打破传输瓶颈,实现安全流转?

在数字化浪潮中&#xff0c;企业对数据安全愈发重视&#xff0c;网络隔离成为保护核心数据的重要手段。内外网隔离、办公网与研发网隔离等措施&#xff0c;虽为数据筑牢了防线&#xff0c;却也给数据传输带来了诸多难题。传统的数据传输方式在安全性、效率、管理等方面暴露出明…...

TikTok创作者市场关闭!全新平台TikTok One将带来哪些改变?

TikTok创作者市场关闭&#xff0c;全新平台TikTok One上线&#xff0c;创作者和品牌将迎来哪些新机遇&#xff1f; 近日&#xff0c;TikTok宣布关闭其原有的创作者市场&#xff08;TikTok Creator Marketplace&#xff09;&#xff0c;并推出全新平台TikTok One。这一消息在社…...

LeetCode hot 100—矩阵置零

题目 给定一个 m x n 的矩阵&#xff0c;如果一个元素为 0 &#xff0c;则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。 示例 示例 1&#xff1a; 输入&#xff1a;matrix [[1,1,1],[1,0,1],[1,1,1]] 输出&#xff1a;[[1,0,1],[0,0,0],[1,0,1]]示例 2&#xff1…...

部署Windows Server自带“工作文件夹”实现企业网盘功能完整步骤

前文已经讲解过Windows Server自带的“工作文件夹”功能&#xff0c;现以Windows Server 2025为例介绍部署工作文件夹的完整步骤&#xff1a; 为了确保您能够顺利部署和充分利用工作文件夹的功能&#xff0c;我将按照以下步骤进行讲解。 请注意&#xff0c;在域环境中部署工作…...

植物大战僵尸杂交版v3.3最新版本(附下载链接)

B站游戏作者潜艇伟伟迷于12月21日更新了植物大战僵尸杂交版3.3版本&#xff01;&#xff01;&#xff01;&#xff0c;有b站账户的记得要给作者三连关注一下呀&#xff01; 不多废话下载链接放上&#xff1a; 夸克网盘链接&#xff1a;&#xff1a;https://pan.quark.cn/s/6f2a…...

非关系型数据库和关系型数据库的区别

非关系型数据库&#xff08;NoSQL&#xff09;和关系型数据库&#xff08;SQL&#xff09;的主要区别体现在以下几个方面&#xff1a; 数据模型&#xff1a; 关系型数据库&#xff08;SQL&#xff09;&#xff1a;数据以表格形式存储&#xff0c;数据行和列组成&#xff0c;每个…...

CPU负载高告警问题的定位与优化建议

#作者&#xff1a;猎人 文章目录 背景一&#xff0e;问题排查1.1 找到相应的容器1.2 找到对应的deployment1.3 查看pod日志1.4 查看nginx配置文件1.5 查看deployment的yaml文件 二&#xff0e;优化建议 背景 Docker 版本&#xff1a;19.03.14 Operating System: Red Hat Ent…...

2月28日,三极管测量,水利-51单片机

众所周知&#xff0c;三极管&#xff08;BJT&#xff09;有三个管脚&#xff0c;基极&#xff08;B&#xff09;、集电极&#xff08;C&#xff09;、发射极&#xff08;E&#xff09;&#xff0c;在实际应用中&#xff0c;不可避免地会遇到引脚辨别的问题。接下来就讲下三极管…...

批量提取 Word 文档中的图片

在 Word 文档中&#xff0c;我们可以插入图片、文本、链接等各种各样的资源。在某些场景下我们需要提取这些信息&#xff0c;比如我们需要提取 Word 文档中的图片&#xff0c;将每一个 Word 文档中的图片都提取出来放到一个单独的文件夹中&#xff0c;那么我们应该怎么做呢&…...

C#—Settings配置详解

C#—Settings配置详解 在C#项目中&#xff0c;全局配置通常指的是应用程序的设置&#xff08;settings&#xff09;&#xff0c;这些设置可以跨多个类或组件使用&#xff0c;并且通常用于存储应用程序的配置信息&#xff0c;如数据库连接字符串、用户偏好设置等。 Settings配置…...

UI自动化框架介绍

selenium Pytest Allure 优势 1.1 更高效的自动化测试 Selenium 提供了强大的浏览器自动化能力&#xff0c;可以模拟用户与网页的交互。它能够在不同浏览器上运行测试&#xff0c;确保 Web 应用程序在多种环境下的兼容性。Pytest 是一个非常灵活、简洁的 Python 测试框架&a…...

【工具推荐】在线提取PDF、文档、图片、论文中的公式

网址1&#xff1a;https://simpletex.cn/ai/latex_ocr 网址2: https://www.latexlive.com/home 推荐理由&#xff1a;无需下载&#xff0c;在线使用&#xff0c;直接 截图 CTRLV 效果更佳。...

帮我设计一个c语言学习阶段

以下是一个针对不同学习阶段的C语言学习计划&#xff0c;你可以根据自己的基础和目标进行调整&#xff1a; 第一阶段&#xff1a;基础语法与程序结构&#xff08;第1-4周&#xff09; 目标 熟悉C语言的基本语法和程序结构。 能够编写简单的程序。 学习内容 环境搭建 安装…...

解决windows npm无法下载electron包的问题

1.将nsis.zip解压到C:\Users\XXX\AppData\Local\electron-builder\Cache 2.将winCodeSign.zip解压到C:\Users\XXX\AppData\Local\electron-builder\Cache 3.将electron-v20.3.8-win32-ia32.zip复制到C:\Users\XXX\AppData\Local\electron\Cache 4.将electron-v20.3.8-win32-…...

网络编程 day01

网络编程 day01 0. 网络编程课程介绍1. 认识网络1.网络发展史2.局域网与广域网局域网&#xff08;LAN&#xff09;广域网&#xff08;Wan&#xff09; 3.光猫4.路由器5.交换机与路由器6.网线 2. IP1. 基本概念2. 网络号/主机号&#xff08;二级划分&#xff09;3. IP地址分类整…...

DeepSeek 赋能智慧能源:微电网优化调度的智能革新路径

目录 一、智慧能源微电网优化调度概述1.1 智慧能源微电网概念1.2 优化调度的重要性1.3 目前面临的挑战 二、DeepSeek 技术探秘2.1 DeepSeek 技术原理2.2 DeepSeek 独特优势2.3 DeepSeek 在 AI 领域地位 三、DeepSeek 在微电网优化调度中的应用剖析3.1 数据处理与分析3.2 预测与…...

Python:操作 Excel 折叠

💖亲爱的技术爱好者们,热烈欢迎来到 Kant2048 的博客!我是 Thomas Kant,很开心能在CSDN上与你们相遇~💖 本博客的精华专栏: 【自动化测试】 【测试经验】 【人工智能】 【Python】 Python 操作 Excel 系列 读取单元格数据按行写入设置行高和列宽自动调整行高和列宽水平…...

FFmpeg 低延迟同屏方案

引言 在实时互动需求激增的当下&#xff0c;无论是在线教育中的师生同屏演示、远程办公的屏幕共享协作&#xff0c;还是游戏直播的画面实时传输&#xff0c;低延迟同屏已成为保障用户体验的核心指标。FFmpeg 作为一款功能强大的多媒体框架&#xff0c;凭借其灵活的编解码、数据…...

Day131 | 灵神 | 回溯算法 | 子集型 子集

Day131 | 灵神 | 回溯算法 | 子集型 子集 78.子集 78. 子集 - 力扣&#xff08;LeetCode&#xff09; 思路&#xff1a; 笔者写过很多次这道题了&#xff0c;不想写题解了&#xff0c;大家看灵神讲解吧 回溯算法套路①子集型回溯【基础算法精讲 14】_哔哩哔哩_bilibili 完…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

如何在最短时间内提升打ctf(web)的水平?

刚刚刷完2遍 bugku 的 web 题&#xff0c;前来答题。 每个人对刷题理解是不同&#xff0c;有的人是看了writeup就等于刷了&#xff0c;有的人是收藏了writeup就等于刷了&#xff0c;有的人是跟着writeup做了一遍就等于刷了&#xff0c;还有的人是独立思考做了一遍就等于刷了。…...

QT3D学习笔记——圆台、圆锥

类名作用Qt3DWindow3D渲染窗口容器QEntity场景中的实体&#xff08;对象或容器&#xff09;QCamera控制观察视角QPointLight点光源QConeMesh圆锥几何网格QTransform控制实体的位置/旋转/缩放QPhongMaterialPhong光照材质&#xff08;定义颜色、反光等&#xff09;QFirstPersonC…...

并发编程 - go版

1.并发编程基础概念 进程和线程 A. 进程是程序在操作系统中的一次执行过程&#xff0c;系统进行资源分配和调度的一个独立单位。B. 线程是进程的一个执行实体,是CPU调度和分派的基本单位,它是比进程更小的能独立运行的基本单位。C.一个进程可以创建和撤销多个线程;同一个进程中…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...

Python网页自动化Selenium中文文档

1. 安装 1.1. 安装 Selenium Python bindings 提供了一个简单的API&#xff0c;让你使用Selenium WebDriver来编写功能/校验测试。 通过Selenium Python的API&#xff0c;你可以非常直观的使用Selenium WebDriver的所有功能。 Selenium Python bindings 使用非常简洁方便的A…...