今日找人突擊面試經(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.并查集:維護連通性