精华 今日头条实习生招聘418在线笔试编程交流贴
发布于 2017-04-18 21:07 12057 次浏览 0 赞 最后一次编辑是 2017-04-20 12:22 来自 试题交流  

官方题解请关注头条号“头条招聘”,打开或下载今日头条APP,搜索“头条招聘”并关注。

以下官方题解来源:“今日头条校园”微信号:“toutiaohr


Prob. A- 两数组找相同的元素

题目大意

给定两个无序数组求交集,时间复杂度要求 O(nlogn) 或 O(n)。


题解

简单题。排序二分、Tree set/map 都可以实现 log 级别的快速查找,也可以利用 hash 实现 O(1) 的查找复杂度。


值得注意的是,各个语言的一些基于无序查找的 List find 方法都是线性复杂度的(例如 c++ 的 vector::find,javascript 的 Array.indexof 等),不满足要求。


Prob. B - DAU 统计

题目大意

给定一堆 64 位 ID,根据题目规则求 distinct ID 的数量。


题解

简单题,本质上就是实现一个 unique 方法。做法很多,一个简单的实现方法就是排序之后进行相邻比对即可。尽管时限上卡得不严,但由于读入的数据量很大,在 IO 上也有些优化的余地。例如对于 C++ 的用户,更推荐使用 scanf 而不是带 IO 同步的 cin(也可以采用 getchar/fread 进一步优化);对于 java,stream buffered input method 在性能上也比裸的 scanner 更好。当然即便不加这些优化,上述算法也能顺利通过测试数据。


作为一个在线笔试题,这个题目是非常简单的。一个留给各位思考的 meta problem 是,如果应用于更大规模的场景下,又应当如何实现这个问题?


Prob. C - 形式化算式

题目大意

根据题目格式,对一个算式(包含数字和加减乘除)进行点阵输出。


题解

代码实现题。先将各个字符的点阵存起来,然后确定最后要输出的所有字符(例如 sprintf),接下来模拟输出就可以了。整体实现上没什么难度,一些 corner case 包括小数点,末尾 0 等,小心处理即可。


Prob. D - 任务执行策略

题目大意

给定一个任务依赖的下三角矩阵,每个任务依赖于它在矩阵中下方的两个子任务,当且仅当子任务都执行完成之后才能执行当前任务。求执行恰好 k 个任务的最大权值之和。


题解

动态规划。

如图,如果我们选择了 Job(i, j),除了要同时选中 Job(i + 1, j)之外,也意味着 Job(i + 1, j + 1), Job(i + 2, j + 2) … Job(i + d, j + d) 这一条链全部都要选中。既然每条斜线都是选择一个后缀,因此可以据此划分阶段进行动态规划。


考虑 f[i, j, m] 表示前 i 条斜线,总共选择了 m 个任务,其中第 i 条斜线自下往上选择了 j 个任务时的最大权值和,那么转移时只需要保证第 i - 1 条斜线需要选择的任务个数 >= j - 1 即可。状态转移方程为


f[i, j, m] = max(f[i - 1, j2, m - j]) + sum[i, j] (j - 1 <= j2 <= i)


这里 sum[i, j] 表示第 i 条斜线的最下面 j 个任务的权值之和。这个转移的复杂度是 O(n) 的,总复杂度会达到 O(n^3 * m),不符合要求。问题的关键在于如何快速地获得 max(f[i - 1, j2, m - j]) 这一项,这里的优化方式很多,简单举两个方法:


  1. 用另一个数组维护每条斜线的 f 数组的后缀的最大值,那么 max(f[i - 1, j2, m - j]) 这一项就可以 O(1) 得到;

  2. 将 f 的定义改为,第 i 条斜线自下往上 至少 选择了 j 个任务的最大权值和,那么转移时就不需要枚举 j2 了。具体的转移方程留给各位重新推导一下。


优化之后可以得到 O(n^2 * m) 的时间复杂度。


当然这个题目也可以有另外的状态划分方式。注意到 Job(i, j) 选中时,除了 Job(i + 1, j + 1) 这个任务之外,Job(i + 1, j), Job(i + 2, j) … Job(n, j) 这一条链也必须选中,那么也可以用和上述对称的方式来构造转移方程。时间复杂度同样也是 O(n^2 * m) 的。


欢迎大家积极讨论!

88 条回复

一样的代码,java就ac不了。。。

2017-04-18 21:09

javascript第二题也ac不了。。。

2017-04-18 21:10
2

我用python写的第一第二题思路跟上面的一模一样,结果一个也AC不了。。有谁跟我一样情况吗。。还是是我手残不知道哪里写错了

2017-04-18 21:11
1

就是  太坑了

2017-04-18 21:11

最后一题想不出状态方程。。唉

2017-04-18 21:11

最后一题还以为是树形dp呢,想了好长时间

2017-04-18 21:11
import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main{

	public static void main(String[] args) {
		// TODO Auto-generated method stub
        Scanner input = new Scanner(System.in);
		
		int m = input.nextInt();
		List<Integer> a = new ArrayList<Integer>();
		for(int i = 0; i != m; i ++){
			a.add(input.nextInt());
		}
		
		int n = input.nextInt();
		List<Integer> result = new ArrayList<Integer>();
		for(int i = 0; i != n; i ++){
			int b = input.nextInt();
			if(a.contains(b)){
				result.add(b);
			}
		}
		input.close();
		
		for(int b : result){
			System.out.print(b + "\t");
		}
	}
}

想不通为什么通过率不是100%,居然超时了。。。

2017-04-18 21:12

Python 内置的 set 性能不够,我也很绝望啊...

2017-04-18 21:12
1

有没有JS的题解,来一发

2017-04-18 21:12
acmcoderQxqBn90z 回复 coder_CJD9FT5S

我也以为是树形,后来想通是三角形的问题,但是还是不会了。。。

2017-04-18 21:13

第三题简直有毒啊

2017-04-18 21:13

想问js的答案= =

2017-04-18 21:13

赛码网的系统耍流氓,java也是用HashSet一会AC 50%,一会AC 90%,一会AC 80%。

最后一个动态规划,看都看不懂。

1

2 3

1 1 1

运行4个任务,最大不是7,竟然是6.搞不懂为什么是6?

2017-04-18 21:13
1

第三题输入方式也不说清楚,用getline一直百分之0。真是够了,还我的百分之百啊,赛马码

2017-04-18 21:13

同样第一题百分之50

第二题百分之10的举手。。。。

看来还是要多练习啊

2017-04-18 21:13

不到十分钟做完前两道题,花了一个半小时也没做出来动归这道。

2017-04-18 21:13

看到官方题解,第三题也写这么长。。我心里就平衡了

2017-04-18 21:14
coder_J73SG34D 回复 acmcoderQxqBn90z

Java基本上都是超时,特么真是鼓励C艹,打压Java

2017-04-18 21:14

最后一道题,看不懂,以前还在poj见过类似的,并做过的,但是今天不知道为什么,就是看不懂啥意思/(ㄒoㄒ)/~~


2017-04-18 21:14
coder_arkcIAiw 回复 coder_J73SG34D

你怎么7

2017-04-18 21:14

第二题,用java的HashSet实现,只AC了80%。。。

2017-04-18 21:15
1
acmcoderQxqBn90z 回复 coder_CXVBFJ23

跟你一样,感觉钱两题思路真的是很简单,但是就是通过率不能100%,好坑,还有第三题,完全就是耗时间写就可以了,原来还可以这样解题,第4题是真难,前面三个题是坑

2017-04-18 21:15
coder_CJD9FT5S 回复 coder_J73SG34D

只能选择3 1 1 1, 6啊

2017-04-18 21:15
coder_bxZZt5PV 回复 coder_J73SG34D

我也是用java啊,可以AC100%啊

2017-04-18 21:16

python set 让我很绝望   ac各种低  

2017-04-18 21:16
3
coder_CJD9FT5S 回复 acmcoderH13qRDhi

一样一样啊

2017-04-18 21:16

第三道题我感觉自己的答案正确,愣是没通过。

第二道题 用hashMap第一次 通过80%,后面就成60% 了,测试环境真是无语了。附上第三题的代码

package com.kuiblog.jinritoutiao;


import java.text.DecimalFormat;
import java.util.Scanner;

