当前位置: 首页 > article >正文

力扣 754 到达终点数字 思路讲解

在这里插入图片描述
在这里插入图片描述
题意

  • 从i=1开始,到i=target,所需要的最小移动次数
  • 每次移动可以向左也可以向右
  • 移动的距离遵守 1,2,3,4,5,…n

思路

  • 向左移动x可以等效成向右移动-x,左右移动等效成向右移动适当加-号
  • 分情况讨论
  1. 一直往右移动,刚好到达 target,此时次数最少为n
  2. 一直往右移动,超过target距离为d

d为偶数
即将d/2反向,即可到达target, 最少为 n+1。证明:d/2一定在[1, n]中。
显而易见:d 的最大值为,从n-1跳了n部,即 d = n-1(偶数) (n-1)/2,一定在[1, n]中。最小次数为 n
d为奇数
由于反向操作只能将 s 减少偶数,无法处理相距奇数的情况,必须多走一两步,将相距变为偶数,才能处理。 将一个数num反向,则造成的结果为sum-2*num
1.向往回走一步n+1,在往前走一步n+2,n+2-(n+1)=1, 此时d+1一定为偶数,回到上述情况。最小次数为n+2
2.往前继续走一步,n+1, 如果n+1+d<2n为偶数,则将[n+1+d]/2改为负数,最小次数为n+1
3.往前继续一步,n+1,如果 n+1+d<2n为奇数。则继续往前一步,n+1+d+n+2必为偶数,
n+2 <= (2n+3+d)/2 <= 1.5n+1,当d=1,和d=n-1时成立,最小次数为n+2

第1种情况和第3种情况是同一种情况。
在这里插入图片描述
图来至于灵茶灵神题解


http://www.kler.cn/a/586496.html

相关文章:

  • 快速使用Python爬虫根据关键词获取衣联网商品列表:实战指南
  • 【教学类-43-26】20240312 数独4宫格的所有可能(图片版 576套样式,空1格-空8格,每套65534张*576小图=3千万张小图)
  • 亚马逊自养号测评,IP纯净度的重要性
  • 使用Composer实现自动加载类
  • 指令微调 (Instruction Tuning) 与 Prompt 工程
  • Spring @RequestMapping 注解详解
  • python--面试题--基础题
  • 优化 Java 数据结构选择与使用,提升程序性能与可维护性
  • 云原生大佬重生,记忆逐步复苏(十三:selinux模块)
  • 天梯赛-前世档案 二进制的巧妙使用
  • Qt常用控件之表单布局QFormLayout
  • 测试开发 - 正浩创新 - 一面面经(已OC)
  • 场景题:一个存储IP地址的100G 的文件, 找出现次数最多的 IP ?
  • 嵌入式学习L6网络编程D3TCP
  • Sidekick:你的 macOS 本地 AI 助手,畅享智能对话!
  • 0011__Apache Spark
  • 帮助和配置文件
  • DataWhale 大语言模型 - Transformer模型介绍
  • MindGYM:一个用于增强视觉-语言模型推理能力的合成数据集框架,通过生成自挑战问题来提升模型的多跳推理能力。
  • Redis分布式锁深度剖析:从原理到Redisson实战,破解脑裂与高并发锁难题