去哪兒筆試技術(shù)崗18編程

1、 題目1、日本旅行題目描述：楚喬、宇文玥和燕洵在日本旅行，經(jīng)過(guò)了幾天的游玩之后，錢(qián)包里出現(xiàn)了大量硬幣，楚喬決定用錢(qián)包里的硬幣為宇文玥和燕洵在自動(dòng)機(jī)買(mǎi)水。楚喬的錢(qián)包里有 1 元、5 元、10元、50 元、100 元和 500 元硬幣各 C1,C5,C10,C50,C100,C500 枚。現(xiàn)在要用這些硬幣來(lái)到自動(dòng)機(jī)買(mǎi)價(jià)格為 A 的飲料，假設(shè)自動(dòng)也不能少，最少需要多少枚硬幣？ 機(jī)所需的硬幣金額必須是剛剛好，不能多 限制條件0= C1,C5,C10,C50,C100,C500=10000000000=A=1000000000依次輸入 C1,C5,C10,C50,C100,C500 和 A，以空格分隔，

2、輸出最少所需硬幣數(shù)，如果該金額不能由所給硬幣湊出，則返回 NOWAY輸入依次輸入 C1,C5,C10,C50,C100,C500 和 A，以空格分隔輸出輸出最少所需硬幣數(shù)，如果該金額不能由所給硬幣湊出，則返回 NOWAY樣例輸入3 2 1 3 0 2 620樣例輸出62、帶權(quán)的 DAG 節(jié)點(diǎn)排序題目描述：DAG 即 Directed Acyclic Graph, 有向無(wú)環(huán)圖. 用 DAG 可以描述一些有依賴關(guān)系的任務(wù) 組, 而這些任務(wù)還有另外一個(gè)屬性, 即都有一個(gè)權(quán)重, 標(biāo)示這個(gè)任務(wù)的重要性.刺猬實(shí)習(xí) 我們需要你來(lái)實(shí)現(xiàn)一個(gè)算法, 對(duì) DAG 里面的節(jié)點(diǎn)進(jìn)行排序, 保證排序不違背 DAG 的依賴

3、關(guān)系, 即一個(gè)任務(wù) A 如果排在任務(wù) B 前面, 那么在 DAG 中不能存在由 B外一個(gè)要求就是, 讓權(quán)重大的任務(wù)盡量?jī)?yōu)先執(zhí)行.到 A 的路徑.另輸入在第一行給定 DAG 的節(jié)點(diǎn)數(shù) n 和邊數(shù) e.后面 n 行, 每一行是 節(jié)點(diǎn)的 標(biāo)號(hào)和權(quán)重, seq weight.最后 e 行, 每一行是對(duì)于邊的描述, s t.輸出排序好的節(jié)點(diǎn)標(biāo)號(hào),在一行內(nèi)輸出,空格隔開(kāi).樣例輸入4 41 22 33 54 41 21 32 43 4樣例輸出1 3 2 43、模擬 LRU Cache 題目描述：刺猬實(shí)習(xí) LRU 全稱是 Least Recently Used, LRU Cache 的核心設(shè)計(jì)思想是, 如果一

4、個(gè)數(shù)據(jù)在最近一段時(shí)間沒(méi)有被訪問(wèn)到，那么在將來(lái)它被訪問(wèn)的可能性也很小。 在 cache 大小固定的情況 下, 如果 cache 滿了, 會(huì)把最近最久沒(méi)有訪問(wèn)的元素刪掉.實(shí)現(xiàn)程序禁用各種語(yǔ)言基礎(chǔ)庫(kù)中的 LinkedHashMap.輸入在第一行給定 cache 的大小 m, 對(duì) cache 執(zhí)行讀寫(xiě)操作的次數(shù) n.從第二行開(kāi)始, 有 n 行操作命令.操作有兩種情況, put 和 get.put 命令格式是 put key value, 表示向 cache 寫(xiě)入數(shù)據(jù).get 命令格式是 get key, 標(biāo)示從 cache 讀取數(shù)據(jù).輸出對(duì)于 n 行命令中的每一行 get 命令.如果對(duì)于數(shù)據(jù)存在, 就把 value 在單獨(dú)一行打印出來(lái).如果不存在,就在單獨(dú)一行打印 null.樣例輸入3 5put a bpu