谁适合看这篇文章
- 使用Java语言笔试的技术同学
- 在笔试过程中，遇见过莫名奇妙的问题，比如明明算法复杂度是可以通过的题目，但却只通过30%，50%或者90%
- 因为上述原因，没能通过笔试，得到面试机会的同学
- 正在准备笔试，或者要开始笔试的同学
行文思路
本文主要通过一个例子，来分析在笔试中可能遇到的一些问题，并提供一个解决方案。
有刷过Leetcode同学可能都知道，我们不需要自己处理输入输出，只要完成核心代码部分即可。但在牛客笔试时，却是要自己处理输入输出。
可能第一次在牛客上做笔试的很多同学，也在这里磕上过很多时间。
但你真的磕对了吗？并不见得。很多同学都会使用new Scanner(System.in)来处理输入，但这正式问题所在，请看下面的案例分析。
案例
以上图中的题目为例子，该题目要求使用c/c++1s，使用其他语言2s。因此使用Java解决该问题的人，时间不能超过2s。
这道题目思路因该很简单，对苹果堆进行求前缀和，之后使用二分查找即可。算下来，时间复杂度为O(n)，主要时间复杂度是在求前缀和。
原版 用时1877ms：
大家仔细看一下，这版用时1877ms，就快接近2ms了。我相信这道题背后的测试案例是随机生成的，因此可能很大也可能很小，此时你刚好过了
但是下一次就不一定了，就比如可能给你弹出个case通过率30%，或者通过率90%，显示时间超出限制之类的。这显然完全跟你的核心算法实现没有关系
这里主要的耗时都在处理输入输出上面了，也就是`in.nextInt()`和`System.out.println()`耗费了很长时间。
改进版 改进输入输出
可以看出使用改进之后的输入输出，时间立马降到1s一下，这可是c/c++的显示要求。所以有时候，明显算法实现是对的，但是就是不能通过所有的案例
以及出现莫名奇妙的超时错误，可能就要想想自己是不是在处理IO输入输出上浪费了太多时间。下面给出一个模版，希望能帮助到大家顺利通过笔试。
FastScanner 模版
import java.util.*;
import java.io.*;
public class Main {
public static void main(String[] args) {
PrintWriter sout = new PrintWriter(System.out);
FastScanner in = new FastScanner(System.in);
// Input code here
// Solve problem
// Output code here
// Must close
sout.close();
}
}
class FastScanner {
private final BufferedReader reader;
private StringTokenizer tokenizer;
public FastScanner(InputStream in) {
reader = new BufferedReader(new InputStreamReader(in));
tokenizer = null;
}
public String next() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
tokenizer = new StringTokenizer(reader.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken();
}
public String nextLine() {
if (tokenizer == null || !tokenizer.hasMoreTokens()) {
try {
return reader.readLine();
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return tokenizer.nextToken("\n");
}
public long nextLong() {
return Long.parseLong(next());
}
public int nextInt() {
return Integer.parseInt(next());
}
public double nextDouble() {
return Double.parseDouble(next());
}
public int[] nextInts(int n) {
int[] ints = new int[n];
for (int i = 0; i < n; i++) {
ints[i] = nextInt();
}
return ints;
}
public long[] nextLongs(int n) {
long[] longs = new long[n];
for (int i = 0; i < n; i++) {
longs[i] = nextLong();
}
return longs;
}
} 总结
本文并没有对java.util.Scanner为什么会慢做更多的深入，喜欢探究的同学自行百度哈～
全部评论
(0) 回帖