算法工程師，一個聽起來非常高大上的職業~ 不但輕輕松松月入過萬，算法知識更是進入大廠必考的題目。
如何通過大廠算法崗面試？
如何輕輕松松拿到高薪？
如何成為算法技術大牛？
... ...
今天開發者社群就來為小夥伴們送福利啦！10+大廠面試必看的算法模拟題精解合輯送上，每天一個算法小知識，輕松備戰大廠面試！
1、找出二叉搜尋樹的第2大的數
給定一個二叉搜尋樹，找出其第二大的數。
示例1
比如二叉搜尋樹如下
那麼第二大的值是25。
解題過程： 這是一個關于二叉搜尋樹的知識點。
對于二叉搜尋樹，若它的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值； 若它的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值。
因為題中沒有說這是一棵平衡的樹，是以某些節點可能隻有一棵子樹。
對于樹中最大的數是很容易找到的，一直選擇右子樹直到右子樹為空就可以了。
對于第2大的數，存在兩種情況。一種是最大數的節點存在左子樹，一種是不存在左子樹。
檢視更多>>2、打怪獸
現在有3隻怪獸，他們的都有自己的血量a,b,c(1<=a,b,c<=100)，當Tom打死第一怪獸的時候花費的代價為0，其餘的怪獸的代價為目前的怪獸的血量減去上一個怪獸的血量的絕對值。問Tom打死這些怪獸所需要的最小代價?
解題過程： 根據題意，本題使用貪心算法完成，政策是每次打怪獸都選擇代價最小的一隻。
由于第一次打怪獸的花費為0，是以第一次可以打血量最小的（最大的也可以），接下來每次選擇怪獸的時候就可以選擇花費代價最小的。由于每次打怪獸的代價都是：目前怪獸的血量和上一個怪獸的血量的差的絕對值。于是可以得出結論，最小代價為所有怪獸血量的最大值減最小值。
3、超級區間
Tom現在有一個長度為n的數組，Jerry給Tom定義了一種超級區間，如果區間[l,r]滿足(a[l]+…+a[r])>=k,則區間[l,r]被稱為超級區間，現在Jerry想讓Tom告訴他數組中有多少個超級區間？
解題過程： 使用 尺取法 對搜尋空間進行周遊。
設目前區間為[L, R]。初始L = R = 0；使用尺取法需要判斷什麼時候調整L和R。
數組中的所有數都為正數。
情況1：假設對于某個區間[L1, R1]滿足超級區間的定義。因為所有數都為正數，是以保持L1不變，依次增加R1直到n為止的所有區間都滿足超級區間的定義。
情況2：假設對于某個區間[L2，R2]不滿足超級區間的定義。則需要保持L2不動，增加R2才可能滿足超級區間的定義。
情況3：是情況2拓展。如果[L2，n]不滿足超級區間的定義，則任何i>L2，區間[i, n]都不滿足超級區間的定義。
4、變換的密鑰
Tom最開始有一個密鑰s1，s1是長度為n的由小寫字母組成的字元串。Jerry也有一個長度為n的由小寫字母組成的密鑰s2。
現在有m組關系，每組關系由兩個數字[u,v]構成(1<=u,v<=26)，表示26個字母表中的第u個小寫字母可以直接轉換為第v個小寫字母。
假設u=1，v=2,那麼說明字母'a'可以直接轉換為字母'b'。現在Tom對于s1的每個字母使用無數次轉換，請判斷s1能否轉換為s2。
解題過程： 根據題意，隻要根據給出的初始關系，計算出對于每個字母可以變成的字母，就可以直接判斷s1能不能轉化成s2了。
例如樣例中計算過後：
a -> a,c,d
b -> b,c
c -> a,c,d
d -> d 對于這個結果，可以使用一個26*26的二維數組change來儲存。每一行表示原始字母，每一清單示可以變換成的字母。1表示可以變化，0表示不能變換。
5、能量半徑
codancer來到了一個能量平面上的中心，坐标為(0,0)，接下來巫師Tom會在q個坐标上放置能量點，每個能量點的能量值為1，為了打敗哥斯拉，他需要至少k點的能量，是以他想确定一個最小的整數半徑r使得codancer能夠從這個圓心為(0,0)，半徑為r的圓形區域内得到至少k個能量值，請你幫他确定最小的整數半徑r？
解題過程： 題目的含義就是找到距離原點最近的第k個點，并求它的半徑。
計算每個點到原點的距離，為了減少計算量可以隻計算到平方。使用long[n]這樣的數組來儲存。使用long類型是為了防止平方之後結果超出int類型範圍。
對距離進行從小到大排序；取排序後的第k個數值開根号，轉化為int類型并加1。加1是因為開根号後可能為小數，轉化成int類型會直接舍去小數部分，導緻結果比實際小一些。
6、全奇數組
codancer現在有n個正整數a[1],a[2]…a[n]，Tom告訴codancer他可以進行下列操作，選擇某個偶數x，把這n個數中全部等于x的數字除2，Tom想知道把這n個數字全部變成奇數最少需要幾次這樣的操作？
解題過程： 從題意及示例可以知道，應該從大到小進行操作。當除2後，需要快速查找是否有相等的其他數，這個需求可以使用HashSet代替。
是以，先将n個中的偶數入HashSet，再對HashSet中元素從大到小排序，依次周遊；
每個元素除2後從HashSet查找，存在則移除，計數+1，直到該數變成奇數。
最壞情況下，除2過程沒有重複數字。
7、移動射擊
你正在數軸上跟小精靈對戰。你擁有一個十分強力的技能稱為移動射擊，但是這個技能有一個缺點是在你發動之後隻能改變一次方向。
你可以認為你的位置在數字0的位置上，在數軸的正方向上有n隻精靈，負方向上有m隻精靈。移動射擊可以造成w點傷害。每個精靈都有自己的血量，當血量降為0時死亡。
在最開始時你可以選擇向正方向或負方向釋放移動射擊，并且可以在任意時刻改變技能的方向。請問你最多可以擊殺多少隻小精靈?(n，m，w以及精靈的血量均在[1, 100000]範圍内)
解題過程： 首先了解題意，題目說的“發動之後隻能改變一次方向”是幹擾你的，因為即使你在中間過程中左右擺，但宏觀上還是最多改變了一次方向。
如果說：我先殺左邊一個，然後轉頭殺右邊一個，再轉頭殺左邊三個，又回頭殺右邊1個，看起來是不是改變了三次方向，其實呢，相當于我先殺左邊四個，再回頭殺右邊兩個，效果是一樣的。因為你想這個問題的時候，可以忽略這個限制。
8、數組變換
給出一個長度為 n 的數組，和一個正整數 d。
你每次可以選擇其中任意一個元素 a[i] 将其變為 a[i] + d 或 a[i] - d，這算作一次操作。
你需要将所有的元素全部變成相等元素，如果有解，請輸出最小操作次數，如果無解請輸出-1。
解題過程： 首先判斷無解的情況，可以發現 a[i]，a[i]+d, a[i]-d 在 模d情況下的餘數不會發生改變，是以如果原數組中的存在任意兩個數字它們對d取餘結果不同，那麼此時無解。
設餘數為r。判斷完無解之後，需要求出最小值。
先将數組a[i]排序，然後除以d，得到從r變成a[i]需要的步數。
枚舉元素a[i]，将所有元素全部變成a[i]需要考慮兩部分，i之前和i之後:對于i之前的元素，假設都是r，那麼需要 (i-1)*a[i]，但是因為并不都是0，所有我們可以用一個變量val存放前i-1項的和，然後我們在減去val就是前i-1個元素真正需要操作的步數。
9、樹的拆分
給你一個有n個節點的樹,節點标号1-n。每個節點有一個權值w[i]，一棵樹的價值為樹上所有不同的權值的數量。
現在你可以删除一條邊，問删除一條邊後形成的兩棵新樹的價值之和最大為多少？
解題過程： 如果我們删除了一條邊，那麼一定将其分成了兩棵樹，其中一棵樹一定為原樹的子樹，那麼我們就可以利用DFS序将樹周遊一遍得出每個點的時間戳。
DFS序即為每個點的在一次DFS中的周遊順序，從定義可以知道，子樹上的每個節點的DFS序一定連續，是以我們可以求出每棵子樹所對應的區間，剩下的節點即為另一棵樹。
此時我們就可以利用樹狀數組求每個區間裡面不同的數的個數，由于一個子樹區間可能會在數組中間，會将剩下的數字分為左右兩部分，是以我們需要将原權值數組擴充一倍，然後進行計算。
需要注意的是，現在這個權值數組不是輸入的權值數組，而是根據DFS序進行重新排序的數組。
10、Codancer的炸彈引爆
Codancer終于抵達了惡龍的城堡。現在他在城堡周圍擺放了n枚電力炸彈，每個電力炸彈有兩種屬性m和p，隻有已經引爆了m枚電力炸彈或者Codancer直接花費p的電力，第i枚炸彈才會被引爆，現在Codancer想使用最少的電力引爆所有的炸彈，請計算最少需要多少電力？
解題過程： 花費8電力引爆第3枚炸彈，那麼第1枚就會被自動引爆，那麼第2枚也會被自動引爆。
這種方案的花費是最小的。
11、Codancer的旅行
期末考試終于結束啦，Codancer開始了他的旅行，現在整個地圖上由n個城市，這些城市之間有n-1條道路相連，每條道路都有一個距離，并且保證整個圖是連通的，即這個地圖可以看作是一棵樹，現在假設Codancer要從城市A到城市B，那麼他的路費就是從A-B的路徑上邊權最大的邊的權值wmaxx元。現在Codancer有k元，他想知道他能選擇那些(A,B)并且A
<
B使得codancer能夠到達。
解題過程： 根據樣例資料 從1到2的花費為1，從1到3的花費為2，從2到3的花費為1，花費都小于3，是以總共有三種方案。
首先按照邊權将這些邊從小到大排序，使用并查集記錄目前連通塊内的最大的邊權。
當u和v連接配接起來的時候，假設此時的聯通塊大小為cnt,則答案應該加上cnt*(cnt-1)/2，同時應該減去之前u和v單獨為連通塊的方案數。
令ans[i]為最大邊權為第i條時構成的連通塊的方案數，那麼對于k，二分查找最大的小于等于k的下标id，最終答案就是ans[id]。
熱門活動
備戰大廠每日挑戰算法，堅持打卡更有社群定制周邊獎品等你赢！ 算法程式設計題目精解征文開始啦！快來Show出你的最優思路更多資源
阿裡面試官分享+真實面經+筆試模拟題，面試充電，就看這篇 面試一點通，幫你拿下好工作！