分割咱们：有道技术团队助手：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 校招技术空宣专场与你面对面，答疑解惑、揭晓有道工作一手秘闻！