41.和为S的连续正数序列

• 题目：小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!

输出描述:

输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序

• 思路：

双指针问题
当总和小于sum，大指针继续+
否则小指针+
当小指针>=大指针，输出结果

class Solution {
public:
    vector<vector<int> > FindContinuousSequence(int sum) {
        vector<vector<int> > allRes;
        int phigh = 2,plow = 1;
         
        while(phigh > plow){
            int cur = (phigh + plow) * (phigh - plow + 1) / 2;
            if( cur < sum)
                phigh++;
             
            if( cur == sum){
                vector<int> res;
                for(int i = plow; i<=phigh; i++)
                    res.push_back(i);
                allRes.push_back(res);
                plow++;
            }
             
            if(cur > sum)
                plow++;
        }
         
        return allRes;
    }
};

42.和为S的两个数字

• 题目：输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
• 思路：

假设：若b>a,且存在，
a + b = s;
(a - m ) + (b + m) = s
则：(a - m )(b + m)=ab - (b-a)m - mm* < ab；说明外层的乘积更小
也就是说依然是左右夹逼法！！！只需要2个指针
1.left开头，right指向结尾
2.如果和小于sum，说明太小了，left右移寻找更大的数
3.如果和大于sum，说明太大了，right左移寻找更小的数
4.和相等，把left和right的数返回

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum) {
        vector<int> result;
        int length = array.size();
        int start = 0;
        int end = length - 1;
        while (start < end)
        {
            if (array[start] + array[end] == sum)
            {
                result.push_back(array[start]);
                result.push_back(array[end]);
                break;
            }
            else if (array[start] + array[end] < sum)
                start++;
            else
                end--;
        }
        return result;
    }
};

43.左旋转字符串

• 题目：汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
• 思路：

class Solution {
public:
    string LeftRotateString(string str, int n) {
        int len = str.size();
        if(len == 0) return str;
        n %= len;//取余数防止无意义的循环位移
        for(int i = 0, j = n - 1; i < j; ++i, --j) swap(str[i], str[j]);
        for(int i = n, j = len - 1; i < j; ++i, --j) swap(str[i], str[j]);
        for(int i = 0, j = len - 1; i < j; ++i, --j) swap(str[i], str[j]);
        return str;
    }
};

44.翻转单纯顺序列

• 题目：牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
• 思路：

从前往后一直读取，遇到空格之后就把之前读取到的压到结果的前面并添加上空格。最后当循环结束，如果那个用来读取的字符串不为空，那么就再把它压到结果前，这次就不用再结果的最前面加空格了

//tmp是当前正在处理的单词，res是反转之后的句子。当一个单词结束后将它拼接到res的前面。
class Solution {
public:
    string ReverseSentence(string str) {
     string res = "", tmp = "";
        for(unsigned int i = 0; i < str.size(); ++i){
            if(str[i] == ' ') res = " " + tmp + res, tmp = "";
            else tmp += str[i];
        }
        if(tmp.size()) res = tmp + res;
        return res;
    }
};

45.扑克牌顺子

• 题目：LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_)...他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子.....LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。
• 思路：

考略到顺子的特性，最大值和最小值之差绝对为4，
然而又有大小王的存在，所以a[4]-a[jokers] <=4

class Solution {
public:
    bool IsContinuous( vector<int> numbers ) {
        int len=numbers.size();
        if(len!=5)  return false;
        sort(numbers.begin(),numbers.end());
        int jokers=0;//计算王的数目
        for(int i=0;i<5&&numbers[i]==0;i++){
            jokers++;
        }
        if(jokers>4) return false;
     
        for(int i=jokers+1;i<5;i++){
            if(numbers[i]==numbers[i-1])//判断对子的存在
                return false;
        }
        int dis=numbers[4]-numbers[jokers];
        if(dis<=4)   return true;
        return false;
    }
};

46.圆圈中最后剩下的数

• 题目：每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0...m-1报数....这样下去....直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)
  如果没有小朋友，请返回-1
• 思路：>http://zhedahht.blog.163.com/blog/static/2541117420072250322938/