public class Main6 {
	static int[][] a1 = new int[][] { { 1 }, { 1 }, { 1 }, { 1 }, { 1 } };
	static int[][] a2 = new int[][] { { 1, 1, 1 }, { 0, 0, 1 }, { 1, 1, 1 },
			{ 1, 0, 0 }, { 1, 1, 1 } };
	static int[][] a3 = new int[][] { { 1, 1, 1 }, { 0, 0, 1 }, { 1, 1, 1 },
			{ 0, 0, 1 }, { 1, 1, 1 } };
	static int[][] a4 = new int[][] { { 1, 0, 1 }, { 1, 0, 1 }, { 1, 1, 1 },
			{ 0, 0, 1 }, { 0, 0, 1 } };
	static int[][] a5 = new int[][] { { 1, 1, 1 }, { 1, 0, 0 }, { 1, 1, 1 },
			{ 0, 0, 1 }, { 1, 1, 1 } };
	static int[][] a6 = new int[][] { { 1, 1, 1 }, { 1, 0, 0 }, { 1, 1, 1 },
			{ 1, 0, 1 }, { 1, 1, 1 } };
	static int[][] a7 = new int[][] { { 1, 1, 1 }, { 0, 0, 1 }, { 0, 0, 1 },
			{ 0, 0, 1 }, { 0, 0, 1 } };
	static int[][] a8 = new int[][] { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 },
			{ 1, 0, 1 }, { 1, 1, 1 } };
	static int[][] a9 = new int[][] { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 1, 1 },
			{ 0, 0, 1 }, { 1, 1, 1 } };
	static int[][] a0 = new int[][] { { 1, 1, 1 }, { 1, 0, 1 }, { 1, 0, 1 },
			{ 1, 0, 1 }, { 1, 1, 1 } };
	static int[][] b1 = new int[][] { { 0, 0, 0 }, { 0, 1, 0 }, { 1, 1, 1 },
			{ 0, 1, 0 }, { 0, 0, 0 } };
	static int[][] b2 = new int[][] { { 0, 0, 0 }, { 0, 0, 0 }, { 1, 1, 1 },
			{ 0, 0, 0 }, { 0, 0, 0 } };
	static int[][] b3 = new int[][] { { 0, 0, 0 }, { 1, 0, 1 }, { 0, 1, 0 },
			{ 1, 0, 1 }, { 0, 0, 0 } };
	static int[][] b4 = new int[][] { { 0, 0, 0 }, { 0, 0, 1 }, { 0, 1, 0 },
			{ 1, 0, 0 }, { 0, 0, 0 } };
	static int[][] b5 = new int[][] { { 0, 0, 0 }, { 1, 1, 1 }, { 0, 0, 0 },
			{ 1, 1, 1 }, { 0, 0, 0 } };
	static int[][] b6 = new int[][] { { 0, 0 }, { 0, 0 }, { 0, 0 }, { 1, 1 },
			{ 1, 1 } };

	public static void main(String[] args) {

		//String s = "1 + 2 ";
		// for (int i = 0; i < 5; i++) {
		// myPrint(a1, i);
		// myPrintSpace();
		// myPrint(a2, i);
		// myPrintSpace();
		// myPrint(a3, i);
		// myPrintSpace();
		// myPrint(a4, i);
		// myPrintSpace();
		// myPrint(a5, i);
		// myPrintSpace();
		// myPrint(a6, i);
		// myPrintSpace();
		// myPrint(a7, i);
		// myPrintSpace();
		// myPrint(a8, i);
		// myPrintSpace();
		// myPrint(a9, i);
		// myPrintSpace();
		// myPrint(a0, i);
		// myPrintSpace();
		// myPrint(b1, i);
		// myPrintSpace();
		// myPrint(b2, i);
		// myPrintSpace();
		// myPrint(b3, i);
		// myPrintSpace();
		// myPrint(b4, i);
		// myPrintSpace();
		// myPrint(b5, i);
		// myPrintSpace();
		// myPrint(b6, i);
		// myPrintSpace();
		// System.out.println();
		// }
		Scanner scanner = new Scanner(System.in);

		while (scanner.hasNext()) {
			// 将表达式分为两部分
			int a = scanner.nextInt();
			String s = scanner.next();
			int b = scanner.nextInt();
			int result = 0;
			String resultString = "";
			System.out.println("a:"+a+"b:"+b+"运算:"+s);
			// try {
			// System.out.println(jse.eval(input));
			// } catch (ScriptException e) {
			// // TODO Auto-generated catch block
			// e.printStackTrace();
			// }
			if (s.equals("+")) {
//				System.out.println("加法运算");
				
				result = a + b;
				resultString = a + "+" + b + "=" + result;
			} else if (s.equals("-")) {
//				System.out.println("减法");
				
				result = a - b;
				resultString = a + "-" + b + "=" + result;
			} else if (s.equals("*")) {
//				System.out.println("乘法");
				
				result = a * b;
				resultString = a + "*" + b + "=" + result;
			} else if (s.equals("/")) {
//				System.out.println("除法");
				
				float c = (float)a/b;
				DecimalFormat df = new DecimalFormat("0.00");//格式化小数   
				String d = df.format(c);
				resultString = a+"/"+b+"="+d;
			}
			//System.out.println(resultString);
			char[] charArray = resultString.toCharArray();
			myPrint(charArray);
		}
	}

	public static void myPrint(int[][] a, int row) {
		for (int i = 0; i < a[row].length; i++) {
			if (a[row][i] == 1) {
				System.out.print("*");
			} else {
				System.out.print(" ");
			}
		}
	}

	public static void myPrintSpace() {
		System.out.print("  ");
	}

	public static void myPrint(char[] a) {
		for (int i = 0; i < 5; i++) {
			for (int j = 0; j < a.length; j++) {
				switch (a[j]) {
				case '1':
					myPrint(a1, i);
					if (j != a.length-1) {
						myPrintSpace();
					}
					break;
				case '2':
					myPrint(a2, i);
					if (j != a.length-1) {
						myPrintSpace();
					}
					break;
				case '3':
					myPrint(a3, i);
					if (j != a.length-1) {
						myPrintSpace();
					}
					break;
				case '4':
					myPrint(a4, i);
					if (j != a.length-1) {
						myPrintSpace();
					}
					break;
				case '5':
					myPrint(a5, i);
					if (j != a.length-1) {
						myPrintSpace();
					}
					break;
				case '6':
					myPrint(a6, i);
					if (j != a.length-1) {
						myPrintSpace();
					}
					break;
				case '7':
					myPrint(a7, i);
					if (j != a.length-1) {
						myPrintSpace();
					}
					break;
				case '8':
					myPrint(a8, i);
					if (j != a.length-1) {
						myPrintSpace();
					}
					break;
				case '9':
					myPrint(a9, i);
					if (j != a.length-1) {
						myPrintSpace();
					}
					break;
				case '0':
					if (j != a.length-1) {
                        myPrint(a0, i);
						myPrintSpace();
					}
					break;
				case '+':
					myPrint(b1, i);
					myPrintSpace();
					break;
				case '-':
					myPrint(b2, i);
					myPrintSpace();
					break;
				case '*':
					myPrint(b3, i);
					myPrintSpace();
					break;
				case '/':
					myPrint(b4, i);
					myPrintSpace();
					break;
				case '=':
					myPrint(b5, i);
					myPrintSpace();
					break;
				case '.':
					myPrint(b6, i);
					myPrintSpace();
					break;
				default:
					break;
				}
			}
			System.out.println();
		}

	}
}


2017-04-18 21:16
coder_arkcIAiw 回复 coder_J73SG34D

ArrayList扩容很费时的呀,你数据大了,要扩容很多次的

2017-04-18 21:16
acmcoderQxqBn90z 回复 coder_KV3TY7KH

同感,做完好想吐槽

2017-04-18 21:17

哈哈哈 刚看到那个第四题说7的 我以为就我的读题能力有问题 原来还有同类 哈哈哈 写完代码才发现看错题了,心累,应该做第三题的,思路很简单,就是懒,不想写....

2017-04-18 21:17
coder_X7VUP3VK 回复 coder_J73SG34D

不能把2加进去,因为2依赖于下一行的1,1但是1,1并不在这个任务集合中

2017-04-18 21:17
acmcoder2ZEBGgBx 回复 coder_CXVBFJ23

应该是python,set性能问题,我是写python换成java的hashset过的,而且java的hashset可以一开始设置初始容量,避免一直扩容,python的set不知道有没有这个功能

2017-04-18 21:18

怀疑 第一题的 js 测试数据有问题,都不去重吗

//50% 通过
var m = read_line();
var mArr = {};
var res = [];

function inArray(item){
	if(item in mArr && mArr[item]===1) {
        mArr[item]++;
        return true
    };
	return false;
}

for(var i=0;i<m;i++){
	mArr[read_line()] = 1;
}

var n = read_line();
for(var i=0;i<n;i++){
	var str = read_line();
	if(inArray(str)){
		res.push(str);
	}
}
print(res.join(' '));
//90% 通过
var m = read_line();
var mArr = {};
var res = [];

function inArray(item){
	if(item in mArr ) {
        mArr[item]++;
        return true
    };
	return false;
}

for(var i=0;i<m;i++){
	mArr[read_line()] = 1;
}

var n = read_line();
for(var i=0;i<n;i++){
	var str = read_line();
	if(inArray(str)){
		res.push(str);
	}
}
print(res.join(' '));

2017-04-18 21:19
acmcoderQxqBn90z 回复 coder_arkcIAiw

那有什么解决方法吗?因为调试这个,感觉浪费了很多时间。

2017-04-18 21:19

dp好难

2017-04-18 21:20

第3题:

//#define LOCAL

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<set>


using namespace std;


struct node{

char key;

char img[5][5];

};


node num[16];


char s[11][5]={"*",//0

"***",//1

"* *",//2

"  *",//3

"*  ",//4

" * ",//5

"****",//6

"    ",//7

"   ",//8

 "**",//9

 "  "};//10


