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

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

news 2025/12/16 9:13:42

给定两个字符串，分别为字符串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





















日语AI面试高效通关秘籍：专业解读与青柚面试智能助攻




在如今就业市场竞争日益激烈的背景下&#xff0c;越来越多的求职者将目光投向了日本及中日双语岗位。但是&#xff0c;一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧&#xff1f;面对生疏的日语交流环境&#xff0c;即便提前恶补了…...






编程新知
2025/12/15 19:31:14



















Java 语言特性(面试系列2)




一、SQL 基础 1. 复杂查询 &#xff08;1&#xff09;连接查询&#xff08;JOIN&#xff09; 内连接&#xff08;INNER JOIN&#xff09;&#xff1a;返回两表匹配的记录。 SELECT e.name, d.dept_name
FROM employees e
INNER JOIN departments d ON e.dept_id  d.dept_id; 左…...






编程新知
2025/10/24 14:20:29



















【杂谈】-递归进化：人工智能的自我改进与监管挑战




递归进化&#xff1a;人工智能的自我改进与监管挑战 文章目录 递归进化&#xff1a;人工智能的自我改进与监管挑战1、自我改进型人工智能的崛起2、人工智能如何挑战人类监管&#xff1f;3、确保人工智能受控的策略4、人类在人工智能发展中的角色5、平衡自主性与控制力6、总结与…...






编程新知
2025/12/9 0:22:01



















docker详细操作--未完待续




docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 
Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...






编程新知
2025/12/15 20:23:19



















练习（含atoi的模拟实现,自定义类型等练习）




一、结构体大小的计算及位段 
&#xff08;结构体大小计算及位段 详解请看&#xff1a;自定义类型&#xff1a;结构体进阶-CSDN博客&#xff09; 
1.在32位系统环境&#xff0c;编译选项为4字节对齐&#xff0c;那么sizeof(A)和sizeof(B)是多少&#xff1f; 
#pragma pack(4)st…...






编程新知
2025/12/15 11:25:14



















Cloudflare 从 Nginx 到 Pingora：性能、效率与安全的全面升级




在互联网的快速发展中&#xff0c;高性能、高效率和高安全性的网络服务成为了各大互联网基础设施提供商的核心追求。Cloudflare 作为全球领先的互联网安全和基础设施公司&#xff0c;近期做出了一个重大技术决策&#xff1a;弃用长期使用的 Nginx&#xff0c;转而采用其内部开发…...






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



















【python异步多线程】异步多线程爬虫代码示例




claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 
代码 
Python多线程爬虫教程 
核心概念 
多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...






编程新知
2025/10/24 7:04:27



















【论文阅读28】-CNN-BiLSTM-Attention-（2024）




本文把滑坡位移序列拆开、筛优质因子&#xff0c;再用 CNN-BiLSTM-Attention 来动态预测每个子序列&#xff0c;最后重构出总位移&#xff0c;预测效果超越传统模型。 文章目录 1 引言2 方法2.1 位移时间序列加性模型2.2 变分模态分解 (VMD) 具体步骤2.3.1 样本熵&#xff08;S…...






编程新知
2025/12/14 18:18:37



















springboot 日志类切面，接口成功记录日志，失败不记录




springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 
自定义一个注解方法 import java.lang.annotation.ElementType;
import java.lang.annotation.Retention;
import java.lang.annotation.RetentionPolicy;
import java.lang.annotation.Target;/***…...






编程新知
2025/12/10 18:41:12



















GraphRAG优化新思路-开源的ROGRAG框架




目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...






编程新知
2025/12/14 9:30:02