宝宝也能看懂的 leetcode 周赛 - 169 - 3

1306. Jump Game III

Hi 大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之 leetcode 题解。

这里是第 169 期的第 3 题,也是题目列表中的第 1306 题 -- 『Jump Game III』

题目描述

Given an array of non-negative integers arr, you are initially positioned at start index of the array. When you are at index i, you can jump to i + arr[i] or i - arr[i], check if you can reach to any index with value 0.

Notice that you can not jump outside of the array at any time.

Example 1:

Input: arr = [4,2,3,0,3,1,2], start = 5
Output: true
Explanation:
All possible ways to reach at index 3 with value 0 are:
index 5 -> index 4 -> index 1 -> index 3
index 5 -> index 6 -> index 4 -> index 1 -> index 3

Example 2:

Input: arr = [4,2,3,0,3,1,2], start = 0
Output: true
Explanation:
One possible way to reach at index 3 with value 0 is:
index 0 -> index 4 -> index 1 -> index 3

Example 3:

Input: arr = [3,0,2,1,2], start = 2
Output: false
Explanation: There is no way to reach at index 1 with value 0.

Constraints:

1 <= arr.length <= 5 * 10^4
0 <= arr[i] < arr.length
0 <= start < arr.length

官方难度

MEDIUM

解决思路

题目的内容是一个小游戏,可以想象这样一个场景:

  1. 面前放着几张纸牌,每个纸牌下面写着一个数字
  2. 游戏开始时,作为我们起始位置的纸牌已经确定啦
  3. 把纸牌翻过来,看到后面的数字为 n,那么我们现在可以选择向左走 n 步或者向右走 n 步,但是不能超出纸牌的范围
  4. 不断的重复这个过程,直到我们遇到翻过来的数字为 0 我们就成功啦
  5. 如果无论如何都找不到 0,那么我们就失败啦

那么回到题目中,纸牌和背后的数字是一个给定的由非负整数组成的数组,起始位置是给定的一个下标,我们需要返回 true 或者 false

我们先想一想,如果是玩这个游戏的话,我们会怎么玩呢?由于出发点是确定的,而结束的点不确定,因为可能会有多个 0 的存在,所以我们可以从出发点开始不断的做尝试。基于此我们可以得到两种思路:

  • 遇到了选择左右的情况时,我们把两种情况都记录下来,然后继续针对所有已经记录的内容逐个继续尝试,不过需要注意循环的情况。
  • 遇到了选择左右的情况时,先选择一个方向,然后继续走下去,直到发生了循环再退到上一个选择点重新选择。

其实上述两种思路也就对应了两种很常见的遍历思路,即广度优先遍历和深度优先遍历。这部分内容我会在数据结构的新坑中详细介绍。

广度优先遍历

基于上面的第一种思路,我们用到了一个 visited 集合来判断是否已经访问过,从而规避循环。同时我们用一个 queue 来保存所有记录节点,方便基于延伸。具体代码如下:

const canReach = (arr, start) => {
  const visited = new Set();
  const queue = [start];
  for (let len = 0, max = arr.length; len < queue.length; ++len) {
    const idx = queue[len];
    if (visited.has(idx)) continue;
    if (arr[idx] === 0) return true;
    visited.add(idx);
    idx + arr[idx] < max && queue.push(idx + arr[idx]);
    idx - arr[idx] >= 0 && queue.push(idx - arr[idx]);
  }
  return false;
};

这里算是一个非常常见的广度优先遍历的实现模板了,不过具体到这道题其实还可以再优化一下。我们可以注意到题目的限制条件里,arr 的每个值取值范围是 [0, arr.length]。基于此,我们可以通过赋值为一个范围外的特殊值来标识已经访问过,从而去掉 visited 集合的使用。我这里直接使用了 -1 作为特殊值,具体代码如下:

const canReach = (arr, start) => {
  const queue = [start];
  for (let len = 0, max = arr.length; len < queue.length; ++len) {
    const idx = queue[len];
    if (arr[idx] === -1) continue;
    if (arr[idx] === 0) return true;
    idx + arr[idx] < max && queue.push(idx + arr[idx]);
    idx - arr[idx] >= 0 && queue.push(idx - arr[idx]);
    arr[idx] = -1;
  }
  return false;
};