void init(){

//0

num[0].key='0';

strcpy(num[0].img[0],s[1]);

strcpy(num[0].img[1],s[2]);

strcpy(num[0].img[2],s[2]);

strcpy(num[0].img[3],s[2]);

strcpy(num[0].img[4],s[1]);

//1

num[1].key='1';

strcpy(num[1].img[0],s[0]);

strcpy(num[1].img[1],s[0]);

strcpy(num[1].img[2],s[0]);

strcpy(num[1].img[3],s[0]);

strcpy(num[1].img[4],s[0]);

//2

num[2].key='2';

strcpy(num[2].img[0],s[1]);

strcpy(num[2].img[1],s[3]);

strcpy(num[2].img[2],s[1]);

strcpy(num[2].img[3],s[4]);

strcpy(num[2].img[4],s[1]);

//3

num[3].key='3';

strcpy(num[3].img[0],s[1]);

strcpy(num[3].img[1],s[3]);

strcpy(num[3].img[2],s[2]);

strcpy(num[3].img[3],s[3]);

strcpy(num[3].img[4],s[1]);

//4

num[4].key='4';

strcpy(num[4].img[0],s[2]);

strcpy(num[4].img[1],s[2]);

strcpy(num[4].img[2],s[1]);

strcpy(num[4].img[3],s[3]);

strcpy(num[4].img[4],s[3]);

//5

num[5].key='5';

strcpy(num[5].img[0],s[1]);

strcpy(num[5].img[1],s[4]);

strcpy(num[5].img[2],s[1]);

strcpy(num[5].img[3],s[3]);

strcpy(num[5].img[4],s[1]);

//6

num[6].key='6';

strcpy(num[6].img[0],s[1]);

strcpy(num[6].img[1],s[4]);

strcpy(num[6].img[2],s[1]);

strcpy(num[6].img[3],s[2]);

strcpy(num[6].img[4],s[1]);

//7

num[7].key='7';

strcpy(num[7].img[0],s[1]);

strcpy(num[7].img[1],s[3]);

strcpy(num[7].img[2],s[3]);

strcpy(num[7].img[3],s[3]);

strcpy(num[7].img[4],s[3]);

//8

num[8].key='8';

strcpy(num[8].img[0],s[1]);

strcpy(num[8].img[1],s[2]);

strcpy(num[8].img[2],s[1]);

strcpy(num[8].img[3],s[2]);

strcpy(num[8].img[4],s[1]);

//9

num[9].key='9';

strcpy(num[9].img[0],s[1]);

strcpy(num[9].img[1],s[2]);

strcpy(num[9].img[2],s[1]);

strcpy(num[9].img[3],s[3]);

strcpy(num[9].img[4],s[1]);

//+

num[10].key='+';

strcpy(num[10].img[0],s[8]);

strcpy(num[10].img[1],s[5]);

strcpy(num[10].img[2],s[1]);

strcpy(num[10].img[3],s[5]);

strcpy(num[10].img[4],s[8]);

//-

num[11].key='-';

strcpy(num[11].img[0],s[8]);

strcpy(num[11].img[1],s[8]);

strcpy(num[11].img[2],s[1]);

strcpy(num[11].img[3],s[8]);

strcpy(num[11].img[4],s[8]);

//*

num[12].key='*';

strcpy(num[12].img[0],s[8]);

strcpy(num[12].img[1],s[2]);

strcpy(num[12].img[2],s[5]);

strcpy(num[12].img[3],s[2]);

strcpy(num[12].img[4],s[8]);

/// 

num[13].key='/';

strcpy(num[13].img[0],s[8]);

strcpy(num[13].img[1],s[3]);

strcpy(num[13].img[2],s[5]);

strcpy(num[13].img[3],s[4]);

strcpy(num[13].img[4],s[8]);

//=

num[14].key='=';

strcpy(num[14].img[0],s[7]);

strcpy(num[14].img[1],s[6]);

strcpy(num[14].img[2],s[7]);

strcpy(num[14].img[3],s[6]);

strcpy(num[14].img[4],s[7]);

//.

num[15].key='.';

strcpy(num[15].img[0],s[10]);

strcpy(num[15].img[1],s[10]);

strcpy(num[15].img[2],s[10]);

strcpy(num[15].img[3],s[9]);

strcpy(num[15].img[4],s[9]);

 

}


int getPos(char c){

for(int i=0;i<16;i++)

if(c==num[i].key)

return i;

}

int main(){

#ifdef LOCAL

freopen("3_input.txt","r",stdin);

freopen("3_output.txt","w",stdout);

#endif

init();


int a,b,resultInt;

int resultFloat;

char op;

int is_float;

while(scanf("%d%c%d",&a,&op,&b)==3){

is_float=0;

if(op=='+')resultInt=a+b;

else if(op=='-')resultInt=a+b;

else if(op=='*')resultInt=a*b;

else{

resultInt=a/b;

if(resultInt*b!=a){

is_float=1;

resultFloat=(a*1.0/b-resultInt)*100;

}

}

for(int k=0;k<5;k++){

// print a 0 

char aStr[10];

itoa(a,aStr,10);

for(int j=0;j<strlen(aStr);j++){

int pos=getPos(aStr[j]);

cout<<num[pos].img[k]<<"  ";

}

//print op 0

int pos=getPos(op);

cout<<num[pos].img[k]<<"  ";

//print b 0

char bStr[10];

itoa(b,bStr,10);

for(int j=0;j<strlen(bStr);j++){

int pos=getPos(bStr[j]);

cout<<num[pos].img[k]<<"  ";

}

// print == 0

cout<<num[14].img[k]<<"  ";

// print result int part 0 

char resultIntStr[10];

itoa(resultInt,resultIntStr,10);

for(int j=0;j<strlen(resultIntStr);j++){

int pos=getPos(resultIntStr[j]);

cout<<num[pos].img[k]<<"  ";

}

if(is_float){

//print result float part 0  

char resultFloatStr[10];

itoa(resultFloat,resultFloatStr,10);

//print dot.

cout<<num[15].img[k]<<"  ";

//print float 0

int pos=getPos(resultFloatStr[0]);

cout<<num[pos].img[k]<<"  ";

//print float-1

pos=getPos(resultFloatStr[1]);

cout<<num[pos].img[k];

}

// print endl.

cout<<endl; 

}

}


return 0;

}


2017-04-18 21:21

我想知道为什么AC不了。前三题都符合题意,且打印符合要求啊。没有一个AC100%的。

2017-04-18 21:21

用js写得好绝望。。。明明是对的就是AC不了。。。求问这是什么情况

2017-04-18 21:21
1
#include <iostream> 
#include <algorithm> 
#include <vector>

using namespace std;

int main()
{
    char Num[10][5][3]={{{'*','*','*'},{'*',' ','*'},{'*',' ','*'},{'*',' ','*'},{'*','*','*'}},
                        {{' ','*',' '},{' ','*',' '},{' ','*',' '},{' ','*',' '},{' ','*',' '}},
                        {{'*','*','*'},{' ',' ','*'},{'*','*','*'},{'*',' ',' '},{'*','*','*'}},
                        {{'*','*','*'},{' ',' ','*'},{'*','*','*'},{' ',' ','*'},{'*','*','*'}},
                        {{'*',' ','*'},{'*',' ','*'},{'*','*','*'},{' ',' ','*'},{' ',' ','*'}},
                        {{'*','*','*'},{'*',' ',' '},{'*','*','*'},{' ',' ','*'},{'*','*','*'}},
                        {{'*','*','*'},{'*',' ',' '},{'*','*','*'},{'*',' ','*'},{'*','*','*'}},
                        {{'*','*','*'},{' ',' ','*'},{' ',' ','*'},{' ',' ','*'},{' ',' ','*'}},
                        {{'*','*','*'},{'*',' ','*'},{'*','*','*'},{'*',' ','*'},{'*','*','*'}},
                        {{'*','*','*'},{'*',' ','*'},{'*','*','*'},{' ',' ','*'},{'*','*','*'}}};

    char Fh[6][5][3]=    {{{' ',' ',' '},{' ','*',' '},{'*','*','*'},{' ','*',' '},{' ',' ',' '}},
                        {{' ',' ',' '},{' ',' ',' '},{'*','*','*'},{' ',' ',' '},{' ',' ',' '}},
                        {{' ',' ',' '},{'*',' ','*'},{' ','*',' '},{'*',' ','*'},{' ',' ',' '}},
                        {{' ',' ',' '},{' ',' ','*'},{' ','*',' '},{'*',' ',' '},{' ',' ',' '}},
                        {{' ',' ',' '},{'*','*','*'},{' ',' ',' '},{'*','*','*'},{' ',' ',' '}},
                        {{' ',' ',' '},{' ',' ',' '},{' ',' ',' '},{' ','*','*'},{' ','*','*'}}};
    
    char result[5][70];
    int i, j, k;
    int a, b, c;
    char d, e;
    int fh;
    cin >> a >> d >> b ;
    //cout << a << d << b <<endl;

    switch(d){
    case '+':
        {
            fh = 0; 
            c = a + b;
            break;
        }
    case '-': 
        {
            fh = 1; 
            c = a - b;
            break;
        }
    case '*': 
        {
            fh = 2; 
            c = a * b;
            break;
        }
    case '/': 
            {
            fh = 3; 
            c = float(a / b);
            break;
        }
    }
    //cout << c << endl;
    //cout << fh << endl;


    for(i=0; i<5; ++i)
    {
        j=0;
        int num;
        for(num=0; num<3; ++num)//a
        {
            result[i][j]=Num[a][i][num];
            j++;
        }
        result[i][j++]=' ';
        result[i][j++]=' ';
        for(num=0; num<3; ++num)//+
        {
            result[i][j]=Fh[fh][i][num];
            j++;
        }
        result[i][j++]=' ';
        result[i][j++]=' ';
        for(num=0; num<3; ++num)//b
        {
            result[i][j]=Num[b][i][num];
            j++;
        }
        result[i][j++]=' ';
        result[i][j++]=' ';
        for(num=0; num<3; ++num)//=
        {
            result[i][j]=Fh[4][i][num];
            j++;
        }
        result[i][j++]=' ';
        result[i][j++]=' ';
        for(num=0; num<3; ++num)//c
        {
            result[i][j]=Num[c][i][num];
            j++;
        }
        result[i][j]='\0';
    }

    for(i=0; i<5;++i)
    {
        printf("%s\n", result[i]);
    }

    return 0;
}
2017-04-18 21:23
test 回复 acmcoderQxqBn90z

