41. 和为S的两个数字
- 输入一个递增排序的数组和一个数字S，在数组中查找两个数，是的他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
- 对应每个测试案例，输出两个数，小的先输出。
// Solution:(1)固定一个数字，比较另一个——时间复杂度O(n^2);
// (2)前后两个index扫描，如果和大，则大数指针左移，如果和小，则小数指针又移，
// 根据乘积性质，能保证第一对输出的两个数乘积最小——时间复杂度O(n).
class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> res;
if (array.size() == 0)
return res;
int index_low = 0;
int index_high = array.size()-1;
while (index_low < index_high) {
if (array[index_low] + array[index_high] == sum) {
res.push_back(array[index_low]);
res.push_back(array[index_high]);
break;
} else if (array[index_low] + array[index_high] < sum) {
index_low ++;
} else {
index_high --;
}
}
return res;
}
};
42. 和为S的连续正数序列
- 输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
// Solution: 分析从small到big的和，small=1，big=2初始化，且small<(1+sum)/2
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> res;
vector<int> oneRes;
if (sum < 3) // 1+2=3
return res;
int small = 1;
int big = 2;
int middle = (1 + sum) / 2; // 和为sum时，small最大值
int curSum = small + big;
oneRes.push_back(small);
oneRes.push_back(big);
while (small < middle) {
if (curSum == sum) {
res.push_back(oneRes);
big ++; //改变big或small都可以
curSum += big;
oneRes.push_back(big);
} else if (curSum < sum) {
big ++;
curSum += big;
oneRes.push_back(big);
} else if (curSum > sum){
curSum -= small;
oneRes.erase(oneRes.begin());
small ++;
}
}
return res;
}
};
43. 翻转单词顺序
- 同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？
class Solution {
public:
string ReverseSentence(string str) {
if (str.size() == 0)
return "";
// 全部反转
Reverse(str, 0, str.size()-1);
// 反转单词
int start = 0, end = 0;
while (start < str.size()) {
if (str[start] == ' ') { //上个单词结尾
start ++;
end ++;
} else if (str[end] == ' ' || str[end] == '\0') {// 一个单词
Reverse(str, start, end-1);
start = end + 1;
end ++;
} else { // 固定start，寻找单词结尾
end ++;
}
}
return str;
}
void Reverse(string & str, int start, int end) {
while (start < end) {
swap(str[start ++], str[end --]);
}
}
};
44. 左旋字符串
- 对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
// Solution:类似上一题，将左右两部分当作两个单词，分别旋转，然后整个字符串旋转
class Solution {
public:
string LeftRotateString(string str, int n) {
if (str.size() < n)
return "";
Reverse(str, 0, n-1);
Reverse(str, n, str.size()-1);
Reverse(str, 0, str.size()-1);
return str;
}
void Reverse(string & str, int start, int end) {
while (start < end) {
swap(str[start ++], str[end --]);
}
}
};
n个筛子点数
problem
solution
code
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的运气如何。为了方便起见,你可以认为大小王是0。
// Solution:(1)先从小到大排序，然后统计0的个数、隔空的个数，
// 如果0个数<空个数或者数组中有重复非0数，则不是顺子;
// (2)是顺子需要满足两个条件，一是没有非零重复数字，二是max-min < 5/
class Solution {
public:
bool IsContinuous( vector<int> numbers ) {
if (numbers.size() == 0)
return false;
sort(numbers.begin(), numbers.end()); //小到大
int numOfZero = 0, numOfGap = 0;
// count zeros
for (int i = 0; i < numbers.size() && numbers[i] == 0; i ++)
numOfZero ++;
// count gaps and check double numbers
int low_index = numOfZero;
int high_index = low_index + 1;
while (high_index < numbers.size()) {
if (numbers[low_index] == numbers[high_index]) {
return false;
}
numOfGap += numbers[high_index] - numbers[low_index] -1;
low_index = high_index;
high_index ++;
}
return (numOfZero < numOfGap) ? false : true;
}
};
// Solution:(1)先从小到大排序，然后统计0的个数、隔空的个数，
// 如果0个数<空个数或者数组中有重复非0数，则不是顺子;
// (2)是顺子需要满足两个条件，一是没有非零重复数字，二是max-min < 5/
class Solution {
public:
bool IsContinuous( vector<int> numbers ) {
if (numbers.size() != 5)
return false;
int max = -1, min = 14, flag = 0;
for (int i = 0; i < numbers.size(); i ++) {
if (numbers[i] > 14 || numbers[i] < 0) return false;
if (numbers[i] == 0) continue;
if (((flag >> numbers[i]) & 1) == 1) return false; //重复
flag |= (1 << numbers[i]);
if (max < numbers[i]) max = numbers[i];
if (min > numbers[i]) min = numbers[i];
if (max - min >= 5) return false;
}
return true;
}
};
