題目描述

輸入一個遞增排序的數組和一個數字S，在數組中查找兩個數，是的他們的和正好是S，如果有多對數字的和等于S，輸出兩個數的乘積最小的。
輸出描述:

對應每個測試案例，輸出兩個數，小的先輸出。

解析：兩個指針，p1指向數組首，p2指向數組尾，判斷兩指針數據累加和，每當累加合為S則存入vector<vector<int>>vv數組，并保存乘積最小的乘積以及數組下標，累加和小于S則右移p1，大于S則左移p2，直到p1=p2.這個方法把全部符合累加和為S的數據對都存儲在了vector<vector<int>>vv數組中，需要的話能夠從vector<vector<int>>vv數組中取得全部符合的數據對。

class Solution { public:vector<int> FindNumbersWithSum(vector<int> array,int sum){vector< vector< int > > vv;vector< int > v;int length=array.size();if(length==0 || length==1)return v;vector <int>::iterator p1; vector <int>::iterator p2; p1=array.begin();p2=array.end()-1;int minMultiply=1000;//存放乘積最小值int indexMin=-1;//存放乘積最小值temp存放在vv里的下標int cnt=-1;while(*p1 < *p2){if(*p1 + *p2 == sum)//每求得一個存入vv里{cnt++;v.clear();v.push_back(*p1);v.push_back(*p2);vv.push_back(v);int multiply= *p1 * *p2;if(multiply < minMultiply)//乘積最小則存最小下標，替換最小乘積{minMultiply=multiply;indexMin=cnt;}p1++;}if(*p1 + *p2 < sum)//和小于sum則p1右移直到和大于或等于sump1++; if(*p1 + *p2 > sum)//和大于sum則p2左移直到和小于或等于sump2--;}if(cnt != -1)//找到,賦值v=vv[indexMin];return v;} };

題目描述

小明很喜歡數學,有一天他在做數學作業時,要求計算出9~16的和,他馬上就寫出了正確答案是100。但是他并不滿足于此,他在想究竟有多少種連續的正數序列的和為100(至少包括兩個數)。沒多久,他就得到另一組連續正數和為100的序列:18,19,20,21,22。現在把問題交給你,你能不能也很快的找出所有和為S的連續正數序列? Good Luck!
輸出描述:
輸出所有和為S的連續正數序列。序列內按照從小至大的順序，序列間按照開始數字從小到大的順序

解析：仿照上一題定義兩數：small和big，累加small到big，和為所求sum則把small到big之間的數存入數組，否則改變small與big的值 FindContinuousSequence1按開始數字從小到大的順序存儲
FindContinuousSequence2按開始數字從大到小的順序存儲
class Solution { public:vector<vector<int> > FindContinuousSequence1(int sum) {vector< vector< int > > array;vector< int > v;int big = 2 ;int small = 1 ;int addSum = 0 ;while( small != sum / 2 + 1 ){addSum=0;for( int i = small ;i <= big ; i ++ ){addSum += i;}if( addSum > sum ){small++;if( big == small )break;continue;}if( addSum < sum ){big++;continue;}if( addSum == sum ){v.clear();for(int j = small ; j <= big ; j ++ ){v.push_back(j);}array.push_back(v);small++;big++;continue;} }return array;} vector<vector<int> > FindContinuousSequence2(int sum)?{vector< vector< int > > array;vector< int > v;int big = sum / 2 + 1 ;int small = big-1 ;int addSum = 0 ;while( small > 0 ){addSum=0;for( int i = small ;i <= big ; i ++ ){addSum += i;}if( addSum > sum ){big--;if( big == small )small--;<span style="white-space:pre"> </span> <span style="white-space:pre"> </span>continue;}if( addSum < sum ){small--;continue;}if( addSum == sum ){v.clear();for(int j = small ; j <= big ; j ++ ){v.push_back(j);}array.push_back(v);<span style="white-space:pre"> </span>small--; <span style="white-space:pre"> </span>big--;continue;} ? ? ? ?}return array;} };

題目描述

JOBDU最近來了一個新員工Fish，每天早晨總是會拿著一本英文雜志，寫些句子在本子上。同事Cat對Fish寫的內容頗感興趣，有一天他向Fish借來翻看，但卻讀不懂它的意思。例如，“student. a am I”。后來才意識到，這家伙原來把句子單詞的順序翻轉了，正確的句子應該是“I am a student.”。Cat對一一的翻轉這些單詞順序可不在行，你能幫助他么？
解析：先翻轉每個字符，再逐個翻轉每個單詞 class Solution { public:void reverse(char *start,char *end){if(start==NULL || end==NULL)return;char temp;while(start < end){temp = *start;*start = *end;*end = temp;start ++;end --;}}string ReverseSentence(string str) {string str1;str1=str;if(str1.size() == 0)return str1;int length=str1.size();char *start=&str1[0];char *end=&str1[length-1];reverse(start,end);start=end=&str1[0];while(*start != '\0'){while(*end != ' ' && *end != '\0')end++;end--;//翻轉當前單詞reverse(start,end);//移動到下個單詞while(*start != ' ' && *start != '\0')start++;while(*end != ' ' && *end != '\0')end++;if(*start != '\0')//不是結尾，繼續{start++;end++;}}return str1;} };

題目描述

匯編語言中有一種移位指令叫做循環左移（ROL），現在有個簡單的任務，就是用字符串模擬這個指令的運算結果。對于一個給定的字符序列S，請你把其循環左移K位后的序列輸出。例如，字符序列S=”abcXYZdef”,要求輸出循環左移3位后的結果，即“XYZdefabc”。是不是很簡單？OK，搞定它！

解析：我們發現：左移n個字母 等價于 ：1、把先前n個字母反轉 2、把剩下的字母反轉 3、最后把全部字母反轉 。即三次reverse（）函數

class Solution { public:void reverse(char *start,char *end){if(start==NULL || end==NULL)return;char temp;while(start < end){temp = *start;*start = *end;*end = temp;start ++;end --;}}string LeftRotateString(string str, int n) {string str1;str1=str;if(str1.size() == 0 || n== 0)return str1;int length=str1.size();char *start = &str1[0];char *end = &str1[n-1];reverse(start,end);start=&str1[n];end=&str1[length-1];reverse(start,end);start=&str1[0];end=&str1[length-1];reverse(start,end);return str1;} };

總結

以上是生活随笔為你收集整理的剑指offer 算法 （知识迁移能力2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。