应该用纯数组,先快排,再二分查找。

2017-04-18 21:24

第一道愣是没ac过去,第三题真的是想了很久有没有简便的方法最后时间不够就写了数字的编码,看到答案那么长心里舒服多了

2017-04-18 21:25

动归必须要重点刷题,因为动归很多次功亏于溃了

2017-04-18 21:25

第二题为什么STL的map不行啊....


2017-04-18 21:26

最后一个预处理后进行回溯,越写越乱

前面AC的也不好,感觉要跪了,最后一个啊 忍不住了

2017-04-18 21:27
acmcoderQxqBn90z 回复 test

厉害,一个题考了好多

2017-04-18 21:27

<unordered_set>可以用,<unordered_map>不能用这样真的好么。。

2017-04-18 21:27

第一和第二题有没有ac的答案呀,java版本的

2017-04-18 21:28
1
coder_VFK26DFJ 回复 acmcoderQxqBn90z

import java.util.HashSet; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); HashSet<Long> set = new HashSet<>(); while(true){ Long l = sc.nextLong(); if(l != 0){ if(!set.contains(l)){ set.add(l); } }else{ System.out.print(set.size()); break ; } } } }

2017-04-18 21:32
coder_DBXDE3M8 回复 coder_X7VUP3VK

我也是,求解答,赛码网能给出测试用例吗?或者说明原因啊

2017-04-18 21:32

第一题 两数组找相同元素 如果用二分查找A中的元素不是得先排序吗?

2017-04-18 21:33
coder_Svn0dFpY 回复 coder_NVZQ9AXU

map好像也是的,显示内存超了,后来改成位存储,还是没到100%。。。。

2017-04-18 21:33

说出来你们可能不信,第三题我把输出看成9行了,结果显示过了80%。。。。不知道你们怎么judge的,标准是什么,不会是人工看吧。。。。

2017-04-18 21:34
4
import java.util.Scanner;

class Test {
}

public class Main {
	public static void main(String args[]) {
		String[][] str = { { "***", "* *", "* *", "* *", "***" }, // 0
				{ "*", "*", "*", "*", "*" }, // 1
				{ "***", "  *", "***", "*  ", "***" }, // 2
				{ "***", "  *", "***", "  *", "***" }, // 3
				{ "* *", "* *", "***", "  *", "  *" }, // 4
				{ "***", "*  ", "***", "  *", "***" }, // 5

				{ "***", "*  ", "***", "* *", "***" }, // 6
				{ "***", "  *", "  *", "  *", "  *" }, // 7
				{ "***", "* *", "***", "* *", "***" }, // 8
				{ "***", "* *", "***", "  *", "***" }, // 9
				{ "   ", " * ", "***", " * ", "   " }, // +10
				{ "   ", "   ", "***", "   ", "   " }, // -11
				{ "   ", "* *", " * ", "* *", "   " }, // *12
				{ "   ", "  *", " * ", "*  ", "   " }, /// 13
				{ "   ", "***", "   ", "***", "   " }, // =14
				{ "  ", "  ", "  ", "**", "**" },// xiaoshu15
		};

		Scanner cin = new Scanner(System.in);
		String string = cin.nextLine();
		String[] strings = string.split(" ");
		int a = Integer.parseInt(strings[0]);
		int b = Integer.parseInt(strings[2]);
		cin.close();

		StringBuilder sbBuilder = new StringBuilder();
		sbBuilder.append(string);

		if (strings[1].equals("+")) {
			int d = a + b;
			sbBuilder.append(" = " + d);
			System.out.println(sbBuilder);

			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < sbBuilder.length(); j++) {

					if (sbBuilder.charAt(j) - '0' >= 0 && sbBuilder.charAt(j) - '0' <= 9)
						System.out.print(str[sbBuilder.charAt(j) - '0'][i] + " ");
					else if (sbBuilder.charAt(j) == '+') {
						System.out.print(" " + str[10][i] + " ");
					} else if (sbBuilder.charAt(j) == '=') {
						System.out.print(" " + str[14][i] + " ");
					}
					// System.out.print(str[0][i]);
				}
				System.out.println();
			}

		} else if (strings[1].equals("-")) {
			int d = a - b;
			sbBuilder.append(" = " + d);
			System.out.println(sbBuilder);

			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < sbBuilder.length(); j++) {

					if (sbBuilder.charAt(j) - '0' >= 0 && sbBuilder.charAt(j) - '0' <= 9)
						System.out.print(str[sbBuilder.charAt(j) - '0'][i] + " ");
					else if (sbBuilder.charAt(j) == '-') {
						System.out.print(" " + str[11][i] + " ");
					} else if (sbBuilder.charAt(j) == '=') {
						System.out.print(" " + str[14][i] + " ");
					}
					// System.out.print(str[0][i]);
				}
				System.out.println();
			}

		} else if (strings[1].equals("*")) {
			double d = a * b;
			sbBuilder.append(" = " + d);
			System.out.println(sbBuilder);

			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < sbBuilder.length(); j++) {

					if (sbBuilder.charAt(j) - '0' >= 0 && sbBuilder.charAt(j) - '0' <= 9)
						System.out.print(str[sbBuilder.charAt(j) - '0'][i] + " ");
					else if (sbBuilder.charAt(j) == '*') {
						System.out.print(" " + str[12][i] + " ");
					} else if (sbBuilder.charAt(j) == '=') {
						System.out.print(" " + str[14][i] + " ");
					}
					// System.out.print(str[0][i]);
				}
				System.out.println();
			}

		} else if (strings[1].equals("/")) {
			double d = (double) a / (double) b;
			sbBuilder.append(" = " + d);
			System.out.println(sbBuilder);

			for (int i = 0; i < 5; i++) {
				for (int j = 0; j < sbBuilder.length(); j++) {

					if (sbBuilder.charAt(j) - '0' >= 0 && sbBuilder.charAt(j) - '0' <= 9)
						System.out.print(str[sbBuilder.charAt(j) - '0'][i] + " ");
					else if (sbBuilder.charAt(j) == '/') {
						System.out.print(" " + str[13][i] + " ");
					} else if (sbBuilder.charAt(j) == '=') {
						System.out.print(" " + str[14][i] + " ");
					} else if (sbBuilder.charAt(j) == '.') {
						System.out.print(" " + str[15][i] + " ");
					}
					// System.out.print(str[0][i]);
				}
				System.out.println();
			}

		}

	}
}

有些小数点可能没考虑


2017-04-18 21:36

日了狗了。转移方程都是对的

2017-04-18 21:37

import java.util.ArrayList;

import java.util.HashMap;

import java.util.Scanner;

public class St {

public static void main(String[] args) {

HashMap<Long,Integer> res = new HashMap<Long,Integer>();

ArrayList<Long> arr = new ArrayList<Long>();

Scanner in = new Scanner(System.in);

Long uid;

int i;

while (in.hasNext()) {

int n = 0;

uid = in.nextLong();

if (uid == 0) 

break;

else if (!res.containsKey(uid)){ 

res.put(uid, 0);

arr.add(uid);

}

}

System.out.print(arr.size());         

}

}


2017-04-18 21:37

第一题 两数组找相同元素 二分查找A 不是得先排序吗?这样时间复杂度至少O(nlgn),还不如直接查找O(n)。

但是不知道为什么第一题我的只有50%???

2017-04-18 21:38
coder_pqbsmmO5 回复 coder_CXVBFJ23

第一次在赛码答题,感觉是鼓励c/c++,我也用python,都是TimeOut

2017-04-18 21:41
coder_VFK26DFJ 回复 acmcoderQxqBn90z

直接用一个HashSet就可以了啊,我的通过了,你可以看看