深度优先遍历

基于上面的第二种思路,我们可以通过基于递归的方式来实现不断的层层深入,以及遇到循环后回退。具体代码如下:

const canReach = (arr, start) => {
  const val = arr[start];
  if (val === 0) return true;
  if (val === -1) return false;
  arr[start] = -1;
  return (start - val >= 0 && canReach(arr, start - val)) || (start + val < arr.length && canReach(arr, start + val));
};

递归实现的一个很明显的好处就是,看起来代码量更少了。特别适合懒懒的张小猪本猪,哈哈哈哈 >.<

另外值得注意的一点是,我们这里没有用到那个额外的 queue 去记录。那么是否我们的额外空间复杂度就是 O(1) 了呢?其实并不是的。因为我们其实是通过递归的调用栈来变相的记录了路径和回退过程。所以,在考虑额外的空间复杂度的时候,我们需要把递归的调用栈考虑进去,也就是说这里的空间复杂度其实还是 O(n)。

最后,利用到参数的默认值可以进行运算、逻辑运算符、以及逗号表达式,我们可以把上述代码变成一行实现,具体如下:

const canReach = (arr, start, val = arr[start]) => val === 0 || (arr[start] = -1, val !== -1) && ((start - val >= 0 && canReach(arr, start - val)) || (start + val < arr.length && canReach(arr, start + val)));

友情提示:生产环境中不要这样写哈,被打死我不负责,哈哈哈哈。

总结

这道题中我们可以了解到深度优先遍历和广度优先遍历这两种遍历思路,以及在具体的场景中我们还可以做的一些小优化。这两种遍历方式在以后应该会挺常见的。最后再强调一下,一行的那个写法真的会被同事打死的,哈哈哈哈嗝 >.<

相关链接

Image placeholder
zhangleilei
未设置
  26人点赞

没有讨论,发表一下自己的看法吧

推荐文章
宝宝也能看懂的 leetcode 周赛 - 169 - 2

1305.AllElementsinTwoBinarySearchTreesHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第2题,也是题目列表中的第13

宝宝也能看懂的 leetcode 周赛 - 169 - 1

1304.FindNUniqueIntegersSumuptoZeroHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第1题,也是题目列表中的第1304题

宝宝也能看懂的 leetcode 周赛 - 169 - 4

1307.VerbalArithmeticPuzzleHi大家好,我是张小猪。欢迎来到『宝宝也能看懂』系列之leetcode题解。这里是第169期的第4题,也是题目列表中的第1307题--『Verba

我从来不觉得程序员是吃青春饭的!这里有169万份分析数据

阅读本文约需要5分钟程序员这个职业究竟可以干多少年,在中国这片神奇的土地上,很多人都说只能干到30岁,然后就需要转型。在很多面试中,问到应聘者未来的规划都能听到好些应聘都说程序员是个青春饭。因为,大多

pymysql fetchone () , fetchall () , fetchmany ()

最近在用python操作mysql数据库时,碰到了下面这两个函数,标记一下: 1.定义 1.1fetchone(): 返回单个的元组,也就是一条记录(row),如果没有结果则返回None 1.2fet

LeetCode 刷题笔记

从AmazonOA高频题开始 总结每一道做过的题目,先总结一下思路,然后记录从中获取的新知识。题目顺序不是按照序号顺序的,而是题目在真实面试中出现的频率排序。由于之前已经做过一些了,所以那些题目暂时还

用 Rust 刷 leetcode 第二题

Problem Youaregiventwonon-emptylinkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredinre

用 Rust 刷 leetcode 第一题

problemGivenanarrayofintegers,return indices ofthetwonumberssuchthattheyadduptoaspecifictarget. Youm

用 Rust 刷 leetcode 第二题

ProblemYouaregiventwo non-empty linkedlistsrepresentingtwonon-negativeintegers.Thedigitsarestoredin 

LeetCode 112. 路径总和

描述给定一个二叉树和一个目标和,判断该树中是否存在根节点到叶子节点的路径,这条路径上所有节点值相加等于目标和。说明:叶子节点是指没有子节点的节点。注意点:必须联通到叶节点分析从根节点开始,每当遇到一个

算法-最小栈-LeetCode155

