AlibabaGroup阿里巴巴集團阿里云開發者“藏經閣”一、算法思想1.1排序算法筆試模擬題精解之“數組變換”7算法筆試模擬題精解之“打怪獸”9算法筆試模擬題精解之“最大邊權和”算法筆試模擬題精解之“最強的團隊”算法筆試模擬題精解之“Tom愛吃巧克力”15算法筆試模擬題精解之“吃奶酪”算法筆試模擬題精解之“一的個數”19算法筆試模擬題精解之“Bob的花束”21算法筆試模擬題精解之“錢莊”算法筆試模擬題精解之“移動射擊”26算法筆試模擬題精解之“相似數組”29算法筆試模擬題精解之“過吊橋”32算法筆試模擬題精解之“完美排列”35算法筆試模擬題精解之“采摘圣誕果”37算法比賽模擬題精解之“TairitsuandDynamicObjects”39算法筆試模擬題精解之“Codancer的炸彈引爆”41算法筆試模擬題精解之“學習小組”43算法筆試模擬題精解之“恢復字符串”451.3DP/動態規劃47算法筆試模擬題精解之“矩陣最小路徑和” 算法筆試模擬題精解之“尋找等比數列”49算法筆試模擬題精解之“字符配對”52算法筆試模擬題精解之“數組染色”54算法筆試模擬題精解之“連綿的群山”57算法筆試模擬題精解之“難住Tom的問題”算法筆試模擬題精解之“變化的字符”63算法筆試模擬題精解之“跳房子”算法筆試模擬題精解之“寒假活動”67算法筆試模擬題精解之“最短路”算法筆試模擬題精解之“codancer上樓”72算法筆試模擬題精解之“木棒拼接”74算法筆試模擬題精解之“Codancer的數組封印”77算法筆試模擬題精解之“Jerry的異或運算”80算法筆試模擬題精解之“小明的數學作業”82算法筆試模擬題精解之“奇偶數列”841.4剪枝88算法筆試模擬題精解之“斐波那契字符數”881.5尺取法92算法筆試模擬題精解之“超級區間”92算法筆試模擬題精解之“調整數組”95算法筆試模擬題精解之“最優分組”98算法筆試模擬題精解之“破譯密碼”二、數據結構1032.1圖103算法筆試模擬題精解之“變換的密鑰”1032.2搜索107算法筆試模擬題精解之“2的冪次方數”算法筆試模擬題精解之“能量半徑”算法筆試模擬題精解之“蘋果收獲程序”算法筆試模擬題精解之“恐怖的輻射”114算法筆試模擬題精解之“樹的拆分”算法筆試模擬題精解之“Password”119算法筆試模擬題精解之“神奇數字在哪里”122算法筆試模擬題精解之“神奇的棋子”1242.3樹126算法筆試模擬題精解之“全奇數組”算法筆試模擬題精解之“Codancer的旅行”129算法筆試模擬題精解之“Codancer的求和”132算法筆試模擬題精解之“找出二叉搜索樹的第2大的數”2.4線型138算法筆試模擬題精解之“最大矩形面積”算法筆試模擬題精解之“最活躍的數”140算法筆試模擬題精解之“非遞減序列”142算法筆試模擬題精解之“Tom跳方格”144算法筆試模擬題精解之“復雜的字符串”算法筆試模擬題精解之“神秘消失”三、計算154算法筆試模擬題精解之“最后的勝者”154算法筆試模擬題精解之“朋友一生一起走”158 算法筆試模擬題精解之“正三角塔”算法筆試模擬題精解之“組隊難題”算法筆試模擬題精解之“2n合體”算法筆試模擬題精解之“平行線”算法筆試模擬題精解之“疊疊高”算法筆試模擬題精解之“公平”算法筆試模擬題精解之“Tom的手工課”175算法筆試模擬題精解之“填數問題”算法筆試模擬題精解之“Jerry的考驗”179算法筆試模擬題精解之“超車”181算法筆試模擬題精解之“壞掉的時鐘”185算法筆試模擬題精解之“期末考試”算法筆試模擬題精解之“滑雪比賽”算法筆試模擬題精解之“數組變換”你需要將所有的元素全部變成相等元素，如果有解，請輸出最小操作次數，如果無解請輸出-1。8>算法筆試模擬題精解之“數組變換”8輸出一個數字，表示最小的操作次數，如果無解輸出-1。52[3,5,7,1,9]6之前的元素，假設都是r，那么需要(i-1)*a[i]，但是因為并不都是0，所有我們可以用一個變量val存放前i-1項的和，然后我們在減去val就是前i-1個元素真正需要對于i之后的元素，也是類似的。我們假設i之后的所有項和為val，假設我們要將它們變為r，則消耗即為val，但是我們只需要將其變為a[i]，因此需要減去(n-i)*a[i]。899算法筆試模擬題精解之“打怪獸”簡介：根據題意，本題可使用貪心算法完成，策略是每次打怪獸都選擇代價最小現在有3只怪獸，他們的都有自己的血量a,b,c(1<=a,b,c<=100)，當Tom打死第一怪獸的時候花費的代價為0，其余的怪獸的代價為當前的怪獸的血量減去上一個怪獸的血量的絕對值。問Tom打死這些怪獸所需要的25>算法筆試模擬題精解之“打怪獸”6由于第一次打怪獸的花費為0，所以第一次可以打血量最小的（最大的也可以接下來每次選擇怪獸的時候就可以選擇花費代價最小的。由于每次打怪獸的代價都是：當前怪獸的血量和上一個怪獸的血量的差的絕對值。于是可以得出結論，最小代51.2貪心算法筆試模擬題精解之“最大邊權和”簡介：根據題意，最終需要將n個點連通并達1<=ai<=1000)，現在可以將任意兩個點相連，連起來以后這條邊也有一個值稱為邊權，這個邊的邊權為這兩個點的點權之和的一半。現在需要你添加n-1條邊，問將>算法筆試模擬題精解之“最大邊權和”[2,4,6,8,10]30實現過程中，首先求出最大的點權，然后計算出其他點與這個權值最大的點的邊6算法筆試模擬題精解之“最強的團隊”簡介：根據題意，最強團隊即團隊中每個小隊的能力值都是最高的。即解決這道有一個陣營，里面有n個小隊(1<=n<=100)，每個小隊都有他們的能力值現在有一個緊急情況，需要從這些小隊中選出連續的幾個小隊，組成一個最強的團隊。最強的團隊的定義為這個團隊的所有小隊的平均能力值最高。如果有多個最強>算法筆試模擬題精解之“最強的團隊”[1,2,3,3,2,1]2根據題意，最強團隊即團隊中每個小隊的能力值都是最高的。即解決這道題需要具體實現時，可以先找出數組中最大的能力值是多少，然后設置一個標記tag。接著遍歷數組，比較每個數組元素和最大值，數組元素等于最大的值的時候，將tag在tag等于1時統計連續最大值的數量，若統計到多個最大值，則記錄最大的算法筆試模擬題精解之“Tom愛吃巧克力”<算法筆試模擬題精解之“Tom愛吃巧克力”簡介：根據題意，可以得知這道題可以運用貪心算法，策略是每次都去買最便宜Tom非常喜歡巧克力，他上次買的巧克力吃完了，所以他打算再去買k塊巧克力回來(1<=k<=1e5)，他又是一個非常節儉的一個人，所以他想花最少的錢去買巧>算法筆試模擬題精解之“Tom愛吃巧克力”25根據題意，可以得知這道題可以運用貪心算法，策略是每次都去買最便宜的巧由于題目給的二維數組是亂序的，可以根據巧克力的價格對二維數組從小到大進行排序，便于Tom選擇最便宜的巧克力。Arrays類中只提供了一維數組的排序，如果要用Arrays對二維數組排序，需要重寫Compara排序完成后，接下來操作就比較簡單了。遍歷數組，優先買便宜的巧克力，直到算法筆試模擬題精解之“吃奶酪”簡介：根據題意，如果要花費最少時間，則每個奶酪都讓離奶酪最近的人去拿，Tom和Jerry都很喜歡吃奶酪，現在有n塊奶酪散落在坐標軸上(1<=n<=100000)，他們分別在a1,a2,a3...an(1<=ai<=100000,一個點可以有多塊奶酪)上，Tom和Jerry分別在1和100000兩個點上，他們每走一步需要花費1s，問他4[350,2000,80000,99999]>算法筆試模擬題精解之“吃奶酪”20000根據題意，如果要花費最少時間，則每個奶酪都讓離奶酪最近的人去拿，因此，具體實現時，可以設置一個time值，然后遍歷數組。判斷每一塊奶酪的坐標范圍，根據坐標判斷應該讓誰拿，再計算拿到這個奶酪需要多長時間，如果時間大于用這種方法，遍歷整個數組后的time值即為Tom和Jerry拿到所有奶酪所用7算法筆試模擬題精解之“一的個數”給你兩個數字l、r，問在區間[l,r]內的所有數中，二進制表示下“1”的個數最輸出一個數字表示[l,r]內二進制下“1”的個數最多的數。如果有多個，輸出符5>算法筆試模擬題精解之“一的個數”所求數字可分為兩部分，高位部分和低位部分，高位部分的值等于l,r高位相等(1<<(count-1))-1算法筆試模擬題精解之“Bob的花束”<算法筆試模擬題精解之“Bob的花束”簡介：本題充分理解題意后，直接模擬這個“選取最大值”的過程就可以得到結為了方便挑選，Bob給這9種花分別標號1-9，Bob希望買到的花按照編號可輸出一個數字，表示Bob可以排出的最大數字。如果Bob不能排出任何一個數字，則輸出-1。>算法筆試模擬題精解之“Bob的花束”2[9,11,1,12,5,8,9,10,6]首先，選取最大值，意味著首先這個結果的“位數”要足夠多，比如假設所有的花價格都是1元錢，則11111111是花9塊錢能買到的最大值，而不是333或者9其次，在位數確定的情況下，高位數字越大，結果也就越大，比如同樣是8元錢，只能購買價格為5的5號花，和價格為3的3號花時，購買35就是最差的方案，而53才是正確答案。而且因為每個花的數量是無限的，所以可以模擬這個“從高位開始，逐個選取能買得起的最大的數字；同時每選完一位后，要確保剩下的錢，提示：根據上面邏輯寫出的答案，在充分理解優化后，至少可以達到2遍掃時間復雜度：O(9n)算法筆試模擬題精解之“錢莊”會向中央銀行申請兌換錢幣，假設錢莊有一些散錢使得2^k1+2^k2+...+2^km=2^x（x為非負整數那么就可以將這些散錢兌換成一個大錢幣，問在錢莊收到的這些散4>算法筆試模擬題精解之“錢莊”1這樣算的：對于底數為2冪數相同的兩個個1組成一個2，此時共有兩個2，這兩個2組成一個3，此時共有兩個3，兩個三具體過程：遍歷一遍m找出m中的最大數max，定義一個數組arr[max+2],用于統計出m數組中，每個數字出現的次數，即ar遍歷錢幣數組m,只要數組中的當前元素x可以兌換一個大金幣(有兩個以上相所以空間復雜度為:O(100000)~O(1)針對錢幣數組遍歷一次,每一次會做自底向上的所以最差情況下時間復雜度,每次都會自底向上發生轉換;所以時間復雜度最差為:O(n^2)，其中n為錢幣數;>算法筆試模擬題精解之“移動射擊”算法筆試模擬題精解之“移動射擊”簡介：首先理解題意，題目說的“發動之后只能改變一次方向”是干擾你的，因你正在數軸上跟小精靈對戰。你擁有一個十分強力的技能稱為移動射擊，但是這上有m只精靈。移動射擊可以造成w點傷害。每個精靈都有自己的血量，當血量降在最開始時你可以選擇向正方向或負方向釋放移動射擊，并且可以在任意時刻改變技能的方向。請問你最多可以擊殺多少只小精靈?(n，m，w以及精靈的血量均在輸入內容為五個，前三個為三個數字：正方向上的精靈個數344大致思路：首先理解題意，題目說的“發動之后只能改變一次方向”是干擾你如果說：我先殺左邊一個，然后轉頭殺右邊一個，再轉頭殺左邊三個，又回頭殺右邊1個，看起來是不是改變了三次方向，其實呢，住此時的位置index_a=i，退出循環，退出后加上這句if(i==n||a[i]>w)index_a--;因為index_a指向的是剛好不超過w對b數組也是如此，然后開始從index_a往后一步一步走;>算法筆試模擬題精解之“移動射擊”當index_a一直走到底，可返回ans.算法筆試模擬題精解之“相似數組”簡介：要解出相似數組的最長長度，即要求相似數組中的每個元素盡可能的小，任選一段連續的區間[l,r]，將其替換為這段區間的所有數字的和。比如，對于[1,3,4,5,11,9]，你可以選擇區間[3,5]你現在需要通過上述操作將兩個數組變成相同的數組，相同的定義是：對于兩個如果這兩個數組可以變成相同的數組，那么我們稱這兩個數組是相似數組，否則不是相似數組。我們并不在意操作的次數，我們只在意在這兩個數組經過操作之后變成相同數組的時候最長的長度是多少，如果它們本來不相似請輸出-1。組a和b的長度，再分別輸入含有n個數字的數組a和含有30>算法筆試模擬題精解之“相似數組”30543要解出相似數組的最長長度，即要求相似數組中的每個元素盡可能的小，把握這如果sum_a==sum_b：判斷：如果兩個指針都等于各自數組的長度(即i==n&&j==m)，則返回結果(returnans3131如果以上兩個條件都不滿足(即兩個指針都小于數組長度)，則當前區間和更新為此時指向的元素(即sum_a=a[i],su表示越界)，如果越界，那么返回-1(表示不是相似數組)，如果沒越界，給區別和加上當前元素(即sum_a+a[i])如果sum_a>sum_b:如果越界，那么返回-1(表示不是相似數組)，>算法筆試模擬題精解之“過吊橋”算法筆試模擬題精解之“過吊橋”B同學在機房敲了半個多月的代碼之后終于打算出門玩一玩了。這天他準備去爬這個吊橋總共由n塊標號為1-n的木板組成，由于年久失修，這些木板有些已經快要壞掉了，每塊木板都有一個值ai表示第i塊木板還有ai分鐘就要壞掉了，即B同學過吊橋時一步只能走一塊或兩塊木板請問他在吊橋這邊最多可以玩多長時間可以認為B同學能在一分鐘內通過吊4[10,3,5,10]5在第五分鐘，還剩124三塊木板可以通過根據題意，要知道B同學還能在橋的一頭逗留的時間，需數組中有可能會有相同的數字，而value值要存儲所有數字的索引，所以索引接下來對數組進行升序排序，再創建一個大小相同的數組status用來記錄木板每遍歷一個數，就通過HashMap查找其索引，在status數組中根據這個索引將這個木板的狀態置為-1，代表木板壞掉了。然后判斷是否符合不能通過橋的條件，34>算法筆試模擬題精解之“過吊橋”34若符合條件，此時在數組遍歷的數即為可以逗留的時間。若不符合條件，則繼續遍歷空間復雜度：O(2n)2算法筆試模擬題精解之“完美排列”簡介：本文通過兩種解法描述86題“完美排列”的解題過程，更有對應的時間完美排列的定義為一個長度為n的數組，n個元素各不相同且每個元素均在現在給你長度為n的數組，你每次可以進行如下操作：任選數組中的一個元素，236>算法筆試模擬題精解之“完美排列”363->20->1本題是一道典型的貪心算法題，問題可以通過每步的最優策略分治解決。如果將當填充槽2時，依舊用上面的思路就可以了。用剩下的(n-1)個數字中最小的數字去通過加減1進入槽2，必定是填充槽2所有方式中的最佳策略。上面的反復掃描非常浪費時間，不如提前對數組排序，然后從排序后遞增數組的3算法筆試模擬題精解之“采摘圣誕果”簡介：我們定義數組a[i]表示第i天可以采摘的剛剛結出來的果子，數組b[i]表第a[i]天結出b[i]個果實。果園里有許多圣誕你，作為圣誕樹的看守者，必須采摘盡可能多的圣誕果，但是你每天最多只能采摘v個圣誕果，當然，可以是不同的果樹上的。現在你需要判斷自己最多可以收獲多38>算法筆試模擬題精解之“采摘圣誕果”383你可以在第一天在第一棵樹上摘三個，第二天在第二棵樹上摘三個，第三天在第我們定義數組a[i]表示第i天可以采摘的剛剛結出來的果子，數組b[i]表示第i假設我們當前處于第i天，那么顯然我們應該采摘b[i]中的果實，然后再采摘a[i]中的果實，因為如果不采摘b[i]中的果實，則它們會在下一天被偷吃。在更新之時間復雜度：O(3000)空間復雜度：O(3000)39算法比賽模擬題精解之“TairitsuandDynamicObjects”<39Hikari和Tairitsu面前有n個物品，這些物品編號為1,2,..初始n個物品均可被選取。Hikari與Tairitsu會輪流選取當前可選取的物品中設Hikari選取的物品編號的集合為H，所有物品均被選取完之后，Hikari得分為∑ai(i∈H)；而Tairitsu得分為Hikari和Tairitsu都希望自己的得分比對方大，你需要求出注意：若對于某個人來說，剩余的物品中有多個對兩人分數大小關系影響相同的40>算法比賽模擬題精解之“TairitsuandDynamicObjects”405[1,2,3,4,5][5,4,3,2,1]根據題意，分析得知，Hikari和Tairitsu每次會優先選擇ai+bi的值最大的物的值。降序排好后，Hikari和Tairitsu依次按順序選擇物品，Hikari先選看完之后是不是有了想法了呢，快來練練手吧>>查看題目：TairitsuandDynamicObjects41算法筆試模擬題精解之“Codancer的炸彈引爆”<41算法筆試模擬題精解之“Codancer的炸彈引爆”Codancer終于抵達了惡龍的城堡。現個電力炸彈有兩種屬性m和p，只有已經引爆了m枚電力炸彈或者Codan花費p的電力，第i枚炸彈才會被引爆，現在Codance342>算法筆試模擬題精解之“Codancer的炸彈引爆”428花費8電力引爆第3枚炸彈，那么第1枚就會被自動引爆，那么第2枚也會被花費8電力引爆第3枚炸彈，那么第1枚就會被自動引爆，那么第2枚也會被本題使用貪心策略，考慮按照所需要的電力從大到小排序，假設從第i+1n枚炸彈已經用電力引爆的炸彈個數為cnt，由于在[1,i-1]最多再引爆i-1枚炸彈，如果此時i-1+cnt<mi，說明就需要再花費電力4343算法筆試模擬題精解之“學習小組”在一個課堂上，有n個學生(1<=n<=3e5)，每個學生都有他們自己的學分便交流，所有的小組都是由相鄰的學生組成(abc相鄰,不存在ac個小組的情況)，現在老師想讓每個小組的學分差值盡量小(最大值減去最小值)，請第一行和第二行輸入兩個數n、m表示有n個學生要分成m個小組，再輸入n53[1,3,5,7,9]44>算法筆試模擬題精解之“學習小組”444比如我們要將一個數組分成3組，那么可以假設為，[a1,ai],[ai+1,aj],[aj+1,an]這三組，然后我們所要求的值就是(ai-a1)+(aj-ai+1)+(an-aj+1).那么就可以推導出an-a1+aj-aj+1-ai-ai+1，所以就是an-a1減去最大的m-1個相鄰的差值，那么ai-ai+1這個顯然是差分的性質，所以我們對于原數列求一個差分數組出來，然后對差分數組進行排序，貪心的去減去前m-1個最大的4545算法筆試模擬題精解之“恢復字符串”充數字將這兩個字符串恢復成一個合法的表達式。并且只能填入正整數，恢復后的表也不可以變成“1+0-1”。定義你的消耗為你填充的所有正整數的和。比如“1+1-2”相信你通過思考已經發現最小差值總是0，因此你只需要求出差值為0時的最小46>算法筆試模擬題精解之“恢復字符串”46“++-”“--+”1.兩個字符串都沒有負號的時候，最優解的所有位置都填1。最小消耗為2*2.表達式中僅需要有一個負號，表達式的值就可以為任何值。此時兩個表達式不妨假設都加在第一位。計算出s1,s2的正負號數量的差，分別為x和y。假設47471.3DP/動態規劃算法筆試模擬題精解之“矩陣最小路徑和”簡介：本題可以用動態規劃的方法來解決。計算一個格子到右下角的最小路徑需要兩個數據，一個是右邊格子到右下角的最小路徑，一個是下邊格子到右下角的最小48>算法筆試模擬題精解之“矩陣最小路徑和”48計算一個格子到右下角的最小路徑需要兩個數據，一個是右邊格子到右下角的最小路徑，一個是下邊格子到右下角的最小路徑，兩個數據的較小值加上當前格子的數即dp[i,j]=min(dp[i+1,j],dp[i,j+1])+m[i,j]由于計算當前格子最小路徑需要右邊和下邊格子的最小路徑。因此，需要從底向如下圖所示，通過觀察可以發現，同一對角線上的數字的橫縱坐標和是相等的，我們以對角線的方向為順序，從右下角向左上角計算出每個格子的最小路徑。最后可計算得出dp[0,0]。24949算法筆試模擬題精解之“尋找等比數列”簡介：最簡單的方法，就是遍歷數組中所有可能的三元組，逐個檢驗每組數是否Alice和Bob都是數學高手，有一天Alice給了Bob一個長度為n的數組a，要求Bob在數組中找出3個數，要求三個數能夠組成一個公比為k的等比數列，且5>算法筆試模擬題精解之“尋找等比數列”[1,1,2,2,4]4最簡單的方法，就是遍歷數組中所有可能的三元組，逐個檢驗每組數是否符合公數列中每個數字只有4種可能的狀態。其中帶同時屬于一個或多個等比數列的第無法與前后數字組成任何等比數列表示數字處于上面哪種狀態，完全由這個數字及其之前的數字決定，它的狀態與這就意味著，一次遍歷，同時用map將每個遍歷的數字歸屬到前面4種狀態中的1個或多個里。遍歷結束，輸出第3種狀態“同時屬于空間復雜度：O(kn)>算法筆試模擬題精解之“字符配對”算法筆試模擬題精解之“字符配對”簡介：本題可以使用動態規劃來解決，對于第i個字符，有選和不選兩種，如果選，則和第i-1個字符組合創造權值，如果不選，就單獨出來沒有權值，取兩者中加給你一個字符串，字符串中僅包含"A","B",現在有四種字符串"AA","AB","BA","BB"，每種字符串都有他們的權值，問從給出的字符串中能夠得到的最大權值再輸入一個數組，數組中包含四個數字a,b,c,d，依次表示字符串"AA","AB",3大致思路：動態規劃問題，對于第i個字符，有選和不選兩種，如果選，則和第i-1個字符組合創造權值，如果不選，就單獨出來沒有權值，取兩者中加權最大的具體過程：定義一個字典map，key分別為"AA","AB","BA","BB"，value為對應的權值。定義大小為n的數組dp，dp[i]表示前i問，dp[0]=0，dp[1]=map.get此時dp[i]=dp[i-2]+map.get(s.substring(i-1,i+1)).針對這兩個選擇，取權值最大時間復雜度為O(n)空間復雜度為O(n)2>算法筆試模擬題精解之“數組染色”算法筆試模擬題精解之“數組染色”簡介：可以采用鏈表的思想，定義一個數組temp來存放每個遞增的子串，題目知識點：DP、LIScodancer現在有一個長度為n的數組a,對于每個這個數組的每個數字，我們5[2,1,4,5,3]目需要求出最少的遞增子串有多少個，采取的思路是遞增的子串越密集越好，即若有具體思路：定義一個數組temp來存放每個遞增的子串，那么我先將第一個元素面，又因為這是個數組，不是鏈表，而且鏈接后temp[j]值再也用不上，和鏈表的最>算法筆試模擬題精解之“數組染色”可以發現，每次比較都是和鏈表最后一個元素比較，所以前面的元素可以覆蓋，如下面的直接覆蓋法，也是用數組實現，很簡單。而且還可以發現，temp數組永遠是遞減的，這樣也滿足密集子串，因為從上往下走，找到滿足的即可停止，不需要繼續往下。最終，temp數組有幾個元素，答案就是多少。可以用ans一致指向temp完全理解本解法需要理解我定義的密集子串和鏈接法轉直接覆蓋等概念。好好理5算法筆試模擬題精解之“連綿的群山”簡介：可以將山化分為幾個小連續區間，每個區間保證越來越高，并且保證每個區間盡可能的長。除第一個和最后一個區間，中間的其余區間，有移除可能的是每個區間的最小值和最大值，第一個區間有移除可能的是最小值，最后一個區間有移除可小森家的北面有一條連綿的山脈，山脈高低起伏。小森很好奇這些山中最多有幾他又想，假如可以移除其中一座，這個答案最大又會是多少？當然了，他也可以>算法筆試模擬題精解之“連綿的群山”[5,10,6,7,8]4大致思路：可以將山化分為幾個小連續區間，每個區間保證越來越高，并且保證每個區間盡可能的長。除第一個和最后一個區間，中間的其余區間，有移除可能的是每個區間的最小值和最大值，第一個區間有移除可能的是最小值，最后一個區間有移具體過程：初始化兩個數組，oneIndex和arr，arr保存當前增區間的長度，（5,10遞增，6，7，8為一個增區間)，oneIndex={0,2}（因為ar這下明白這兩個數組的含義了吧。接下來遍歷oneIndex區間，也就是找出arr中所有為1的值的索引（arr數組這樣的話，即使3是第二個區間中最小的，也應該移除，因為這個}260>算法筆試模擬題精解之“難住Tom的問題”60算法筆試模擬題精解之“難住Tom的問題”簡介：拿樣例來說23100,說明有3個桶，第0個桶一定是空的，那么符合條Jerry和Tom在公園里感到很無聊，于是就開始研究起來題目了，Jerry有一個n+1個桶(1<=n<=300)，這些桶的編號為0,1,2,...,n，然后讓Tom去構造這些桶61613拿樣例來說23100,說明有3個桶，第0個桶一定是空的，那么符合條件的有({0},{1},{1,1}),({0},{1},{1,2}),({0},{1},{1,3}),({0},{1},{2,1}),({0},{1},{3,1}),({0},{2},{2,1}),({0},{2},{2,2}),({0},{2},{3,1}),({0},{3},{3,1}),({0},{3},{3,2}),({0},{3},{3,3})，那么如果這個數字插在2的左邊，一定是要比2大的數才可以，如果插到右邊對于這個情況來說沒有限制條件，如果對于位數較多的數列來說也要考慮到字典序>算法筆試模擬題精解之“難住Tom的問題”一共有三種狀態，當你的p沒位置了就沒有地方可插，那么這個數就不插了算法筆試模擬題精解之“變化的字符”有一個字符串s(1<=|s|<=3e5，|s|為奇數)，這個字符串只包含0,1現在可以通過一些操作來縮短這個字符串，每次操作可以任意選擇連續的三個字符，然后將這個連續的三個字符變成出現數量最多的那個字符(比如001變為0，通過更改字符'.'，問通過(|s|-1)/2次操作后最終這個字符串只剩下一個1的方輸入一行字符串s64>算法筆試模擬題精解之“變化的字符”64"1.0.1"4分別可以把字符串變為10001100111100111011，這四種都可以使得最后時間復雜度：O(24n)算法筆試模擬題精解之“跳房子”動到第i+a[i]個位置，并且不能超過n。你可以選擇移動到的位置包括：i,i+1,請輸出-1。566>算法筆試模擬題精解之“跳房子”662最優路徑為：1->2->5設f(i)為到第i個位置處的最小步數。初始化f的每個位置步數都是一個足夠大對于一個位置j來說，它的最小步數應該是前面所有可以一步到達它這里的位置空間復雜度O(n)時間復雜度O(n^2)每個位置都可以直接走到終點的時候。（但是可以判斷算法筆試模擬題精解之“寒假活動”但是小森又是一個討厭重復的人，因此他不會連著兩天做同樣的運動，但是可以也就是說，只有當滑雪館開門并且前一天他沒有去滑雪的時候他才能去滑雪。游現在小森已經得到了寒假時候滑雪館和游泳館的開門安排，即數組a，他現在想68>算法筆試模擬題精解之“寒假活動”685[3,3,1,2,0]1小森的最優策略是第一天滑雪，第二天游泳，第三天滑雪，第四天游泳，第五天小森只有3種可能的狀態(不運動、滑雪、游泳)。本題要求不運動的最小值天數，可以反向思維，求運動的最大天數，然后用總天數減去最大運動天數即為最小運dpi=max(dpi-1,dpi-1,dpi-1)dpi=max(dpi-1+1,dpi-1+1)dpi=max(dpi-1,dpi-1,dpi-1)dpi=max(dpi-1+1,dpi-1+1)dpi=max(dpi-1,dpi-1,dpi-1)空間復雜度：O(kn)>算法筆試模擬題精解之“最短路”算法筆試模擬題精解之“最短路”圖，初始狀態連通圖中只有水庫1一個結點。然加入連通圖的條件是道路兩端的水庫至少有一個在連通圖中，道路加入連通圖后，道《缺氧》是KleiEntertainment所制作并發行的一款模擬游戲。這是一個太空殖民地模擬游戲，玩家需要管理你的復制人，幫助他們挖掘、建立和維護一個地下的小行星基地。你需要水、食物、氧氣、適當的調節壓力和適宜的溫度來維持他們活著并在這里，氧氣是必不可少的，沒有氧氣，復制人就會無法生存。電解制氧是一個非常實用的制氧方法，將水通過電解器之后，電解器會消耗水產生氧氣和氫氣，氧氣復制人在進行了一段時間的挖掘之后，在地圖里發現了n個水庫，他們的命名方法非常暴力，水庫1，水庫2，...，水庫n。他中a[i]=x,y,z表示水庫x與水579是，假設一開始沒有道路，只有n個水庫。建立一個連通圖，初始狀態連通圖中只有水庫1一個結點。然后將逐步將道路加入連通圖中，道路加入連通圖的條件是道路兩當所有道路加入連通圖后，數組中記錄的水庫1到水庫n的距離即為所求最短>算法筆試模擬題精解之“codancer上樓”算法筆試模擬題精解之“codancer上樓”簡介：這是一個動態規劃問題。對于每層需要保存兩個值。一個是這層選擇選擇走樓梯的最小花費，記為Ta(i)。另一個是這層選擇坐電梯的最小花費，記為Tb(i)。如果codancer從第x層走樓梯到第y層(y>x)，那么他所花費的時間是如果他從x層坐電梯到第y層，那么他所花費的時間是c+(b[x]+b[x+1]+…第二個輸入一個整數c(1<=n<=100000,1<=c<=1000)，表示等電梯花費的接下來輸入兩個數組a和b，數組中n-1個數字代表數組a和b(1<=a[i],算法筆試模擬題精解之“codancer上樓”<417對于每層需要保存兩個值。一個是這層選擇選擇走樓梯的最小花費，記為Ta(i)。時間復雜度O(n)空間復雜度O(2*n)>算法筆試模擬題精解之“木棒拼接”算法筆試模擬題精解之“木棒拼接”Codancer現在由n根木棒，第i根木棒的長度為l[i]，并且每根木棒只有紅、現在codancer想得到一根長度為L的木棍，codancer可以選擇其中的一些按照一定的順序把這若干根木棒拼接起來，但是codancer要求相鄰的兩根木棒的顏色現在codancer想知道有多少種拼接方案（只要是存在順序不同或者木棒不同就336所有的排列方案為:根據樣例所有的排列方案為:>算法筆試模擬題精解之“木棒拼接”考慮使用動態規劃算法，令dpi表示在第i中狀態中最后一根木棒是第j根木棒算法筆試模擬題精解之“Codancer的數組封印”<算法筆試模擬題精解之“Codancer的數組封印”簡介：我們逆向思考，對于給定的數組每次刪去一個數，相鄰兩次操作的答案不知識點：DP、LIS有被解封的數字構成的數組的LIS的長度，現在Codancer想讓Tom計算第一行是一個正整數n，代表a數組和b數組的長度，接下來第一行輸入數組>算法筆試模擬題精解之“Codancer的數組封印”4[4,2,1,3][1,2,4,3]6L[4]=2解封后為{4,2,1,3}第三步解封后數組為{4,2,3}，因此L[3]第四步解封后數組為{4,2,1,3}，因此L[4]=2算法筆試模擬題精解之“Codancer的數組封印”<紅色數字構成的序列即為LIS。我們逆向思考，對于給定的數組每次刪去一個數，相鄰兩次操作的答案不會超我們就要重新求LIS,否則答案保持不變，由于隨機生成的全排列LIS長度的期望為sqrt(n)，因此最多計算sqrt(n)次LIS。時間復雜度：O(nsqrt(n)*log(n))。580>算法筆試模擬題精解之“Jerry的異或運算”80算法筆試模擬題精解之“Jerry的異或運算”Jerry最近在研究異或運算，異或也叫半加運算，其運算法則相當于不帶進位的381算法筆試模擬題精解之“Jerry的異或運算”<81dp[1]=2。他們的(u,v)分別是{(0,0)}和{(0,0),(1,0)}。從二進制上來看u和v，兩者的末位只有0或1，那么二者的末位和有0,1,2三>算法筆試模擬題精解之“小明的數學作業”算法筆試模擬題精解之“小明的數學作業”簡介：關鍵在于對題目的了解，數學老師讓小明求的是n個數中最長的等眾所周知，小明是一個數學小能手，有一天數學老師給了小明一個長度為n請注意子序列的定義：在原來序列中找出任意數量，任意位置的元素，在不調換6[0,1,3,5,6,9]4因為我們肯定要保存一個公差作為狀態量，但是直接枚舉0-1e9又不現實。所以我們巧妙的設計出了這個狀態，使得我們的公差就84>算法筆試模擬題精解之“奇偶數列”84算法筆試模擬題精解之“奇偶數列”這個數列是一個不完整的數列，意思是說數列中有幾個位置是空的，Tom想讓你幫他把空的位置填上數字，當然是有要求的，對于一個數列來說，如果相鄰兩位的數字奇偶性不同，這個數列的權值就+1，請你算出來將空位補上以后，權值最小為5[0,5,0,2,3]21.空位在左右兩側（以左側舉例）-10也就是最邊上是連續的空位，然后接一2.空位在左右兩側（以左側舉例）-11也就是最邊上是連續的空位，然后接一3.空位在中間，兩側都是奇數1-11；4.空位在中間，兩側都是偶數0-10；5.空位在中間，兩側一奇一偶0-11。5.只能為186>算法筆試模擬題精解之“奇偶數列”86第3，4種，因為填錯了會增加2，比一二種多，所以排第一（相同情況按照空1.遍歷一次，從原數組中提取出這5種空位，同時計算沒有填入的奇數偶數分2.按照(3，4)(1，2)(5)分成三組，對前兩組按照空位從少到多排序3.按照貪心策略的順序先判斷(3，4)中有多少可以增加0的，并消耗掉對應的奇數偶數個數，增加為然后判斷(1，2)中有多少可以增加0的，并消耗掉對應的奇數偶數個數，增加我們可以將問題抽象一下，其實就是求對于當前這一個位置之前有多少個奇偶對，可以進一步轉換成求前一位的奇偶性，不88>算法筆試模擬題精解之“斐波那契字符數”881.4剪枝算法筆試模擬題精解之“斐波那契字符數”簡介：本題應充分利用斐波那契數列的性質，自頂向下對問題逐步剪枝，定位需Tom發現了一種神奇的字符串-斐波那契字符串,定義f[1]=0,f[本題在答題過程中很多小伙伴反應會出現超內存的現象，導致JVM崩潰。但其8989這是一道找規律的題目，最簡單的想法可以是自底向上地構建出從第一個字符串本題應充分利用斐波那契數列的性質，自頂向下對問題逐步剪枝，定位需要判斷1.先算出n=19對應的字符串長度len，也就是斐波那契數列的第19項。考慮到k是int類型，故可以先算出n=1~47對應的斐波那契數組成的數組（n=47時，斐波那契數大于2^31-1，無需再提前計算更多的斐波那契數然后直接在計算好的斐波那契數組中取出第19項。2.找到n-2=17，n-1=18對應的斐波那契字符串長度（也就是第17/18個斐要找的數字在n=17對應的斐波那契字符串中，也就是n=19對應的斐波那4.根據判斷結果，將n賦值為n-2或n-1，同時將k賦值為k或(k-len1)，完成剪枝。回到第1步，遞歸向下搜索。直到n=1或者2，這時k也變為90>算法筆試模擬題精解之“斐波那契字符數”90它的前半部分屬于第i-2個字符串，后半部分屬于第i-1個字符串。這樣，當給定具體的n和k時，我們可以首先判斷k位于第n個字符串的前半部分還是后半部分，然后遞歸的把k傳遞給第n-2或n-1個字符串。a)K<=len[i-2]前半部分，調用find(i-2,k)b)K>len[i-2]后半部分，調用find(i-1,k-len[i-2])9191上面的計算在第一步時會遇到問題，當n大于幾十的時候，len就會超出int的對這個問題的解決基于對遞歸過程的觀察，第4步a）中k始終是不變的，i的奇偶性也保持不變。所以在計算第1步len時可以提前停止，當發現len[i]>=k且i與n的奇偶性相同時。第4步中的遞歸起始也可以使用第i個字符時間復雜度O(2*n)空間復雜度O(n)3>算法筆試模擬題精解之“超級區間”1.5尺取法算法筆試模擬題精解之“超級區間”簡介：使用尺取法對搜索空間進行遍歷。設當前區間為[L,R]。初始L=R=Tom現在有一個長度為n的數組，Jerry給Tom定義了一種超級區間，如果區輸入整數n,整數k(1<=n,k<=100000)，和一個大小為n的數組，數組的每個54情況1：假設對于某個區間[L1,R1]滿足超級區間的定義。因為所有數都為正情況2：假設對于某個區間[L2，R2]不滿足超級區間的定義。則需要保持L2不94>算法筆試模擬題精解之“超級區間”94對于情況1，因為L不變時，后面的所有R都滿足條件，所以可以修改為空間復雜度O(1)記錄當前區間數組元素的和算法筆試模擬題精解之“調整數組”簡介：首先理解題意：經過k次操作后能出現次數最多的元素,以及這個元素的他想在操作不超過k次的情況下，使得數組中某一元素的出現次數盡可能的多，96>算法筆試模擬題精解之“調整數組”96因為ai的大小被限定在[0,10^4],所以可以使用一個數組arr,來統遍歷數組arr,對于任意不等于0的數arr[i],逆向遍歷前面所有*不為0的如果是k不夠減,則得在判斷k能夠再減去多少個arr[算減去所有的arr[j]的2.遍歷數組arr,找出出現最多的次數以及對應的最小值.如果arr[j]*(i-j)<=k,證明當前的操作次數能夠將j全部變成i,加上所有的jj轉成i使用k/(i-j)計算還能夠將多少個判斷temp和最大值是否大于最大次數max,如果大于,則更新max和maxValue注意:當arr[j]順利遍歷到arr[0]時退出循環,因為我們的比較最大3.返回數組398>算法筆試模擬題精解之“最優分組”98算法筆試模擬題精解之“最優分組”簡介：一組數字，在不改變順序的情況下，每相鄰兩個數字之間的差值是確定給出一個長度為n的數組和一個數字k，你需要在數組中選出一些數字，這些數字兩兩之間的差值不能超過k。你需要判斷最多能夠挑出的數字個數。（n在[1,100000]之間，k和數組中的數字在[1，1000000000]之間）55[13,4,6,9,20]9999很多同學在思考這道題的過程中，碰到最大的難點就是，一個數字可能同時屬于多個分組，而這個分組的大小，可能是從2~n任何一個數字。這樣的組合方式，如比如，如果這道題提供了一個長100的數組用例，那么選出一組數可能的組合方式，就有2^100≈1024^10≈10^30種。所以我們發現，拖累解題過程最直接的點，在于題目給的數據結構不合理。對一于是，我們可以考慮，如何優化這道題提供的數據。對數組，在不違反題目要求的情況下，最簡單的優化方式就是排序。排序的時間復雜度很低，好的排序算法的空間復雜度為常數級，對本題影響很小。所以不妨假設對于一組有序的數字，再去考慮當右指針與左指針的差值超過k時，我們可以嘗試移動左指針，重新滿足上當右指針與左指針的差值不超過k時，我們可以嘗試移動右指針，尋找所求試著應用上面的思想，最佳方案應該可以達到：最壞情況下兩個指針各遍歷一次時間復雜度：O(nlogn)>算法筆試模擬題精解之“破譯密碼”算法筆試模擬題精解之“破譯密碼”給你一個長度為n的序列，元素標號1-n。問能夠找到多少對不同的（L,R1423三個子序列分別為[1,3],[1,4],[2情況1：假設對于某個區間[L1,R1]滿足題目要求。則保持L1不變，依次增加情況2：假設對于某個區間[L2，R2]不滿足題目要求。則需要保持L2不動，增情況3：是情況2拓展。如果[L2，n]不滿足題目要求，則任何i>L2，區間[i,使用一個2*n的數組numb來記錄當前區間[L,R]內每個元素的出現次數。numbL和numbR表示區間[L,R]對應的numb數組范圍。因為每個數都是按照進入區間[L,R]的順序離開區間[L,R]的，相當于一個隊列，所以numb數組可以用numbL和numbR來表示當前區間[L,R]內的元素，而不用考慮中間某個數不在區>算法筆試模擬題精解之“破譯密碼”4.L每次減1，都要給numb數組中對應的數出現次數-1。當減為0時，要對于情況1，因為L不變時，后面的所有R都滿足條件，所以可以修改為空間復雜度O(2*n)numb數組的空間2.1圖算法筆試模擬題精解之“變換的密鑰”簡介：根據題意，只要根據給出的初始關系，計算出對于每個字母可以變成的字母，就可以直接判斷s1能不能轉化成s2了。對于求冪操作有可以加快計算的方法，知識點：廣度優先搜索/BFS、Floyed最短路、圖Tom最開始有一個密鑰s1，s1是長度為n的由小寫字母組成的字符串。Jerry現在有m組關系，每組關系由兩個數字[u,v]構成(1<=u,v<=26)，表示26個假設u=1，v=2,那么說明字母'a'可以直接轉換為字母'b'。現在Tom對于s1>算法筆試模擬題精解之“變換的密鑰”如果s1能變成s2,則輸出YES,否則輸出NO。64"YES"樣例：aabbcc->cabbcc->cdbbcc->cdbccc->cdbcac->cdbcaa->cdbcad根據題意，只要根據給出的初始關系，計算出對于每個字母可以變成的字母，就對于這個結果，可以使用一個26*26的二維數組change來保存。每一行表示經過0-2次變換后可以達到的字母的結果相當于change*change，0-3次對應的相當于change*change*change，0-n次對應的就是change^n。這是一個矩從右向左，每一項都是前一項的平方。這樣原來需要12次乘法的操作變成了3>算法筆試模擬題精解之“變換的密鑰”與求數的次冪類似，矩陣也可以用相同的方法加速計算。對于這道題本身，因為矩陣中非0的結果表示可以進行變換，所以相乘時沒有必要算出具體的值，時間復雜度O(5*26*26*26)5是求32次冪需要的矩陣乘法次數。26*26*26空間復雜度O(2*26*26)一個二維數組保存當前結果，一個保存相乘后的結果。2.2搜索算法筆試模擬題精解之“2的冪次方數”簡介：對于本題，因為要從數組中刪除數字。刪除分為兩步，一是定位（查找Tom是一個十分喜歡數學的人，尤其喜歡2的冪次方的數字。現有n數字；3>算法筆試模擬題精解之“2的冪次方數”1哈希表，都是可選的方式。既然追求最佳解法，你不妨先試試將題目提供的數據結構之后的第二個難點，就是如何得出“與某個數相加為2的冪次方數”的數字了。我們知道，用二進制表示時，一個2的冪次方的正整數，譬如2，4，8，16...，只有最高位為1，其余位都是0，譬如b1，b10，b100，b1000...所以，對每個數字，只要用位元算找到它的最高位1的位置，就可以確本題最后的陷阱，在于正確理解“與這個數相加為2的冪例子來說，對于數字1，它不僅與1相加為2的冪次方數，與3，7，15...相加后，結果都是2的冪次方數。很多同學想到位運算的時候，可能忽略了這個條件，而只考時間復雜度：O(31n)（考慮到本題Integer4算法筆試模擬題精解之“能量半徑”簡介：題目的含義就是找到距離原點最近的第k個點，并求它的半徑。這個題的關鍵在于排序算法。使用最簡單的冒泡排序，時間復雜度O(n^2)；使用快速排序等好一點的排序算法，時間復雜度O(nlog(n))；也可以使用java中Arrays類中的codancer來到了一個能量平面上的中心，坐標為(0,0)，接下來巫師Tom會在q個坐標上放置能量點，每個能量點的能k點的能量，因此他想確定一個最小的整數半徑r使得codancer能夠從這個圓心為>算法筆試模擬題精解之“能量半徑”3[[1,1],[-1,1],[-1,-1],[2,3]]2當半徑為2的時候可以收集到1,1,[-1,-1]處的能量。long[n]這樣的數組來保存。使用long類型是為了防止平方之后結果超出2.對距離進行從小到大排序也可以使用java中Arrays類中的sort函數。算法筆試模擬題精解之“蘋果收獲程序”簡介：因為每次下落時，蘋果樹每一層的節點都會往下掉一層。由此可以想到，如果蘋果樹某一層的節點的數目為奇數時，這一層的節點的蘋果掉落到第一層時，由于一個節點只能存儲一個二進制位的原因，只會剩下一個蘋果。而如果蘋果樹某一層的節點數目為偶數，這一層的節點的蘋果掉落Alice和Bob在春天的時候種下了一棵蘋果樹，為了吃到蘋果，他們每天都會去給蘋果樹澆水。一眨眼到了蘋果成熟的時候，但是他們卻因為平時照顧蘋果樹太累了，沒有更多的精力去收獲蘋果。身為程序猿的Bob靈機一動，寫了一個自動收獲但是這個程序有一個致命的Bug：每當有兩個蘋果同時掉落到同一個節點的時>算法筆試模擬題精解之“蘋果收獲程序”第二行有n-1個數p2,p3,...,pn，(1<=pi滾落到節點2上面的蘋果會因為bug5[1,2,2,2]3蘋果收獲程序在正常情況下，有多個蘋果落到同一節點時，應該會是一個相加的情況。結合這個BUG的情況，可以猜想，這個程序的BUG也許是因為這棵樹每個節點只能存儲一個二進制位導致的，在這種情況下出現的BUG和題目中的相符。因為每次下落時，蘋果樹每一層的節點都會往下掉一層。由此可以想到，如果蘋果樹某一層的節點的數目為奇數時，這一層的節點的蘋果掉落到第一層時，由于一個節點只能存儲一個二進制位的原因，只會剩下一個蘋果。而如果蘋果樹某一層的節點數目為偶數，這一層的節點的蘋果掉落到第一層的節點是第二層，以此類推，通過判斷一個節點會掉落到的層數來判斷該結點當提交以后，發現還有一些測試用例無法通過，通過分析以后發現，還需要注意一個問題。在遍歷數組計算每個節點所在的層時，需要注意，如果數組中的數字表示這個節點會掉落到自身節點的位置上，也就是這個節點的蘋果不會往下層掉，會永遠留在這個節點，因此在統計每層的節點數時，這個節點