2017-04-18 21:43
%第一题  AC 100%
import java.util.*;
public class Main {
	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		HashSet<Integer> hashset = new HashSet<Integer>();
		int a = in.nextInt();
		for(int i = 0; i < a; i++){
   			hashset.add(in.nextInt());
   		}
		int b = in.nextInt();
		int len = hashset.size();
		ArrayList<Integer> r = new ArrayList<Integer>();
		for(int i = 0; i < b; i++){
			int tmp = in.nextInt();
			if(hashset.contains(tmp))
				r.add(tmp);
   		}
		for (int i : r)
			System.out.print(i + " ");
		
	}
}

%第二题 AC 100%
import java.util.*;
public class Main {
	
	    public static void main(String[] args) {
			Scanner in = new Scanner(System.in);
			HashSet<Long> hashset = new HashSet<Long>();
			while(in.hasNext()) {
				Long s = in.nextLong();
				if(s != 0)  {
					hashset.add(s);
				}
				else
					break;
			}
			System.out.println(hashset.size());
			
		}
	

}


2017-04-18 21:44
2
/*今日头条2017校园招聘 技术综合
形式化算式
时间限制:C/C++语言 1000MS;其他语言 3000MS
内存限制:C/C++语言 65536KB;其他语言 589824KB
题目描述:
我们有如下形式化的数字
*    ***   ***   * *   ***   ***   ***   ***   ***   ***
*      *     *   * *   *     *       *   * *   * *   * *
*    ***   ***   ***   ***   ***     *   ***   ***   * *
*    *       *     *     *   * *     *   * *     *   * *
*    ***   ***     *   ***   ***     *   ***   ***   **

分别表示 1 2 3 4 5 6 7 8 9 0
有如下形式化的符号:
 *        * *    *   ****
***  ***   *    *
 *        * *  *     ****    **
							**
*/
#include<iostream>
#include<string>
#include<cstring>
#include<vector>
#include<sstream>
using namespace std;
int printGF(char c){
	int wid = 0;
	switch (c){
	case'+':wid = 3;break;
	case'-':wid = 3;break;
	case'*':wid = 3; break;
	case'/':wid = 3; break;
	case'=':wid = 4; break;
	case'.':wid = 2; break;
	case'0':wid = 3; break;
	case'1':wid = 1; break;
	case'2':wid = 3; break;
	case'3':wid = 3; break;
	case'4':wid = 3; break;
	case'5':wid = 3; break;
	case'6':wid = 3; break;
	case'7':wid = 3; break;
	case'8':wid = 3; break;
	case'9':wid = 3; break;

	}
	return wid;
}
void setsgs(int width, int height, char c, vector<vector<char> >& sigs){
	switch (c){
	case'+':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++)
			if (i == 2 || (i == 1 && (j - width) == 1) || (i == 3 && (j - width) == 1))
				sigs[i][j] = '*';
		}
		break;
	case'-':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++)
			if (i==2)
				sigs[i][j] = '*';
		}
		break;
	case'*':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++)
			if (i + j - width == 3 || (i == 1 && (j - width) == 0) || (i ==3 && (j - width) == 2))
				sigs[i][j] = '*';
		}
		break;
	case'/':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++)
			if (i+j-width == 3)
				sigs[i][j] = '*';
		}
		break;
	case'=':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 4; j++)
			if (i == 1||i==3)
				sigs[i][j] = '*';
		}
		break;
	case'.':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 2; j++)
			if (i == 3||i==4)
				sigs[i][j] = '*';
		}
		break;
	case'0':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width+3; j++)
			if (j-width==0||j-width==2||i==0||i==4)
				sigs[i][j] = '*';
		}
		break;
	case'1':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width+1; j++)
				sigs[i][j] = '*';
		}
		break;
	case'2':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++){
				if (i == 0 || i == 2 || i == 4 || (j - width) == 0 || (j - width) == 2)
					sigs[i][j] = '*';
				if (i == 1 && (j - width) == 0 || i == 3 && (j - width) == 2)
					sigs[i][j] = ' ';
			}
		}
		break;
	case'3':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++)
			if (i  == 0||i==2||i==4||(j-width)==2)
				sigs[i][j] = '*';
		}
		break;
	case'4':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++)
			if (i == 2 || j - width == 2 || i<=2&&(j-width == 0))
				sigs[i][j] = '*';
		}
		break;
	case'5':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++){
				if (i == 0 || i == 2 || i == 4 || (j - width) == 0 || (j - width) == 2)
					sigs[i][j] = '*';
				if (i == 1 && (j - width) == 2 || i == 3 && (j - width) == 0)
					sigs[i][j] = ' ';
			}
		}
		break;
	case'6':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++){
				if (i == 0 || i == 2 || i == 4 || (j - width) == 0 || (j - width) == 2)
					sigs[i][j] = '*';
				if (i == 1 && (j - width) == 2 )
					sigs[i][j] = ' ';
			}
		}
		break;
	case'7':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++)
			if (i == 0 ||  (j - width) == 2)
				sigs[i][j] = '*';
		}
		break;
	case'8':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++)
			if (i == 0 || i == 2 || i == 4 || (j - width) == 0|| (j - width) == 2)
				sigs[i][j] = '*';
			
		}
		break;
	case'9':
		for (int i = 0; i < height; i++){
			for (int j = width; j < width + 3; j++)
			if (i==0||i == 2 || j - width == 2 || i <= 2 && (j - width == 0))
				sigs[i][j] = '*';
		}
		break;

	}
}
int main(){
	//int data[N];
	//memset(data,0,sizeof(int)*N);
	string str;
	int a, b;
	char ope;
	if (cin >> str){
		
		stringstream ss;
		string temp="";
		int width = 0, height = 5, len = str.length();
		for (int i = 0; i < len; i++)
		{
			if (str[i]>='0'&&str[i]<='9')
			{
				temp += str[i];
			}
			else{
				ss << temp; ss >> a;
				ss.clear();
				//cout << temp<<endl;
				temp = "";
				ope = str[i];
			}
			
		}
		//cout << temp << endl;
		//width += len - 1;
		ss << temp; ss >> b; ss.clear();
		//cout << a << ope << b << endl;
		
		int zhengshu = 0, xiaoshu = 0;
		float res;
		switch (ope){
		case'+':res=a+b; break;
		case'-':res =a-b; break;
		case'*':res = a*b; break;
		case'/':res = 1.0*a/b; break;
		}
		zhengshu = res;
		ss << res; ss >> temp; ss.clear();
		cout << temp << endl;
		str += "="+temp;
		cout << str << endl;
		len = str.length();
		for (int i = 0; i <len; i++)
		{
			
			width += printGF(str[i]);
			//width += 1;
		}
		//cout << temp << endl;
		width += len - 1;
		cout << width<<endl;
		vector<char> p(width,' ');
		vector<vector<char> >sigs(height, p);
		int wid = 0;
		for (int i = 0; i < len; i++)
		{
			setsgs(wid,height,str[i],sigs);
			wid += printGF(str[i]);
			wid += 1;
		}
		for (int i = 0; i < height; i++){
			for (int j = 0; j < width; j++)
				cout << sigs[i][j];
			cout << endl;
		}
	}
	system("pause");
	return 0;
}


2017-04-18 21:49
coder_K25MQADF 回复 coder_G4X8VTFZ


public void countKehu(){
		Scanner s=new Scanner(System.in);
		String ip=s.next();
		int count=0;
		HashMap<String,Integer> data = new HashMap<String,Integer>();
		while(!"0".equals(ip)){
			if(data.containsKey(ip)){
				;
			}else{
				count++;
				data.put(ip, 1);
			}
			ip=s.next();
		}
		System.out.println(count);
	}


2017-04-18 21:51
coder_VFK26DFJ 回复 coder_G4X8VTFZ

第二题,ac的

import java.util.HashSet;

import java.util.Scanner;

public class Main {

public static void main(String[] args) {

Scanner sc = new Scanner(System.in);

HashSet<Long> set = new HashSet<>();

while(true){

Long l = sc.nextLong();

if(l != 0){

if(!set.contains(l)){

set.add(l);

}

}else{

System.out.print(set.size());

break ;

}

}

}


}


2017-04-18 21:55

看别人用Java写的,一么一样的代码,别人居然能ac。。。。

