机试day4
找x
描述
输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。
输入描述：
测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。
输出描述：
对于每组输入,请输出结果
输入：
2
1 3
0
输出：
-1思路：直接一个个找
#include <iostream>
using namespace std;
int main() {
int n;
while(scanf("%d", &n)!=EOF) {
int a[n], x;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
scanf("%d", &x);
int i = 0;
for (; i < n; i++) {
if (a[i] == x) {
printf("%d\n", i);
break;
}
}
if (i == n)
printf("-1");
}
}查找
描述
输入数组长度 n 输入数组 a[1...n] 输入查找个数m 输入查找数字b[1...m] 输出 YES or NO 查找有则YES 否则NO 。
输入描述：
输入有多组数据。 每组输入n，然后输入n个整数，再输入m，然后再输入m个整数（1<=m,n<=100）。
输出描述：
如果在n个数组中输出YES否则输出NO。
输入：
5
1 5 2 4 3
3
2 5 6
输出：
YES
YES
NO思路：sort并二分查找
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
int n, m;
while(scanf("%d", &n)!=EOF) {
int a[n];
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a+n);
scanf("%d", &m);
for (int i = 0; i < m; i++) {
int x;
scanf("%d", &x);
int low = 0, high = n - 1;
while(low <= high) {
int mid = (low + high) / 2;
if (x == a[mid]) {
printf("YES\n");
break;
} else if (x < a[mid]) {
high = mid - 1;
} else {
low = mid + 1;
}
}
if (low > high)
printf("NO\n");
}
}
}注意：mid = (low + high) / 2; 这里其实用 mid = low + (high - low) / 2 其实更好，可以防止整型溢出的情况【但通常不会有那么多的数要排吧】
找最小数
描述
第一行输入一个数n，1 <= n <= 1000，下面输入n行数据，每一行有两个数，分别是x y。输出一组x y，该组数据是所有数据中x最小，且在x相等的情况下y最小的。
输入描述：
输入有多组数据。 每组输入n，然后输入n个整数对。
输出描述：
输出最小的整数对。
输入：
5
3 3
2 2
5 5
2 1
3 6
输出：
2 1思路：视为结构，并进行sort排序
#include <iostream>
#include <algorithm>
using namespace std;
struct Data {
int x, y;
};
bool compare(Data a, Data b) {
if (a.x == b.x) {
return a.y < b.y;
} else {
return a.x < b.x;
}
}
int main() {
int n;
while (scanf("%d", &n) != EOF) {
Data d[n];
for (int i = 0; i < n; i++) {
scanf("%d %d", &d[i].x, &d[i].y);
}
sort(d, d + n, compare);
printf("%d %d\n", d[0].x, d[0].y);
}
}打印极值点下标
打印极值点下标_牛客题霸_牛客网 (nowcoder.com)
描述
在一个整数数组上，对于下标为i的整数，如果它大于所有它相邻的整数， 或者小于所有它相邻的整数，则称该整数为一个极值点，极值点的下标就是i。
输入描述：
每个案例第一行为此数组元素个数k(4＜k＜80)，第二行是k个整数，每两个整数之间用空格分隔
输出描述：
每个案例输出为n个数字（其中n为该案例中极值点的个数）：每个数字对应相应数组的相应极值点下标值，下标值之间用空格分隔。
思路：就是一个判断呗
#include <iostream>
using namespace std;
int main() {
int k;
while (scanf("%d", &k) != EOF) {
int d[k];
for (int i = 0; i < k; i++)
scanf("%d", &d[i]);
if (d[0] != d[1])
printf("0 ");
for (int i = 1; i < k - 1; i++) {
if ((d[i - 1] < d[i] && d[i + 1] < d[i]) || (d[i - 1] > d[i] && d[i + 1] > d[i]))
printf("%d ", i);
}
if (d[k - 1] != d[k - 2])
printf("%d", k - 1);
printf("\n");
}
}找位置
描述
对给定的一个字符串，找出有重复的字符，并给出其位置，如：abcaaAB12ab12 输出：a，1；a，4；a，5；a，10，b，2；b，11，1，8；1，12， 2，9；2，13。
输入描述：
输入包括一个由字母和数字组成的字符串，其长度不超过100。
输出描述：
可能有多组测试数据，对于每组数据， 按照样例输出的格式将字符出现的位置标出。 1、下标从0开始。 2、相同的字母在一行表示出其出现过的位置。
输入：
abcaaAB12ab12
输出：
a:0,a:3,a:4,a:9
b:1,b:10
1:7,1:11
2:8,2:12思路：这题不简单，看了题解好多都用了c++的map、vector，不用的话实现起来挺困难的
但是依然能看到大佬不用这些就解决的思路，如下思路：每找到一个新的字符，去后面找所有和他相同的，找到设置为*，并每次找到后打印上一个，最后循环完，如果tmp的值仍和i相同，说明没有找到相同的字符；找到就输出
#include <iostream>
using namespace std;
int main() {
string s;
while (cin >> s) {
for (int i = 0; i < s.size(); i++) {
if (s[i] == '*')
continue;
int tmp = i;
for (int j = i + 1; j < s.size(); j++) {
if (s[j] == s[i]) {
s[j] = '*';
printf("%c:%d,", s[i], tmp);
tmp = j;
}
}
if (tmp != i)
printf("%c:%d\n", s[i], tmp);
}
}
}