開篇記錄面試第27天—貪心算法

21號(hào)下午去面的快看漫畫莹汤,前面聊的都挺好,問什么項(xiàng)目啊颠印,機(jī)器學(xué)習(xí)基礎(chǔ)答的還算滿意纲岭,面試官說那做個(gè)題吧,就一路跪了线罕。一共三道題止潮,我大概描述一下。

問題

  1. 給定一組時(shí)間序列钞楼,格式是(m,n),記錄的會(huì)議開始時(shí)間和結(jié)束時(shí)間喇闸,求要多少個(gè)會(huì)議室才能把所有會(huì)議都安排下。
  2. 給定一個(gè)亂序數(shù)組询件,找出任意一個(gè)波峰燃乍,波峰的定義是大于與它相鄰的兩個(gè)值,對(duì)于邊界值雳殊,只要大于相鄰的那個(gè)即可橘沥,要求是時(shí)間復(fù)雜度盡可能低。
  3. 一個(gè)房間里有100盞燈夯秃,每個(gè)燈有一個(gè)開關(guān)座咆,現(xiàn)在有100個(gè)人痢艺,依次進(jìn)入房間,每個(gè)人操作一次自己編號(hào)以及自己編號(hào)整數(shù)倍的燈介陶,求最后所有人操作完還有哪些燈是亮著的堤舒。

思路

  1. 第一題其實(shí)我當(dāng)時(shí)已近描述的差不多了,只不過當(dāng)時(shí)寫代碼可能有點(diǎn)吃力哺呜。這個(gè)沒找到原題舌缤,一般都是給定了會(huì)議室數(shù)目,求能開幾個(gè)會(huì)某残。在這篇知乎里https://zhuanlan.zhihu.com/p/21510179看到了一些說明国撵,如果我們兩兩比較,看后開始的會(huì)議是否位于先開始的會(huì)議之間玻墅,算法復(fù)雜度O(n^2)介牙。如果對(duì)會(huì)議室進(jìn)行排序然后再插入,復(fù)雜度可以降低到O(N*logN)澳厢。最快的應(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ì)議室刻蚯。
  2. 當(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)扯衰倦,再悟一悟吧。
  3. 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)遺憾烹植。
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
  • 序言:七十年代末,一起剝皮案震驚了整個(gè)濱河市愕贡,隨后出現(xiàn)的幾起案子草雕,更是在濱河造成了極大的恐慌,老刑警劉巖固以,帶你破解...
    沈念sama閱讀 222,729評(píng)論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件墩虹,死亡現(xiàn)場(chǎng)離奇詭異,居然都是意外死亡憨琳,警方通過查閱死者的電腦和手機(jī)诫钓,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,226評(píng)論 3 399
  • 文/潘曉璐 我一進(jìn)店門,熙熙樓的掌柜王于貴愁眉苦臉地迎上來篙螟,“玉大人菌湃,你說我怎么就攤上這事”槁裕” “怎么了惧所?”我有些...
    開封第一講書人閱讀 169,461評(píng)論 0 362
  • 文/不壞的土叔 我叫張陵骤坐,是天一觀的道長。 經(jīng)常有香客問我纯路,道長或油,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 60,135評(píng)論 1 300
  • 正文 為了忘掉前任驰唬,我火速辦了婚禮顶岸,結(jié)果婚禮上,老公的妹妹穿的比我還像新娘叫编。我一直安慰自己辖佣,他們只是感情好,可當(dāng)我...
    茶點(diǎn)故事閱讀 69,130評(píng)論 6 398
  • 文/花漫 我一把揭開白布搓逾。 她就那樣靜靜地躺著卷谈,像睡著了一般。 火紅的嫁衣襯著肌膚如雪霞篡。 梳的紋絲不亂的頭發(fā)上世蔗,一...
    開封第一講書人閱讀 52,736評(píng)論 1 312
  • 那天,我揣著相機(jī)與錄音朗兵,去河邊找鬼污淋。 笑死,一個(gè)胖子當(dāng)著我的面吹牛余掖,可吹牛的內(nèi)容都是我干的寸爆。 我是一名探鬼主播,決...
    沈念sama閱讀 41,179評(píng)論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼盐欺,長吁一口氣:“原來是場(chǎng)噩夢(mèng)啊……” “哼赁豆!你這毒婦竟也來了?” 一聲冷哼從身側(cè)響起冗美,我...
    開封第一講書人閱讀 40,124評(píng)論 0 277
  • 序言:老撾萬榮一對(duì)情侶失蹤魔种,失蹤者是張志新(化名)和其女友劉穎,沒想到半個(gè)月后墩衙,有當(dāng)?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體务嫡,經(jīng)...
    沈念sama閱讀 46,657評(píng)論 1 320
  • 正文 獨(dú)居荒郊野嶺守林人離奇死亡,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內(nèi)容為張勛視角 年9月15日...
    茶點(diǎn)故事閱讀 38,723評(píng)論 3 342
  • 正文 我和宋清朗相戀三年漆改,在試婚紗的時(shí)候發(fā)現(xiàn)自己被綠了心铃。 大學(xué)時(shí)的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片。...
    茶點(diǎn)故事閱讀 40,872評(píng)論 1 353
  • 序言:一個(gè)原本活蹦亂跳的男人離奇死亡挫剑,死狀恐怖去扣,靈堂內(nèi)的尸體忽然破棺而出,到底是詐尸還是另有隱情,我是刑警寧澤愉棱,帶...
    沈念sama閱讀 36,533評(píng)論 5 351
  • 正文 年R本政府宣布唆铐,位于F島的核電站,受9級(jí)特大地震影響奔滑,放射性物質(zhì)發(fā)生泄漏艾岂。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點(diǎn)故事閱讀 42,213評(píng)論 3 336
  • 文/蒙蒙 一朋其、第九天 我趴在偏房一處隱蔽的房頂上張望王浴。 院中可真熱鬧,春花似錦梅猿、人聲如沸氓辣。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,700評(píng)論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽钞啸。三九已至,卻和暖如春喇潘,著一層夾襖步出監(jiān)牢的瞬間体斩,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,819評(píng)論 1 274
  • 我被黑心中介騙來泰國打工颖低, 沒想到剛下飛機(jī)就差點(diǎn)兒被人妖公主榨干…… 1. 我叫王不留硕勿,地道東北人。 一個(gè)月前我還...
    沈念sama閱讀 49,304評(píng)論 3 379
  • 正文 我出身青樓枫甲,卻偏偏與公主長得像,于是被迫代替她去往敵國和親扼褪。 傳聞我的和親對(duì)象是個(gè)殘疾皇子想幻,可洞房花燭夜當(dāng)晚...
    茶點(diǎn)故事閱讀 45,876評(píng)論 2 361

推薦閱讀更多精彩內(nèi)容