超全算法筆試模擬題精解合集_第1頁
超全算法筆試模擬題精解合集_第2頁
超全算法筆試模擬題精解合集_第3頁
超全算法筆試模擬題精解合集_第4頁
超全算法筆試模擬題精解合集_第5頁
已閱讀5頁,還剩312頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)

文檔簡介

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

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

評論

0/150

提交評論