10道筆試編程題

據(jù)說全做對的同學

都順利地拿到了 offer！

同學們，請開始你們的 ~~bug~~

啊不

表演吧！

文章來源：網(wǎng)易有道，原文鏈接：http://techblog.youdao.com/?p=2527&utm_source=tuicool&utm_medium=referral

一、熱身運動

1.1找到重復數(shù)字

給定一個包含?n+1?個整數(shù)的數(shù)組 nums ，其數(shù)字都在 1 到 n 之間（包括 1 和 n），可知至少存在一個重復的整數(shù)。假設(shè) nums 只有一個重復的整數(shù) ，找出這個?重復的數(shù)?。

難度：一星

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 256MB，其他語言512MB

64bit IO Format: %lld

樣例：?輸入?：[1,3,4,2,2]?返回?：2

1.2 ** **三角形面積

輸入三個點的坐標，輸出三個點組成的?三角形的面積?。（結(jié)果保留三位小數(shù)點并四舍五入）\

難度：一星

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 256MB，其他語言512MB

Special Judge, 64bit IO Format: %lld

知識點：計算幾何

樣例：

輸入?：12，-70，95，91，-72，35

輸出?：11119.500

二、伸展運動

2.1 分解自然數(shù)

一個自然數(shù)可以將它分解成若干個自然數(shù)相乘?，F(xiàn)在給你一個指定的自然數(shù)n，請求出每種分解自然數(shù)之和的最小值是多少。

難度：二星

時間限制：C/C++ 5秒，其他語言10秒

空間限制：C/C++ 32MB，其他語言64M

64bit IO Format: %lld

樣例：

輸入：6?返回：5?說明：6分解為2 * 3，那么最小的和為2+3=5

2.2 恢復異常數(shù)

有一個一維整數(shù)數(shù)組?fuzzyArray，里面存儲的是從 1 到 n 這 n 個數(shù)，不過是亂序存儲；這時有一個位置的數(shù)字變成了 -1。請用最優(yōu)的空間復雜度和時間復雜度求出這個異常數(shù)的位置和原來的值。\

難度：二星

時間限制：C/C++ 5秒，其他語言10秒

空間限制：C/C++ 256 MB，其他語言512 MB

64bit IO Format: %lld

知識點：測試開發(fā)、數(shù)組

樣例：

輸入?：?[2, -1, 3]

返回：?[1,1]

說明：?異常數(shù)組原本應(yīng)該是存儲從 1 到 3 的數(shù)，不過是亂序的，但是實際數(shù)組是 [2, -1, 3]，說明數(shù)組 pos=1 的位置，原來的數(shù)字 1 變成了 -1，因此返回 [1, 1]

2.3 訂單平均等待時間

有一個奶茶店，同一時間只能處理一個訂單的制作，現(xiàn)有一個顧客訂單列表 orders（二維數(shù)組），每個訂單都包含兩個元素：第一個元素表示訂單到達的時間，orders 中訂單按到達時間非遞減順序排列；第二個元素表示訂單制作需要的時間；當顧客訂單到達時，奶茶店一旦空閑就會開始制作該訂單的奶茶。每一位顧客都會一直等待奶茶店完成他的訂單。奶茶店會嚴格按照訂單順序處理訂單。請你返回訂單列表中所有顧客平均需要等待的時間。與標準答案誤差在 10-5 范圍以內(nèi)，都視為正確。

難度：二星

時間限制：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。

三、全身運動

3.1 數(shù)字與字母

給你一個僅包含數(shù)字和大寫字母的字符數(shù)組，找到一個最長的子串，使得子串中包含相同個數(shù)的數(shù)字和字母。子串必須是原數(shù)組中連續(xù)的一部分。請你返回子串的長度?，若沒有這樣的子串返回 0?。

難度：三星

時間限制：C/C++ 1 秒，其他語言 2 秒

空間限制：C/C++ 256 MB，其他語言512 MB

64bit IO Format: %lld

知識點：字符串處理

樣例：

輸入：?[A,A,A]

返回：?0

3.2 木棍拼接

