剑指offer 算法 （知识迁移能力2）

题目描述

输入一个递增排序的数组和一个数字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）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。