聯繫我們：有道技術團隊助手：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 校招技術空宣專場與你面對面，答疑解惑、揭曉有道工作一手秘聞！