class Solution {
public:
    int LastRemaining_Solution(int n, int m)
    {
        if(n==0)
            return -1;
        if(n==1)
            return 0;
        else
            return (LastRemaining_Solution(n-1,m)+m)%n;
    }
};

47.求1+2+3+...+n

• 题目：求1+2+3+...+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
• 思路：

1.需利用逻辑与的短路特性实现递归终止。
2.当n==0时，(n>0)&&((sum+=Sum_Solution(n-1))>0)只执行前面的判断，为false，然后直接返回0；
3.当n>0时，执行sum+=Sum_Solution(n-1)，实现递归计算Sum_Solution(n)。

class Solution {
public:
    int Sum_Solution(int n) {
        int sum = n;
        bool ans = (n>0)&&((sum+=Sum_Solution(n-1))>0);
        return sum;
    }
};

48.不用加减乘除左加法

• 题目：写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。。
• 思路：

相加各位 + 计算进位
十进制思想
5+7 各位相加：2 进位：10
2+10 12 0
12+0
二进制计算过程
5+7 各位相加：101^111=010 进位：101&111=101 (<<1=1010)
2+10 各位相加：010^1010=1000 进位：010&1010=010 <<1=0100
8+4 1000^0100=1100 1000&0100=0
12+0

class Solution {
public:
    int Add(int num1, int num2)
    {
        if (num2 == 0) return num1;
        return Add(num1^num2, (num1&num2)<<1 );
    }
};

49.把字符串转换成整数

• 题目：将一个字符串转换成一个整数(实现Integer.valueOf(string)的功能，但是string不符合数字要求时返回0)，要求不能使用字符串转换整数的库函数。 数值为0或者字符串不是一个合法的数值则返回0。

输入描述:

输入一个字符串,包括数字字母符号,可以为空

输出描述:

如果是合法的数值表达则返回该数字，否则返回0

输入

+2147483647
1a33

输出

2147483647
0

• 思路：

边界条件：
数据上下 溢出
空字符串
只有正负号
有无正负号
错误标志输出

class Solution {
public:
    int StrToInt(string str) {
        if(str.empty())
            return 0;
        int symbol = 1;
        if(str[0] == '-'){//处理负号
            symbol = -1;
            str[0] = '0'; //这里是‘0’ 不是0
        }else if(str[0] == '+'){//处理正号
            symbol = 1;
            str[0] = '0';
        }
        long long sum = 0;
        for(int i=0;i<str.size();++i){
            if(str[i] < '0' || str[i] > '9'){
                sum = 0;
                break;
            }
            sum = sum *10 + str[i] - '0';
            if( ((symbol>0) && (sum > 0x7FFFFFFF)) || ((symbol<0) && (sum > 0x80000000)) )
            {
                    sum=0;
                    break;
                }//处理溢出
        }
        return symbol * sum;
    }
};

50.数组中重复的数字

• 题目：在一个长度为n的数组里的所有数字都在0到n-1的范围内。 数组中某些数字是重复的，但不知道有几个数字是重复的。也不知道每个数字重复几次。请找出数组中任意一个重复的数字。 例如，如果输入长度为7的数组{2,3,1,0,2,5,3}，那么对应的输出是第一个重复的数字2。
• 思路：

不需要额外的数组或者hash table来保存，题目里写了数组里数字的范围保证在0 ~ n-1 之间，所以可以利用现有数组设置标志，当一个数字被访问过后，可以设置对应位上的数 + n，之后再遇到相同的数时，会发现对应位上的数已经大于等于n了，那么直接返回这个数即可。

class Solution {
public:
    // Parameters:
    //        numbers:     an array of integers
    //        length:      the length of array numbers
    //        duplication: (Output) the duplicated number in the array number
    // Return value:       true if the input is valid, and there are some duplications in the array number
    //                     otherwise false
    bool duplicate(int numbers[], int length, int* duplication) {
        for(int i=0;i!=length;++i){
        int index=numbers[i]%length;
        if(numbers[index]>=length){
            *duplication=index;
            return 1;
        }              
        numbers[index]+=length;  
    }
    return 0;
    }
};