劍指offer41到50題總覽：
- 和為S的連續(xù)正數(shù)序列
- 和為S的兩個(gè)數(shù)字
- 左旋轉(zhuǎn)字符串
- 反轉(zhuǎn)單詞順序列
- 撲克牌順子
- 孩子們的游戲(圓圈中最后留下的數(shù))
- 求1+2+3+...+n
- 不用加減乘除做加法
- 把字符串轉(zhuǎn)換成整數(shù)
- 數(shù)組中重復(fù)的數(shù)組
41、和為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ù)字從小到大的順序吴汪。
解題思路
一種方法是硬性計(jì)算寄摆，如sum=100蜈亩，則從50個(gè)數(shù)的和開始懦窘，如果是50個(gè)數(shù)的和，那么這50個(gè)數(shù)應(yīng)該是那些連續(xù)的數(shù)稚配，如果找不到則找49個(gè)數(shù)的和畅涂。直到發(fā)現(xiàn)8個(gè)數(shù)可以，100/8=12道川，100%8=4午衰，則這8個(gè)數(shù)的第8/2=4個(gè)數(shù)應(yīng)該是12立宜，第8個(gè)數(shù)應(yīng)該是16，并且這8個(gè)數(shù)都為正數(shù)臊岸，符合要求橙数。
另一種方法是雙指針技術(shù)，就是相當(dāng)于有一個(gè)窗口帅戒，窗口的左右兩邊就是兩個(gè)指針商模，我們根據(jù)窗口內(nèi)值之和來(lái)確定窗口的位置和寬度。通過(guò)等差數(shù)列的計(jì)算公式計(jì)算窗口內(nèi)數(shù)的和蜘澜，如果和<sum施流，則high++；如果和>sum鄙信，則low++瞪醋；如果和=sum，則將窗口內(nèi)的數(shù)加入list装诡，high++银受，再去尋找別的窗口。
import java.util.ArrayList;
public class Solution {
public ArrayList<ArrayList<Integer> > FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> final_list = new ArrayList<>();
int low = 1;//窗口左邊界
int high = 2;//窗口右邊界
while(low < high){
int n = (low+high)*(high-low+1)/2;//計(jì)算窗口內(nèi)數(shù)的和
if(n == sum){//和等于sum鸦采，將窗口內(nèi)的數(shù)加入list
ArrayList<Integer> list = new ArrayList<>();
for(int i=low; i<=high; i++) {
list.add(i);
}
final_list.add(list);
low++;//繼續(xù)尋找新窗口宾巍，右邊界high++;
}else if(n < sum){high++;}//窗口內(nèi)數(shù)的和小于sum，則high++;
else{low++;}//窗口內(nèi)數(shù)的和大于sum渔伯，則low++;
}
return final_list;
}
}
42顶霞、和為S的兩個(gè)數(shù)字
題目描述
輸入一個(gè)遞增排序的數(shù)組和一個(gè)數(shù)字S，在數(shù)組中查找兩個(gè)數(shù)锣吼，使得他們的和正好是S选浑，如果有多對(duì)數(shù)字的和等于S，輸出兩個(gè)數(shù)的乘積最小的玄叠。
輸出描述:
對(duì)應(yīng)每個(gè)測(cè)試案例古徒，輸出兩個(gè)數(shù)，小的先輸出读恃。
解題思路
如果有多組數(shù)和為S隧膘，則乘積最小的一定是兩個(gè)數(shù)的差值較大的那一組。設(shè)置兩個(gè)指針寺惫，一個(gè)左指針i疹吃，一個(gè)右指針j，第一個(gè)得到的和為S的一組一定是乘積最小的一組肌蜻。我們對(duì)左指針和右指針?biāo)傅臄?shù)的和進(jìn)行判斷互墓，如果和<sum，則i++蒋搜；如果和>sum篡撵，則j++判莉；如果和=sum，則返回i和i所指向的一組數(shù)育谬。
import java.util.ArrayList;
public class Solution {
public ArrayList<Integer> FindNumbersWithSum(int [] array,int sum) {
ArrayList<Integer> list = new ArrayList<>();
int i = 0;//左指針券盅，只能右移
int j = array.length-1;//右指針，只能左移
while(i <= j){
if(array[i] + array[j] == sum){//找到了第一個(gè)和為sum的一組數(shù)
list.add(array[i]);
list.add(array[j]);
break;
}else if (array[i] + array[j] > sum){//和>sum膛檀，則右指針左移锰镀，讓和小一點(diǎn)
--j;
}else{//和<sum，則左指針右移咖刃，讓和大一點(diǎn)
++i;
}
}
return list;
}
}
43泳炉、左旋轉(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，搞定它紧帕！
解題思路
方法很多盔然，可以將兩個(gè)abcXYZdef連起來(lái)，形成abcXYZdefabcXYZdef焕参，再取從n開始的轻纪，與原來(lái)的字符串一樣長(zhǎng)的子串。也可以將abcXYZdef分割成兩個(gè)子串a(chǎn)bc和XYZdef叠纷，再反向連接成XYZdefabc。
注意事項(xiàng)
- n可能大于str.length潦嘶。
public class Solution {
public String LeftRotateString(String str,int n) {
if(str.length() == 0 || str.length() == 1){
return str;
}else{
n = n%str.length();//n可能大于str的長(zhǎng)度
String back = str.substring(n); //提取子串的后半部分
String front = str.substring(0,n);//提取子串的前半部分
return back+front;//將后半部分提前涩嚣，連接兩個(gè)子串
}
}
}
44、反轉(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)這些單詞順序可不在行，你能幫助他么矫钓？
解題思路
方法很多要尔，一種方法是將串split，然后反向連接或用棧新娜；一種方法是先將每個(gè)單詞反轉(zhuǎn)赵辕，再將整個(gè)串反轉(zhuǎn)。也可以先整個(gè)串反轉(zhuǎn)概龄，再每個(gè)單詞反轉(zhuǎn)匆帚。
注意事項(xiàng)
- 用例中有輸入字符串為空格的情況。
public class Solution {
public String ReverseSentence(String str) {
if(str.length()<=1 || str.trim().equals("")){return str;}
char[] chars = str.toCharArray();
int pre_i=0;//上一個(gè)空格的下標(biāo)
int i = 0;//i用來(lái)尋找空格旁钧，遇到空格則將[pre_i, i-1]之間的字符反轉(zhuǎn)
while(i<chars.length){
if(chars[i] == ' '){//找到空格
reverse(chars, pre_i, i-1);//將[pre_i, i-1]之間的字符反轉(zhuǎn)
while(chars[i] == ' '){//這里其實(shí)不用循環(huán)只i++也可以吸重，為了防止有多個(gè)空格，用了循環(huán)歪今。用例中沒有多個(gè)空格的情況嚎幸。
i++;
}
pre_i = i;//更新上一個(gè)空格的下標(biāo)
}else{
i++;
}
}
reverse(chars, pre_i, i-1);//i=str.length但最后一個(gè)單詞還沒有反轉(zhuǎn)，反轉(zhuǎn)最后一個(gè)單詞
reverse(chars, 0, chars.length-1);//將整個(gè)串反轉(zhuǎn)
return new String(chars);將char數(shù)組轉(zhuǎn)化為String
}
public void reverse(char[] chars, int start, int end){
char temp;
while(start < end){//將頭尾指針指向的字符進(jìn)行交換
temp = chars[start];
chars[start] = chars[end];
chars[end] = temp;
start++;//頭指針+1
end--;//尾指針-1
}
}
}
45寄猩、撲克牌順子
題目描述
LL今天心情特別好,因?yàn)樗ベI了一副撲克牌,發(fā)現(xiàn)里面居然有2個(gè)大王,2個(gè)小王(一副牌原本是54張_)...他隨機(jī)從中抽出了5張牌,想測(cè)測(cè)自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿＜稻А！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13田篇。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”替废。LL決定去買體育彩票啦。 現(xiàn)在,要求你使用這幅牌模擬上面的過(guò)程,然后告訴我們LL的運(yùn)氣如何泊柬， 如果牌能組成順子就輸出true椎镣，否則就輸出false。為了方便起見,你可以認(rèn)為大小王是0兽赁。
解題思路
計(jì)算序列中0的個(gè)數(shù)状答，并將其他數(shù)排序，計(jì)算空檔的數(shù)量刀崖，如果0的個(gè)數(shù)不夠填補(bǔ)空檔惊科，則返回false。
import java.util.ArrayList;
import java.util.Collections;
public class Solution {
public boolean isContinuous(int [] numbers) {
if(numbers.length!=5){return false;}
int count_0 = 0;//計(jì)算0的個(gè)數(shù)
int vacancy = 0;//計(jì)算空檔的個(gè)數(shù)
ArrayList<Integer> list = new ArrayList<>();
for(int i=0; i<numbers.length; i++){
if(numbers[i] != 0){//將非0數(shù)加入list
list.add(numbers[i]);
}else{//計(jì)算0的個(gè)數(shù)
++count_0;
}
}
Collections.sort(list);//對(duì)非零數(shù)進(jìn)行排序
for(int i=1; i<list.size(); i++){//對(duì)list中的數(shù)遍歷亮钦，計(jì)算空檔的個(gè)數(shù)
if(list.get(i)-list.get(i-1) > 1){//有空檔馆截，計(jì)算有幾個(gè)空檔
vacancy += list.get(i) - list.get(i-1)-1;
}else if(list.get(i)-list.get(i-1) == 0){//如果出現(xiàn)對(duì)子，即相同數(shù)蜂莉，則一定不是順子蜡娶，返回false
return false;
}
}
if(vacancy>count_0){return false;}
else{return true;}
}
}
46混卵、孩子們的游戲(圓圈中最后留下的數(shù))
題目描述
每年六一兒童節(jié),牛客都會(huì)準(zhǔn)備一些小禮物去看望孤兒院的小朋友,今年亦是如此翎蹈。HF作為呕床ぃ客的資深元老,自然也準(zhǔn)備了一些小游戲。其中,有個(gè)游戲是這樣的:首先,讓小朋友們圍成一個(gè)大圈荤堪。然后,他隨機(jī)指定一個(gè)數(shù)m,讓編號(hào)為0的小朋友開始報(bào)數(shù)合陵。每次喊到m-1的那個(gè)小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個(gè)小朋友開始,繼續(xù)0...m-1報(bào)數(shù)....這樣下去....直到剩下最后一個(gè)小朋友,可以不用表演,并且拿到牛客名貴的“名偵探柯南”典藏版(名額有限哦!!_)澄阳。請(qǐng)你試著想下,哪個(gè)小朋友會(huì)得到這份禮品呢拥知？(注：小朋友的編號(hào)是從0到n-1)
解題思路
約瑟夫環(huán)問題。如果用數(shù)組碎赢，則注意判斷是否已經(jīng)出列低剔。用java的ArrayList可以，考慮到頻繁刪除肮塞，可用LinkedList襟齿。
import java.util.LinkedList;
public class Solution {
public int LastRemaining_Solution(int n, int m) {
if(n == 0){return -1;}
if(n == 1){return 0;}
LinkedList<Integer> list = new LinkedList<>();
for(int i=0; i<n; i++){//所有數(shù)入LinkedList
list.add(i);
}
int current_index = 0;//當(dāng)前下標(biāo)
while(list.size()>1){
current_index = (current_index + m -1) % list.size();//每次current_index指向的小朋友就是喊0的小朋友，所以最后一個(gè)小朋友只需往后走m-1步枕赵。
list.remove(current_index);//刪除喊m-1的小朋友
}
return(list.get(0));//返回最后的一個(gè)小朋友的下標(biāo)
}
}
47、求1+2+3+...+n
題目描述
求1+2+3+...+n拷窜，要求不能使用乘除法开皿、for、while篮昧、if赋荆、else、switch懊昨、case等關(guān)鍵字及條件判斷語(yǔ)句（A?B:C）窄潭。
解題思路
利用短路求值原理原理，在做&&與運(yùn)算的時(shí)候疚颊，一旦前面的條件判斷為假狈孔，則后面的條件就不進(jìn)行運(yùn)算。
public class Solution {
public int Sum_Solution(int n) {
int sum = n;
boolean flag = (sum>1) && ((sum += Sum_Solution(n-1)) > 0);//遞歸計(jì)算材义，這里有人寫的是sum>0，計(jì)算結(jié)果是一樣的嫁赏。
return sum;
}
}
48其掂、不用加減乘除做加法
題目描述
寫一個(gè)函數(shù)，求兩個(gè)整數(shù)之和潦蝇，要求在函數(shù)體內(nèi)不得使用+款熬、-深寥、*、/四則運(yùn)算符號(hào)贤牛。
解題思路
此題就是需要我們用位運(yùn)算實(shí)現(xiàn)加法惋鹅。主要用到與運(yùn)算、移位和異或運(yùn)算殉簸。
如計(jì)算5->101闰集，7->111
與運(yùn)算101&111=101，左移一位(101&111)<<1=1010般卑，得到進(jìn)位值武鲁。
異或運(yùn)算101^111=010，得到不算進(jìn)位蝠检，各位應(yīng)該得到的值沐鼠。
之后我們應(yīng)該將與運(yùn)算得到的進(jìn)位值1010和異或運(yùn)算得到的結(jié)果010相加，得到最終結(jié)果叹谁。這樣相加依然會(huì)有進(jìn)位值饲梭，我們將1010和010看作新的需要計(jì)算和的兩個(gè)數(shù)，繼續(xù)計(jì)算他們的與和異或焰檩，直到與運(yùn)算得到的進(jìn)位值為0為止憔涉。
public class Solution {
public int Add(int num1,int num2) {
while(num2 != 0){//num2為與運(yùn)算和位移運(yùn)算的結(jié)果，即進(jìn)位值锅尘。
int xor = num1 ^ num2;//異或運(yùn)算监氢，得到不進(jìn)位應(yīng)該得到的值
int and = (num1 & num2) << 1;//與運(yùn)算和位移運(yùn)算，計(jì)算得到進(jìn)位值
num1 = xor;//將不進(jìn)位得到的值看作新的num1
num2 = and;//將進(jìn)位值看作新的num2藤违，重復(fù)以上操作浪腐，直到進(jìn)位值為0
}
return num1;//進(jìn)位值num2為0，則num1即為我們要得到的兩數(shù)之和顿乒。
}
}
49议街、把字符串轉(zhuǎn)換成整數(shù)
題目描述
將一個(gè)字符串轉(zhuǎn)換成一個(gè)整數(shù)(實(shí)現(xiàn)Integer.valueOf(string)的功能，但是string不符合數(shù)字要求時(shí)返回0)璧榄，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫(kù)函數(shù)特漩。 數(shù)值為0或者字符串不是一個(gè)合法的數(shù)值則返回0。
輸入描述:
輸入一個(gè)字符串,包括數(shù)字字母符號(hào),可以為空
輸出描述:
如果是合法的數(shù)值表達(dá)則返回該數(shù)字骨杂，否則返回0
解題思路
難在要考慮很多奇怪的情況涂身。
注意事項(xiàng)
- 用例中有-2147483648這個(gè)用例，而int的最大值是2147483647搓蚪，-2147483648無(wú)法通過(guò)2147483648取反得到蛤售。
import java.util.ArrayList;
public class Solution {
public int StrToInt(String str) {
if(str.length() == 0){return 0;}
char[] chars = str.toCharArray();
boolean neg = false;//是否為負(fù)值
int index = 0;//index為整數(shù)真正開始的地方，跳過(guò)正負(fù)號(hào)，跳過(guò)數(shù)前面所有的0
if(chars[0]=='-'){//如果第一個(gè)字符為負(fù)號(hào)悴能，則index+1
index = 1;
neg = true;
}else if(chars[0]=='+'){//如果第一個(gè)字符為正號(hào)揣钦，index+1
index = 1;
}//如果沒有正負(fù)號(hào)，則為正數(shù)漠酿。index=0
if(index>=chars.length){return 0;}//如果字符串為“+”或“-”就結(jié)束了冯凹，則返回0
//遍歷后面的每個(gè)字符，跳過(guò)前面的0炒嘲，確定index的值宇姚。
while(chars[index] < '1' || chars[index] > '9'){
if(chars[index] == '0' && index+1<chars.length){//如果遇到了1-9之外的數(shù)，但這個(gè)數(shù)是0摸吠，且0后面還有數(shù)空凸，則index++
++index;
}else{
return 0;//如果遇到了1-9之外的數(shù)，1.這個(gè)數(shù)是0寸痢，但0后面沒有數(shù)了呀洲，則轉(zhuǎn)換為整數(shù)的結(jié)果就是0。2.這個(gè)數(shù)不是0啼止，是0-9以外的符號(hào)道逗，不管后面是否還有數(shù)，都不符合轉(zhuǎn)換規(guī)則
}
}
ArrayList<Integer> num_list = new ArrayList<>();//將可用數(shù)字加入list
for(int i=index; i<chars.length; i++){//遍歷0后面的所有字符
if(chars[i] < '0' || chars[i] > '9'){//如果是0-9以外的字符献烦，則不符合轉(zhuǎn)換條件
return 0;
}else{
num_list.add(chars[i]-48);//將字符轉(zhuǎn)化為int滓窍，加入list
}
}
int sum = 0;
for(int i=0; i<num_list.size(); i++){//將list中的數(shù)加起來(lái)
if(neg){
sum -= num_list.get(i)*Math.pow(10,(num_list.size()-1-i));
}else{
sum += num_list.get(i)*Math.pow(10,(num_list.size()-1-i));
}
}
return sum;
}
}
50、數(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)的輸出是第一個(gè)重復(fù)的數(shù)字2跺嗽。
解題思路
設(shè)置一個(gè)與數(shù)組長(zhǎng)度一樣的boolean數(shù)組arr，全部置為false页藻。遍歷每一個(gè)數(shù)桨嫁，如遇到第一個(gè)2，則將arr[2]置為true份帐；遇到第一個(gè)3璃吧，則將arr[3]置為true，直到遇到第二個(gè)2废境，發(fā)現(xiàn)arr[2]已經(jīng)置為true肚逸，則將2賦值給duplication[0]爷辙，返回true彬坏。
public boolean duplicate(int numbers[],int length,int [] duplication) {
if(length == 0){//不知道用例是怎么寫的朦促，這里寫numbers.length==0會(huì)發(fā)生空指針異常
duplication[0] = -1;
return false;
}
boolean[] arr = new boolean[length];//設(shè)置一個(gè)是否訪問的登場(chǎng)數(shù)組
for(int i=0; i<arr.length; i++){//全部設(shè)置為false
arr[i] = false;
}
for(int i=0; i<numbers.length; i++){
if(arr[numbers[i]] == false){//如果沒有訪問則置為true
arr[numbers[i]] = true;
}else{
duplication[0] = numbers[i];//如果已經(jīng)訪問，則賦值給duplication[0]栓始，返回true
return true;
}
}
return false;
}
}
結(jié)尾
如果您發(fā)現(xiàn)我的文章有任何錯(cuò)誤务冕，或?qū)ξ业奈恼掠惺裁春玫慕ㄗh，請(qǐng)聯(lián)系我幻赚！如果您喜歡我的文章禀忆，請(qǐng)點(diǎn)喜歡~*我是藍(lán)白絳，感謝你的閱讀落恼！
