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

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

news 2026/2/7 22:43: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





















变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析




一、变量声明设计&#xff1a;let 与 mut 的哲学解析 
Rust 采用 let 声明变量并通过 mut 显式标记可变性&#xff0c;这种设计体现了语言的核心哲学。以下是深度解析&#xff1a; 
1.1 设计理念剖析 
安全优先原则&#xff1a;默认不可变强制开发者明确声明意图 
let x  5;   …...






编程新知
2025/9/28 20:12:12



















React hook之useRef




React useRef 详解 
useRef 是 React 提供的一个 Hook&#xff0c;用于在函数组件中创建可变的引用对象。它在 React 开发中有多种重要用途&#xff0c;下面我将全面详细地介绍它的特性和用法。 
基本概念 
1. 创建 ref 
const refContainer  useRef(initialValue);initialValu…...






编程新知
2025/6/11 15:21:26



















UE5 学习系列（三）创建和移动物体




这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; 
B 站视频&#xff1a;s03-创建和移动物体 
如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...






编程新知
2026/1/24 10:00:31



















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




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






编程新知
2026/2/6 9:48:02



















BCS 2025｜百度副总裁陈洋：智能体在安全领域的应用实践




6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...






编程新知
2026/2/1 11:33:19



















鱼香ros docker配置镜像报错：https://registry-1.docker.io/v2/




使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 
wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 
网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...






编程新知
2025/12/31 6:28:08



















MySQL用户和授权




开放MySQL白名单 
可以通过iptables-save命令确认对应客户端ip是否可以访问MySQL服务&#xff1a; test: # iptables-save | grep 3306 -A mp_srv_whitelist -s 172.16.14.102/32 -p tcp -m tcp --dport 3306 -j ACCEPT -A mp_srv_whitelist -s 172.16.4.16/32 -p tcp -m tcp -…...






编程新知
2025/8/25 19:12:45



















【分享】推荐一些办公小工具




1、PDF 在线转换 
https://smallpdf.com/cn/pdf-tools 
推荐理由&#xff1a;大部分的转换软件需要收费&#xff0c;要么功能不齐全&#xff0c;而开会员又用不了几次浪费钱&#xff0c;借用别人的又不安全。 
这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...






编程新知
2026/1/25 14:40:59



















如何更改默认 Crontab 编辑器 ？




在 Linux 领域中&#xff0c;crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用&#xff0c;用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益&#xff0c;允许他们自动执行各种系统任务。 
编辑 Crontab 文件通常使用文本编…...






编程新知
2026/1/30 3:27:35



















Qt 事件处理中 return 的深入解析




Qt 事件处理中 return 的深入解析 
在 Qt 事件处理中&#xff0c;return 语句的使用是另一个关键概念&#xff0c;它与 event->accept()/event->ignore() 密切相关但作用不同。让我们详细分析一下它们之间的关系和工作原理。 
核心区别&#xff1a;不同层级的事件处理 
方…...






编程新知
2025/6/10 21:19:52