记2019春招笔试算法题(一)

前言

春招准备得很晚,基础知识啃一点忘一点,还是需要一个大块时间片做做复习。目前感觉投的数量还不够多,这两天再看看多投几家。自己还是比较想做游戏研发,虽然没什么底子,不过能做后台也知足了。

先记录一下题目,之后研究一下最优解再发解答。

3.28 米哈游 游戏客户端

  1. 求十进制长整数的二进制表示。
    语言限制:C/C++
    输入:一个十进制非负整数n,保证n<10^1024。
    输出:一个二进制数,是n的二进制表示形式。

输入样例#1:

0

输出样例#1:

0

输入样例#2:

2019

输出样例#2:

11111100011
  1. 有一块方形区域,用二维平面的x-y坐标表示。现要在不同的小正方形区域内涂色,涂过色的区域再涂色的话状态不变,当涂了n个区域后,求这个区域被涂色部分的面积。
    空间限制:使用内存不大于64MB。
    输入:第一行为一个非负整数n,表示涂色的小正方形区域数量。接下来的n行,每一行有三个整数,前两个数x、y为小正方形左下角顶点的坐标,保证x∈[0,65530]、y∈[0,65530],第三个数a为小正方形的边长,保证a∈(0,5]。
    输出:一个数字,表示被涂色的面积。

输入样例#1:

1
2 2 2

输出样例#1:

4

输入样例#2:

2
0 0 2
1 1 2

输出样例#2:

7

3.28 巨人网络 游戏研发

  1. 有n个方块,每个方块的长、宽、高是a、b、h。不旋转每个方块,把它们叠在一起,要求每个方块下面的方块的长和宽必须大于其自身的长和宽。求能叠起的最大高度。
    输入:第一行为一个非负整数n,表示方块的数量。接下来的n行,每一行有三个正整数,表示其中一个方块的a、b、h。
    输出:一个数字,表示能叠起的最大高度。

输入样例#1:

1
1 2 3

输出样例#1:

3

输入样例#2:

2
1 2 3
4 5 6

输出样例#2:

9
  1. 有一棵给定结构的二叉树,其中有10个节点,根据每个节点不同的值,求根节点到所有叶子节点的路径中所有节点的值之和最大的一条。
    说明:树结构和节点名称如下图
    Tree
    输入:10个整数,分别表示A-J节点的值。
    输出:节点值之和最大的路径从根节点起的节点名称字符串,如果有多条,输出任意一条。

输入样例#1:

1 2 3 1 2 3 1 2 3 0

输出样例#1:

ABEI

4.3 拼多多 Java开发

  1. 一个含有偶数个元素的数组,在其中每次选择两个元素计算相加之和,再在剩下的元素中继续选择两个元素计算相加之和,直至所有元素用尽。求一种选择方法,使得所有和的最大值和最小值的差值最小。
    输入:第一行为一个非负整数n,表示数组中元素的数量。第二行为n个整数,表示数组中的元素。
    输出:一个数字,表示最大值和最小值的差值。

输入样例#1:

4
2 9 4 6

输出样例#1:

1

输入样例#2:

6
1 2 3 4 5 6

输出样例#2:

0
  1. 给定0-9十种数字每一种的可用数量,使用给定的这些数字构造一个m位数和一个n位数,使得他们的乘积最小,求这个乘积。
    说明:构造的数字可以包含一个或多个前导0。
    输入:第一行为10个非负整数,分别表示0-9中每种数字的个数。第二行为一个正整数m。第三行为一个正整数n。
    输出:一个数字,表示最小乘积。

输入样例#1:

1 3 0 0 0 0 0 0 0 0
2
2

输出样例#1:

11

输入样例#2:

1 9 0 0 0 0 0 0 0 0
9
1

输出样例#2:

0
  1. 有一堆袜子,每只的颜色用一个数字c来表示,当两只袜子的颜色差小于或等于定义的阈值k时,判定他们为可接受的一双袜子。求在n只袜子中任意挑选两只,它们可以被接受的概率。
    输入:第一行为一个数组,每个元素表示每一只袜子的颜色c。第二行为一个整数,表示阈值k。
    输出:一个小数,保留小数点后六位,表示这个概率。

输入样例#1:

[1, 2, 5, 6]
1

输出样例#1:

0.333333

输入样例#2:

[1, 2]
2

输出样例#2:

1.000000
  1. 定义以下对单一字符串的操作为一个步骤:添加一个字符、修改一个字符、删除一个字符。给定两个字符串s1、s2,求使其中一个字符串变为另一个字符串所需的最小步骤数。
    输入:第一行为字符串s1。第二行为字符串s2。
    输出:一个数字,表示该最小步骤数。

输入样例#1:

horse
ros

输出样例#1:

3

LeetCode原题,最小编辑距离,是个Hard。
Edit Distance - LeetCode

4.8 携程 后台开发

  1. 给定一个单链表,判断其是否有环。
    输入:从头结点开始的链表中的每个元素。
    输出:若有环,输出true。否则,输出false。

输入样例#1:

a b c d e f

输出样例#1:

false

输入样例#2:

a b c d b

输出样例#2:

true
  1. 给定一个单链表,按组反转其中的k个元素,若最后一组不足k个元素,则不进行反转。
    说明:不允许修改链表元素的值,只允许修改其位置。
    输入:第一行为从头结点开始的链表中的每个元素,以数组的形式表示。第二行为一个正整数k。
    输出:反转后的链表元素,以数组的形式表示。

输入样例#1:

[1,2,3,4,5,6,7]
2

输出样例#1:

[2,1,4,3,6,5,7]

输入样例#2:

[1,2,3,4,5]
3

输出样例#2:

[3,2,1,4,5]
  1. 给定一组Path或XPath,输出其中每个路径中每个子节点被相同路径访问过的次数,固定根节点和叶子节点为1。
    输入:一个数字n,为Path的数量。接下来有n个Path或XPath。
    输出:对于每个Path或XPath,输出一个字符串,表示从头节点开始每个子节点被相同路径访问过的次数。

输入样例#1:

1 /order

输出样例#1:

1

输入样例#2:

2 /order/tree /order/tree/

输出样例#2:

11 11

输入样例#3:

4 /order/ /order/tree/node /order/tree/ /order/tree/node/

输出样例#3:

1 111 11 121

输入样例#4:

5 /order/tree/node /order/tree/node/subnode/ /order/tree/node/subnode /order/tree/node /order/tree/node/

输出样例#4:

111 1111 1221 121 131

4.10 吉比特 游戏研发

  1. 给定一个数组,求其中一段连续子序列,使序列中所有元素的和最小。
    输入:第一行为一个数字n,表示数组中元素的数量。第二行为n个整数,表示数组中的元素。
    输出:这段子序列中所有元素的和。

输入样例#1:

5
2 -3 1 0 -2

输出样例#1:

-4

输入样例#2:

3
1 1 1

输出样例#2:

1
  1. 我们把类似125065187、12201198这样的数字定义为“2018数”,这种数字可以在删除其中几位数的情况下变为2018。对于一个数n,求不大于n的所有正整数中“2018数”的数量。
    时间限制:运行时间不大于2秒。
    输入:一个正整数n,保证n<1000000000。
    输出:不大于n的所有正整数中2018数的数量。

输入样例#1:

2018

输出样例#1:

1

输入样例#2:

20182018

输出样例#2:

92237

“记2019春招笔试算法题(一)”的一个回复

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注