2017-04-18 21:57
import java.util.Scanner;
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int a = sc.nextInt();
		String op = sc.next();
		int b = sc.nextInt();
		int res = 0;
		double resDivide = 0;
		if (op.equals("+")) {
			res = a + b;
		}
		if (op.equals("-")) {
			res = a - b;
		}
		if (op.equals("*")) {
			res = a * b;
		}
		if (op.equals("/")) {
			res = a / b;
			resDivide = (double) a / (double) b;
		}
		System.out.println(resDivide);
		int temp = 0;
		int x_a = (int) Math.log10((double) a);
		int x_b = (int) Math.log10((double) b);
		int xres = (int) Math.log10((double) res);
		if (!op.equals("/") || (op.equals("/") && a % b == 0)) {
			for (int i = 1; i < 6; i++) {
				int aa = a;
				for (int j = x_a; j >= 0; j--) {
					temp = (int) (aa / Math.pow(10, (double) j));
					System.out.print(printNumRow(i, temp));
					System.out.print("  ");
					aa -= temp * Math.pow(10, (double) j);
				}
				
				System.out.print(printOpRow(i,op));
				System.out.print("  ");
				int bb = b;
				for (int j = x_b; j >= 0; j--) {
					temp = (int) (bb / Math.pow(10, (double) j));
					System.out.print(printNumRow(i, temp));
					System.out.print("  ");
					bb -= temp * Math.pow(10, (double) j);
				}
				
				System.out.print(printOpRow(i,"="));
				System.out.print("  ");
				int res1 = res;
				for (int j = xres; j >= 0; j--) {
					temp = (int) (res1 / Math.pow(10, (double) j));
					System.out.print(printNumRow(i, temp));
					if (j != 0) {
						System.out.print("  ");
					}
					res1 -= temp * Math.pow(10, (double) j);
				}
				System.out.print("\n");
			}
		} else {
			for (int i = 1; i < 6; i++) {
				int aa = a;
				for (int j = x_a; j >= 0; j--) {
					temp = (int) (aa / Math.pow(10, (double) j));
					System.out.print(printNumRow(i, temp));
					System.out.print("  ");
					aa -= temp * Math.pow(10, (double) j);
				}
				
				System.out.print(printOpRow(i,op));
				System.out.print("  ");
				int bb = b;
				for (int j = x_b; j >= 0; j--) {
					temp = (int) (bb / Math.pow(10, (double) j));
					System.out.print(printNumRow(i, temp));
					System.out.print("  ");
					bb -= temp * Math.pow(10, (double) j);
				}
				
				System.out.print(printOpRow(i,"="));
				System.out.print("  ");
				int res1 = res;
				for (int j = xres; j >= 0; j--) {
					temp = (int) (res1 / Math.pow(10, (double) j));
					System.out.print(printNumRow(i, temp));
					System.out.print("  ");
					res1 -= temp * Math.pow(10, (double) j);
				}
				System.out.print(printOpRow(i,"."));
				System.out.print("  ");
				int res2 = (int) Math.round(resDivide * 100);
				res2 = res2 % 100;
				for (int j = 1; j >= 0; j--) {
					temp = (int) (res2 / Math.pow(10, (double) j));
					System.out.print(printNumRow(i, temp));
					if (j != 0) {
						System.out.print("  ");
					}
					res2 -= temp * Math.pow(10, (double) j);
				}
				System.out.print("\n");
			}
		}
	}
	
	public static String printNumRow(int row, int num) {
		String res = null;
		if (row == 1) {
			switch(num) {
			case 1: 
				res = "*";
				break;
			case 2: case 3: case 5: case 6: case 8: case 7: case 9: case 0:
				res = "***";
				break;
			case 4:
				res = "* *";
				break;
			}
		}
		if (row == 2) {
			switch(num) {
			case 1: 
				res = "*";
				break;
			case 2: case 3: case 7: 
				res = "  *";
				break;
			case 4: case 8: case 9: case 0:
				res = "* *";
				break;
			case 5: case 6:
				res = "*  ";
				break;
			}
		}
		if (row == 3) {
			switch(num) {
			case 1: 
				res = "*";
				break;
			case 2: case 3: case 4: case 5: case 6: case 8: case 9: 
				res = "***";
				break;
			case 7:  
				res = "  *";
				break;
			case 0:
				res = "* *";
				break;
			}
		}
		if (row == 4) {
			switch(num) {
			case 1: 
				res = "*";
				break;
			case 2:
				res = "*  ";
				break;
			case 3: case 4: case 5: case 7: case 9: 
				res = "  *";
				break;
			 case 6: case 8: case 0:
				res = "* *";
				break;
			}
		}
		if (row == 5) {
			switch(num) {
			case 1: 
				res = "*";
				break;
			case 2: case 3: case 5: case 6: case 8:  case 9: case 0:
				res = "***";
				break;
			case 4: case 7:
				res = "  *";
				break;
			}
		}
		return res;
	}
	
	public static String printOpRow(int row, String op) {
		String res = null;
		if (row == 1) {
			if (op.equals("=")) {
				res = "    ";
			} else if (op.equals(".")) {
				res = "  ";
			} else {
				res = "   ";
			}
		}
		if (row == 2) {
			switch(op) {
			case "+":
				res = " * ";
				break;
			case "-":
				res = "   ";
				break;
			case "*": 
				res = "* *";
				break;
			case "/":
				res = "  *";
				break;
			case "=":
				res = "****";
				break;
			case ".":
				res = "  ";
				break;
			}
		}
		if (row == 3) {
			switch(op) {
			case "+":
				res = "***";
				break;
			case "-":
				res = "***";
				break;
			case "*": 
				res = " * ";
				break;
			case "/":
				res = " * ";
				break;
			case "=":
				res = "    ";
				break;
			case ".":
				res = "  ";
				break;
			}
		}
		if (row == 4) {
			switch(op) {
			case "+":
				res = " * ";
				break;
			case "-":
				res = "   ";
				break;
			case "*": 
				res = "* *";
				break;
			case "/":
				res = "*  ";
				break;
			case "=":
				res = "****";
				break;
			case ".":
				res = "**";
				break;
			}
		}
		if (row == 5) {
			switch(op) {
			case "+":
				res = "   ";
				break;
			case "-":
				res = "   ";
				break;
			case "*": 
				res = "   ";
				break;
			case "/":
				res = "   ";
				break;
			case "=":
				res = "    ";
				break;
			case ".":
				res = "**";
				break;
			}
		}
		return res;
	}
}

我的第三题代码 将近300行眼睛快瞎了

2017-04-18 21:59

你们谁看懂第四题了  给讲讲?///




2017-04-18 22:04
1

有没有原题,想回顾一下

2017-04-18 22:05

赛码网有没有这几道题啊,想再写一写提交看运行对不对。求链接

2017-04-18 22:37
1
/*
题目意思都不清晰,拿头猜题意写
*/
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <iostream>

using namespace std;

char num[5][60] = { "*    ***   ***   * *   ***   ***   ***   ***   ***   ***",
                    "*      *     *   * *   *     *       *   * *   * *   * *",
                    "*    ***   ***   ***   ***   ***     *   ***   ***   * *",
                    "*    *       *     *     *   * *     *   * *     *   * *",
                    "*    ***   ***     *   ***   ***     *   ***   ***   ***"};
char op[5][60]  = { "                               ",
                    " *        * *    *   ****      ",
                    "***  ***   *    *              ",
                    " *        * *  *     ****   ** ",
                    "                            ** "};

int numSt[11] = {0,5,11,17,23,29,35,41,47,53};
int opSt[6] = {0,5,10,15,21,28};
int numSz[10] = {1,3,3,3,3,3,3,3,3,3};
int opSz[6] = {3,3,3,3,4,2};

vector<vector<char>> ans_vector(5);
int M[256];

void add(int id){
    if(id <= 10){
        for(int i = 0; i < 5; i++){
            for(int j = 0, st = numSt[id]; j < numSz[id]; j++){
                ans_vector[i].push_back(num[i][st+j]);
            }
            ans_vector[i].push_back(' ');
            ans_vector[i].push_back(' ');
        }
    }else{
        id -= 11;
        for(int i = 0; i < 5; i++){
            for(int j = 0, st = opSt[id]; j < opSz[id]; j++){
                ans_vector[i].push_back(op[i][st+j]);
            }
            ans_vector[i].push_back(' ');
            ans_vector[i].push_back(' ');
        }
    }
}

int main(){
    
    for(int i = 1; i <= 9; i++) M['0'+i] = i-1;
    M['0'] = 9;
    M['+'] = 11;
    M['-'] = 12;
    M['*'] = 13;
    M['/'] = 14;
    M['='] = 15;
    M['.'] = 16;

    string arr;
    getline(cin, arr);
    double ans = 0;
    int preop = -1;
    
    int len = arr.length();
    for (int i = 0; i < len;){
        while(i < len && arr[i] == ' ') i++;
        bool isf = false, isnum = false;
        int dig = 0, nodig = 0;
        double pre = 1;
        while((i < len) && ((arr[i] >= '0' && arr[i] <= '9')||arr[i] == '.')){
            isnum = true;
            if(arr[i] == '.') isf = true, add(M[arr[i]]);
            else if(isf){
                nodig = nodig * 10 + arr[i] - '0';
                pre *= 0.1;
                add(M[arr[i]]);
            }else{
                dig = dig * 10 + arr[i] - '0';
                add(M[arr[i]]);
            }
            i++;
        }
        if(isnum){
            if(preop == -1) ans = dig + nodig*pre;
            else if(preop == 11) ans += dig + nodig*pre;
            else if(preop == 12) ans -= dig + nodig*pre;
            else if(preop == 13) ans *= dig + nodig*pre;
            else if(preop == 14) ans /= dig + nodig*pre;
        }
        if(i < len && M[arr[i]] != 0){
            preop = M[arr[i]];
            add(preop);
            i++;
        }
    }
    
    add(M['=']);
    
    char res[1000];
    if(ans-int(ans)==0) sprintf(res,"%d",int(ans));
    else if(ans*10-int(ans*10)==0)sprintf(res,"%.1f",ans);
    else sprintf(res,"%.2f",ans);
    int res_len = strlen(res);
    for(int i = 0; i < res_len; i++) add(M[res[i]]);

    for(int i = 0; i < 5; i++){
        for(int j = 0; j < ans_vector[i].size(); j++) cout << ans_vector[i][j];
        cout << "\n";
    }
    return 0;
}


