面試前有用的突擊

今日找人突擊面試經(jīng)驗和編程思路卸察,雖然這些不能速成,但也是頗受啟發(fā)铅祸,得到了幾點告誡:

1.面試過程要循序漸進坑质,先從最簡單的解決思路開始,逐漸優(yōu)化到次優(yōu)和最優(yōu)

2.準備面試临梗,各種類型的題目都接觸一點涡扼,txt寫代碼和想思路的時間各占一半

3.當我們拿到題目的時候,首先要想怎么用邏輯思維解決這個題目夜焦,然后思考編程怎么實現(xiàn)壳澳,不要直接用編程思維去想題目,這樣非常容易卡死茫经。

下面描述幾個算法題:

1.微軟的2個題目其1:

https://hihocoder.com/problemset/problem/1499

難度L2

對于任意一個機器人而言巷波,有三種狀態(tài):造機器人萎津、做任務+造機器人、一直做任務抹镊。最優(yōu)的情況一定是先造足夠多的機器人锉屈,然后開始做任務,因為如果你交叉進行垮耳,那么做相同任務花費的時間可能更多颈渊,因為一個機器人做任務和造機器人穿插進行所做的任務<機器人造相同數(shù)目的機器人然后一直做任務。貪心策略

2.微軟的2個題目-其2

https://hihocoder.com/problemset/problem/1500

難度L3

這個題目本身不是特別難终佛,但是很復雜俊嗽,是一個與樹相關的問題。每一個節(jié)點都可以求一個最小代價铃彰,逐層向上绍豁。【背包問題:能夠獲取足夠信息的最小代價(每個點僅與自己的孩子有關)】

3.Different ways to addParentheses

https://leetcode.com/problems/different-ways-to-add-parentheses/#/description

遞歸+記憶化

從數(shù)學的思維來理解牙捉,而不是加括號的方式來理解竹揍,因為括號只是一種運算優(yōu)先級的表示,括號要加起來邪铲,可能能加很多個芬位。從數(shù)學思維來理解,考慮最后一個運算的符號带到,可能是所有符號中的任何一個昧碉,左邊一坨的結果集和右邊一坨的結果集操作【遞歸】,某兩個數(shù)字之間得到的結果集是固定的阴孟,那么可以用dict記錄下來【記憶化】晌纫。

可以用python的set來實現(xiàn)

import?collections

s = collections.Counter()

s.update("aaabbbbcc")

print(s)

4.BestTime to Buy and Sell Stock with Cooldown

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/#/description

動態(tài)規(guī)劃

如果沒有銷售冷凍的這種情況,任何時候我當前的操作均由下一天決定永丝,如果第二天股票漲了那我就買,如果第二天股票跌了那我就賣出去箭养,在不斷地買賣過程中累積利潤慕嚷。

F(I,j):第i天開始狀態(tài)為j;如果j為手上持股狀態(tài)毕泌,該值表示股票數(shù)目喝检;如果j表示手上不持股狀態(tài),該值表示總利潤撼泛。

F(I挠说,手上持股)=max { F(I-1,手上不持股)/Price(I-1),F(I-1,手上持股)}

F(I,手上不持股/前一天剛賣愿题,今天冷凍)=F(I-1损俭,手上持股)*Price(I-1)

F(I蛙奖,手上不持股/今天不冷凍)=max {F(I-1,手上不持股/不冷凍),F(xiàn)(I-1)杆兵,手上不持股/冷凍}

Function表示的是狀態(tài)雁仲,+-*/表示狀態(tài)之間的操作【動態(tài)規(guī)劃】

5.貪心策略

Minimum Number of Arrows to Burst Balloons

https://leetcode.com/problems/minimum-number-of-arrows-to-burst-balloons/#/description

從數(shù)學的思路去思考,每次找最小的右端點琐脏,能夠保證射中的最多攒砖,然后找到端點后,將射中的區(qū)間移除日裙。

6.中位數(shù)

https://leetcode.com/problems/wiggle-sort-ii/#/description

找到中位數(shù)吹艇,將中位數(shù)右邊的數(shù)字插入左邊的序列。O(n)的時間找中位數(shù)昂拂,隨機選取一個數(shù)掐暮,將比他大的放左邊,比他小的放右邊政钟,取中位數(shù)下標的那一邊路克。

7.位運算

https://leetcode.com/problems/integer-replacement/#/description

使用動態(tài)規(guī)劃的思路,先將這個數(shù)轉換成二進制养交,偶數(shù)就是移位操作【右移】精算。基數(shù)有兩種操作碎连,取更小的那個灰羽。

