精华 今日头条3.30官方题解
发布于 2017-03-30 21:34 7331 次浏览 1 赞 最后一次编辑是 2017-03-31 20:52 来自 笔试面试  

同学们可以加入今日头条求职讨论QQ群:436398498


Prob 1. 找出函数的最宽尖峰

正确率:1149 / 5371


题意:求给定数列 A 中先升后降的最长连续子序列,要求 O(n)。


题解:简单题。预处理 left[i] 表示以 A[i] 为结尾的连续最长上升序列长度,right[i] 表示 A[i] 为起始的连续最长下降序列长度,那么答案实际上就是 max{left[i] + right[i] - 1},更新答案时顺便记录最优区间即可。


唯一的 trick 是 left[i] > 1 和 right[i] > 1 必须同时满足,这一点在题目中已经有说明。



Prob 2. Paragraph

正确率:732 / 3732


题意:给定一个英文段落(包含 n 个句子)和 m 次查询,每次给定一个句子,求段落中相同单词数量最多的句子。各个英文句子不包含标点,大小写不敏感。


题解:做法很多,时间卡得也比较宽松。一个简单做法是对原文的各个英文句子,都预处理包含的单词集合(如果用 hash set 的话,这一步复杂度是 O(n * w))。对于每次查询,枚举句子中的单词到各个 set 中查找是否存在,随后统计出现次数取 max 即可。这样查询部分总的复杂度是 O(m * w * n)。


更快的做法是对原文出现的所有单词,通过一个 hash map 维护它们分别出现在哪些原文句子中,这个预处理的复杂度同样是 O(n * w) 的。在每次查询的时候,枚举句子中的单词,给它在原文中出现过的句子进行计数,最后在所有的计数当中取 max 即为答案。查询部分的复杂度是 O(m * (w + n)) 的。


无论是哪种做法,最重要的 trick 是各个单词的去重,防止多次计数。很多同学在代码中踩了这个坑。


Prob. 3 绘制括号序列

正确率:87 / 1655


题意:给定一个合法的括号序列,以字符矩阵的形式翻转后输出。


题解:代码实现题。先预处理每一个括号的深度,从而推出应打印的括号的大小,剩下的就是扫一遍处理下打印细节了。一个可能的 trick:注意行末不要输出多余的空格。


Prob. 4 数列

正确率:36 / 4550


题意:给定两个数列 A 和 B 以及 q 组查询 (x, y),每次求满足 A[i] >= x 且 B[i] >= y 这样的 i 的数量。


题解:暴力的 O(n * q) 的做法可以通过 30% 的数据。考虑把原先所有 (A[i], B[i]) 整数对按照 A 排序,所有查询按照 x 排序。随后从小到大扫描所有查询 (x[i], y[i]),维护一个指针 k 指向 AB 对中满足 A[k] >= x[i] 的位置。对于当前的这次查询,要求的就是所有大于 k 的位置中,满足 B[k] >= y[i] 的数量。因此我们维护一个高效支持 insert / delete / lower_bound 的数据结构来维护当前合法的 B 的值即可,满足条件的包括树状数组,平衡树等,复杂度都在 log 级别。(如果将 k 从后往前维护,可以省去 delete 操作)


总的复杂度为 O(n + qlogn)。


获取更多今日头条招聘信息,欢迎关注头条校招官方公众号

toutiaohr


同学们可以加入今日头条求职讨论QQ群:436398498

14 条回复

为什么别的都是考完就出,头条要过两天才出啊~~

2017-03-30 21:37
2

同问+1

2017-03-30 21:40
小码快跑 回复 coder_6B8G8TZZ

因为这次是今日头条要出题解,之前是赛码进行题解的:)

2017-03-30 21:40

把测试放出来行不……

2017-03-30 21:41

哎,坑了,就做出两道~~

2017-03-30 21:50
1

已放弃治疗。还是好好学习吧

2017-03-30 21:55

我建议把题目改成不要输入输出的 类似LeetCode那种只写function多好啊 。 刷惯了Leetcode 第一次做这种 写main 写输出的。Debug半天最后才知道是输入输出的问题,血崩。

2017-03-31 02:02
2

能把ac代码放出来吗,第三题还是不知道哪里错了

2017-04-01 09:07

第二题答案

import java.util.*;

public class Main {

public static void main(String[] args) {

long startTime = System.currentTimeMillis();//获取当前时间

Scanner sc = new Scanner(System.in);

int n = sc.nextInt();

int m = sc.nextInt();

sc.nextLine();//nextLine()方法返回的是Enter键之前的所有字符,它是可以得到带空格的字符串的。

List<String> lstString = new ArrayList<String>();

for (int i = 1; i <=m + n; i++) {

lstString.add(sc.nextLine());

}

List<String> lstend = new ArrayList<String>();


lstend = GetLst(lstString, n, m);


for (int i = 0; i < lstend.size(); i++) {

System.out.println(lstend.get(i));

}

long endTime = System.currentTimeMillis();

System.out.println("程序运行时间:"+(endTime-startTime)+"ms");

}


private static List<String> GetLst(List<String> lstString, int n, int m) {

// 把每行的句子拆分然后放到HashSet里面,前n个是查询库,后m个是被查询库

List<HashSet<String>> setList = new ArrayList<HashSet<String>>();// 所有HashSET放到一个集合中,一共n+m个

//setList.remove(0);

for (int i = 0; i <lstString.size(); i++) {

HashSet<String> stringSet = new HashSet<String>();// 把每行句子拆分的单词放到set集合,使其不重复

String[] s1 = lstString.get(i).split(" ");

stringSet.add(s1[0].toLowerCase());

for (int j = 1; j < s1.length; j++) {

stringSet.add(s1[j]);

}

setList.add(stringSet);

}

int[][] arraymn = new int[m][n];// 用来计数

for (int j = setList.size() - m; j < setList.size(); j++) {// 后m个被查询库

for (int i = 0; i < setList.size() - m; i++) {// 查询库

// tList.get(i).

Iterator<String> iter = setList.get(j).iterator();// setList.get(j)第j个HashSet

while (iter.hasNext()) {// 拿出第n个句子里单词匹配

String x = iter.next();

if (setList.get(i).contains(x)) {

arraymn[j - n][i]++;// 每有一个包含就计数一次,得到一个二维计数数组

}


}

}

}

List<String> lstEnd=new ArrayList<String>();

for (int i = 0; i < arraymn.length; i++) {

int max=0;int k=0;//用来获取最大值的下标

for (int j = 0; j < arraymn[i].length; j++) {

if(arraymn[i][j]>max)//拿到最大值的下标

{

max=arraymn[i][j];

k=j;

}

}

lstEnd.add(lstString.get(k));

}

return lstEnd;

}

}


2017-04-01 14:11
2

头条题解只有文字说明,无参考代码?

2017-04-01 18:43

求放出测试题啊,都没办法回头联系一下了!

2017-04-02 14:19
小码快跑 回复 acmcodernJYLNjGS

这个需要头条方面同意,我们会尽快协调

2017-04-02 14:30
coder_W5TW8YCG 回复 coder_ZDCZSM8S

这个你提前不锻炼没办法啊

2017-04-05 10:25

真赞!

2017-04-06 23:41
添加回复
回到顶部