LeetCode 841 钥匙和房间(怎么减少程序运行时间、BFS、lambda、sync_with_stdio、cin.tie)

编程之美

Posted by 白夜行的狼 on September 4, 2018

0. 写在最前面

本文持续更新地址:https://haoqchen.site/2018/09/04/LeetCode841/

你的Star是作者坚持下去的最大动力哦~~~

  今天刷841的时候看到一个大神写的巨高级的代码。在这里分享以下。这位大神用了BFS来解题,然后其中穿插了lambda表达式、stdio与输入输出流相关的知识。读懂后恍然大悟~~~~

title

该大神的答案:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
static auto x = []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

class Solution {
public:
    bool canVisitAllRooms(vector<vector<int>>& rooms) {
        int room_nums = rooms.size();
        list<int> li;
        vector<bool> vb(room_nums, false);
        int visit_cnt = 0;
        li.push_back(0);
        ++visit_cnt;
        vb[0] = true;
        while(!li.empty())
        {
            int idx = li.front();
            li.pop_front();
            
            int len = rooms[idx].size();
            for(int i = 0; i < len; ++i)
            {
                if(!vb[rooms[idx][i]])
                {
                    li.push_back(rooms[idx][i]);
                    vb[rooms[idx][i]] = true;
                    ++visit_cnt;
                }
            }
        }
        return visit_cnt == room_nums;
    }
};

  solution采用BFS来进行解答,相信很多人都能想到,我自己也是这么写的。先定义一个跟rooms长度一样的bool数组vb,初始化为0。如果访问到了一个还未访问的房间(vb为0)则vb相应位置1,并将相应的房间序号放到队列中。对队列进行遍历,最后比较已经访问的房间数跟总房间数是否一直来判断是否都可达。

然而精彩的地方在于:

1
2
3
4
5
6
static auto x = []()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    return 0;
}();

  这里作者采用定义变量x的形式让这段代码在main函数前被调用。这里的{…}其实是一个lambda表达式,然后x是调用该表达式(后面的();表明其是对表达式的调用),然后用auto做类型声明。同时static表明该变量只用于当前文件,不影响其他文件中的x变量。

  然后为什么要这么做呢?因为C++的cin和cout为了兼容C中的scanf、printf(在stdio.h中)函数,让C++代码中可以同时用这四个函数。C++中的输入输出都是先放到缓冲区,再输出。所以效率非常的低,甚至有人做过实验,如果用scanf来进行操作只要2秒,而用cin居然要8秒。ios::sync_with_stdio(false);的作用就是取消iostream的这种兼容。但是需要注意的是,如果取消了这种兼容,C++和C中的输入输出就不能混用了(理论上C++的cin要比scanf快)。

  然后cin.tie(nullptr);的作用是取消cin跟cout的绑定。tie是将两个stream绑定的函数,比如可以将输入跟某个文件流指针绑定,就可以直接往文件中输入了。默认cin与cout绑定,解除后可以加快两者的速度,原理没有深入进去尚且不明。

参考

lambda表达式参考博客
IO口加速参考博客


喜欢我的文章的话Star一下呗Star

版权声明:本文为白夜行的狼原创文章,未经允许不得以任何形式转载