题目最小栈设计一个支持push,pop,top操作,并能在常数时间内检索到最小元素的栈。push(x) --将元素x推入栈中。pop() --删除栈顶的元素。top() --获取栈顶元素。getMin

算法-下一个更大元素 I-LeetCode.496

题目下一个更大的元素I给定两个没有重复元素的数组 nums1和 nums2 ,其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数

Leetcode上最南的是哪道题?

大家伙想要找份好工作,刷题是一道绕不过的坎,Leetcode大家都很熟悉了,很多公司面试的时候会用上面的原题,今天我们就来看看这Leetcode上的题!首先依然通过利索的爬虫获取了Leetcode官网

全网最通俗易懂的Kafka入门

前言只有光头才能变强。文本已收录至我的GitHub仓库,欢迎Star:https://github.com/ZhongFuCheng3y/3y众所周知,消息队列的产品有好几种,这里我选择学习Kafka

终于有篇看的懂的 B 树文章了!

索引,相信大多数人已经相当熟悉了,很多人都知道MySQL的索引主要以B+树为主,但是要问到为什么用B+树,恐怕很少有人能把前因后果讲述完整。本文就来从头到尾介绍下数据库的索引。索引是一种数据结构,用于

一篇文章看懂,存储虚拟化在不同用例中的实践与优势

存储虚拟化是一种对物理存储资源进行抽象的技术,使其看起来像是一个集中的资源。虚拟化掩盖了管理内存、网络、服务器和存储中资源的复杂性。存储虚拟化运行在多个存储设备上,使它们看起来就像一个单一的存储池。这

DeepFakes进化版DeepNude惊现!一键“脱衣“,火到宕机

大数据文摘出品作者:蒋宝尚、赵伟人工智能的黑暗面能有多黑?这边DeepFake带来的余震还没有被平息,本周,又一AI偏门应用爆出,一键直接“脱掉”女性的衣服!海外媒体Motherboard测试图片显然

IEEE态度转变:解除对华为评审限制

大数据文摘出品作者:周素云、魏子敏IEEE的态度发生变化。今晨,IEEE电气电子工程师学会中国官网及官方公众号同时发出声明,表示IEEE向美国商务部要求就出口管制条例在IEEE出版活动的适用性做出说明

PHP跌出前十,铁打的 Python 连续3年第一:IEEE Spectrum 2019编程语言排行榜出炉

Python势头不减,依旧第一,而且进一步拉开了与其他语言的差距。这一结果,来自IEEESpectrum2019年度编程语言排行榜。这已经是Python连续3年保持第一。在Python之下,第二交椅的

IEEE官方禁止华为参与期刊审稿,当全球最大技术学术机构向政治弯腰

大数据文摘出品作者:魏子敏、宋欣仪5月29日,作为全球最大专业技术组织之一的IEEE(电气和电子工程师协会)被曝出,在发给会员的内部邮件中禁止华为员工作为旗下期刊杂志的编辑和审稿人。今天早晨,IEEE

beego 使用 coding 的 webhook 2.0 进行自动部署

beego使用coding的webhook2.0进行自动部署本文介绍beego在coding上如果使用webhook2.0进行自动部署。coding的webhook1.0教程coding平台端的设置这

PhpSpreadsheet 小教程

关于PhpSpreadsheet简单教程 今天遇到一个问题,涉及php与excel之间数据转换。之前一直用PHPExcel,他们的开发组不更新了。但是找到了PhpSpreadsheet。 一.介绍

etcd 常用操作介绍

安装 最简单的安装方法是直接去etcdGitHub的Release页下载预编译好的二进制文件。etcd官方为各个系统提供了不同的二进制文件,供开发者根据自己的系统去下载。 下载地址:https://g

etcd 常用操作介绍

安装 最简单的安装方法是直接去etcdGitHub的Release页下载预编译好的二进制文件。etcd官方为各个系统提供了不同的二进制文件,供开发者根据自己的系统去下载。 下载地址:https://g

etcd 在超大规模数据场景下的性能优化

作者|阿里云智能事业部高级开发工程师 陈星宇(宇慕)划重点etcd优化背景问题分析优化方案展示实际优化效果本文被收录在5月9日cncf.io官方blog中,链接:https://www.cncf.io