木工小王有一些長短不一的木棍，他想知道這些木棍能否拼接起來組成一個正方形。請寫一個程序解決小王的疑惑。

說明： 1. 可將單根木棍作為正方形的一條邊，也可將多根木棍拼接起來作為正方形的一條邊。 2. 所有木棍必須使用，且每根木棍只能使用一次。

難度：三星

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 32MB，其他語言64MB

64bit IO Format: %lld

知識點：dfs、剪枝

樣例：

輸入：?[4，1，1，1]

返回：?[false]

說明：?這四根木棍無法拼接成正方形

3.3?刪除最短子數(shù)組使剩余數(shù)組有序

輸入一個整數(shù)數(shù)組 array，請你刪除一個子數(shù)組，使得 array 中剩下的元素是非遞增的。子數(shù)組可以是原數(shù)組中連續(xù)的一個子序列，或者為空。請你返回這個最短的子數(shù)組的長度。

難度：三星

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 256MB，其他語言512MB

64bit IO Format: %lld

知識點：數(shù)組

樣例：

輸入：?[5,4,3,7,8,2,1]

返回值：?2

說明：?刪除的最短子數(shù)組是 [7,8]，長度是 2。剩余的元素為 [5,4,3,2,1]，為非遞增。

四、跳躍運動

4.1 任務(wù)分配

在離線機器翻譯系統(tǒng)中有時會一次接受到多個翻譯句子的請求，這些句子的翻譯時間可以按照長度預估為jobs，jobs[i]表示第i個請求句子的翻譯時間。系統(tǒng)會啟動 k 個線程同時去處理這些翻譯任務(wù)。為了減少響應(yīng)時間，我們需要將這些翻譯請求分配給不同的線程去處理，每個請求只能分配給一個線程，一個線程的處理時間為分配給它的所有請求句子翻譯時間的和。系統(tǒng)的處理時間為所有線程翻譯完分配任務(wù)的時間，你的目標是優(yōu)化分配方式使得系統(tǒng)能盡快時間處理完所有請求。請計算出整個系統(tǒng)最短的處理時間。

難度：五星

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 32MB，其他語言64MB

64bit IO Format: %lld

知識點：貪心、線性動態(tài)規(guī)劃

樣例：

輸入：?[3,2,3],3

返回：?3

說明：?三個請求分配給三個任務(wù)，系統(tǒng)處理時間為3

4.2 熟能生巧

賣油翁有兩個油壺，它們的容量分別為 a 升和 b 升，顧客想要購買 c 升的油，由于兩個油壺都沒有刻度，因此賣油翁只能采取如下3種操作：

將其中一個油壺裝滿油

將其中一個油壺的油全部倒掉

將一個油壺的油倒入另一個油壺中。如果源油壺油的容量大于目標油壺剩余容積，則經(jīng)過此操作后源油壺保留剩余容量，目標油壺裝滿油，否則經(jīng)過此操作后源油壺容量為空，目標油壺容量為之前容量+源油壺容量。

賣油翁想知道能否經(jīng)過若干次上述操作后使得其中一個油壺中油的容量等于顧客的購買容量c升。請寫一個程序來解決賣油翁的問題，如果可經(jīng)過數(shù)次操作得到目標容量則輸出需要操作的最少次數(shù)，否則輸出?-1。

難度：五星

時間限制：C/C++ 1秒，其他語言2秒

空間限制：C/C++ 32MB，其他語言64MB

64bit IO Format: %lld

知識點：bfs

樣例：

輸入：?[5，3，6]

返回：?[-1]

說明：?[不能經(jīng)過數(shù)次操作使得其中一個油壺中油的容量等于6]

無論你是功力深厚的代碼大神

還是努力成長的勇敢牛牛

都期待你的加入！

對于準備學習編程的小伙伴，如果你想更好的提升你的編程核心能力（內(nèi)功）不妨從現(xiàn)在開始！

微信公眾號：C語言編程學習基地

整理分享（多年學習的源碼、項目實戰(zhàn)視頻、項目筆記，基礎(chǔ)入門教程）

歡迎轉(zhuǎn)行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！