2017-04-18 22:57
#include <cstdio>
#include <cstring>

using namespace std;
char screen[5][1000];
int k;

char a0[5][4] = {"***", "* *", "* *", "* *", "***"};
char a1[5][4] = {"*  ", "*  ", "*  ", "*  ", "*  "};
char a2[5][4] = {"***", "  *", "***", "*  ", "***"};
char a3[5][4] = {"***", "  *", "***", "  *", "***"};
char a4[5][4] = {"* *", "* *", "***", "  *", "  *"};
char a5[5][4] = {"***", "*  ", "***", "  *", "***"};
char a6[5][4] = {"***", "*  ", "***", "* *", "***"};
char a7[5][4] = {"***", "  *", "  *", "  *", "  *"};
char a8[5][4] = {"***", "* *", "***", "* *", "***"};
char a9[5][4] = {"***", "* *", "***", "  *", "***"};
char jia[5][4]    = {"   ", " * ", "***", " * ", "   "};
char jian[5][4]   = {"   ", "   ", "***", "   ", "   "};
char cheng[5][4]  = {"   ", "* *", " * ", "* *", "   "};
char chu[5][4]    = {"   ", "  *", " * ", "*  ", "   "};
char dengyu[5][4] = {"   ", "***", "   ", "***", "   "};
char dian[5][4]   = {"   ", "   ", "   ", " **", " **"};

void draw(char c) {
    char (*q)[5][4];

    if (c == ' ') {
        for (int i = 0; i < 5; ++i) {
            for (int j = 0; j < 2; ++j) {
                screen[i][j + k] = ' ';
            }
        }
        k += 2;
        return;
    } else if (c == '0') {
        q = &a0;
    } else if (c == '1') {
        q = &a1;
    } else if (c == '2') {
        q = &a2;
    } else if (c == '3') {
        q = &a3;
    } else if (c == '4') {
        q = &a4;
    } else if (c == '5') {
        q = &a5;
    } else if (c == '6') {
        q = &a6;
    } else if (c == '7') {
        q = &a7;
    } else if (c == '8') {
        q = &a8;
    } else if (c == '9') {
        q = &a9;
    } else if (c == '.') {
        q = &dian;
    } else if (c == '+') {
        q = &jia;
    } else if (c == '-') {
        q = &jian;
    } else if (c == '*') {
        q = &cheng;
    } else if (c == '/') {
        q = &chu;
    } else if (c == '=') {
        q = &dengyu;
    }

    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < 3; ++j) {
            screen[i][j + k] = (*q)[i][j];
        }
    }
    k += 3;
}

int main() {
    memset(screen, 0, sizeof(screen));
    k = 0;

    int a, b;
    char op;
    int r1;
    double r2;

    bool xiaoshu = false;
    scanf("%d %c %d", &a, &op, &b);
    if (op == '+') {
        r1 = a + b;
    } else if (op == '-') {
        r1 = a - b;
    } else if (op == '*') {
        r1 = a * b;
    } else {
        if (a % b == 0) {
            r1 = a / b;
        } else {
            r2 = (double)a / b;
            xiaoshu = true;
        }
    }

    char s[100];
    if (!xiaoshu)
        sprintf(s, "%d %c %d = %d", a, op, b, r1);
    else
        sprintf(s, "%d %c %d = %.2f", a, op, b, r2);

    for (char *p = s; *p != '\0'; ++p) {
        draw(*p);
    }

    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < k; ++j)
            printf("%c", screen[i][j]);
        printf("\n");
    }
    return 0;
}


2017-04-18 23:12

第一题python为什么不A?


import sys

s1 = set()


n = int(sys.stdin.readline())


for i in range(n):

num = int(sys.stdin.readline().strip())

s1.add(num)


n = int(sys.stdin.readline().strip())


ret = []

for i in range(n):

num = int(sys.stdin.readline().strip())

if num in s1:

ret.append(num)


print(' '.join(map(str, ret)))


2017-04-18 23:45

第四题答案??

2017-04-18 23:55

第四题:一遇dp就跪了,暴力能过30%。。

给出的答案思路大概是这样的。所谓的翻转是指

   1                     1

A:2 3     =>     B:1 2

   1 1 1               1 3 1

就是把对角线平放,然后求前缀和。所以sum数组保存的是

   1

C:1 3

   1 4 5

dp是根据第C个三角行来看的。

因为memset(dp, 200, sizeof(dp)),所以dp中保存的是很小的负数。

故max函数的后半部分可以看成判定(i,j)在k次选择中可否被选中。

dp[i - 1][std::max(0, j - 1)][k - j] + sum[i][j]),表示如果第i行消费了j次机会,则前i-1行用了k-j次机会。那么为什么是中间j-1呢,因为从上面的三角形转换加前缀和可以看出,
2          1
1 1   =>   1 3 所以,求一个任务及其依赖任务的值就是 dp[i-1][j-1][] + sum[i][j]

说的有点乱,总之就是要从原来三角形的对角去看,调试几遍就懂了。


第三题:AC,原来只需要考虑一个双元运算即可,想复杂了,写成了能计算无括号的四则运算。。

#include <bits/stdc++.h>
using namespace std;

vector<vector<string>> nums = {
        {"***", "*",    "***",   "***",   "* *",   "***",   "***",   "***",   "***",   "***",   },
        {"* *", "*",    "  *",   "  *",   "* *",   "*  ",   "*  ",   "  *",   "* *",   "* *",   },
        {"* *", "*",    "***",   "***",   "***",   "***",   "***",   "  *",   "***",   "***",   },
        {"* *", "*",    "*  ",   "  *",   "  *",   "  *",   "* *",   "  *",   "* *",   "  *",   },
        {"***", "*",    "***",   "***",   "  *",   "***",   "***",   "  *",   "***",   "***",   }};

vector<vector<string>> op = {
        {"   ", "   ", "   ", "   ", "    ", "  "},
        {" * ", "   ", "* *", "  *", "****", "  "},
        {"***", "***", " * ", " * ", "    ", "  "},
        {" * ", "   ", "* *", "*  ", "****", "**"},
        {"   ", "   ", "   ", "   ", "    ", "**"}};

map<char, int> op_hash;

double calculate(string s, bool& is_float) {
    istringstream in('+' + s + '+');
    double total = 0, term = 0, n;
    char op;
    while (in >> op) {
        if (op == '+' or op == '-') {
            total += term;
            in >> term;
            term *= 44 - op;
        } else {
            in >> n;
            if (op == '*')
                term *= n;
            else {
                if ((int)term % (int)n != 0) {
                    is_float = true;
                }
                term /= n;
            }
        }
    }
    return total;
}

void output(string res) {
    for (int i = 0; i < 5; ++i) {
        for (int j = 0; j < res.size(); ++j) {
            if (isdigit(res[j])) {
                cout << nums[i][res[j] - '0'] << "  ";
            }
            else if (res[j] != ' '){
                cout << op[i][op_hash[res[j]]] << "  ";
            }
        }
        cout << endl;
    }
}

int main() {
    string s;
    op_hash['+'] = 0;
    op_hash['-'] = 1;
    op_hash['*'] = 2;
    op_hash['/'] = 3;
    op_hash['='] = 4;
    op_hash['.'] = 5;
    while(getline(cin, s)) {
        bool is_float = false;
        auto ans = calculate(s, is_float);
        stringstream ss;
        if (is_float)
            ss << fixed << setprecision(2) << ans;
        else
            ss << fixed << setprecision(0) << ans;
        string res = s + "=" + ss.str();
        output(res);
    }
    return 0;
}


2017-04-19 01:26
4
小码快跑 回复 coder_8aPVMgZv

同学你好,真题需要经过头条的许可才能公布,我们会争取尽快公布

2017-04-19 08:56

有没有java版本的呀

2017-04-19 09:02
1
coder_uRMETFVS 回复 coder_2R9CJG77

我也看错了,,以为只是三角形斜边有依赖呢。。

2017-04-19 09:52
java.util.Arrays;
import java.util.*;
public class Main {

