首页 > 其他分享 >js.青蛙过河

js.青蛙过河

时间:2024-11-07 18:44:58浏览次数:3  
标签:stones set 过河 sum 石子 青蛙 js add

链接:403. 青蛙过河 - 力扣(LeetCode)

题目:

一只青蛙想要过河。 假定河流被等分为若干个单元格,并且在每一个单元格内都有可能放有一块石子(也有可能没有)。 青蛙可以跳上石子,但是不可以跳入水中。

给你石子的位置列表 stones(用单元格序号 升序 表示), 请判定青蛙能否成功过河(即能否在最后一步跳至最后一块石子上)。开始时, 青蛙默认已站在第一块石子上,并可以假定它第一步只能跳跃 1 个单位(即只能从单元格 1 跳至单元格 2 )。

如果青蛙上一步跳跃了 k 个单位,那么它接下来的跳跃距离只能选择为 k - 1k 或 k + 1 个单位。 另请注意,青蛙只能向前方(终点的方向)跳跃。

示例 1:

输入:stones = [0,1,3,5,6,8,12,17]
输出:true
解释:青蛙可以成功过河,按照如下方案跳跃:跳 1 个单位到第 2 块石子, 然后跳 2 个单位到第 3 块石子, 接着 跳 2 个单位到第 4 块石子, 然后跳 3 个单位到第 6 块石子, 跳 4 个单位到第 7 块石子, 最后,跳 5 个单位到第 8 个石子(即最后一块石子)。

示例 2:

输入:stones = [0,1,2,3,4,8,9,11]
输出:false
解释:这是因为第 5 和第 6 个石子之间的间距太大,没有可选的方案供青蛙跳跃过去。

提示:

  • 2 <= stones.length <= 2000
  • 0 <= stones[i] <= 231 - 1
  • stones[0] == 0
  • stones 按严格升序排列

相关标签:动态规划

思路:

这是我的思路草图,第一列为stones数组,第二列为二维数组sum索引

后面为stones数组对应石头可跳的单位长度

先让初始化sum,sum = Array.from({ length: stones.length }, () => new Set()),让sum数组使用set,以便后续重复添加可自动去重。

遍历数组中的每一个set,如果stones[f] + set中的值 是stones数组中存在的,

则让在sum[stones[f] + set中的值]的set中,加上可跳的 k - 1k 或 k + 1 个单位。

代码中的 f 是sum数组的索引,f 每次++ ,代表跳到了第几块石头。

 max说明可以跳到的最远是第几块石头。

循环结束条件是f<=max,如果遍历的石头块数比最远可跳到的第几个石头值还大,则结束循环返回false。

最远可跳到的第几个石头值如果为stones的长度-1,表示可以跳到最后一个石头上,则结束函数返回true。

代码: 

/**

 * @param {number[]} stones

 * @return {boolean}

 */

var canCross = function(stones) {

   // 使用set是为了后续自动去重

    let sum = Array.from({ length: stones.length }, () => new Set()) , n = stones.length

    let f = 0 , max = 0

    sum[0].add(1)

    while(f<=max){

        for(let i of sum[f]){

            let index = stones.indexOf(i+stones[f])

            // 表示可以跳到最后一个石头上

            if(index == n-1) return true

            if(index!=-1){

                // 用max记录最远可跳到的第几个石头值

                max = index>max?index:max

                 // 加上可跳的 k - 1、k 或 k + 1 个单位

                if(i==1){

                    sum[index].add(1)

                    sum[index].add(2)

                }else{

                    sum[index].add(i-1)

                    sum[index].add(i)

                    sum[index].add(i+1)

                }

            }

        }

        f++

    }

    return false

};

 

标签:stones,set,过河,sum,石子,青蛙,js,add
From: https://blog.csdn.net/qq_62541773/article/details/143601285

