专栏首页程序员维他命带你入门 DissCode,从而攻克大厂面试题!

带你入门 DissCode,从而攻克大厂面试题!

今年七月份,我开始写公众号。有两个目的,第一是为了增加自己在技术圈内的影响力,第二是促进更多人来重视算法。于是我写了一系列文章来讲解一些大学课本上有的但是被很多人忽视的算法。比如并查集、快速幂、RMQ 问题等等。

很长时间以来,有很多读者反馈“好难”、“看不懂”等等。在回答和回怼“哪里难”、“哪里看不懂”的同时,我也在反思,为什么算法面试会让大家如此的抵触?

其实原因很简单,算法是要靠时间去学去练。

目前快速消费的时代很多人更加在乎 ROI,但其实我们知道有些东西是需要量变才能产生质变的。在原来学生时代的时候,语文和英语这两门课程都是量变才能产生质变的代表。所以想学好算法,在面试中有更好的表现,那就需要多练习

那些 x 天学懂算法的课程或许只停留在“懂”的阶段,但是面试考察的是 coding。《让技术一瓜共食》公众号内容也是这样,多半都是在我的“讲述”,没有实际的“练习”,这种模式是永远无法让你得到提高的,所以这就是为什么我要做 DissCode 的原因。我希望通过真实的题目、代码和纯白板环境来帮助读者提高算法实力。

多说无意,来看 DissCode 要怎么玩。


基于 QDUOJ 的二次开发

首先我确定 DissCode 是帮助还原面试、笔试题目的,所以我需要线上 OJ 来承载和模拟评判。

核心工作我并没有做什么,在 ICPC 圈子中有很多知名的 OJ 项目,例如 HustOJ、VerwandlungOJ、JNOJ 等等,而 DissCode 使用的是 QDUOJ(青岛大学评判系统)方案,原因是因为 QDUOJ 是服务化的架构,并且使用 Docker 灵活部署,十分方便。

另外 QDUOJ 可以使用 IO 模式和 ICPC 模式(也就是常说的 ACM 竞赛模式),而面试题往往都是当你有较为高效的解法,就算是通过了面试,这种感觉和 IO 得分规则十分相似。

如何在 DissCode 上通过 DSC1001

先放一个链接[1],在下面的原文链接也可以直接访问。

其实就是一道很简单的求解 A + B 的题目,而且是两个 32 位正整数,所以我们使用 int 类型就可以直接求解出来。但是为什么很多人提交代码后会一直 WA 呢?

这里我们要注意三个地方:

  1. 测试数据含有多组;
  2. 每组输出包含一行;
  3. 输出 A + B 的结果;

测试数据含有多组

为什么要拿出这个来讨论呢?其实这句话对于没使用过其他 OJ 的同学是存在一些歧义的。多组测试数据的意思是在一个测试文件中,会有多组测试数据。这个要从 DissCode 使用的 Judger 大致原理开始说起,便于大家方便理解,我们通过 C 语言来讲述 Judger 的评判原理。

对于 A + B 这道题目,我们首先编写了以下代码:

#include <stdio.h>

int main() {
    int a, b;
    scanf("%d %d", &a, &b);
    printf("%d", a + b);
}

这段代码编译后在本机运行,是可以求出 a + b 的结果的。但是只能求出一组输入的答案。当我们想继续输入第二组测试数据的时候,我们发现程序已经退出了。

所以我们将 scanf 输入使用 EOF 的方式进行输入,让它一直读到 ctrl+z 为止:

#include <stdio.h>

int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        printf("%d", a + b);
    }
}

这样就可以求解出多组 A + B 的结果了。

你可能会问到为什么我们要一直读到 ctrl+z 呢?DissCode 到底是如何确定输入终止条件的呢?其实 DissCode 在运行程序的时候,会对你的代码进行输入重定向,你可以理解成 DissCode 的 Judger 会将你的提交代码修改成如下:

#include <stdio.h>

int main() {
    freopen("data.in", "r", stdin);
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        printf("%d", a + b);
    }
}