	public static void main(String[] args) {
		//定义数字 数组
		String num[][]=new String [10][5];
		num[0][0]="***";
		num[0][1]="* *";
		num[0][2]="* *";
		num[0][3]="* *";
		num[0][4]="***";
		
		num[1][0]="*  ";
		num[1][1]="*  ";
		num[1][2]="*  ";
		num[1][3]="*  ";
		num[1][4]="*  ";
		
		num[2][0]="***";
		num[2][1]="  *";
		num[2][2]="***";
		num[2][3]="*  ";
		num[2][4]="***";
		
		num[3][0]="***";
		num[3][1]="  *";
		num[3][2]="***";
		num[3][3]="  *";
		num[3][4]="***";
		
		num[4][0]="* *";
		num[4][1]="* *";
		num[4][2]="***";
		num[4][3]="  *";
		num[4][4]="  *";
		
		num[5][0]="***";
		num[5][1]="*  ";
		num[5][2]="***";
		num[5][3]="  *";
		num[5][4]="***";
		
		num[6][0]="***";
		num[6][1]="*  ";
		num[6][2]="***";
		num[6][3]="* *";
		num[6][4]="***";
		
		num[7][0]="***";
		num[7][1]="  *";
		num[7][2]="  *";
		num[7][3]="  *";
		num[7][4]="  *";
						
		num[8][0]="***";
		num[8][1]="* *";
		num[8][2]="***";
		num[8][3]="* *";
		num[8][4]="***";
		
		num[9][0]="***";
		num[9][1]="* *";
		num[9][2]="***";
		num[9][3]="  *";
		num[9][4]="***";
		
		//定义运算符 数组
		String ops[][]=new String [6][5];
		ops[0][0]="   ";
		ops[0][1]=" * ";
		ops[0][2]="***";
		ops[0][3]=" * ";
		ops[0][4]="   ";
		
		ops[1][0]="   ";
		ops[1][1]="   ";
		ops[1][2]="***";
		ops[1][3]="   ";
		ops[1][4]="   ";
		
		ops[2][0]="   ";
		ops[2][1]="* *";
		ops[2][2]=" * ";
		ops[2][3]="* *";
		ops[2][4]="   ";
		
		ops[3][0]="   ";
		ops[3][1]="  *";
		ops[3][2]=" * ";
		ops[3][3]="*  ";
		ops[3][4]="   ";
		
		ops[4][0]="   ";
		ops[4][1]="***";
		ops[4][2]="   ";
		ops[4][3]="***";
		ops[4][4]="   ";
		
		ops[5][0]="   ";
		ops[5][1]="   ";
		ops[5][2]="   ";
		ops[5][3]=" **";
		ops[5][4]=" **";
		
		
		Scanner sc=new Scanner(System.in);		
		int m=sc.nextInt();
		String op1=sc.next();
		int n=sc.nextInt();	
			
		float result=0;		
		String str_res="";	
			
		if(op1.equals("+"))
			result=m+n;
		else if(op1.equals("-"))
			result=m+n;
		else if(op1.equals("*"))
			result=m*n;
		else result=m/(float)n;
	    

		String res=null;
		if(op1.equals("+")||op1.equals("-")||op1.equals("*")||m%n==0)
					{res=Integer.toString((int)result);}
		else res=Float.toString(result);
	
		
		//第一个操作数
		ArrayList alm=new ArrayList();		
		while(m>0)
		{
			alm.add(m%10);
			m=m/10;			
		}		
		int mm1[]=new int[alm.size()];
		for(int j=0;j<mm1.length;j++)
		{
			mm1[j]=(int)alm.get(mm1.length-1-j);
			str_res+=mm1[j];
		}
		str_res+=op1;
		//第二个操作数
       ArrayList aln=new ArrayList();		
		while(n>0)
		{
			aln.add(n%10);
			n=n/10;			
		}		
		int nn1[]=new int[aln.size()];
		for(int j=0;j<nn1.length;j++)
		{
			nn1[j]=(int)aln.get(nn1.length-1-j);
			str_res+=nn1[j];
		}
		str_res+='=';

		char rr1[]=new char[res.length()];
		for(int j=0;j<res.length();j++)
		{
			rr1[j]=res.charAt(j);
			str_res+=rr1[j];
		}
		


		//把数字和运算符都进行组合,组成一个字符串,然后进行显示;
		
	
		char[] char_res=str_res.toCharArray();
		System.out.println(Arrays.toString(char_res));
		System.out.println(char_res[0]<'9'&&char_res[0]>'0');//注意字符数组 元素是字符,
									//比较时,应该和‘1’或‘9’进行比较,而不是和0或9进行比较;
		for(int j=0;j<5;j++)//一共5行,分别输出;
							//只能一行一行的进行输出;
			{
				for(int k=0;k<char_res.length;k++)					
				{
					if(char_res[k]>='0'&&char_res[k]<='9')
						System.out.print(num[char_res[k]-'0'][j]+"  ");
					else if(char_res[k]=='+')
						System.out.print(ops[0][j]+"  ");
					else if(char_res[k]=='-')
						System.out.print(ops[1][j]+"  ");
					else if(char_res[k]=='*')
						System.out.print(ops[2][j]+"  ");
					else if(char_res[k]=='/')
						System.out.print(ops[3][j]+"  ");
					else if(char_res[k]=='=')
						System.out.print(ops[4][j]+"  ");
					else if(char_res[k]=='.')
						System.out.print(ops[5][j]+"  ");						
				}
				System.out.println();
			}		
	}
}
很容易理解的方法


2017-04-19 11:23

第三题ac代码

import java.util.*;

import java.math.RoundingMode;

import java.text.NumberFormat;

public class Main {

public static void main(String[] args) {

NumberFormat nf = NumberFormat.getNumberInstance();

nf.setMaximumFractionDigits(2);

nf.setRoundingMode(RoundingMode.UP);

Scanner s = new Scanner(System.in);

String[][] num = new String[][] { 

{ "***", "* *", "* *", "* *", "***" }, 

{ "*", "*", "*", "*", "*" },

{ "***", "  *", "***", "*  ", "***" }, 

{ "***", "  *", "***", "  *", "***" },

{ "* *", "* *", "***", "  *", "  *" },

{ "***", "*  ", "***", "  *", "***" },

{ "***", "*  ", "***", "* *", "***" },

{ "***", "  *", "  *", "  *", "  *" },

{ "***", "* *", "***", "* *", "***" }, 

{ "***", "* *", "***", "  *", "***" }

};

String jia[] = new String[] { "   ", " * ", "***", " * ", "   " };

String jian[] = new String[] { "   ", "   ", "***", "   ", "   " };

String cheng[] = new String[] { "   ", "* *", " * ", "* *", "   " };

String chu[] = new String[] { "   ", "  *", " * ", "*  ", "   " };

String deng[] = new String[] { "    ", "****", "    ", "****", "    " };

String dian[] = new String[] { "  ", "  ", "  ", "**", "**" };

String kong[] = new String[] { "  ", "  ", "  ", "  ", "  " };

int a = s.nextInt();

String c = s.next();

int b = s.nextInt();

List<String[]> l = new ArrayList<>();

String as[] = (a + "").split(""); //第一个数字

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

int t = Integer.parseInt(as[i]);

l.add(num[t]);

l.add(kong);

}

String re = "";

if (c.equals("+")) { //操作符

l.add(jia);

re = (a + b) + "";

} else if (c.equals("-")) {

l.add(jian);

re = (a - b) + "";

} else if (c.equals("*")) {

l.add(cheng);

re = (a * b) + "";

}

else if (c.equals("/")) {

l.add(chu);

re = nf.format(a / 1.0 / b);

}

l.add(kong);

String bs[] = (b + "").split(""); //第二个数字

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

int t = Integer.parseInt(bs[i]);

l.add(num[t]);

l.add(kong);

}

l.add(deng); //等号

l.add(kong);

String rs[] = (re + "").split("");

for (int i = 0; i < rs.length; i++) { //计算结果

int t = -1;

try {

t = Integer.parseInt(rs[i]);

l.add(num[t]);

l.add(kong);

} catch (Exception e) {

l.add(dian);

l.add(kong);

}

}

String tt[] = new String[5];

for (int i = 0; i < 5; i++) { //去掉行末多余的两个空格

StringBuffer str = new StringBuffer();

for (int j = 0; j < l.size(); j++) {

str.append(l.get(j)[i]);

}

tt[i] = str.substring(0, str.length() - 2);

}

for (int i = 0; i < 5; i++) {

System.out.println(tt[i]);

}

}

}


2017-04-19 11:24
2
coder_4vhHVVpr 回复 coder_NFJ8PYSX

一题60%,二题40%。。。

2017-04-19 16:22

请问什么时候可以提交昨天比赛编程题

2017-04-19 17:20

求一下第四题动态规划的AC的代码~

2017-04-19 20:30

头条招聘里也没有题解啊,上午看还有代码题解怎么现在看就没了?

2017-04-19 22:20
coder_CJD9FT5S 回复 acmcoderQxqBn90z

a.contains(b)

2017-04-25 15:44
benjamin 回复 coder_DvmxJXcy

多谢~

2017-04-25 21:02

头条的实习生群是多少啊?

2017-04-25 21:57
coder_Z49WRV2B 回复 acmcoderyy4o4sMn

讲的乱七八糟不知所云。。

2017-05-10 16:40

师弟师妹,师兄帮你内推阿里巴巴

师兄微信号: alibabazp

师兄专门为你排忧解难,同时赠送相关学习资料。

内推贴:

https://discuss.acmcoder.com/topic/5d50cb6751f256de05b3dd5a


2019-08-15 19:21
甜美果汁 回复 coder_KAWW875N

niubilyty

2019-08-22 15:05
添加回复
回到顶部