算法练习-2:送外卖
n 个小区排成一列,编号为从 0 到 n-1 。一开始,美团外卖员在第0号小区,目标为位于第 n-1 个小区的配送站。
给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] ,在每个小区 i 里你有两种选择:
1) 选择a:向前 a[i] 个小区。
2) 选择b:向前 b[i] 个小区。
把每步的选择写成一个关于字符 ‘a’ 和 ‘b’ 的字符串。求到达小区n-1的方案中,字典序最小的字符串。如果做出某个选择时,你跳出了这n个小区的范围,则这个选择不合法。
• 当没有合法的选择序列时,输出 “No solution!”。
• 当字典序最小的字符串无限长时,输出 “Infinity!”。
• 否则,输出这个选择字符串。
字典序定义如下:串s和串t,如果串 s 字典序比串 t 小,则
• 存在整数 i ≥ -1,使得∀j,0 ≤ j ≤ i,满足s[j] = t[j] 且 s[i+1] < t[i+1]。
• 其中,空字符 < ‘a’ < ‘b’。
简述:现有一个整数n,及两个长度为n的数组num1和num2,每个数组中的元素i表示能够在当前位置移动的距离(正/负),每次在位置i移动时可以选择num1[i]或num2[i],要求通过选择num1和num2来移动,最终到达n-1的位置,其中使用"a"和"b"分别表示选择的数组,最终得到一个字符串s,返回最小字典序的s,其他情况:若最小字典序无限长则返回"Infinity!",若不能到达n-1位置则返回"No solution!"
思路:
首先理解题意,现在需要返回三种值:s,"Infinity!"和"No solution!":
① s和"No solution!":当能到达n-1位置并返回最小字典序s,不能到达返回"No solution!";(解决,能过90%样例)
② "Infinity!":需要能够到达n-1的位置,同时s为最小字典序,且路径中有环;(本题难点,刚开始没理解为什么有环还能到终点,不应该在环里循环出不去吗,画了个图才理解)

