offer（拿来吧你！网易有道笔试编程题特辑）
联系我们：有道技术团队助手：ydtech01 / 邮箱：ydtech@rd.netease.com
欢迎应届生同学们
来到2022年校招运动会
现在迎面向你们走来的
是网易有道代表队！
（传送门：http://hr.youdao.com/ ）
文章图片
他们食堂好吃
他们从不内卷
今天，他们还带来了
10道笔试编程题
据说全做对的同学
都顺利地拿到了 offer！
同学们，请开始你们的 bug
啊不
表演吧！
一、热身运动
1.1 找到重复数字
给定一个包含 n+1 个整数的数组 nums ，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设 nums 只有一个重复的整数 ，找出这个重复的数。
- 难度：一星
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 256MB，其他语言512MB
- 64bit IO Format: %lld**
- 输入：[1,3,4,2,2]
- 返回：2
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 返回重复数字
* @param nums int整型一维数组
* @return int整型
*/
public int duplicate (int[] nums) {
// write code here
int n = nums.length;
int l = 1, r = n - 1, ans = -1;
while (l <= r) {
int mid = (l + r) >> 1;
int cnt = 0;
for (int i = 0;
i < n;
++i) {
if (nums[i] <= mid) {
cnt++;
}
}
if (cnt <= mid) {
l = mid + 1;
} else {
r = mid - 1;
ans = mid;
}
}
return ans;
}
}1.2 三角形面积
输入三个点的坐标，输出三个点组成的三角形的面积。（结果保留三位小数点并四舍五入）
- 难度：一星
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 256MB，其他语言512MB
- Special Judge, 64bit IO Format: %lld
- 知识点：计算几何
- 输入：12，-70，95，91，-72，35
- 输出：11119.500
#include
#include
#include using namespace std;
int main() {
double x1, y1, x2, y2, x3, y3;
cin >> x1 >> y1 >> x2 >> y2 >> x3 >> y3;
double xa = (x1 - x2);
double ya = (y1 - y2);
double xb = (x3 - x2);
double yb = (y3 - y2);
float area = fabs((xa * yb - ya * xb) / 2.0);
printf("%.3f", area);
return 0;
} 二、伸展运动 2.1 分解自然数
一个自然数可以将它分解成若干个自然数相乘。现在给你一个指定的自然数 n，请求出每种分解自然数之和的最小值是多少。
- 难度：二星
- 时间限制：C/C++ 5秒，其他语言10秒
- 空间限制：C/C++ 32MB，其他语言64M
- 64bit IO Format: %lld
- 输入：6
- 返回：5
- 说明：6分解为2 * 3，那么最小的和为2+3=5
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 得到分解自然数之和的最小值
# @param n int整型 自然数n
# @return int整型
#
class Solution:
def getMinSum(self , n ):
if n <= 1:
return n
temp = int(n / 2)
while temp != 0:
if n % temp == 0:
if temp == 1 and n / temp == n:
print(n)
return n
else:
return self.getMinSum(n / temp) + self.getMinSum(temp)
else:
temp -= 12.2 恢复异常数
有一个一维整数数组 fuzzyArray，里面存储的是从 1 到 n 这 n 个数，不过是乱序存储；这时有一个位置的数字变成了 -1。请用最优的空间复杂度和时间复杂度求出这个异常数的位置和原来的值。
- 难度：二星
- 时间限制：C/C++ 5秒，其他语言10秒
- 空间限制：C/C++ 256 MB，其他语言512 MB
- 64bit IO Format: %lld
- 知识点：测试开发、数组
- 输入 ： [2, -1, 3]
- 返回： [1,1]
- 说明： 异常数组原本应该是存储从 1 到 3 的数，不过是乱序的，但是实际数组是 [2, -1, 3]，说明数组 pos=1 的位置，原来的数字 1 变成了 -1，因此返回 [1, 1]
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 函数：求出异常数的位置和原来的值
# @param fuzzyArray int整型一维数组 含有异常数的数组
# @return int整型一维数组
#
class Solution:
def fuzzyNumber(self , fuzzyArray ):
flag = 1
pos = 0
sumnumber = 0
index = 0
for item in fuzzyArray:
if item == -1:
if flag == 0:
return [-1, -1]
flag = 0
pos = index
else:
sumnumber += item
index += 1
orisum = (index + 1) * index / 2
orinumber = orisum - sumnumber
return [pos, orinumber]2.3 订单平均等待时间
有一个奶茶店，同一时间只能处理一个订单的制作，现有一个顾客订单列表 orders（二维数组），每个订单都包含两个元素：第一个元素表示订单到达的时间，orders 中订单按到达时间非递减顺序排列；第二个元素表示订单制作需要的时间；当顾客订单到达时，奶茶店一旦空闲就会开始制作该订单的奶茶。每一位顾客都会一直等待奶茶店完成他的订单。奶茶店会严格按照订单顺序处理订单。请你返回订单列表中所有顾客平均需要等待的时间。与标准答案误差在 10-5 范围以内，都视为正确。
- 难度：二星
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 256MB，其他语言512MB
- Special Judge, 64bit IO Format: %lld
- 知识点：模拟
- 输入：[[1,2],[1,3],[4,3]]
- 返回： 4.00000
- 说明： 第一个订单在时刻1到达，奶茶店立即开始处理订单，在时刻3完成，第一位顾客需要等待的时间为 3-1=2；
第二个订单在时刻1到达，奶茶店正在处理第一个订单，第一个订单在时刻3完成并开始处理订单2，第二个订单在时刻6完成，第二位顾客需要等待的时间为 6-1=5；
第三个订单在时刻4到达，奶茶店正在处理第二个订单，第二个订单在时刻6完成并开始处理订单3，第三个订单在时刻9完成，第二位顾客需要等待的时间为 9-4=5；所以平均值为 (2+5+5)/3=4。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param orders int整型二维数组
* @return double浮点型
*/
public double averageWaitingTime (int[][] orders) {
int currentTime=0;
long timeSum=0;
//注意越界
for(int[] a:orders){
if(a[0]>currentTime){
timeSum+=a[1];
currentTime=a[0]+a[1];
}else{
timeSum+=a[1]+currentTime-a[0];
currentTime=a[1]+currentTime;
}
}
return (double)timeSum/orders.length;
}
}三、全身运动 3.1 数字与字母
给你一个仅包含数字和大写字母的字符数组，找到一个最长的子串，使得子串中包含相同个数的数字和字母。子串必须是原数组中连续的一部分。请你返回子串的长度 ，若没有这样的子串返回 0 。
- 难度：三星
- 时间限制：C/C++ 1 秒，其他语言 2 秒
- 空间限制：C/C++ 256 MB，其他语言512 MB
- 64bit IO Format: %lld
- 知识点：字符串处理
- 输入： [A,A,A]
- 返回： 0
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param str char字符型一维数组
* @return int整型
*/
public int findLongestSubarray (char[] str) {
Map map = new HashMap<>();
map.put(0,-1);
int prefixSum = 0;
int longest = 0;
for (int i = 0;
i < str.length;
i++) {
char c = str[i];
prefixSum += Character.isDigit(c)?-1:1;
if (!map.containsKey(prefixSum)){
map.put(prefixSum,i);
}else{
// i-map.get(prefixSum) == i-left+1
if (i-map.get(prefixSum)>longest){
longest = i-map.get(prefixSum);
}
}
}
return longest;
}
} 3.2 木棍拼接
木工小王有一些长短不一的木棍，他想知道这些木棍能否拼接起来组成一个正方形。请写一个程序解决小王的疑惑。
说明：
- 可将单根木棍作为正方形的一条边，也可将多根木棍拼接起来作为正方形的一条边。
- 所有木棍必须使用，且每根木棍只能使用一次。
- 难度：三星
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 32MB，其他语言64MB
- 64bit IO Format: %lld
- 知识点：dfs、剪枝
- 输入： [4，1，1，1]
- 返回： [false]
- 说明： 这四根木棍无法拼接成正方形
#include
#include class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 判断输入不同长度木棍能否拼接成一个正方形
* @param sticks int整型vector 输入木棍长度
* @return bool布尔型
*/
bool canLinkToSquare(vector& sticks) {
if (sticks.size() < 4) {
return false;
}int len = std::accumulate(sticks.begin(), sticks.end(), 0);
if (len == 0 || len % 4 != 0) {
return false;
}int max = *std::max_element(sticks.begin(), sticks.end());
if (max > len / 4) {
return false;
}std::sort(sticks.begin(), sticks.end());
std::vector marks(sticks.size(), false);
return dfs(sticks, marks, len / 4, 0, 0, 0);
}/**
*
* 利用dfs判断输入不同长度木棍能否拼接成一个正方形
* @param sticks int整型vector 输入木棍长度
* @param marksbool vector木棍是否被使用
* @param lenint整型木棍边长
* @param countint整型已拼成的边的个数
* @param lint整型当前边的长度
* @param possize_t整型当前使用的木棍位置
* @return bool布尔型
*/
bool dfs(const vector &sticks, vector &marks, const int len,
int count, int l, size_t pos) {
if (count == 3) return true;
for (int i = pos;
i < sticks.size();
i++) {
if (marks[i]) continue;
if (l + sticks[i] == len) {
marks[i] = true;
if (dfs(sticks, marks, len, count + 1, 0, 0))
return true;
marks[i] = false;
return false;
} else if (l + sticks[i] < len) {
marks[i] = true;
if (dfs(sticks, marks, len, count, l + sticks[i], i + 1))
return true;
marks[i] = false;
if (l == 0)
return false;
while (i + 1 < sticks.size() && sticks[i] == sticks[i + 1])
i++;
}
}return false;
}};
3.3 删除最短子数组使剩余数组有序
输入一个整数数组 array，请你删除一个子数组，使得 array 中剩下的元素是非递增的。子数组可以是原数组中连续的一个子序列，或者为空。请你返回这个最短的子数组的长度。
- 难度：三星
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 256MB，其他语言512MB
- 64bit IO Format: %lld
- 知识点：数组
- 输入： [5,4,3,7,8,2,1]
- 返回值： 2
- 说明： 删除的最短子数组是 [7,8]，长度是 2。剩余的元素为 [5,4,3,2,1]，为非递增。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组 原数组
* @return int整型
*/
public int findLengthOfShortestSubarray (int[] arr) {
int n = arr.length;
int left = 0;
while (left + 1 < n && arr[left] >= arr[left+1]) {
left++;
}
// [0...left]有序
if (left == n - 1) {
return 0;
}
// [right...n-1]有序
int right = n - 1;
while (right > 0 && arr[right - 1] >= arr[right]) {
right--;
}// 完全删除一边[left+1, n-1], 或者[0...right - 1]
int result = Math.min(n - left - 1, right);
// 左边和右边各保留一部分
int i = 0, j = right;
while (i <= left && j <= n - 1) {
if (arr[i] >= arr[j]) {
// [0...i] 和 [j...n-1] 有序, 删除 [i+1...j-1]
result = Math.min(result, j - i - 1);
i++;
} else {
// 小的+1
j++;
}
}
return result;
}
}四、跳跃运动 4.1 任务分配
在离线机器翻译系统中有时会一次接受到多个翻译句子的请求，这些句子的翻译时间可以按照长度预估为 jobs，jobs[i]表示第i个请求句子的翻译时间。系统会启动 k 个线程同时去处理这些翻译任务。为了减少响应时间，我们需要将这些翻译请求分配给不同的线程去处理，每个请求只能分配给一个线程，一个线程的处理时间为分配给它的所有请求句子翻译时间的和。系统的处理时间为所有线程翻译完分配任务的时间，你的目标是优化分配方式使得系统能尽快时间处理完所有请求。请计算出整个系统最短的处理时间。
- 难度：五星
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 32MB，其他语言64MB
- 64bit IO Format: %lld
- 知识点：贪心、线性动态规划
- 输入： [3,2,3],3
- 返回： 3
- 说明： 三个请求分配给三个任务，系统处理时间为3
class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 调度jobs中的任务，分配给k个worker处理，返回系统最短的处理时间
* @param jobs int整型vector 翻译时长数组
* @param k int整型 开启翻译线程数
* @return int整型
*/
int minimumProcessTime(vector& jobs, int k) {
// write code here
int n = jobs.size();
if (n <= k) {
return *max_element(jobs.begin(), jobs.end());
}
vector tot(1 << n, 0);
for (int i = 1;
i < (1 << n);
i++) {
for (int j = 0;
j < n;
j++) {
if ((i & (1 << j)) == 0) continue;
int left = (i - (1 << j));
tot[i] = tot[left] + jobs[j];
break;
}
}vector> dp(k, vector(1 << n, -1));
for (int i = 0;
i < (1 << n);
i++) {
dp[0][i] = tot[i];
}for (int j = 1;
j < k;
j++) {
for (int i = 0;
i < (1 << n);
i++) {
int minv = 1e9;
for (int s = i;
s;
s = (s - 1) & i) { // 枚举 i 的全部子集
int left = i - s;
int val = max(dp[j-1][left], tot[s]);
minv = min(minv, val);
}
dp[j][i] = minv;
}
}
return dp[k-1][(1< 4.2 熟能生巧
卖油翁有两个油壶，它们的容量分别为 a 升和 b 升，顾客想要购买 c 升的油，由于两个油壶都没有刻度，因此卖油翁只能采取如下3种操作：
- 将其中一个油壶装满油
- 将其中一个油壶的油全部倒掉
- 将一个油壶的油倒入另一个油壶中。如果源油壶油的容量大于目标油壶剩余容积，则经过此操作后源油壶保留剩余容量，目标油壶装满油，否则经过此操作后源油壶容量为空，目标油壶容量为之前容量+源油壶容量。
- 难度：五星
- 时间限制：C/C++ 1秒，其他语言2秒
- 空间限制：C/C++ 32MB，其他语言64MB
- 64bit IO Format: %lld
- 知识点：bfs
- 输入： [5，3，6]
- 返回： [-1]
- 说明： [不能经过数次操作使得其中一个油壶中油的容量等于6]
class Solution {
public:
// 两油壶状态
class State {
public:
State(int _a, int _b) : a(_a), b(_b), step(0), op(-1) {};
public:
int a;
// a壶油量
int b;
// a壶油量
int step;
// 经过多少步到达此状态
int op;
// 到达此状态经过的操作编号
};
void update(std::queue &q, std::vector> &visited,
State &next, int step, int op) {
assert(next.a >= 0 && next.b >= 0);
if (!visited[next.a][next.b]) {
next.step = step;
next.op = op;
q.push(next);
visited[next.a][next.b] = true;
}
}/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
* 能否经过数次操作得到目标容量，可以的话请输出需要操作的最小次数，不可以的话请输出-1。
* @param a int整型 a壶容量
* @param b int整型 b壶容量
* @param c int整型 目标容量
* @return int整型
*/
int findShortestStep(int a, int b, int c) {
if (c > a && c > b)
return -1;
if (c == a || c == b)
return 1;
if (a == b)
return -1;
else if (b > a)
std::swap(a, b);
if (c > b && c < a && a % b == 0 && c % b == 0) {
int ua = a / b;
int uc = c / b;
return std::min(ua - uc, uc) * 2;
}if (c == a - b) {
return 2;
}State init(0, 0);
std::vector> visited(a + 1, std::vector(b + 1, false));
visited[0][0] = true;
std::queue q;
q.push(init);
while (!q.empty()) {
State s = q.front();
if (s.a == c || s.b == c) {
return s.step;
}// fill a
State next(0, 0);
if (s.a < a) {
next.a = a;
next.b = s.b;
update(q, visited, next, s.step + 1, 0);
}// fill b
if (s.b < b) {
next.a = s.a;
next.b = b;
update(q, visited, next, s.step + 1, 1);
}// drop a
if (s.a) {
next.a = 0;
next.b = s.b;
update(q, visited, next, s.step + 1, 2);
}// drop b
if (s.b) {
next.a = s.a;
next.b = 0;
update(q, visited, next, s.step + 1, 3);
}// pour a to b
if (s.a && s.b < b) {
if (s.a <= b - s.b) {
next.a = 0;
next.b = s.b + s.a;
} else {
next.a = s.a - (b - s.b);
next.b = b;
}
update(q, visited, next, s.step + 1, 4);
}// pour b to a
if (s.b && a > s.a) {
if (s.b <= a - s.a) {
next.a = s.a + s.b;
next.b = 0;
} else {
next.b = s.b - (a - s.a);
next.a = a;
}
update(q, visited, next, s.step + 1, 5);
}q.pop();
}return -1;
}
};
无论你是功力深厚的代码大神
还是努力成长的勇敢牛牛
有道技术团队都期待你的加入！
欢迎投递网易有道！
（传送门：http://hr.youdao.com/ ）
【offer（拿来吧你！网易有道笔试编程题特辑）】彩蛋： 8月16日（周一）19:00，网易有道 2022 校招技术空宣专场与你面对面，答疑解惑、揭晓有道工作一手秘闻！
推荐阅读
- 考研英语阅读终极解决方案——阅读理解如何巧拿高分
- 拿着旧地图，找不到新大陆
- 生命中最迷人的部分轻拿轻放
- 凡有的，还要多给他，凡没有的，连他现有的也要拿走
- 七夕情浓（高逼格的单身生活，还得拿钱买单）
- 清华教授用了12小时讲完的Python，整整400集，拿走不谢！
- 剑指|剑指 Offer 13. 机器人的运动范围（dfs,bfs)
- 拿起一本书，如何透视它呢（）
- 贵（贱？）
- 加拿大冰壶体验