6)三步排序
针对此题目的原理:left始终指向第一个0,left左侧均小于0;
right指向第一个大于0的数,right右侧均大于0;
mod指向此前的操作数,探兵;
填空为:
mod++;
补充快速排序模板:
void quick_sort(int arr[], int l, int r)
{
if (l >= r) return;
int i = l - 1, j = r + 1, x = arr[l + r >> 1];
while (i < j)
{
do i ++; while (arr[i] < x);
do j --; while (arr[j] > x);
if (i < j) swap(arr[i], arr[j]);
}
quick_sort(arr, l, j);
quick_sort(arr, j + 1, r);
}
7)错误票据
解题思路:考察的是在不知数据个数的前提下存储一个数组的方法,这里可以采用sstream库的优势,进行巧妙地转化,进而解决此题。
#include <iostream>
#include <sstream>
using namespace std;
const int maxn = 100000;
int data[maxn];
int line;
void s2i(string &str, int &data)
{
stringstream ss;
ss << str;
ss >> data;
}
int main()
{
int index = 0, dh, ch;
cin >> line;
getchar();
for (int i = 0; i < line; i++)
{
string s, temp;
getline(cin, s);
istringstream iss(s);
while (getline(iss, temp, ' '))
{
s2i(temp, data[index++]);
}
}
sort(data, data + index);
for (int i = 1; i < index; i++)
{
if (data[i] == data[i - 1] + 2)
dh = data[i] - 1;
if (data[i] == data[i - 1])
ch = data[i];
}
cout << dh << " " << ch << endl;
// getchar();
return 0;
}
8)翻硬币
解题思路:找规律,找到最开始不同的地方开始计数,找到最后一个不同的地方,两者坐标之差即为所求的答案。
#include <iostream>
#include <stdio.h>
#include <string.h>
using namespace std;
int main()
{
int ans = 0, flag = -1;
string s, temp;
getline(cin, s);
getline(cin, temp);
for (int i = 0; i < s.size(); i++)
{
if (s[i] != temp[i])
{
if (flag == -1)
{
flag = i;
}
else
{
ans += (i - flag);
flag = -1;
}
}
}
cout << ans;
// getchar();
return 0;
}
9)带分数
int i=atoi(字符串.c_str())//把字符串转换为整数
s.substr(begin,end);//从字符串s中截取特定长度的字符串
next_permutation()//全排列函数
注意:不能够反复的截取字符串,截取字符串会发生拷贝,新建串,申请内存空间,重新生成字符串,此时sunstr消耗的不是常数时间!
处理方法:
const char *str=s.c_str();
parse(*str,0,i);
int parse(const char *arr,int pos,int len)//pos位置,len串的长度
{
int ans=0,t=1;
for(int i =pos+len-1;i>=pos;i--)
{
ans+=(arr[i]-'0')*t;
t*=10;
}
return ans;
}
代码如下:
#include <algorithm>
#include <cstring>
#include <iostream>
#include <stdio.h>
using namespace std;
int init(const char *arr, int pos, int len)
{
int ans = 0, t = 1;
for (int i = len + pos - 1; i >= pos; i--)
{
ans += (arr[i] - '0') * t;
t *= 10;
}
return ans;
}
int main()
{
int n, ans = 0;
cin >> n;
string s = "123456789";
do
{
const char *str = s.c_str();
for (int i = 1; i <= 7; i++)
{
int aint = init(str, 0, i);
if (aint >= n)
break;
for (int j = 1; j <= 9 - i - 1; j++)
{
int bint = init(str, i, j);
int cint = init(str, i + j, 9 - i - j);
if (bint % cint == 0 && aint + bint / cint == n)
ans++;
}
}
} while (next_permutation(s.begin(), s.end()));
cout << ans << endl;
// getchar();
return 0;
}
10)连号区间数
解题思路:当读入一个序列后,根据题目给出的遍历顺序,先第一层循环i遍历数组,第二层循环j从第一层循环i开始遍历,如果i==j时,无疑需要加1,其次如果我们知道一个区间的最大值和最小值,根据连续且递增的规则,如果最大值和最小值之间的差值不等于区间长度,则此区间之间必少元素,反之,如果相等,则满足题意条件,此时ans++;
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int maxn = 50000 + 10;
int arr[maxn];
int n;
int main()
{
int ans = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> arr[i];
}
for (int i = 1; i <= n; i++)
{
int _min = arr[i];
int _max = arr[i];
for (int j = i; j <= n; j++)
{
if (arr[j] > _max)
_max = arr[j];
if (arr[j] < _min)
_min = arr[j];
if (i == j)
ans++;
else if (_max - _min + 1 == j - i + 1)
ans++;
}
}
cout << ans << endl;
return 0;
}