題目來(lái)源：牛客網(wǎng)
題目一 和為S的連續(xù)正數(shù)序列
描述:
小明很喜歡數(shù)學(xué),有一天他在做數(shù)學(xué)作業(yè)時(shí),要求計(jì)算出9~16的和,他馬上就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個(gè)數(shù))。沒多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22。現(xiàn)在把問題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck! 輸出描述:輸出所有和為S的連續(xù)正數(shù)序列癞松。序列內(nèi)按照從小至大的順序，序列間按照開始數(shù)字從小到大的順序
解題思路: 代碼
- 定義兩個(gè)數(shù),start和end(分別為1和2);
- 定義currSum為從start到end序列的和;
- 先固定start,該變end的值;end增加,直到currSum>=sum改變start值換下一個(gè)循環(huán);
- 循環(huán)結(jié)束后,輸出所有的序列;
題目二 和為S兩個(gè)數(shù)字
描述: 輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S，在數(shù)組中查找兩個(gè)數(shù)鬼贱，使得他們的和正好是S，如果有多對(duì)數(shù)字的和等于S香璃，輸出兩個(gè)數(shù)的乘積最小的这难。
輸出描述:值小的那個(gè)先輸出
解題思路: 代碼
- 取遞增序列中第一個(gè)數(shù)start和最后一個(gè)數(shù)end;
- 如果start與end的和小于sum,start加一;
- 如果start與end的和大于sum,end減一;
- 如果start與end的和與sum相同,計(jì)算乘積; 如果乘積小于上一個(gè)相加等于sum的序列,則清除原序列,添加新序列,否則不變;
- 循環(huán)結(jié)束標(biāo)志:start>end; 輸出記錄的序列;
題目三 字符串左旋轉(zhuǎn)
描述: 匯編語(yǔ)言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個(gè)簡(jiǎn)單的任務(wù)葡秒，就是用字符串模擬這個(gè)指令的運(yùn)算結(jié)果雁佳。對(duì)于一個(gè)給定的字符序列S，請(qǐng)你把其循環(huán)左移K位后的序列輸出同云。例如糖权，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結(jié)果，即“XYZdefabc”炸站。是不是很簡(jiǎn)單星澳？OK，搞定它旱易！
解題思路: 代碼
- 解法一: 通過java實(shí)現(xiàn)字符串切割和拼接,這種做法可以,但是比較low;
- 解法二: 舉例:abcXYZdef
先將字符串分割成兩部分,abc和XYZdef. 分別將abc和XYZdef反轉(zhuǎn)得到字符串"cbafedZYX",再將所得到的字符串整體反轉(zhuǎn)得到XYZdefabc;
題目四 翻轉(zhuǎn)單詞順序列
描述:
沤耍客最近來(lái)了一個(gè)新員工Fish，每天早晨總是會(huì)拿著一本英文雜志阀坏，寫些句子在本子上如暖。同事Cat對(duì)Fish寫的內(nèi)容頗感興趣，有一天他向Fish借來(lái)翻看忌堂，但卻讀不懂它的意思盒至。例如，“student. a am I”士修。后來(lái)才意識(shí)到枷遂，這家伙原來(lái)把句子單詞的順序翻轉(zhuǎn)了，正確的句子應(yīng)該是“I am a student.”棋嘲。Cat對(duì)一一的翻轉(zhuǎn)這些單詞順序可不在行酒唉，你能幫助他么？
解題思路: 代碼
解題分為兩步:第一步：反轉(zhuǎn)整個(gè)句子沸移；第二步痪伦，按照空格侄榴，反轉(zhuǎn)單詞;
思路很簡(jiǎn)單,這里用到上一題的字符串反轉(zhuǎn)的函數(shù);
題目五 圓圈中最后剩下的數(shù)(約瑟夫環(huán))
描述:
每年六一兒童節(jié),NowCoder都會(huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為NowCoder的資深元老,自然也準(zhǔn)備了一些小游戲网沾。其中,有個(gè)游戲是這樣的:首先,讓小朋友們圍成一個(gè)大圈牲蜀。然后,他隨機(jī)指定一個(gè)數(shù)m,讓編號(hào)為0的小朋友開始報(bào)數(shù)。每次喊到m的那個(gè)小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個(gè)小朋友開始,繼續(xù)0...m-1報(bào)數(shù)....這樣下去....直到剩下最后一個(gè)小朋友,可以不用表演,并且拿到NowCoder名貴的“名偵探柯南”典藏版(名額有限哦!!_)绅这。請(qǐng)你試著想下,哪個(gè)小朋友會(huì)得到這份禮品呢涣达？
解題思路: 代碼
雖然鏈表在Java中很少用,但是這里定義了一個(gè)循環(huán)鏈表,使用循環(huán)鏈表解題比數(shù)組在運(yùn)算速度上快2~3倍;
- 定義一個(gè)循環(huán)鏈表,將總數(shù)添加到循環(huán)鏈表中;
- 循環(huán)遍歷鏈表,刪除第m個(gè)結(jié)點(diǎn);
- 直到最后一個(gè)結(jié)點(diǎn),返回該結(jié)點(diǎn)值;
題目六 求1+2+3+...+n
描述:
求1+2+3+...+n，要求不能使用乘除法证薇、for度苔、while、if浑度、else寇窑、switch、case等關(guān)鍵字及條件判斷語(yǔ)句（A?B:C）箩张。
解題思路: 代碼
只能用遞歸的方法;
- 讓當(dāng)n==0的時(shí)候終止繼續(xù)遞歸,返回sum值為0;
- 當(dāng)n>0的時(shí)候繼續(xù)執(zhí)行遞歸;
題目七 不用加減乘除做加法
描述:
寫一個(gè)函數(shù)甩骏，求兩個(gè)整數(shù)之和，要求在函數(shù)體內(nèi)不得使用+先慷、-饮笛、*、/四則運(yùn)算符號(hào)论熙。
解題思路: 代碼
題目八 字符串轉(zhuǎn)換為整數(shù)
描述:
將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)福青，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫(kù)函數(shù)。
解題思路: 代碼
- 先看符號(hào)位,然后從高位依次到低位進(jìn)行ASCII碼值的匹配;
題目九 數(shù)組中重復(fù)的數(shù)字
描述:
在一個(gè)長(zhǎng)度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)脓诡。 數(shù)組中某些數(shù)字是重復(fù)的无午，但不知道有幾個(gè)數(shù)字是重復(fù)的。也不知道每個(gè)數(shù)字重復(fù)幾次祝谚。請(qǐng)找出數(shù)組中任意一個(gè)重復(fù)的數(shù)字宪迟。 例如，如果輸入長(zhǎng)度為7的數(shù)組{2,3,1,0,2,5,3}交惯，那么對(duì)應(yīng)的輸出是重復(fù)的數(shù)字2或者3次泽。
解題思路: 代碼
- 將數(shù)組進(jìn)行快排;
- 遍歷數(shù)組,看相鄰的兩個(gè)數(shù)是否相等;
題目十 構(gòu)建乘積數(shù)組
描述:
給定一個(gè)數(shù)組A[0,1,...,n-1],請(qǐng)構(gòu)建一個(gè)數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]。不能使用除法商玫。
解題思路: 代碼
文字描述比較難懂.看代碼容易些:
- 計(jì)算前i-1個(gè)元素的乘積箕憾，及后n-i個(gè)元素的乘積, 分別保存在兩個(gè)數(shù)組中;
- 計(jì)算B[i]的值;
題目十一 表示數(shù)值的字符串
描述:
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）。例如拳昌，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是钠龙。
解題思路: 代碼
代碼給出的方法比較討巧,使用了java的庫(kù)函數(shù),以后有更好的方法繼續(xù)更新;
題目十二 字符流中第一個(gè)不重復(fù)的字符
描述:
請(qǐng)實(shí)現(xiàn)一個(gè)函數(shù)用來(lái)找出字符流中第一個(gè)只出現(xiàn)一次的字符炬藤。例如御铃，當(dāng)從字符流中只讀出前兩個(gè)字符"go"時(shí)，第一個(gè)只出現(xiàn)一次的字符是"g"沈矿。當(dāng)從該字符流中讀出前六個(gè)字符“google"時(shí)上真，第一個(gè)只出現(xiàn)一次的字符是"l"。 輸出描述:如果當(dāng)前字符流沒有存在出現(xiàn)一次的字符羹膳，返回#字符睡互。
解題思路: 代碼
將char一個(gè)一個(gè)存入list中,如果有重復(fù),則刪除元素,無(wú)重復(fù)則在list中添加元素;
題目十三 鏈表中環(huán)的入口結(jié)點(diǎn)
描述:
一個(gè)鏈表中包含環(huán)，請(qǐng)找出該鏈表的環(huán)的入口結(jié)點(diǎn)陵像。
解題思路: 代碼
- 解法一:使用兩個(gè)相鄰的指針,斷開每次的之前的節(jié)點(diǎn),當(dāng)前面的指針指向null時(shí),后面的指針即為環(huán)的入口結(jié)點(diǎn);
- 解法二:使用ArrayList,遍歷鏈表,將每個(gè)Node都存入List,如果list中存在該結(jié)點(diǎn),則該節(jié)點(diǎn)為環(huán)中的入口;
題目十四 刪除鏈表中重復(fù)的結(jié)點(diǎn)
描述:
在一個(gè)排序的鏈表中就珠，存在重復(fù)的結(jié)點(diǎn)，請(qǐng)刪除該鏈表中重復(fù)的結(jié)點(diǎn)醒颖，重復(fù)的結(jié)點(diǎn)不保留妻怎，返回鏈表頭指針。 例如泞歉，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
解題思路: 代碼
定義一個(gè)新的鏈表,讓新鏈表頭結(jié)點(diǎn)的下一個(gè)結(jié)點(diǎn)指向該鏈表的頭結(jié)點(diǎn);定義兩個(gè)新結(jié)點(diǎn),分別為新的鏈表的頭頭結(jié)點(diǎn)和原鏈表的頭結(jié)點(diǎn);在兩個(gè)新結(jié)點(diǎn)中執(zhí)行重復(fù)元素的覆蓋賦值;返回新鏈表頭結(jié)點(diǎn).next;
劍指Offer筆試題（5）
以上代碼全部托管在 Github
