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

两个字符串间的最短路径问题 （100%用例）C卷 (JavaPythonNode.jsC语言C++)

news 2025/10/30 16:10:45

给定两个字符串，分别为字符串A与字符串B。例如A字符串为ABCABBA，B字符串为CBABAC可以得到下图m*n的二维数组，定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1，映射成坐标系如下图
从原点(0,0)到(0,A)为水平边，距离为1，从(0,A)到(A,C)为垂直边，距离为1;假设两个字符串同一位置的两个字符相同则可以作一个斜边，如(A,C)到(B,B)最短距离为斜边，距离同样为1
作出所有的斜边如下图，(0,0)到(B,B)的距离为 1个水平边 +1个垂直边 + 1个斜边 =3
根据定义可知，原点到终点的最短距离路径如下图红线标记，最短距离为9:

输入描述:

空格分割的两个字符串A与字符串B，字符串不为“空串”，字符格式满足正则规则:[A-Z]，字符串长度< 10000

输出描述:

 

原点到终点的最短距离
 

示例1 输入输出示例仅供调试，后台判题数据一般不包含示例
 

输入
 

ABC ABC
 

输出
 

3
 

示例2 输入输出示例仅供调试，后台判题数据一般不包含示例
 

输入
 

ABCABBA CBABAC
 

输出
 

9
 

 

此题采用动态规划的思想实现，跟网上队列操作不一样，不会出现时间复杂度过大问题。
 

 

Java版本
 

