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;
}
};