简单讲就是,由于每个位置有两个选择,所以即使其中一个选择遇到环,最终也能在该位置通过选择另一个选择来跳出环(如果两个选择都是环,那就是不可达"No solution!")。
1、选择DFS算法求解;
2、设定一个全局数组来记录当前位置选择过几遍,来解决是否存在环的问题;
3、对于最小字典序,在DFS里将选择"a"的数组放在选择"b"的数组上面,就可以保证最终得到的是最小字典序(可以这样理解,由于有两个数组,所以可以看做成一个二叉树遍历,把"a"放在上面表示先序遍历,而先序遍历先遍历根"a",然后左子树"a",最后右子树"b",可能理解有误欢迎交流讨论);
代码:
import java.util.*;public class Main {private static StringBuilder ans = new StringBuilder(); // 记录字典序最小字符串private static int[] a; // 数组aprivate static int[] b; // 数组bprivate static int[] visit; // 记录是否经过当前位置private static boolean loop = false; // 判断是否有环public static void main(String[] args){Scanner in = new Scanner(System.in);int len = in.nextInt();a = new int[len];b = new int[len];visit = new int[len];for(int i = 0; i < len; i++){a[i] = in.nextInt();}for(int i = 0; i < len; i++){b[i] = in.nextInt();}if(dfs(0, len-1)){if(loop){ // 能到达存在环System.out.println("Infinity!");}else{ // 能到达不存在环System.out.println(ans);}}else{ // 不能到达System.out.println("No solution!");}}// 输入当前位置及最终位置,返回是否到达终点public static boolean dfs(int cur, int target){// 边界判断if(cur < 0 || cur > target){return false;}// 条件判断if(cur == target){return true;}// 是否存在环if(visit[cur] > 0){visit[cur]++;return false;}visit[cur]++; // 记录当前位置访问次数/*选择"a"的过程,先添加字符,然后判断当前位置能否到达终点,如果能到达返回true,能到达的同时如果当前位置访问次数大于1,说明该位置存在环。如果不能到达,则删除"a",去判断"b"*/ans.append("a");if(dfs(cur+a[cur], target)){if(visit[cur] > 1){loop = true;}return true;}ans.deleteCharAt(ans.length()-1);ans.append("b");if(dfs(cur+b[cur], target)){if(visit[cur] > 1){loop = true;}return true;}ans.deleteCharAt(ans.length()-1);// "a"和"b"都不能到达,返回falsereturn false;}}
相关文章:
算法练习-2:送外卖
n 个小区排成一列,编号为从 0 到 n-1 。一开始,美团外卖员在第0号小区,目标为位于第 n-1 个小区的配送站。 给定两个整数数列 a[0]~a[n-1] 和 b[0]~b[n-1] ,在每个小区 i 里你有两种选择: 1) 选择a:向前 a[…...
八股总结(六):Android基础:四大组件与UI控件
文章目录 Activity一个APP的启动过程基本概念总图zygote是什么?有什么作用?SystemServer是什么?有什么用,与zygote的关系是什么?为什么称为服务端对象?APP、AMS、zygote是三个独立的进程,他们之…...
【P46】JMeter 响应断言(Response Assertion)
文章目录 一、响应断言(Response Assertion) 参数说明二、准备工作三、测试计划设计3.1、包括3.2、匹配3.3、相等3.4、字符串3.5、字符串3.6、或者 一、响应断言(Response Assertion) 参数说明 可以对 Jmeter 取样器的响应消息进…...
19-02 基于业务量级的架构技术选型演进
从零开始——单服务应用 单体应用技术选型 (GitHub、Gitee…)搜索是否有线程的产品用最熟悉的技术,最快的速度上线如果有经费:考虑商业化解决方案 个人小程序怎么做技术选型的 搜索是否有快速搭建下程序的软件技术选型 后端技…...
Server - 高性能的 PyTorch 训练环境配置 (PyTorch3D 和 FairScale)
欢迎关注我的CSDN:https://spike.blog.csdn.net/ 本文地址:https://blog.csdn.net/caroline_wendy/article/details/130863537 PyTorch3D 是基于 PyTorch 的 3D 数据深度学习库,提供了高效、模块化和可微分的组件,以简化 3D 深度学…...
小猫踩球-第14届蓝桥杯省赛Scratch中级组真题第2题
[导读]:超平老师的《Scratch蓝桥杯真题解析100讲》已经全部完成,后续会不定期解读蓝桥杯真题,这是Scratch蓝桥杯真题解析第137讲。 小猫踩球,本题是2023年5月7日举行的第14届蓝桥杯省赛Scratch图形化编程中级组真题第2题…...
嵌入式开发从入门到精通之第二十一节:三轴加速度传感器(BMA250E)
目录 1、工作模式 2、中断支持的模式 2.1 新数据的产生 2.2 任何斜率的变化的监测...
代码随想录算法训练营第三十六天|435. 无重叠区间 763.划分字母区间 56. 合并区间
目录 LeeCode 435. 无重叠区间 LeeCode 763.划分字母区间 LeeCode 56. 合并区间 LeeCode 435. 无重叠区间 435. 无重叠区间 - 力扣(LeetCode) 思路1:按照右边界排序,从左向右记录非交叉区间的个数。最后用区间总数减去非交叉…...
shell 脚本
Shell概述 shell是一个命令行解释器,它接收应用程序/用户命令,然后调用操作系统内核 脚本入门 脚本格式 脚本以#!/bin/bash开头(指定解析器) helloworld # 创建脚本 [linuxlocalhost datas]$ cat helloworld.sh #!/bin/bas…...
Linux :: 【基础指令篇 :: 用户管理(补充):(4)】::用户切换
前言:本篇是 Linux 基本操作篇章的内容! 笔者使用的环境是基于腾讯云服务器:CentOS 7.6 64bit。 学习集: C 入门到入土!!!学习合集Linux 从命令到网络再到内核!学习合集 目录索引&am…...
打印机无法扫描的原因及解决方法
在家庭和办公环境中,打印机已成为不可或缺的设备。它不仅可以打印文件,还可以扫描文档并将它们转换为数字数据。但有时,打印机可能无法扫描文档或图片。以下是可能导致这些问题的原因和解决方法。 出现打印机无法扫描的原因: 1.…...
【Mysql】 数据类型
文章目录 【Mysql】 数据类型数据类型分类数值类型1. tinyint类型2. bit类型3. 小数类型 字符串类型1.char2.varchar3. 日期和时间类型4. enum 和 set 【Mysql】 数据类型 mysql中数据类型的作用: 约束操作者的行为更清晰的代码逻辑不同的功用 – 例如,…...
mysql中如何使用乐观锁和悲观锁
MySQL中可以使用SELECT ... FOR UPDATE语句来实现悲观锁。这个语句会在查询时锁定被查询的行,在事务结束前都不会释放锁。 例如,我们可以使用以下的 SQL 语句来锁定一个特定的行: BEGIN; SELECT * FROM table WHERE id 1 FOR UPDATE; ... C…...
Logstash技术栈总结
Logstash 是一个可以传输和处理你的日志、事务或其他数据的功能强大的工具,可与各种部署集成。 它提供了大量插件,可帮助你解析,丰富,转换和缓冲来自各种来源的数据。 工作原理 Logstash 事件处理有三个阶段:inputs …...
解决:在单项目组件里面引入 base.scss/ base.less 等的外部文件不成功的问题
1、问题展示: 其一、问题描述: 在单文件组件里面使用封装在 base.scss 或 base.less 里面的样式用法一直不成功; 其二、代码: // 虽然已经标明了用的是 scss 的语法,但是页面调用 .scss 里的 style 样式还是不成功&a…...
论文分享 | WSBERT:Weighted Sampling for Masked Language Modeling
本次分享阿里巴巴达摩院语音实验室、新南威尔士大学与香港科技大学(广州)等在ICASSP2023会议发表的论文《Weighted Sampling for Masked Language Modeling》。该论文主要提出了两种简单有效的加权采样策略,来缓解掩码语言模型(ML…...
java 在线音乐网站系统Myeclipse开发mysql数据库struts2结构java编程计算机网页项目
一、源码特点 java 在线音乐网站系统 是一套完善的web设计系统,对理解JSP java编程开发语言有帮助struts2开发技术,系统具有完整的源代码和数据库,系统主要采用B/S模式开发。开发环境为 TOMCAT7.0,Myeclipse8.5开发,数据库为Mys…...
软件测试基础教程学习1
文章目录 软件测试概述1.1 什么是软件测试1.2 软件测试的目的1.3 对软件测试的理解1.4 软件测试的原则1.5 测试人员的职责1.6 测试人员的素质要求 软件测试概述 1.1 什么是软件测试 1)软件测试要发现软件的错误。 2)软件测试最终要以软件满足用户需求为…...
浅谈一下@Async和SpringSecurityContext可能会遇到的问题和解决方案
Async和SpringSecurityContext 场景回溯 在执行一个用时较长的批量插入业务的时候,我尝试使用Async异步对业务进行优化,但是却给我报了空指针的错误,定位之后发现 此处我是基于SpringSecurity来获取用户的 是currentUserService获取到的当前登陆用户为空导致的,但是当前确实是…...
VUE常见面试题
1.为什么要使用Vue? 答:Vue是一款优秀的前端框架,它可以帮助我们快速构建高效、可复用、易维护的Web应用程序,并提供了丰富的API和生态系统。 2. Vue有哪些生命周期钩子函数? 答:Vue有8个生命周期钩子函…...
日语AI面试高效通关秘籍:专业解读与青柚面试智能助攻
在如今就业市场竞争日益激烈的背景下,越来越多的求职者将目光投向了日本及中日双语岗位。但是,一场日语面试往往让许多人感到步履维艰。你是否也曾因为面试官抛出的“刁钻问题”而心生畏惧?面对生疏的日语交流环境,即便提前恶补了…...
PHP和Node.js哪个更爽?
先说结论,rust完胜。 php:laravel,swoole,webman,最开始在苏宁的时候写了几年php,当时觉得php真的是世界上最好的语言,因为当初活在舒适圈里,不愿意跳出来,就好比当初活在…...
.Net框架,除了EF还有很多很多......
文章目录 1. 引言2. Dapper2.1 概述与设计原理2.2 核心功能与代码示例基本查询多映射查询存储过程调用 2.3 性能优化原理2.4 适用场景 3. NHibernate3.1 概述与架构设计3.2 映射配置示例Fluent映射XML映射 3.3 查询示例HQL查询Criteria APILINQ提供程序 3.4 高级特性3.5 适用场…...
DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI
前一阵子在百度 AI 开发者大会上,看到基于小智 AI DIY 玩具的演示,感觉有点意思,想着自己也来试试。 如果只是想烧录现成的固件,乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外,还提供了基于网页版的 ESP LA…...
06 Deep learning神经网络编程基础 激活函数 --吴恩达
深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...
聊一聊接口测试的意义有哪些?
目录 一、隔离性 & 早期测试 二、保障系统集成质量 三、验证业务逻辑的核心层 四、提升测试效率与覆盖度 五、系统稳定性的守护者 六、驱动团队协作与契约管理 七、性能与扩展性的前置评估 八、持续交付的核心支撑 接口测试的意义可以从四个维度展开,首…...
C++.OpenGL (14/64)多光源(Multiple Lights)
多光源(Multiple Lights) 多光源渲染技术概览 #mermaid-svg-3L5e5gGn76TNh7Lq {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-3L5e5gGn76TNh7Lq .error-icon{fill:#552222;}#mermaid-svg-3L5e5gGn76TNh7Lq .erro…...
GitHub 趋势日报 (2025年06月06日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 590 cognee 551 onlook 399 project-based-learning 348 build-your-own-x 320 ne…...
pgsql:还原数据库后出现重复序列导致“more than one owned sequence found“报错问题的解决
问题: pgsql数据库通过备份数据库文件进行还原时,如果表中有自增序列,还原后可能会出现重复的序列,此时若向表中插入新行时会出现“more than one owned sequence found”的报错提示。 点击菜单“其它”-》“序列”,…...
【51单片机】4. 模块化编程与LCD1602Debug
1. 什么是模块化编程 传统编程会将所有函数放在main.c中,如果使用的模块多,一个文件内会有很多代码,不利于组织和管理 模块化编程则是将各个模块的代码放在不同的.c文件里,在.h文件里提供外部可调用函数声明,其他.c文…...
