21號(hào)下午去面的快看漫畫莹汤，前面聊的都挺好，問什么項(xiàng)目啊颠印，機(jī)器學(xué)習(xí)基礎(chǔ)答的還算滿意纲岭，面試官說那做個(gè)題吧，就一路跪了线罕。一共三道題止潮，我大概描述一下。
問題
- 給定一組時(shí)間序列钞楼，格式是(m,n),記錄的會(huì)議開始時(shí)間和結(jié)束時(shí)間喇闸，求要多少個(gè)會(huì)議室才能把所有會(huì)議都安排下。
- 給定一個(gè)亂序數(shù)組询件，找出任意一個(gè)波峰燃乍，波峰的定義是大于與它相鄰的兩個(gè)值，對(duì)于邊界值雳殊，只要大于相鄰的那個(gè)即可橘沥，要求是時(shí)間復(fù)雜度盡可能低。
- 一個(gè)房間里有100盞燈夯秃，每個(gè)燈有一個(gè)開關(guān)座咆，現(xiàn)在有100個(gè)人痢艺，依次進(jìn)入房間，每個(gè)人操作一次自己編號(hào)以及自己編號(hào)整數(shù)倍的燈介陶，求最后所有人操作完還有哪些燈是亮著的堤舒。
思路
- 第一題其實(shí)我當(dāng)時(shí)已近描述的差不多了，只不過當(dāng)時(shí)寫代碼可能有點(diǎn)吃力哺呜。這個(gè)沒找到原題舌缤，一般都是給定了會(huì)議室數(shù)目，求能開幾個(gè)會(huì)某残。在這篇知乎里https://zhuanlan.zhihu.com/p/21510179看到了一些說明国撵，如果我們兩兩比較，看后開始的會(huì)議是否位于先開始的會(huì)議之間玻墅，算法復(fù)雜度
介牙。如果對(duì)會(huì)議室進(jìn)行排序然后再插入，復(fù)雜度可以降低到
澳厢。最快的應(yīng)該是利用bitmap环础，把所有時(shí)間都標(biāo)記在bitmap中，掃描一遍即可剩拢。不是很能理解线得，看了那些給定會(huì)議室數(shù)目的題目后，感覺我自己的思路好像也沒什么問題徐伐，所以也記錄一下吧贯钩。解題的過程是先按照起始時(shí)間排序，如果起始時(shí)間相同呵晨，就按結(jié)束時(shí)間排序魏保，排好以后，從第一個(gè)開始摸屠，去找結(jié)束時(shí)間大于等于當(dāng)前結(jié)束時(shí)間里最小的一個(gè)谓罗，然后合并，直到剩余的里面沒有能合并的季二，再從開始時(shí)間第二個(gè)的開始檩咱，繼續(xù)合并，最后剩下幾個(gè)數(shù)組胯舷，就是需要幾個(gè)會(huì)議室刻蚯。
- 當(dāng)時(shí)我想不到別的辦法，想說要不寫個(gè)二分吧桑嘶，但是我解釋不出來為什么可以二分炊汹，面試官很不滿意。從一篇博客里找到了這樣的描述逃顶，"給定一個(gè)很長的數(shù)組 arr讨便，已知數(shù)組的長度 length 且 length >= 3充甚，已知數(shù)組的第一個(gè)元素不比第二個(gè)元素大，最后一個(gè)元素不比倒數(shù)第二個(gè)元素大霸褒。"我覺得應(yīng)該是要加上這個(gè)條件的伴找。那這樣就跟我想的一樣了，其實(shí)就是利用條件arr[mid]<arr[mid-1],且arr[mid]>arr[mid+1],認(rèn)為這個(gè)已經(jīng)湊成波峰的一半废菱，arr[mid-1]有可能就是一個(gè)波峰技矮，且新出現(xiàn)的數(shù)組arr[0:mid + 1]且滿足最后一個(gè)元素不大于倒數(shù)第二個(gè)元素，所以從[0,mid]繼續(xù)二分殊轴。感覺這個(gè)題還是有點(diǎn)扯衰倦，再悟一悟吧。
-
https://blog.csdn.net/shangzhihaohao/article/details/45011245
這個(gè)博客里有詳細(xì)的說明旁理」⒈遥總結(jié)一下就是所有的燈只有因子個(gè)數(shù)為奇數(shù)個(gè)時(shí)，燈是亮的韧拒，而奇數(shù)個(gè)的只有存在相等因子的才會(huì)出現(xiàn)，比如4=2*2十性，所以4的因子是1叛溢，2，4劲适，所以最后是亮著的楷掉。答案就是100以內(nèi)的所有平方數(shù)。我當(dāng)時(shí)已經(jīng)寫到成對(duì)出現(xiàn)的問題了霞势，沒推出最后的結(jié)果有點(diǎn)遺憾烹植。