import java.util.Scanner;public class Main{public static int get














相关文章：
















两个字符串间的最短路径问题 （100%用例）C卷 (JavaPythonNode.jsC语言C++)




给定两个字符串，分别为字符串A与字符串B。例如A字符串为ABCABBA，B字符串为CBABAC可以得到下图m*n的二维数组，定义原点为(0,0)，终点为(m,n)，水平与垂直的每一条边距离为1，映射成坐标系如下图 从原点(0,0)到(0,A)为水平边，距离为1，从(0,A)到(A,C)为垂直边，距离为1;假设两…...






编程日记
2023/12/30 7:43:36



















通过ADB来实现脚本来控制手机




ADB 
简介 
adb的全称为Android Debug Bridge,安卓调试桥,可以通过调试命令来控制手机,诸如开机,关机等按键控制;或者启动,关闭应用;异或进行触摸模拟. 
通过学习adb,可以实现简单的脚本控制,最大的特点是不需要root,对于普通手机都可以进行,帮助我们完成一些简单的重复性事件,…...






编程日记
2023/12/30 7:38:31



















机器学习之K-means聚类




概念 
K-means是一种常用的机器学习算法，用于聚类分析。聚类是一种无监督学习方法，它试图将数据集中的样本划分为具有相似特征的组（簇）。K-means算法的目标是将数据集划分为K个簇，其中每个样本属于与其最近的簇中心。 
以下是K-means算法的基本步骤： 选择簇的数量（K值）…...






编程日记
2023/12/30 7:34:28



















SSH 端口转发：如何将服务绑定到本地 IP 地址




在日常工作中&#xff0c;我们经常需要访问位于远程服务器上的服务&#xff0c;如数据库、Web 应用程序或其他类型的服务器。直接访问这些服务可能会因为安全限制或网络配置而变得复杂或不可能。这时&#xff0c;SSH 端口转发就成了我们的得力助手。在本篇博客中&#xff0c;我…...






编程日记
2023/12/30 7:31:26



















回归预测 | MATLAB实ZOA-LSTM基于斑马优化算法优化长短期记忆神经网络的多输入单输出数据回归预测模型 （多指标，多图）




回归预测 | MATLAB实ZOA-LSTM基于斑马优化算法优化长短期记忆神经网络的多输入单输出数据回归预测模型 &#xff08;多指标&#xff0c;多图&#xff09; 目录 回归预测 | MATLAB实ZOA-LSTM基于斑马优化算法优化长短期记忆神经网络的多输入单输出数据回归预测模型 &#xff08;…...






编程日记
2023/12/30 7:19:16



















python实现图像的二维傅里叶变换——冈萨雷斯数字图像处理




原理 
二维傅里叶变换是一种在图像处理中常用的数学工具&#xff0c;它将图像从空间域&#xff08;我们通常看到的像素排列&#xff09;转换到频率域。这种变换揭示了图像的频率成分&#xff0c;有助于进行各种图像分析和处理&#xff0c;如滤波、图像增强、边缘检测等。 在数学…...






编程日记
2023/12/30 7:18:15



















We are a team - 华为OD统一考试




OD统一考试 题解&#xff1a; Java / Python / C 题目描述 
总共有 n 个人在机房&#xff0c;每个人有一个标号 (1<标号<n) &#xff0c;他们分成了多个团队&#xff0c;需要你根据收到的 m 条消息判定指定的两个人是否在一个团队中&#xff0c;具体的: 
消息构成为 a b …...






编程日记
2023/12/30 7:15:12



















NFC物联网智慧校园解决方案




近场通信(Near Field Communication&#xff0c;NFC)又称近距离无线通信&#xff0c;是一种短距离的高频无线通信技术&#xff0c;允许电子设备之间进行非接触式点对点数据传输交换数据。这个技术由免接触式射频识别(RFID)发展而来&#xff0c;并兼容 RFID&#xff0c;主要用于…...






编程日记
2023/12/30 7:13:11



















鸿蒙系列--组件介绍之容器组件




一、Badge 
描述&#xff1a;给其他组件添加标记 
子组件&#xff1a;支持单个子组件 1.创建数字标记  Badge(value: {count: number, position?: BadgePosition, maxCount?: number, style: BadgeStyle}) 2.创建字符串标记  Badge(value: {value: string, position?: Badge…...






编程日记
2023/12/30 7:09:07



















perl使用find函数踩坑




前言 
写了一个脚本可以同时检查多个仿真log文件&#xff0c;并生成html表格。按照文件修改时间从新到旧排序。但是一直无法使用stat函数获取修改时间。 
结论&#xff1a;find函数会改变程序执行的当前目录&#xff0c;find(\&process_files, $dir);函数是在$dir目录下运行…...






编程日记
2023/12/30 7:08:05



















Java IDEA JUnit 单元测试




JUnit是一个开源的 Java 单元测试框架&#xff0c;它使得组织和运行测试代码变得非常简单&#xff0c;利用JUnit可以轻松地编写和执行单元测试&#xff0c;并且可以清楚地看到哪些测试成功&#xff0c;哪些失败 
JUnit 还提供了生成测试报告的功能&#xff0c;报告不仅包含测试…...






编程日记
2023/12/30 7:06:04



















深入理解 c++ 函数模板




函数模板是C中的一种强大特性&#xff0c;它允许程序员编写一个可以处理多种数据类型的函数。通过使用模板&#xff0c;我们可以编写一次函数&#xff0c;然后在多种数据类型上使用它&#xff0c;这大大提高了代码的复用性。 
1. 基本概念 函数模板是一种参数化类型的工具&…...






编程日记
2023/12/30 7:05:03



















系列十二、Linux中安装Zookeeper




一、Linux中安装Zookeeper 
1.1、下载安装包 官网&#xff1a;Index of /dist/zookeeper/zookeeper-3.4.11 我分享的链接&#xff1a; 链接&#xff1a;https://pan.baidu.com/s/14Hugqxcgp89f2hqGWDwoBw?pwdyyds         提取码&#xff1a;yyds  1.2、上传至/opt目录 1.3、解…...






编程日记
2023/12/30 7:04:02



















k8s之陈述式资源管理




1.kubectl命令 
kubectl version 查看k8s的版本 
kubectl api-resources 查看所有api的资源对象的名称 
kubectl cluster-info 查看k8s的集群信息 
kubectl get cs 查看master节点的状态 
kubectl get pod 查看默认命名空间内的pod的信息 
kubectl get ns 查看当前集群所有的命…...






编程日记
2023/12/30 7:00:59



















7天玩转 Golang 标准库之 http/net




在构建web应用时&#xff0c;我们经常需要处理HTTP请求、做网页抓取或者搭建web服务器等任务&#xff0c;而Go语言在这方面为我们提供了强大的内置工具&#xff1a;net/http标准库&#xff0c;它为我们操作和处理HTTP协议提供了便利。 基础用法 
一&#xff1a;处理HTTP请求 
首…...






编程日记
2023/12/30 6:59:59



















钡铼技术集IO数据采集可编程逻辑控制PLC无线4G环保物联网关




背景 数据采集传输对于环保企业进行分析和决策是十分重要的&#xff0c;而实时数据采集更能提升环保生产的执行力度&#xff0c;从而采取到更加及时高效的措施。因此实时数据采集RTU成为环保企业的必备产品之一。 产品介绍 在推进环保行业物联网升级过程中&#xff0c;环保RTU在…...






编程日记
2023/12/30 6:57:57



















STM32CubeMX教程10 RTC 实时时钟 - 周期唤醒、闹钟A/B事件和备份寄存器




目录 
1、准备材料 
2、实验目标 
3、实验流程 
3.0、前提知识 
3.1、CubeMX相关配置 
3.1.1 、时钟树配置 
3.1.2、外设参数配置 
3.1.3 、外设中断配置 
3.2、生成代码 
3.2.1、外设初始化函数调用流程 
3.2.2、外设中断函数调用流程 
3.2.3、添加其他必要代码 
4、常用函数 …...






编程日记
2023/12/30 6:54:54



















HarmonyOS4.0系统性深入开发08服务卡片架构




服务卡片概述 
服务卡片&#xff08;以下简称“卡片”&#xff09;是一种界面展示形式&#xff0c;可以将应用的重要信息或操作前置到卡片&#xff0c;以达到服务直达、减少体验层级的目的。卡片常用于嵌入到其他应用&#xff08;当前卡片使用方只支持系统应用&#xff0c;如桌…...






编程日记
2023/12/30 6:51:52



















002文章解读与程序——中国电机工程学报EI\CSCD\北大核心《计及源荷不确定性的综合能源生产单元运行调度与容量配置两阶段随机优化》已提供下载资源




&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;&#x1f446;下载资源链接&#x1f4…...






编程日记
2023/12/30 6:50:50



















Typora快捷键设置详细教程




文章目录 一、快捷键设置步骤二、设置快捷键简单案例参考资料 一、快捷键设置步骤 
在typora软件中&#xff0c;快捷键的设置步骤主要为&#xff1a; 打开【文件】–>【偏好设置】&#xff0c;找到【通用】–>【打开高级设置】&#xff0c;找到 conf.user.json 文件。  然…...






编程日记
2023/12/30 6:49:49





















python打卡day49




知识点回顾&#xff1a; 
通道注意力模块复习空间注意力模块CBAM的定义 
作业&#xff1a;尝试对今天的模型检查参数数目&#xff0c;并用tensorboard查看训练过程 
import torch
import torch.nn as nn# 定义通道注意力
class ChannelAttention(nn.Module):def __init__(self,…...






编程新知
2025/10/29 18:36:01



















ubuntu搭建nfs服务centos挂载访问




在Ubuntu上设置NFS服务器 
在Ubuntu上&#xff0c;你可以使用apt包管理器来安装NFS服务器。打开终端并运行&#xff1a; 
sudo apt update
sudo apt install nfs-kernel-server创建共享目录 
创建一个目录用于共享&#xff0c;例如/shared&#xff1a; 
sudo mkdir /shared
sud…...






编程新知
2025/8/27 13:05:41



















边缘计算医疗风险自查APP开发方案




核心目标：在便携设备（智能手表/家用检测仪）部署轻量化疾病预测模型，实现低延迟、隐私安全的实时健康风险评估。 一、技术架构设计 #mermaid-svg-iuNaeeLK2YoFKfao {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg…...






编程新知
2025/10/30 5:34:26



















MODBUS TCP转CANopen 技术赋能高效协同作业




在现代工业自动化领域&#xff0c;MODBUS TCP和CANopen两种通讯协议因其稳定性和高效性被广泛应用于各种设备和系统中。而随着科技的不断进步&#xff0c;这两种通讯协议也正在被逐步融合&#xff0c;形成了一种新型的通讯方式——开疆智能MODBUS TCP转CANopen网关KJ-TCPC-CANP…...






编程新知
2025/10/27 7:02:56



















Spring Boot面试题精选汇总




&#x1f91f;致敬读者 
&#x1f7e9;感谢阅读&#x1f7e6;笑口常开&#x1f7ea;生日快乐⬛早点睡觉 
&#x1f4d8;博主相关 
&#x1f7e7;博主信息&#x1f7e8;博客首页&#x1f7eb;专栏推荐&#x1f7e5;活动信息 文章目录 Spring Boot面试题精选汇总⚙️ **一、核心概…...






编程新知
2025/9/24 23:08:17



















Robots.txt 文件




什么是robots.txt&#xff1f; 
robots.txt 是一个位于网站根目录下的文本文件&#xff08;如&#xff1a;https://example.com/robots.txt&#xff09;&#xff0c;它用于指导网络爬虫&#xff08;如搜索引擎的蜘蛛程序&#xff09;如何抓取该网站的内容。这个文件遵循 Robots…...






编程新知
2025/9/9 5:38:23



















DBAPI如何优雅的获取单条数据




API如何优雅的获取单条数据 
案例一 
对于查询类API&#xff0c;查询的是单条数据&#xff0c;比如根据主键ID查询用户信息&#xff0c;sql如下&#xff1a; 
select id, name, age from user where id  #{id}API默认返回的数据格式是多条的&#xff0c;如下&#xff1a; 
{&qu…...






编程新知
2025/10/27 21:59:28



















Python如何给视频添加音频和字幕




在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 
环境准备 
在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...






编程新知
2025/9/3 4:12:17



















【JavaSE】绘图与事件入门学习笔记




-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。  坐标体系-像素 …...






编程新知
2025/9/12 0:24:07



















多种风格导航菜单 HTML 实现（附源码）




下面我将为您展示 6 种不同风格的导航菜单实现&#xff0c;每种都包含完整 HTML、CSS 和 JavaScript 代码。 
1. 简约水平导航栏 <!DOCTYPE html>
<html lang"zh-CN">
<head><meta charset"UTF-8"><meta name"viewport&qu…...






编程新知
2025/10/25 16:48:56