和为S的连续正数序列
链接：https://www.nowcoder.com/questionTerminal/c451a3fd84b64cb19485dad758a55ebe 来源：牛客网
小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck!
输出描述:
输出所有和为S的连续正数序列。序列内按照从小至大的顺序，序列间按照开始数字从小到大的顺序
解题思路:
-
相当于公差为1的求和数列
-
采用双指针思想，当总和小于sum，大指针继续加，否则小指针继续加
实现代码
class Solution {
public:
vector<vector<int> > FindContinuousSequence(int sum) {
int pLow = 1,pHigh = 2;
vector<vector<int> > ans;
vector<int> temp;
while (pLow < pHigh) {
int cul = (pHigh + pLow) * (pHigh - pLow + 1) / 2; //对两个指针范围内的数求和
if (cul < sum) {
pHigh++;
}
if (cul == sum) {
for(int i = pLow;i <= pHigh; i++) {
temp.push_back(i);
}
pLow++;
ans.push_back(temp);
temp.clear(); //将vector清零
}
if (cul > sum) {
pLow++;
}
}
return ans;
}
};
左旋转字符串
链接：https://www.nowcoder.com/questionTerminal/12d959b108cb42b1ab72cef4d36af5ec 来源：牛客网
汇编语言中有一种移位指令叫做循环左移（ROL），现在有个简单的任务，就是用字符串模拟这个指令的运算结果。对于一个给定的字符序列S，请你把其循环左移K位后的序列输出。例如，字符序列S=”abcXYZdef”,要求输出循环左移3位后的结果，即“XYZdefabc”。是不是很简单？OK，搞定它！
解题思路
-
我自己的解法是将需要移动的字符剪切出来，在进行拼接
-
大牛的代码，用的是两次翻转字符串。
实现代码
//自己的代码
class Solution {
public:
string LeftRotateString(string str, int n) {
int len = str.size();
if(len < n) {
return ""; //不满足要求的n，需要返回"",不然过不去测试例(:
}
string ans,temp;
for(int i = 0;i < n;i++) {
ans.push_back(str[i]);
}
for(int i = n;i < len;i++) {
temp.push_back(str[i]);
}
ans = temp + ans;
return ans;
}
};
//大牛的代码
class Solution {
public:
string LeftRotateString(string str, int n) {
reverse(str.begin(), str.end());
reverse(str.begin(), str.begin() + str.size() - n);
reverse(str.begin() + str.size() - n, str.end());
return str;
}
};
数字在排序数组中出现的次数
统计一个数字在排序数组中出现的次数。
解题思路
- 自己的想法是用的历遍查找，实现起来确实很简单，但是没什么意义。发现大家都是用的二分法查找····
实现代码
class Solution {
public:
int GetNumberOfK(vector<int> data, int k) {
//return upper_bound(data.begin(), data.end(), k) - lower_bound(data.begin(), data.end(), k);//库函数
return upper(data, k) - lower(data, k);
}
private:
int lower(vector<int>& data, int num)
{
int x = 0, y = data.size();
while (x<y)
{
int mid = x + (y - x) / 2;
if (data[mid] >= num) y = mid;
else x = mid + 1;
}
return x;
}
int upper(vector<int>& data, int num)
{
int x = 0, y = data.size();
while (x<y)
{
int mid = x + (y - x) / 2;
if (data[mid] <= num) x = mid+1;
else y = mid;
}
return x;
}
};