专栏
下载APP

2019-08-02   更新

02 online judge 的原理
Lisanaaa

面试高频算法习题精讲

Lisanaaa · GitHub 开源算法项目万星作者

人不可有傲气,但不可无傲骨。

——徐悲鸿

什么是 online judge ?online judge(在线评判功能)。

在前面的介绍中我们已经知道本专栏是一本基于 LeetCode 算法题库的网站,而online judge 就是网站对于个人所提交的代码的评判功能,这一小节我们来简单认识一下 online judge 的原理。

在开始之前请思考以下问题:

问题一:leetcode中,提交的代码能否改变给定的类名和方法签名?

问题二:leetcode中,进入方法后,执行逻辑前必须重新初始化实例变量,这是为什么?

问题三:为什么问题的样例我过了,提交代码后一直显示wrong answer?

了解 online judge 原理的意义

正如上面那三个问题,跟算法毫无关系。但是,我们了解 online judge 原理后,可以规避一些由于不了解判题系统而导致的低级错误,减少错误提交。

online judge 的组成

一般分为两个部分:

  • web服务:用来展示题目,接收用户提交的代码,并把结果展示给用户;
  • 判题系统:将用户提交记录进入队列,依次在沙箱中判题,并把结果保存在数据库。

online judge 是如何判题的?

要知道题目的种类是很多的,而且类似 LeetCode 的刷题网站有很多。对于各种类型的题目,他们的 online judge 也都各有差别,我在这里大致的将题目分为三种:

  • 用户提交的程序必须包含输入输出部分,输出唯一;
  • 包含输入输出部分,但输出不唯一;
  • 给定一个函数定义,在函数中实现逻辑。

下面我们来看下各种刷题网站的 online judge 是怎么评判对错的:

牛客网:用户提交的程序必须包含输入输出部分,输出唯一

牛客网的 online judge 会预先把测试数据准备好,分为输入文件和正确答案的输出文件。当我们提交代码后,online judge 会自动将我们的代码保存成文件然后进行编译。如果在编译的过程中遇到错误,那么会直接出现compile error。

在编译完成之后判题系统执行我们的代码,并且读取输入文件,将我们的输出定向到输出文件,同时设置超时时间。

## 将 code.py 文件的输出定向到 ouput 文件中
简单的linux例子:cat input | python code.py > output 

如果代码执行时间超出指定时间,会返回 time limit exceed(时限超出)。代码执行完成之后,判题系统将得到的输出文件与正确答案进行比对,如果输出文件与正确答案相同则返回 accepted 。如果输出文件与正确答案比对有差别则返回 wrong answer(错误的答案) 或者output limie exceed(输出太多信息)。

codeforce:包含输入输出部分,但输出不唯一

这类题目很有趣,举个例子:

给定一个正整数N,输出所有符合a+b=N(a和b都是正整数)的ab对

这类题目没有固定的答案,100个人可能有100种答案。这类题目与输出唯一题目不同的是:这种题目在判题的时候不是对比输出文件和正确答案。网站会预先准备一套判题代码,判题代码会读取输出文件和正确答案,然后通过特有的逻辑判断答案的对错。

LeetCode:给定一个函数定义,在函数中实现逻辑

对于这种类型的题目 LeetCode 会针对每一道题目写一个测试代码。你输入什么,测试代码对比输出什么。如果答案不唯一还会根据题目信息写一个校验代码。

判题系统会将我们实现的函数代码进行编译,然后与测试代码放在一起。测试代码调用我们编写的函数进行测试,并且设置超出时间。当我们编写的代码输出结果后,由校验代码判断是否通过。

小结

好了,我们已经大致知道了各种刷题网站是怎么判题的了。其实各种刷题网站在判题方面只是针对各种不同类型的题目稍微有些差异,在其它方面还是很相似的。本专栏中只会针对 LeetCode 进行讲解,有时间的话可以多去 LeetCode 上看看。自己也刷一下题目感受一下,这样以后的学习才会更加的省力(^-^)V。

课程目录
取消 评论 发送