袋熊的树洞

日拱一卒，功不唐捐

0%

今日头条2018春季校园招聘编程题

Posted on Edited on

题目一 找到差值为k的数字对的个数

问题描述

在n个元素的数组中，找到差值为k的数字对去重后的个数

输入描述：

1
2
第一行，n和k，n表示数字个数，k表示差值
第二行，n个正整数

输出描述：

1
差值为k的数字对去重后的个数

示例 1

输入

1
2
5 2
1 5 3 4 2

输出

1
3

说明

1
其中数字对分别为 (1, 3), (5, 3), (4, 2)

示例 2

输入

1
2
6 2
1 5 3 3 4 2

输出

1
3

说明

1
其中数字对分别为 (1, 3), (5, 3), (4, 2)

示例 3

输入

1
2
4 0
1 1 1 1

输出

1
1

说明

1
其中数字对分别为 (1, 1)

备注：

1
2
3
4
5
6
数据范围：
对于 100% 的数据，0 <= k < 100
对于 100% 的数据，数组内数值范围在 [0, 100000000]
对于 30% 的数据，0 < n < 1000
对于 80% 的数据，0 < n < 100000
对于 100% 的数据，0 < n < 1000000

解决方案

这道题目在 LeetCode 有相应的题目，题目为 532. K-diff Pairs in an Array，这道题目我在另一篇博文做了解答，可以参考 LeetCode 532 - K-diff Pairs in an Array

题目二 求函数调用次数

问题描述

定义两个字符串变量：s 和 m，再定义两种操作。

第一种操作：

1
2
m = s;
s = s + s;

第二种操作：

1
s = s + m;

假设 s, m 初始化如下：

1
2
s = "a";
m = s;

求最小的操作步骤数，可以将 s 拼接到长度等 n

输入描述：

1
2
一个整数n，表明我们需要得到s字符串长度
对于100%的数据，0 < n < 10000

输出描述：

1
一个整数，表明总共操作次数

示例 1

输入

1
6

输出

1
3

说明

1
输入是6，表明我们需要得到s字符串长度为6，也就是s最终为"aaaaaa"，那么依次使用2次"第一次操作“和1次"第二种操作"就能达到目的，总共操作次数是3。

示例2

输入

1
5

输出

1
4

说明

1
假设n=5，表明我们需要得到s字符串长度为5，也就是s最终为"aaaaa"，那么直接使用4次"第二种操作“就能达到目的，总共操作次数是4。

示例3

输入

1
4

输出

1
2

说明

1
假设n=4，表明我们需要得到s字符串长度为4，也就是s最终为"aaaa"，那么直接使用2次"第一种操作"就能达到目的，总共操作次数是2。

题目三

没记录到。。。

题目四 Magic

问题描述

给一个包含n个整数元素的集合a，一个包含m个整数元素的集合b。定义magic操作为，从一个集合中取出一个元素，放到另一个集合里，且操作过后每个集合的平均值大于操作前。注意以下两点：

  1. 不可以把一个集合的元素取空，这样就没有平均值了
  2. 值为x的元素从集合b取出放入集合a，但集合a中已有值为x的元素，则a的平均值不变 (因为集合元素不会重复)，b的平均值可能会改变 (因为x被取出了)

问最多可以进行多少次magic操作？

输入描述：

1
2
3
4
5
6
第一行为两个整数n，m
第二行n个整数，表示集合a中的元素
第三行m个整数，表示集合b中的元素
对于30%的数据，最终结果 <= 1
对于70%的数据，输入中的a，b集合元素完全没有重复，即 |a| + |b| = |a 并 b|
对于100%的数据，1 < n, m < 100,000，0 < a[i], b[i] < 100,000,000，集合a中元素互不相同，集合b中元素互不相同

输出描述：

1
输出一个整数，表示最多可以进行的操作次数。

示例 1

输入

1
2
3
3 5
1 2 5
2 3 4 5 6

输出

1
2

说明

1
依次从b集合取出3，4元素放入a集合

题目五 跳板小游戏

问题描述

小T最近迷上了一款跳板小游戏。已知空中有N个高度互不相同的跳板，小T刚开始在高度为0的地方，每次跳跃可以选择与自己当前高度绝对值差小于等于H的跳板，跳跃过后到达以跳板为轴的镜像位置，问小T在最多跳K次的情况下最高能跳多高？ (任意时刻，高度不能为负)

输入描述：

1
2
第一行三个整数N，K，H
以下N行，每行一个整数Ti，表示第i个跳板的离地高度

输出描述：

1
一个整数，表示最高能跳到的高度

示例 1

输入

1
2
3
4
3 3 2
1
3
6

输出

1
8

说明

1
2
3
4
小T初始在高度为0的地方
第一次跳跃只能选择高度为1的跳板，结束后到达高度为2的地方，计算方式：高度1 = 初始高度 + (跳板1高度 - 初始高度)*2 = 0 + (1-0)*2 = 2
第二次跳跃选择高度为3的跳板，结束后到达高度为4的地方，计算方式：高度2 = 高度1 + (跳板2高度 - 高度1)*2 = 2 + (3-2)*2 = 4
第三次跳跃选择高度为6的跳板，结束后到达高度为8的地方，计算方式：高度3 = 高度2 + (跳板3高度 - 高度2)*2 = 4 + (6-4)*2 = 8

备注：

1
2
对于40%的数据，1 <= N, K, H, Ti <= 20
对于100%的数据，1 <= N, K, Ti <= 100,000, 1 <= H <= 100