相关文章

  • 基于nodejs+vue在线音乐网站[开题+源码+程序+论文]计算机毕业设计
    本系统(程序+源码+数据库+调试部署+开发环境)带文档lw万字以上,文末可获取源码系统程序文件列表开题报告内容一、选题背景关于在线音乐网站的研究,现有研究多侧重于音乐推荐算法、版权管理等方面3。专门针对在线音乐网站整体功能架构,包括用户、歌手分类、歌曲信息等综合系统功......
  • 基于nodejs+vue在线音乐播放平台[开题+源码+程序+论文]计算机毕业设计
    本系统(程序+源码+数据库+调试部署+开发环境)带文档lw万字以上,文末可获取源码系统程序文件列表开题报告内容一、选题背景关于在线音乐播放平台的研究,现有研究主要集中在大型商业音乐平台的整体运营、用户体验优化等方面,如QQ音乐、网易云音乐等平台的功能拓展、营销策略等。......
  • 前端跨域问题全解:JSONP、CORS 与代理服务器
    在前端开发中,跨域问题常常给开发者带来困扰。当网页应用需要从不同的源(域名、协议或端口)获取数据时,浏览器会因同源策略而限制这种跨域请求。本文将深入探讨前端跨域问题的产生原因以及多种有效的解决方案,并详细介绍其具体实现步骤。一、跨域问题产生的原因浏览器的同源策略是......
  • js动画和css动画的区别?
    ‌JavaScript动画和CSS动画有一些相似之处,但它们在实现方式、控制方式和性能上有很大的不同。‌实现方式‌CSS动画‌:通过CSS属性(如transition、animation)来实现动画效果。CSS动画通过定义关键帧和动画属性,当触发条件满足时,浏览器会自动执行动画效果,并且通过硬件加速优化性......
  • node.js毕设自助收银系统的分析与研究(程序+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带文档lw万字以上,文末可获取源码系统程序文件列表开题报告内容一、选题背景随着信息技术的迅猛发展,自助收银系统在零售业中的应用越来越广泛。传统的收银方式通常需要大量的人力资源,且容易出现人为错误,效率较低。特别是在一些中......
  • node.js毕设在线心理咨询平台(程序+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带文档lw万字以上,文末可获取源码系统程序文件列表开题报告内容一、选题背景随着现代社会生活节奏的加快和竞争压力的增大,人们的心理健康问题日益凸显。据世界卫生组织(WHO)统计,全球约有3亿人患有抑郁症,而焦虑症患者也达到了约2.64......
  • Nuxt.js 应用中的 build:error 事件钩子详解
    title:Nuxt.js应用中的build:error事件钩子详解date:2024/11/7updated:2024/11/7author:cmdragonexcerpt:build:error是Nuxt.js中的一个生命周期钩子,当构建过程中发生错误时,该钩子将被调用。通过此钩子,开发者可以捕获和响应构建错误,进行相应的处理,例如记录日志或......
  • js中类数组
    在JavaScript中,类数组(Array-likeObject)是指那些拥有类似数组的结构和特征,但并不真正是数组的对象。类数组对象有以下几个特征:具有length属性:类数组对象通常都有一个length属性,表示其元素的个数。可以通过整数索引访问元素:类数组对象的元素可以通过数字索引访问,类似于数......
  • angularJs 之 ng-options 的用法:
     angularjs之ng-optionng-options一般有以下用法:对于数组:labelforvalueinarrayselectaslabelforvalueinarraylabelgroupbygroupforvalueinarraylabeldisablewhendisableforvalueinarraylabelgroupbygroupforvalueinarraytrackbytrackexp......
  • node.js毕设在线小说阅读系统(程序+论文)
    本系统(程序+源码+数据库+调试部署+开发环境)带文档lw万字以上,文末可获取源码系统程序文件列表开题报告内容一、选题背景关于在线小说阅读系统的研究,现有研究主要集中在用户阅读行为、小说推荐算法等方面,专门针对整个系统设计与实现的研究较少。在国内外,在线小说阅读系统作......