難度：★★★
我知道網(wǎng)易互動娛樂實習生筆試題目的時候厉斟，實習生筆試已經(jīng)結(jié)束了。同學說都沒做出來强衡，好奇之下嘗試做了一下擦秽，感覺確實不容易，但是窮舉法應(yīng)該可以過一些測試用例的漩勤。
題目地址戳這里感挥。
題目1 ：電子數(shù)字
這個問題應(yīng)該是這三題里最簡單的一道吧，要求求出可能的數(shù)列組合的個數(shù)越败。對于這題触幼，我把問題轉(zhuǎn)為兩個步驟：
- 從輸入列表中提取每個電子數(shù)字所占位置代表的潛在候選數(shù)字；
- 遍歷各個數(shù)位上的候選數(shù)字究飞，生成候選數(shù)字來比較置谦，最終得出組合的個數(shù)。
生成候選數(shù)字的步驟我直接使用 HashSet 來做數(shù)列交集亿傅，在輸入的時候就生成各個數(shù)位上的候選數(shù)字媒峡。如果說 HashSet 的 contains 方法是 O(1) 的，那么這步的復雜度應(yīng)該是 O(k)葵擎，總體來說就是 O(9k)谅阿。而對于第二步，遍歷……遍歷應(yīng)該是可行的酬滤，畢竟題目規(guī)定了最多只是 5 位數(shù)签餐，對于 1Ghz 的電腦來說，在 1s 內(nèi)完全遍歷 10^5 個數(shù)字組合也不難盯串。
題目2 ：源代碼編譯
源碼編譯這個題實際上我在做阿里移動推薦算法比賽的時候做過——整理文件的依賴關(guān)系并最終生成文件的編譯順序表氯檐。當時處理的是 SQL 文件依賴，因為算法比賽的時候各個人自己獨立地創(chuàng)建表嘴脾，而最終需要一份可以提交的 SQL 文件男摧。當時沒有考慮算法復雜度蔬墩，這次考慮了一下，實際上就是一種帶有特定依賴的排序耗拓。稍微修改一下快排的比較函數(shù)拇颅，應(yīng)該很輕易就能解決這道題∏茄可惜測評時間已過樟插，無法驗證了。
題目3 ：畫線
這道題有很好的應(yīng)用背景——以前做游戲的時候也想過竿刁，怎樣可以合并某些操作從而優(yōu)化整個執(zhí)行流程黄锤。不過以前也就想想，沒實際執(zhí)行過食拜。
這道題的考慮也比較簡單鸵熟，每次獲得輸入后，求出線段的斜率 k 负甸，找出之前已經(jīng)輸入的斜率為 k 的線段集合流强，找出該直線是否可以合并到已經(jīng)輸入的線段集合中。這里可以優(yōu)化的地方估計是建立斜率 k 的線段集合的索引呻待，使得新加入的線段可以快速地判斷能否合并打月，這樣，時間復雜度就可以近似線性了蚕捉。不過奏篙，暴力解的話，應(yīng)該就是 O(n^2) 迫淹。
我想秘通，對于玩 ACM-ICPC 的同學來說，應(yīng)該是小 case 吧千绪，努力學習ing充易。
