資訊專欄INFORMATION COLUMN
摘要：生日禮物題目來源京東實(shí)習(xí)生招聘原題鏈接可在線提交賽碼網(wǎng)題目描述的生日快到了，這一次，小東決定為送一份特別的生日禮物為其慶生。小東計(jì)劃送一個(gè)生日卡片，并通過特別的包裝讓永遠(yuǎn)難忘。
最近2個(gè)月時(shí)間都比較忙，另外還有些其他的事情，幾乎沒有怎么做題和寫文章了，害怕自己又開始懶散起來了，所以還是督促自己不斷地學(xué)習(xí)和練習(xí)編碼。最近還需要好好學(xué)下python面向?qū)ο蟮囊恍┲R了。
今天我們來分析一個(gè)JD的2016實(shí)習(xí)生招聘題目，該題目在賽碼網(wǎng)上標(biāo)為5星難度，我認(rèn)為這個(gè)題目的難點(diǎn)在于對題目的理解，并且如何在較短的時(shí)間內(nèi)選擇一個(gè)更佳的算法來完成coding。
<題目來源： 京東2016實(shí)習(xí)生招聘 原題鏈接-可在線提交(賽碼網(wǎng))>
題目描述BF的生日快到了，這一次，小東決定為BF送一份特別的生日禮物為其慶生。作為高智商中的佼佼者，BF在國外求學(xué)，因此小東無法與之一起慶生。小東計(jì)劃送一個(gè)生日卡片，并通過特別的包裝讓BF永遠(yuǎn)難忘。
她決定把卡片套裝在一系列的信封A?=?{a1,??a2,??...,??an}中。小東已經(jīng)從商店中購買了很多的信封，她希望能夠用手頭中盡可能多的信封包裝卡片。為防止卡片或信封被損壞，只有長寬較小的信封能夠裝入大些的信封，同尺寸的信封不能套裝，卡片和信封都不能折疊。
小東計(jì)算了郵寄的時(shí)間，發(fā)現(xiàn)她的時(shí)間已經(jīng)不夠了，為此找你幫忙包裝，你能幫她嗎？
首先根據(jù)樣例確認(rèn)題目要求。
這里我再給出一組樣例數(shù)據(jù)并且給出正確輸出來驗(yàn)證是否徹底理解題目要求：
5 1000 998
5002 5005
5003 5004
5003 5002
5002 5001
5002 5002
正確的輸出是
2
4
2
注意到以下3個(gè)問題：
(1)題目要求的卡片必須是裝入能裝入且最小的一個(gè)信封
(2)如果有多個(gè)信封可以選擇，那么選擇先拿到手上的，也就是在樣例中先出現(xiàn)的封信，具體可以參見我給出的那組樣例輸出，最后選擇了2而不是3，就是以為在2，3都可用時(shí)，選擇先出現(xiàn)的，也就是第2個(gè)封信
(3)信封不能旋轉(zhuǎn)，但是這點(diǎn)似乎題目中并沒有提及到
現(xiàn)在我們來討論如何解決這個(gè)問題
由于信封要被一層一層的封裝，并且要用到盡可能多的信封。得到的解如果是r[1], r[2], ... r[n]，那么滿足r[i] < r[i + 1] ("<"表示左側(cè)可以被右側(cè)裝下)，這有什么用呢？這提示我們需要對其進(jìn)行一個(gè)整理，得到一個(gè)整理后的序列滿足：
envelop[1], envelop[2], ... envelop[i], ... envelop[n]
envelop[j] !> envelop[i] (i > j) 其中("!>" 表示左側(cè)能不右側(cè)裝下信封，>表示左側(cè)可以裝下右側(cè)信封)
這樣的話，我們可以考慮使用面積進(jìn)行排序。因此面積大的不一定的下面積小的信封，但是面積小的一定裝不下面積大的信封 。
在得到這樣的一個(gè)具體拓?fù)潢P(guān)系(關(guān)于拓?fù)渑判?結(jié)構(gòu)，可以參考相關(guān)資料)序列之后，如果你對動(dòng)態(tài)規(guī)劃(DP)有所了解，似乎首先會想到最長不下降子序列(LIS)問題，因?yàn)樵诘玫酵負(fù)湫蛄泻?，我們可以按這個(gè)序列來劃分階段，來進(jìn)行動(dòng)態(tài)規(guī)劃。
設(shè)f[i]表示，如果選擇i個(gè)信封來裝可以最多使用的信封個(gè)數(shù)，同時(shí)設(shè)g[i]記錄i的前一個(gè)使用的信封的下標(biāo)。由于最后我們要輸出信封的順序編號，別忘記了帶上原來的順序編號，在拓?fù)渑判虻臅r(shí)候，我們可以在遇到多個(gè)入度為0的點(diǎn)時(shí)，優(yōu)先選擇編號較小的點(diǎn)加入拓?fù)湫蛄?/strong>，方便后續(xù)DP時(shí)的處理。
f[i] = max(f[j]) + 1, i > j and f[j] > 0 and envelop[i] > envelop[j]
g[i] = j (f[J] = f[i], j = min{J})
特別注意的是，由于有多個(gè)信封可用時(shí)需要選擇編號較小的，計(jì)算g[i]時(shí)，當(dāng)有多個(gè)f[j]都滿足條件時(shí)，選擇最小的那個(gè)j。
最后的答案是max(f[i])，最后一個(gè)選擇是信封是i最小的那個(gè)。然后我們根據(jù)g[i]可以倒推出所有選擇信封。
至此，問題得到了解決。
但是，我們再咨詢觀察得到的拓?fù)湫蛄邪l(fā)現(xiàn)，當(dāng)確定最開始的信封之后，如果envelop[i] < envelop[j]，并且j是第一個(gè)滿足這個(gè)條件的信封，顯然我們會選擇j，因?yàn)楹竺娴男欧庵淮嬖趦煞N情況，不能裝下j，但是都比較j晚出現(xiàn)，不會選擇。如果能把j裝下，且第一個(gè)出現(xiàn)，我們依然會選擇。反之，如果不按這個(gè)策略選擇，顯然不可能得到更好的解。
簡單反證如下(如果用數(shù)學(xué)歸納法也類似):
現(xiàn)在有序列envelop[] 其中envelop[0]是最小能裝入卡片的信封，envelop[i]是第一個(gè)可以裝下envelop[0]的信封，假設(shè)選擇envelopj得到更優(yōu)的解，那么存在兩種情況：
1) envelop[j] > envelop[i]，這時(shí)加入envelop[i]顯然可以使用多一個(gè)信封，與假設(shè)矛盾
2) envelop[j] !> envelop[j]，選擇更早出現(xiàn)的i才符合題目要求，與假設(shè)矛盾
一些后話：
1.這個(gè)題目不一定每個(gè)人都會立刻想到使用類似LIS的算法，比如不會LIS，又比如一眼就能看出問題本質(zhì)，使用更佳的解法。更多時(shí)候我們可能是一步一步進(jìn)行算法的演進(jìn)，然后再不斷的進(jìn)行更好的選擇和優(yōu)化。問題可以有多種正確解法，但是并不是每種正確解法都是最優(yōu)的。
2.關(guān)于拓?fù)渑判虻姆绞接卸喾N，我這里并沒有使用基于圖的方法，因?yàn)樾枰▓D(O(n^2))在時(shí)間上相對我直接使用O(n^2)的插入排序的方法并沒有優(yōu)勢。
具體實(shí)現(xiàn)的時(shí)候，我每次在原來的信封序列中取一個(gè)，放在已經(jīng)得到的拓?fù)湫蛄蟹庑判蛄械牡谝粋€(gè)位置，然后和后一個(gè)比較，看是否需要交換，如果交換后，繼續(xù)向后比較，不需要交換則比較結(jié)束，繼續(xù)這個(gè)過程知道原來的信封已經(jīng)取完
envelop a和envelop b交換的條件是：
envelop a > envelop b
or
envelop a !> envelop b and envelop a !< envelop b and Pa > Pb
其中Pa > Pb表示a在原給出的信封序列中位置更靠后
3.最后，在參考其他答案的時(shí)候，我也發(fā)現(xiàn)了一個(gè)O(nlogn)的算法，算法思想和我們提到的大致相同，他首選是按面積進(jìn)行一個(gè)排序，然后僅通過O(n)的一次掃描就得到最后的答案，思想比較巧妙。有興趣可以在題目鏈接的“正確答案”中查看。
4.此外，關(guān)于LIS算法以及優(yōu)化可以參考以下文章:
http://blog.csdn.net/hulifang...
http://blog.csdn.net/wall_f/a...
import sys
const_w = 0
const_h = 1
const_p = 2
def is_swap(a, b):
a_contain_b = True if a[const_w] > b[const_w] and a[const_h] > b[const_h] else False
b_contain_a = True if a[const_w] < b[const_w] and a[const_h] < b[const_h] else False
if a_contain_b or (not a_contain_b and not b_contain_a and a[const_p] > b[const_p]):
return True
return False
def sort(envelops):
s_envelops = []
for envelop in envelops:
s_envelops.insert(0, envelop)
for i in range(len(s_envelops) - 1):
if is_swap(s_envelops[i], s_envelops[i + 1]):
temp = s_envelops[i]
s_envelops[i] = s_envelops[i + 1]
s_envelops[i + 1] = temp
else:
break
return s_envelops
def main():
envelops = []
while True:
line = map(int, sys.stdin.readline().strip().split())
if len(line) < 3:
return
n, w, h = line[0], line[1], line[2]
for i in range(n):
line = map(int, sys.stdin.readline().strip().split())
envelops.append((line[0], line[1], i + 1))
s_envelops = sort(envelops)
card_in = -1
min_area = sys.maxint
for i, s_envelop in enumerate(s_envelops):
if s_envelop[const_w] > w and s_envelop[const_h] > h and s_envelop[const_w] * s_envelop[const_h] < min_area:
min_area = s_envelop[const_w] * s_envelop[const_h]
card_in = i
if card_in < 0:
print 0
else:
cnt = 1
results = [s_envelops[card_in][const_p]]
last = s_envelops[card_in]
for i in range(card_in + 1, n):
if s_envelops[i][const_w] > last[const_w] and s_envelops[i][const_h] > last[const_h]:
cnt += 1
results.append(s_envelops[i][const_p])
last = s_envelops[i]
print cnt
for result in results:
print result,
print
envelops[:] = []
# for s_envelop in s_envelops:
# print s_envelop[const_w], s_envelop[const_h], s_envelop[const_p]
if __name__ == "__main__":
main()
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/38645.html
摘要：買糖果題目來源京東實(shí)習(xí)生招聘原題鏈接可在線提交賽碼網(wǎng)問題描述某糖果公司專門生產(chǎn)兒童糖果，它最受兒童歡迎的糖果有兩個(gè)序列，均采用盒式包裝。小東希望你能幫她解決這一問題。 最近比較忙，又有一段時(shí)間沒寫題目了，終于在前幾天把賽碼網(wǎng)上，JD的2016秋招和2017實(shí)習(xí)生招聘剩下的4星難度題目做了，至此所有4星難度題目都解決了，5星難度題目還剩下一個(gè)應(yīng)該是計(jì)算幾何學(xué)的題目，因?yàn)檫@塊我不熟悉，后面...
摘要：拿到秋招的同學(xué)，如確定入職需與用人單位簽署三方協(xié)議，以保證雙方的利益不受損失。當(dāng)然每個(gè)崗位所要求的側(cè)重點(diǎn)不同，但卻百變不離其宗。方法論要想達(dá)成某個(gè)目標(biāo)都有其特定的方法論，學(xué)習(xí)技術(shù)也不例外，掌握適當(dāng)?shù)膶W(xué)習(xí)方法才能事半功倍。 寫在前面的話 筆者從17年的2月份開始準(zhǔn)備春招，其中遇到不少坑，也意識到自己走過的彎路。故寫了這篇文章總結(jié)一番，本文適合主動(dòng)學(xué)習(xí)的，對自己要學(xué)的課程不明確的，對面試有...
摘要：拿到秋招的同學(xué)，如確定入職需與用人單位簽署三方協(xié)議，以保證雙方的利益不受損失。當(dāng)然每個(gè)崗位所要求的側(cè)重點(diǎn)不同，但卻百變不離其宗。方法論要想達(dá)成某個(gè)目標(biāo)都有其特定的方法論，學(xué)習(xí)技術(shù)也不例外，掌握適當(dāng)?shù)膶W(xué)習(xí)方法才能事半功倍。 寫在前面的話 筆者從17年的2月份開始準(zhǔn)備春招，其中遇到不少坑，也意識到自己走過的彎路。故寫了這篇文章總結(jié)一番，本文適合主動(dòng)學(xué)習(xí)的，對自己要學(xué)的課程不明確的，對面試有...
摘要：正如我標(biāo)題所說，簡歷被拒?？戳宋液啔v之后說頭條競爭激烈，我背景不夠，點(diǎn)到為止。。三準(zhǔn)備面試其實(shí)從三月份投遞簡歷開始準(zhǔn)備面試到四月份收，也不過個(gè)月的時(shí)間，但這都是建立在我過去一年的積累啊。 本文是 無精瘋 同學(xué)投稿的面試經(jīng)歷 關(guān)注微信公眾號：進(jìn)擊的java程序員K，即可獲取最新BAT面試資料一份 在此感謝 無精瘋 同學(xué)的分享 目錄： 印象中的頭條 面試背景 準(zhǔn)備面試 ...
閱讀 1036·2022-07-19 10:19
閱讀 1806·2021-09-02 15:15
閱讀 1023·2019-08-30 15:53
閱讀 2668·2019-08-30 13:45
閱讀 2664·2019-08-26 13:57
閱讀 1998·2019-08-26 12:13
閱讀 1016·2019-08-26 10:55
閱讀 558·2019-08-26 10:46