F(n):n為偶數(shù)直接右移一位;n為基數(shù)取min【+1或者-1】

8.拓撲排序

https://leetcode.com/problems/course-schedule/#/description

拓撲排序鱼辙,每一個課程算是一個樹的節(jié)點廉嚼,有依賴關系的課程建立一條邊。如果這些點和邊可以構成有向無環(huán)圖倒戏,有解怠噪;如果有環(huán),則無解杜跷。

思路1:建立一個隊列傍念,找入度為0的點加入隊列,遍歷隊列中的點葛闷,將每個點的后繼加入圖憋槐,同時把該后繼的入度減1,標記已經(jīng)加入圖的點淑趾。如果在這個過程中遇到了入度為0的點就把他加入圖阳仔。如果最后圖中沒有包含所有的點,則無解扣泊。

思路2:將所有的邊反向近范,你要輸出一個點嘶摊,必須輸出這個點的前驅【反向邊就是后繼】,這樣保證先修顺又,知道你輸出了所有的點更卒,如果不能那就無解。

9.并查集:維護連通性

最后編輯于
?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末稚照,一起剝皮案震驚了整個濱河市蹂空,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌果录,老刑警劉巖上枕,帶你破解...
    沈念sama閱讀 222,807評論 6 518
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件,死亡現(xiàn)場離奇詭異弱恒,居然都是意外死亡辨萍,警方通過查閱死者的電腦和手機,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,284評論 3 399
  • 文/潘曉璐 我一進店門返弹,熙熙樓的掌柜王于貴愁眉苦臉地迎上來锈玉,“玉大人,你說我怎么就攤上這事义起±常” “怎么了?”我有些...
    開封第一講書人閱讀 169,589評論 0 363
  • 文/不壞的土叔 我叫張陵默终,是天一觀的道長椅棺。 經(jīng)常有香客問我,道長齐蔽,這世上最難降的妖魔是什么两疚? 我笑而不...
    開封第一講書人閱讀 60,188評論 1 300
  • 正文 為了忘掉前任,我火速辦了婚禮含滴,結果婚禮上诱渤,老公的妹妹穿的比我還像新娘。我一直安慰自己蛙吏,他們只是感情好源哩,可當我...
    茶點故事閱讀 69,185評論 6 398
  • 文/花漫 我一把揭開白布。 她就那樣靜靜地躺著鸦做,像睡著了一般。 火紅的嫁衣襯著肌膚如雪谓着。 梳的紋絲不亂的頭發(fā)上泼诱,一...
    開封第一講書人閱讀 52,785評論 1 314
  • 那天,我揣著相機與錄音赊锚,去河邊找鬼治筒。 笑死屉栓,一個胖子當著我的面吹牛,可吹牛的內容都是我干的耸袜。 我是一名探鬼主播友多,決...
    沈念sama閱讀 41,220評論 3 423
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼堤框!你這毒婦竟也來了域滥?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,167評論 0 277
  • 序言:老撾萬榮一對情侶失蹤蜈抓,失蹤者是張志新(化名)和其女友劉穎启绰,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體沟使,經(jīng)...
    沈念sama閱讀 46,698評論 1 320
  • 正文 獨居荒郊野嶺守林人離奇死亡委可,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,767評論 3 343
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了腊嗡。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片着倾。...
    茶點故事閱讀 40,912評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖燕少,靈堂內的尸體忽然破棺而出卡者,到底是詐尸還是另有隱情,我是刑警寧澤棺亭,帶...
    沈念sama閱讀 36,572評論 5 351
  • 正文 年R本政府宣布虎眨,位于F島的核電站,受9級特大地震影響镶摘,放射性物質發(fā)生泄漏嗽桩。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,254評論 3 336
  • 文/蒙蒙 一凄敢、第九天 我趴在偏房一處隱蔽的房頂上張望碌冶。 院中可真熱鬧,春花似錦涝缝、人聲如沸扑庞。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,746評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽罐氨。三九已至,卻和暖如春滩援,著一層夾襖步出監(jiān)牢的瞬間栅隐,已是汗流浹背。 一陣腳步聲響...
    開封第一講書人閱讀 33,859評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留租悄,地道東北人谨究。 一個月前我還...
    沈念sama閱讀 49,359評論 3 379
  • 正文 我出身青樓,卻偏偏與公主長得像泣棋,于是被迫代替她去往敵國和親胶哲。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,922評論 2 361

推薦閱讀更多精彩內容