在输入的时候,我会以一个 data.in 的文件来当作输入,其中包含了很多组 ab 的值。而 != EOF 刚好也代表了读取文件到文件尾部(EOF = end of file)。但是你提交的时候,千万不要把本地测试的重定向代码提交上来,因为我的文件不一定叫 data.in (笑。

如此,使用 scanf != EOF 就实现了多组测试数据输入。对应的,你只要实现了 Java 和 Python 的对应写法,也自然可以满足多组数据输入这个条件。

每组输出包含一行

知道了以上多组数据输入的问题,当你提交代码的时候可能仍旧会遇到 WA 的返回结果。这是又是为什么呢?

上文已经讲述了,其实 Judger 是以输入文件的方式来录入多组测试数据的,同样的,Judger 也是以输出文件的方式来比对运行结果的

仍旧以上方的代码举例,此时我们在代码中重定向输出:

#include <stdio.h>

int main() {
    freopen("data.out", "w", stdin);
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        printf("%d", a + b);
    }
}

然后运行代码,我们写入两组数据:

1 1
2 2

结果我们发现 data.out 文件中是如下结果:

24

但其实我们需要的文件内容是:

2
4

所以我们知道了,“每组答案包括一行”实际上是让我们的结果包括一个换行符。来修改下代码:

#include <stdio.h>

int main() {
    int a, b;
    while (scanf("%d %d", &a, &b) != EOF) {
        printf("%d\n", a + b);
    }
}

我们提交一下,终于获得了 DissCode 的第一个 AC ?。

输出 A + B 的结果

拿出这个来提一句,其实是为了做一些提示罢了。因为很多朋友在做题目的时候,是不会在意题目的取值范围的(暗示一波 DSC1002 那道斐波那契题目),所以如果 DSC1001 中,我们将 32 位改成 64 位,你觉得应该以什么方式来解答呢?

归根结底其实就是先审题再作答,不仅 DissCode 是这样,你在面试中也要这样。

总结

希望 DissCode 能帮助你提高算法能力并且提高对于面试的自信。希望算法不再是你的痛点,而是你的在面试中的加分项。再说回语文这个高中学科,“书读百遍,其义自见”,当你在 DissCode 或者 LeetCode 上刷够一百两百甚至一千题的时候,你就不会再担心算法面试了,如果还担心那只能说明你在做题的时候“经常作弊”?。

参考资料

[1]

链接: http://disscode.com/problem/DSC1001

本文分享自微信公众号 - 程序员维他命(J_Knight_)

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2019-11-15

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 客户端基本不用的算法系列:图论的开端-七桥问题

    冬瓜一直在想着写一个系列来罗列一些在客户端开发中,根本无法用到的算法。但是在计算机科学中又是能独立出来的学科。这之中图论就是一大块。

    用户2932962
  • 客户端基本不用的算法系列:矩阵快速幂

    我们换一个角度来想,如果有这么一种东西,它也支持乘法和幂运算,同样也拥有像数的乘法一样的规律,是不是也可以进行快速幂的优化?

    用户2932962
  • 面向对象设计的设计模式(十四):策略模式

    有时候在实现某一个功能的时可能会有多个方案:我们需要让系统可以动态灵活地更换方案;而且也能够让开发者方便地增加新的方案或删除旧的方案。

    用户2932962
  • C++ 对vector进行排序

    title: C++ vector排序 tags: c++,vector,排序 grammar_cjkRuby: true --- 每次都要重复造轮子真...

    marsggbo
  • NDK--实现gif图片播放

    部分Gif图片不能自适应大小, 播放速度比实际播放速度快, 如果要显示的gif过大,还会出现OOM的问题。

    aruba
  • socket的简单使用概念socket通信过程,使用步骤:导入头文件创建socket函数connect连接到服务器发送数据接收服务器返回的数据关闭连接例子:请求百度

    用户2141756
  • Noip 2016 Day1 题解

    老师让我们刷历年真题, 然后漫不经心的说了一句:“你们就先做做noip2016 day1 吧” 。。。。。。 我还能说什么,,,,,老师你这是明摆着伤害我们啊2...

    attack
  • 物理挖洞之 3D 效果!

    另一位群友 @云谷 在思路指导下,迅速写了一个版本,传到群里给大家分享,再次感谢!

    白玉无冰
  • 洛谷P1251 餐巾计划问题(最小费用最大流)

    从$S$向$i'$连边$(p, INF)$,表示每天早上可以以$p$的费用无限提供餐巾

    attack
  • View的事件体系

    2.MotionEvent 手指触摸屏幕后的一系列事件,包括ACTION_DOWN,ACTION_MOVE,ACTION_UP

    提莫队长

扫码关注云+社区

领取腾讯云代金券