LeetCode #841 (动态规划) 习题总结

LeetCode #841 (动态规划) 习题总结

如何高效力扣? 答案是多刷和多思考

每一道题,都首先要做到读懂题,而读题也是有技巧的。 通常情况下,题目的文字描述相当晦涩难懂,有时候甚至故意搞文字游戏,为了避免这种情况,读文字只需理解大意,而更深一步的理解就反复读样例吧! 这二者之间要拿捏有度,因为过分理解文字容易绕晕,过分依赖样例理解容易局限。

😭而我这个菜🐦经常拿到题之后一筹莫展 ...

题目描述

N 个房间,开始时你位于 0 号房间。每个房间有不同的号码:0,1,2,...,N-1,并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上,对于每个房间 i 都有一个钥匙列表 rooms[i],每个钥匙 rooms[i][j][0,1,...,N-1]中的一个整数表示,其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初,除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true,否则返回 false

示例 1:

输入: [[1],[2],[3],[]]
输出: true
解释:

我们从 0 号房间开始,拿到钥匙 1。
之后我们去 1 号房间,拿到钥匙 2。
然后我们去 2 号房间,拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间,我们返回 true。

示例 2:

输入: [[1,3],[3,0,1],[2],[0]]
输出: false
解释: 我们不能进入 2 号房间。

提示:
1 <= rooms.length <= 1000
0 <= rooms[i].length <= 1000
所有房间中的钥匙数量总计不超过 3000。

来源:力扣(LeetCode)
链接: https://leetcode-cn.com/problems/keys-and-rooms

解题默认代码模板

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        // Write your code here...
    }
};

解题前的bb叨

刷算法题的大佬们都告诉我,虽然你可能自己试着用Python去刷题会很舒服很爽,几下子就做出来了,但是对于OJ来说最好的语言是C++、Go、Rust这样的系统级编程语言,而Python、JavaScript等脚本语言,虽然拥有很多立即可用的 “偷懒神器”,却很容易超时长。因为 LeetCode 为了测试你代码的正确性,样例经常很极端化。

而提到C++,对这个语言我是又爱又恨,我已经苦脑中语言之争久矣。在LeetCode上的OJ题目大多都涵盖了STL的使用,要想顺利做好题,这些语言方面的基础知识很重要。(😅却也很庞杂...)

其实吧,C++的STL 就跟 Java帮你内置好的集合类、Python内建的丰富数据结构等方式大同小异,也没什么好怕的😄

开始解题

读完题之后,思考一会儿总结道:本题答案是true还是false,取决于你是否能走到所有房间🚪。 而只要我取得一间房间的钥匙🔑,就代表可能走到该房间。所以这样的情况下我们很容易想到动态规划的方法:因为备忘就是动态规划!

我们新建一本备忘录,这个备忘录有几页呢?当然是有几个房间就有几页咯!

一开始时 0 号房间是开启的,也就是说第一次访问的是 0 号房间。 所以我们此时需要一个动作来表示 在备忘录上记住该房间我能走到。

这个动作需要哪些支持呢(即需要哪些参数?)

  • 原始数据: 房间内含有钥匙的情况
  • 我们自建的备忘录
  • 房间号:表示该房间的可访问性将由 false 变为 true

那么我们就可以写出如下代码:

void visitRooms(std::vector<std::vector<int>>& rooms, std::vector<bool> &visited, int room) {
  if(visited[room]) return;
  else {
    visited[room] = true;
    for(int i = 0; i<rooms[room].size(); i++) {
      visitRooms(rooms, visited, rooms[room][i]);
    }
  }
}

一行行解释一下:

  1. 首先写备忘录之前你得先查一遍如果该房间已经是可访问的了,那很OK就直接退出

  2. 而如果不是则把它写进备忘录,然后此时相当于我已经进入了该房间,能看到该房间里有的几把钥匙🔑(rooms[room][i])了

    那么我们依次递归执行这一访问房间、写入备忘录的操作

那么在正式的解决函数中:

bool canVisitAllRooms(std::vector<std::vector<int>>& rooms) {
  std::vector<bool> visited(rooms.size(), false);
  visitRooms(rooms, visited, 0);
  for(int i = 0; i < visited.size(); i++) {
    if(!visited[i]) return false;
  }
  return true;
}
  1. 首先构建了一个一维的布尔变量数组,作为我们的备忘录
  2. 从已经默认打开的 0 号房间开始
  3. 最后我们遍历备忘录,最后执行的结果与 “备忘录里有没有 false ” 是等价的

总结一下

总的来说这是一道相对比较简单的题目,但是确实是一道很经典的动态规划思路的题目,而我刷题刚刚起步,这样的难度正好相符。重点是要理解 “备忘录在何时用” 的问题,且要学会把 “进了房间就能看到钥匙,有了钥匙又能开房” 这样的逻辑思路转化为 “递归” 的代码。

# 刷题 

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×