分割咱们 ： 有道技术团队助手 ：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 <iostream>
#include <cmath>
#include <cstdio>
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<Integer,Integer> 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 <algorithm>
#include <numeric>
class Solution {
public:
/**
* 代码中的类名、办法名、参数名曾经指定，请勿批改，间接返回办法规定的值即可
*
* 判断输出不同长度木棍是否拼接成一个正方形
* @param sticks int 整型 vector 输出木棍长度
* @return bool 布尔型
*/
bool canLinkToSquare(vector<int>& 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<bool> marks(sticks.size(), false);
return dfs(sticks, marks, len / 4, 0, 0, 0);
}
/**
*
* 利用 dfs 判断输出不同长度木棍是否拼接成一个正方形
* @param sticks int 整型 vector 输出木棍长度
* @param marks bool vector 木棍是否被应用
* @param len int 整型 木棍边长
* @param count int 整型 已拼成的边的个数
* @param l int 整型 以后边的长度
* @param pos size_t 整型 以后应用的木棍地位
* @return bool 布尔型
*/
bool dfs(const vector<int> &sticks, vector<bool> &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<int>& jobs, int k) {
// write code here
int n = jobs.size();
if (n <= k) {return *max_element(jobs.begin(), jobs.end());
}
vector<int> 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<vector<int>> dp(k, vector<int>(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<<n)-1];
}
};4.2 游刃有余
卖油翁有两个油壶，它们的容量别离为 a 升和 b 升，顾客想要购买 c 升的油，因为两个油壶 都没有刻度，因而卖油翁只能采取如下 3 种操作：
- 将其中一个油壶装满油
- 将其中一个油壶的油全副倒掉
- 将一个油壶的油倒入另一个油壶中。如果源油壶油的容量大于指标油壶残余容积，则通过此操作后源油壶保留残余容量，指标油壶装满油，否则通过此操作后源油壶容量为空，指标油壶容量为之前容量 + 源油壶容量。
卖油翁想晓得是否通过若干次上述操作后使得其中一个油壶中油的容量等于顾客的购买容量 c 升。请写一个程序来解决卖油翁的问题，如果可通过数次操作失去指标容量则输入须要操作的 起码次数，否则输入 -1。
- 难度：五星
- 工夫限度：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<State> &q, std::vector<std::vector<bool>> &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<std::vector<bool>> visited(a + 1, std::vector<bool>(b + 1, false));
visited[0][0] = true;
std::queue<State> 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/）
彩蛋： 8 月 16 日（周一）19:00，网易有道 2022 校招技术空宣专场与你面对面，答疑解惑、揭晓有道工作一手秘闻！