leetcode 97.交错字符串
思路:LCS
其实也是同一个类型的题目,一般涉及到这种子序列的字符串问题的时候,状态的设置基本上都应该是以...结尾为状态的。这里同样,设置用dp[i][j]为s1,s2字符以i,j结尾能否拼接成s3[i+j]。
那么,首先就是探讨一下转移方程怎么写。我们知道,说是交错,也就是交替拼接字符串。
我们需要考虑两种可能:一种就是当前s1[i]字符与s3[i+j-1]字符是否匹配,如果说这个是匹配的,这样还不够,我们还需要看后面的子字符串是怎么样的情况,所以除去这一个位置的字符我们去看dp[i-1][j]这个状态是不是能够达成。
同理,当s2[j]==s3[i+j-1]的时候,我们还需要看到dp[i][j-1]的状态是怎么样的。
以上的实现只需要用两个if语句实现就可以,轮次判断即可。
注意:这里还需要dp初始化,想一下,我们在s1为空或者s2为空的时候,到底是个什么情况呢?这个时候除了我们需要知道当前位置的字符匹配与否,还需要知道dp[i-1][0]或者dp[0][i-1]这个时候的情况是不是能够达成条件,所以初始化的时候需要额外注意。
dp[0][0]=true,这个是理所当然的。
class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int n=s3.size();if(n!=s1.size()+s2.size())return false;vector<vector<int>>dp(s1.size()+10,vector<int>(s2.size()+10,0));dp[0][0]=1;for(int i=1;i<=s1.size()&&dp[i-1][0];i++){dp[i][0]=(s1[i-1]==s3[i-1]);}for(int i=1;i<=s2.size()&&dp[0][i-1];i++){dp[0][i]=(s2[i-1]==s3[i-1]);}for(int i=1;i<=s1.size();i++){for(int j=1;j<=s2.size();j++){if(s1[i-1]==s3[i+j-1])dp[i][j]=dp[i][j]|dp[i-1][j];if(s2[j-1]==s3[j+i-1])dp[i][j]=dp[i][j]|dp[i][j-1];}}return dp[s1.size()][s2.size()];}
};
相关文章:
leetcode 97.交错字符串
思路:LCS 其实也是同一个类型的题目,一般涉及到这种子序列的字符串问题的时候,状态的设置基本上都应该是以...结尾为状态的。这里同样,设置用dp[i][j]为s1,s2字符以i,j结尾能否拼接成s3[ij]。 那么,首先就…...
The Missing Semester ( Shell 工具和脚本 和 Vim)
管道符号 (1)管道符号 | 将前一个命令的输出作为下一个命令的输入 例如: 以下为 ./semester输出中提取包含 "Last-Modified" 的行并写入文件 last-modified.txt./semester | grep "Last-Modified" > ~/last-modif…...
【Uniapp微信小程序】自定义水印相机、微信小程序地点打卡相机
效果图 template 下方的image图片自行寻找替换! <template><view><camerav-if"!tempImagePath && cameraHeight ! 0":resolution"high":frame-size"large":device-position"device":flash"f…...
SimPO: Simple Preference Optimization with a Reference-Free Reward
https://github.com/princeton-nlp/SimPO 简单代码 class simpo(paddle.nn.Layer):def __init__(self):super(OrPoLoss, self).__init__()self.loss paddle.nn.CrossEntropyLoss()def forward(self,neg_logit, neg_lab, pos_logit, pos_lab,beta,gamma):neg_logit paddle.n…...
CDH6.3.2安装文档
前置环境: 操作系统: CentOS Linux release 7.7 java JDK : 1.8.0_231 1、准备工作 准备以下安装包: Cloudera Manager: cloudera-manager-agent-6.3.1-1466458.el7.x86_64.rpm cloudera-manager-daemons-6.3.1-1466458.el…...
Java实战入门:深入解析Java中的 `Arrays.sort()` 方法
文章目录 一、方法定义参数说明返回值 二、使用场景三、实现原理四、示例代码示例一:对整型数组排序示例二:对字符串数组排序示例三:对自定义对象数组排序 五、注意事项六、总结 在Java编程中,Arrays.sort() 方法是一个非常常用的…...
JavaScript的垃圾回收机制
No.内容链接1Openlayers 【入门教程】 - 【源代码示例300】 2Leaflet 【入门教程】 - 【源代码图文示例 150】 3Cesium 【入门教程】 - 【源代码图文示例200】 4MapboxGL【入门教程】 - 【源代码图文示例150】 5前端就业宝典 【面试题详细答案 1000】 文章目录 一、垃圾…...
小程序使用Canvas设置文字竖向排列
在需要使用的js页面引入js文件,传入对应参数即可 /** * 文本竖向排列 */ function drawTextVertical(context, text, x, y) {var arrText text.split();var arrWidth arrText.map(function (letter) {return 26; // 字体间距,需要自定义可以自己加参数,根据传入参数进行…...
GPT-4o:重塑人机交互的未来
一个愿意伫立在巨人肩膀上的农民...... 一、推出 在人工智能(AI)领域,自然语言处理(NLP)技术一直被视为连接人类与机器的桥梁。近年来,随着深度学习技术的快速发展,NLP领域迎来了前所未有的变革…...
大语言模型拆解——Tokenizer
1. 认识Tokenizer 1.1 为什么要有tokenizer? 计算机是无法理解人类语言的,它只会进行0和1的二进制计算。但是呢,大语言模型就是通过二进制计算,让你感觉计算机理解了人类语言。 举个例子:单1,双2&#x…...
Linux自动挂载服务autofs讲解
1.产生原因 2.配置文件讲解 总结:配置客户端,先构思好要挂载的目录如:/abc/cb 然后在autofs.master中编辑: /abc(要挂载的主目录) /etc/qwe(在这个文件里去找要挂载的副目录,这个名…...
堆结构知识点复习——玩转堆结构
前言:堆算是一种相对简单的数据结构, 本篇文章将详细的讲解堆中的知识点, 包括那些我们第一次学习堆的时候容易忽略的内容, 本篇文章会作为重点详细提到。 本篇内容适合已经学完C语言数组和函数部分的友友们观看。 目录 什么是堆 建堆算法…...
JS数据类型运算符标准库
目录 数据类型运算符标准库对象Object对象属性描述对象Array对象包装对象Boolean对象Number对象String对象Math对象Date对象...
单片机之从C语言基础到专家编程 - 4 C语言基础 - 4.13数组
C语言中,有一类数据结构,它可以存储一组相同类型的元素,并且可以通过索引访问这些元素,没错,这类数据结构就是数组。数组可以说是C语言中非常重要的数据结构之一了。使用数组可以是程序逻辑更加清晰,也更加…...
【码银送书第二十期】《游戏运营与出海实战:策略、方法与技巧》
市面上的游戏品种繁杂,琳琅满目,它们是如何在历史的长河中逐步演变成今天的模式的呢?接下来,我们先回顾游戏的发展史,然后按照时间轴来叙述游戏运营的兴起。 作者:艾小米 本文经机械工业出版社授权转载&a…...
String 类
目录: 一. 认识 String 类 二. String 类的基本用法 三. String对象的比较 四.字符串的不可变性 五. 认识 StringBuffer 和 StringBuilder 一. 认识 String 类: 在C语言中已经涉及到字符串了,但是在C语言中要表示字符串只能使用字符数组或者…...
Chromebook Plus中添加了Gemini?
Chromebook Plus中添加了Gemini? 前言 就在5月29日,谷歌宣布了一项重大更新,将其Gemini人工智能技术集成到Chromebook Plus笔记本电脑中。这项技术此前已应用于谷歌的其他设备。华硕和惠普已经在市场上销售的Chromebook Plus机型,…...
Git Large File Storage (LFS) 的安装与使用
Git Large File Storage [LFS] 的安装与使用 1. An open source Git extension for versioning large files2. Installing on Linux using packagecloud3. Getting Started4. Error: Failed to call git rev-parse --git-dir: exit status 128References 1. An open source Git…...
使用国产工作流引擎,有那些好处?
使用国产工作流引擎的好处主要体现在以下几个方面: 符合企业独特业务: 国产工作流引擎可以深入挖掘和理解企业内部各项业务流程,精细化地定义流程模型和规则,实现“以流程驱动业务”的目标。这有助于企业更好地满足其独特的业务…...
掌握 Go 语言:使用 net/http/httptrace 包优化HTTP请求
掌握 Go 语言:使用 net/http/httptrace 包优化HTTP请求 介绍net/http/httptrace 包的基础概述适用场景 使用httptrace进行网络请求追踪配置httptrace的基本步骤示例:创建一个简单的HTTP客户端,使用httptrace监控连接 示例:追踪HTT…...
测试微信模版消息推送
进入“开发接口管理”--“公众平台测试账号”,无需申请公众账号、可在测试账号中体验并测试微信公众平台所有高级接口。 获取access_token: 自定义模版消息: 关注测试号:扫二维码关注测试号。 发送模版消息: import requests da…...
多模态2025:技术路线“神仙打架”,视频生成冲上云霄
文|魏琳华 编|王一粟 一场大会,聚集了中国多模态大模型的“半壁江山”。 智源大会2025为期两天的论坛中,汇集了学界、创业公司和大厂等三方的热门选手,关于多模态的集中讨论达到了前所未有的热度。其中,…...
从零实现富文本编辑器#5-编辑器选区模型的状态结构表达
先前我们总结了浏览器选区模型的交互策略,并且实现了基本的选区操作,还调研了自绘选区的实现。那么相对的,我们还需要设计编辑器的选区表达,也可以称为模型选区。编辑器中应用变更时的操作范围,就是以模型选区为基准来…...
高危文件识别的常用算法:原理、应用与企业场景
高危文件识别的常用算法:原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件,如包含恶意代码、敏感数据或欺诈内容的文档,在企业协同办公环境中(如Teams、Google Workspace)尤为重要。结合大模型技术&…...
NFT模式:数字资产确权与链游经济系统构建
NFT模式:数字资产确权与链游经济系统构建 ——从技术架构到可持续生态的范式革命 一、确权技术革新:构建可信数字资产基石 1. 区块链底层架构的进化 跨链互操作协议:基于LayerZero协议实现以太坊、Solana等公链资产互通,通过零知…...
【OSG学习笔记】Day 16: 骨骼动画与蒙皮(osgAnimation)
骨骼动画基础 骨骼动画是 3D 计算机图形中常用的技术,它通过以下两个主要组件实现角色动画。 骨骼系统 (Skeleton):由层级结构的骨头组成,类似于人体骨骼蒙皮 (Mesh Skinning):将模型网格顶点绑定到骨骼上,使骨骼移动…...
10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...
JVM虚拟机:内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...
快刀集(1): 一刀斩断视频片头广告
一刀流:用一个简单脚本,秒杀视频片头广告,还你清爽观影体验。 1. 引子 作为一个爱生活、爱学习、爱收藏高清资源的老码农,平时写代码之余看看电影、补补片,是再正常不过的事。 电影嘛,要沉浸,…...
Golang——7、包与接口详解
包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...
