机试day4

博主： Xherlock
发布时间：2023 年 05 月 29 日
317 次浏览
暂无评论
300字数
分类： C/C++&机试

# 机试day4

## 找x

[找x_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/069e2130430c41229ab25e47fa0949a6?tpId=40&tqId=21489&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。

**输入描述**：

测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。

**输出描述**：

对于每组输入,请输出结果

~~~
输入：
2
1 3
0
输出：
-1
~~~

思路：直接一个个找

~~~c++
#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");
    }
}
~~~

## 查找

[查找_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/d93db01c2ee44e8a9237d63842aca8aa?tpId=40&tqId=21531&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

输入数组长度 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并二分查找

~~~c++
#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 其实更好，可以防止整型溢出的情况【但通常不会有那么多的数要排吧】

## 找最小数

[找最小数_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/ba91786c4759403992896d859e87a6cd?tpId=40&tqId=21530&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

第一行输入一个数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排序

~~~c++
#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)](https://www.nowcoder.com/practice/7fd72f8ac7964ba3b8baa8735246e1f1?tpId=40&tqId=21385&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

在一个整数数组上，对于下标为i的整数，如果它大于所有它相邻的整数， 或者小于所有它相邻的整数，则称该整数为一个极值点，极值点的下标就是i。

**输入描述**：

每个案例第一行为此数组元素个数k(4＜k＜80)，第二行是k个整数，每两个整数之间用空格分隔

**输出描述**：

每个案例输出为n个数字（其中n为该案例中极值点的个数）：每个数字对应相应数组的相应极值点下标值，下标值之间用空格分隔。

思路：就是一个判断呗

~~~c++
#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相同，说明没有找到相同的字符；找到就输出

~~~c++
#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);
        }
    }
}
~~~

最后修改：2023 年 05 月 29 日

如果觉得我的文章对你有用，请随意赞赏

发表评论取消回复

评论 *

私密评论

名称 *

🎲

邮箱 *

地址

Reverse（十一）
浏览次数: 2629
Win11新机鼓捣记录
浏览次数: 2382
栈~数制转换
浏览次数: 1604
C++学习
浏览次数: 1603
Python实现文件管理系统（重命名和删除）
浏览次数: 1575

顶点软件
你写得非常清晰明了，让我很容易理解你的观点。
mars
博主你好，请问怎么知道的alloc函数属于Buffer下的方法...
lj
该评论仅登录用户及评论双方可见
Mr.Guan
:@(赞一个)
Typecho
欢迎加入 Typecho 大家族

计算机网络和因特网（三）
浏览次数: 682
系统软件
浏览次数: 500
线程
浏览次数: 424
运输层（三）
浏览次数: 410
运输层（二）
浏览次数: 502

机试day4

Xherlock • 2023 年 05 月 29 日

# 机试day4

## 找x

[找x_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/069e2130430c41229ab25e47fa0949a6?tpId=40&tqId=21489&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

输入一个数n，然后输入n个数值各不相同，再输入一个值x，输出这个值在这个数组中的下标（从0开始，若不在数组中则输出-1）。

**输入描述**：

测试数据有多组，输入n(1<=n<=200)，接着输入n个数，然后输入x。

**输出描述**：

对于每组输入,请输出结果

~~~
输入：
2
1 3
0
输出：
-1
~~~

思路：直接一个个找

~~~c++
#include <iostream>
using namespace std;

## 查找

[查找_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/d93db01c2ee44e8a9237d63842aca8aa?tpId=40&tqId=21531&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

输入数组长度 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并二分查找

~~~c++
#include <iostream>
#include <algorithm>
using namespace std;

**注意**：mid = (low + high) / 2; 这里其实用 mid = low + (high - low) / 2 其实更好，可以防止整型溢出的情况【但通常不会有那么多的数要排吧】

## 找最小数

[找最小数_牛客题霸_牛客网 (nowcoder.com)](https://www.nowcoder.com/practice/ba91786c4759403992896d859e87a6cd?tpId=40&tqId=21530&tPage=1&rp=1&ru=/ta/kaoyan&qru=/ta/kaoyan/question-ranking)

**描述**

**输入描述**：

输入有多组数据。 每组输入n，然后输入n个整数对。

**输出描述**：

输出最小的整数对。

~~~
输入：
5  
3 3  
2 2  
5 5  
2 1  
3 6
输出：
2 1
~~~

思路：视为结构，并进行sort排序

~~~c++
#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;
    }
}

## 打印极值点下标

**描述**

在一个整数数组上，对于下标为i的整数，如果它大于所有它相邻的整数， 或者小于所有它相邻的整数，则称该整数为一个极值点，极值点的下标就是i。

**输入描述**：

每个案例第一行为此数组元素个数k(4＜k＜80)，第二行是k个整数，每两个整数之间用空格分隔

**输出描述**：

每个案例输出为n个数字（其中n为该案例中极值点的个数）：每个数字对应相应数组的相应极值点下标值，下标值之间用空格分隔。

思路：就是一个判断呗

~~~c++
#include <iostream>
using namespace std;

## 找位置

**描述**

对给定的一个字符串，找出有重复的字符，并给出其位置，如：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，不用的话实现起来挺困难的

~~~c++
#include <iostream>
using namespace std;

发表评论 取消回复

机试day4

发表评论取消回复