4621 字
23 分钟
西邮移动应用开发实验室二面题解
2025-04-04
工程
CSDN

B2110 找第一个只出现一次的字符#

题目描述#

给定一个只包含小写字母的字符串，请你找到第一个仅出现一次的字符。如果没有，输出 no。

输入格式#

一个字符串，长度小于

11001100

1100

。

输出格式#

输出第一个仅出现一次的字符，若没有则输出 no。

输入输出样例 #1#

输入 #1#
abcabd
##### 输出 #1

c

输入输出样例 #2#

输入 #2#
aabbcc
##### 输出 #2

no

解题思路#

很常见的哈希，先遍历字符串统计每个字母出现的次数，再按顺序找出第一个出现一次的字符串

解题代码#

哈希数组

#include <iostream>
using namespace std;


int main() {
    string s;
    cin >> s;
    int num[26];
    for (int i = 0; i < 26; i++) {
        num[i] = 0;
    }
    for (int i = 0; i < s.size(); i++) {
        num[s[i] - 'a']++;
    }
    for (char c : s) {
        if (num[c - 'a'] == 1) {
            cout << c << endl;
            return 0;
        }
    }
    cout << "no" << endl;
    return 0;
}
### 补充




#### 当我们需要快速的查找，去重或映射关系时，我们常用到哈希表。




常见的三种哈希结构：




- 数组
- set（集合）
- map（映射）


数组就是简单的哈希表，一些场景就是为数组量身定做的。但需要注意，数组的大小是有限的




在题中可以确定，数组的大小仅需为26（26个字母），用map确实可以，但使用map的空间消耗要比数组大一些，因为map要维护红黑树或者符号表，而且还要做哈希函数的运算。所以数组更加简单直接有效。




## B2136 素数回文数的个数




### 题目描述




求




1111




11




 到




nn




n




 之间（包括




nn




n




），既是素数又是回文数的整数有多少个。




#### 输入格式




一个大于




1111




11




 小于




1000010000




10000




 的整数




nn




n




。




#### 输出格式




1111




11




 到




nn




n




 之间的素数回文数个数。




#### 输入输出样例 #1




##### 输入 #1

23

输出 #1#
1
#### 说明/提示




回文数指左右对称的数，如：




1111




11




，




1212112121




12121




### 解题思路




本题需要判断一个数是否同时满足两个条件：


1.  是素数（只能被 1 和自身整除）。


2.  是回文数（正序与倒序相同）。




### 解题代码




```cpp
#include<iostream>
using namespace std;
bool palindrome (int n) {
    int a[10];
    int i = 0;
    while(n) {
        a[i++] = n % 10;
        n /= 10;
    }
    for (int j = 0; j < i / 2; j++) {
        if (a[j] != a[i - j - 1]) {
          return false;
        }
    }
    return true;
}
bool isPrime(int n) {
    if (n < 2) {
      return false;
    }
    for (int i = 2; i <= n / i; i++) {
        if (n % i == 0) {
          return false;
        }
    }
    return true;
}
int main() {
    int n;
    int cnt = 0;
    cin >> n;
    for (int i = 11; i <= n;i++) {
        if (palindrome(i) && isPrime(i)) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

B2111 基因相关性#

题目描述#

为了获知基因序列在功能和结构上的相似性，经常需要将几条不同序列的 DNA 进行比对，以判断该比对的 DNA 是否具有相关性。

现比对两条长度相同的 DNA 序列。首先定义两条 DNA 序列相同位置的碱基为一个碱基对，如果一个碱基对中的两个碱基相同的话，则称为相同碱基对。接着计算相同碱基对占总碱基对数量的比例，如果该比例大于等于给定阈值时则判定该两条 DNA 序列是相关的，否则不相关。

输入格式#

有三行，第一行是用来判定出两条 DNA 序列是否相关的阈值，随后

22

2

行是两条 DNA 序列（长度不大于

500500

500

）。

输出格式#

若两条 DNA 序列相关，则输出 yes，否则输出no。

输入输出样例 #1#

输入 #1#
0.85
ATCGCCGTAAGTAACGGTTTTAAATAGGCC
ATCGCCGGAAGTAACGGTCTTAAATAGGCC
##### 输出 #1

yes

解题思路#

读取两条 DNA 序列：用 string 类型存储，后计算相同碱基对的比例。
若相同比例 >= 阈值，输出 "yes"，否则输出 "no"。
### 解题代码




```cpp
#include <iostream>
using namespace std;
int main() {
    double n;
    cin >> n;
    string s1;
    string s2;
    cin >> s1;
    cin >> s2;
    int cnt = 0;
    for (int i = 0; i < s1.size(); i++) {
        if (s1[i] == s2[i]) {
            cnt++;
        }
    }
    double res = (double)cnt / s1.size();
    if (res >= n) {
        cout << "yes" << endl;
    } else {
        cout << "no" << endl;
    }
    return 0;
}

P1152 欢乐的跳#

题目描述#

一个

nn

n

个元素的整数数组，如果数组两个连续元素之间差的绝对值包括了

[1,n−1][1,n-1]

[

1

,

n

−

1

]

之间的所有整数，则称之符合“欢乐的跳”，如数组

{1,4,2,3}{1,4,2,3}

{

1

,

4

,

2

,

3

}

符合“欢乐的跳”，因为差的绝对值分别为：

3,2,13,2,1

3

,

2

,

1

。

给定一个数组，你的任务是判断该数组是否符合“欢乐的跳”。

输入格式#

每组测试数据第一行以一个整数

n(1≤n≤1000)n(1 \le n \le 1000)

n

(

1

≤

n

≤

1000

)

开始，接下来

nn

n

个空格隔开的在

[−108,108][-10^8,10^8]

[

−

1

0

8

,

1

0

8

]

之间的整数。

输出格式#

对于每组测试数据，输出一行若该数组符合“欢乐的跳”则输出 Jolly，否则输出 Not jolly。

输入输出样例 #1#

输入 #1#
4 1 4 2 3
##### 输出 #1

Jolly

输入输出样例 #2#

输入 #2#
5 1 4 2 -1 6
##### 输出 #2

Not jolly

说明/提示#

1≤n≤10001 \le n \le 1000

1

≤

n

≤

1000

解题思路#

本题的核心是判断连续元素的差值的绝对值是否形成

[1,n−1][1, n-1]

[

1

,

n

−

1

]

的完整集合。

  • 若 n = 1，默认符合 “欢乐的跳”（因为没有差值）。
  • 计算 |a[i] - a[i-1]| 并存入哈希map。
  • 判断是否包含所有整数 1 到 n-1。

解题代码#

#include <iostream>
#include <unordered_map>        //不要忘了加这个头文件
#include <vector>
#include <cmath>
using namespace std;


int main() {
    int n;
    cin >> n;
    vector<int> nums(n);
    unordered_map<int, int> s;


    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }


    for (int i = 1; i < n; i++) {
        int diff = abs(nums[i] - nums[i - 1]); //abs用于计算绝对值
        if (diff >= 1 && diff < n) {
            s[diff] = 1;
        }
    }


    for (int i = 1; i < n; i++) {
        if (s.count(i) == 0) {
            cout << "Not jolly" << endl;
            return 0;
        }
    }


    cout << "Jolly" << endl;
    return 0;
}
### 补充




#### unordered_map




unordered_map 是 C++ STL（标准模板库）中提供的一个容器，用于存储键值对（key-value pairs）。与 map 不同，unordered_map 使用哈希表（hash table）来存储元素，因此它的元素是无序的。unordered_map 提供的查找、插入和删除操作




##### 常见操作：




插入元素：


•  使用 [] 运算符：umap[key] = value;


•  使用 insert 方法：umap.insert({key, value});




查找元素：


•  使用 find 方法：umap.find(key);


•  find 返回一个迭代器，如果元素存在，返回指向该元素的迭代器；否则，返回 umap.end()。




删除元素：


•  使用 erase 方法：umap.erase(key); 删除某个键值对。


•  也可以删除指定范围的元素，或通过迭代器删除。




访问元素：


•  使用 [] 运算符：umap[key]，如果键不存在，会自动插入一个值为 T()（类型 T 的默认值）的元素。


•  使用 at() 方法：umap.at(key)，如果键不存在，会抛出 out_of_range 异常。




检查元素是否存在：


•  使用 find 方法，返回值与 end() 比较。


•  使用 count 方法：umap.count(key)，如果键存在返回 1，否则返回 0。




## B2092 开关灯




### 题目描述




假设有




NN




N




 盏灯（




NN




N




 为不大于




50005000




5000




 的正整数），从




11




1




 到




NN




N




 按顺序依次编号，初始时全部处于开启状态；第一个人（




11




1




 号）将灯全部关闭，第二个人（




22




2




 号）将编号为




22




2




 的倍数的灯打开，第三个人（




33




3




 号）将编号为




33




3




 的倍数的灯做相反处理（即，将打开的灯关闭，将关闭的灯打开）。依照编号递增顺序，以后的人都和




33




3




 号一样，将凡是自己编号倍数的灯做相反处理。问当第




NN




N




 个人操作完之后，有哪些灯是关闭着的？




#### 输入格式




输入为一行，一个整数




NN




N




，为灯的数量。




#### 输出格式




输出为一行，按顺序输出关着的灯的编号。编号与编号之间间隔一个空格。




#### 输入输出样例 #1




##### 输入 #1

10

输出 #1#
1 4 9
#### 输入输出样例 #2




##### 输入 #2

5

输出 #2#

1 4
### 解题思路




依题，操作数为偶数时，灯光为开启状态（不变），操作数为基数时，灯光熄灭。


操作数和其因子数量有关，由此不难得出，只有编号为完全平方数的灯最终才会是关闭的


eg:  4的因子为1，2，4（3个）




### 解题代码




```cpp
#include <iostream>
#include <cmath>
using namespace std;


int main() {
    int N;
    cin >> N;
    for (int i = 1; i * i <= N; i++) {
        cout << i * i << " ";
    }
    cout << endl;
    return 0;
}

B2140 二进制分类#

题目描述#

若将一个正整数化为二进制数，在此二进制数中，我们将数字

11

1

的个数多于数字

00

0

的个数的这类二进制数称为

AA

A

类数，否则就称其为

BB

B

类数。

例如：

(13)10=(1101)2(13)_{10}=(1101)_2

(

13

)

10

​

=

(

1101

)

2

​

，其中

11

1

的个数为

33

3

，

00

0

的个数为

11

1

，则称此数为

AA

A

类数；

(10)10=(1010)2(10)_{10}=(1010)_2

(

10

)

10

​

=

(

1010

)

2

​

，其中

11

1

的个数为

22

2

，

00

0

的个数也为

22

2

，称此数为

BB

B

类数；

(24)10=(11000)2(24)_{10}=(11000)_2

(

24

)

10

​

=

(

11000

)

2

​

，其中

11

1

的个数为

22

2

，

00

0

的个数为

33

3

，则称此数为

BB

B

类数；

程序要求：求出 1~n 之中（

1≤n≤10001 \le n \le 1000

1

≤

n

≤

1000

），全部

A,BA,B

A

,

B

两类数的个数。

输入格式#

输入

nn

n

。

输出格式#

一行，包含两个整数，分别是

AA

A

类数和

BB

B

类数的个数，中间用单个空格隔开。

输入输出样例 #1#

输入 #1#
7
##### 输出 #1

5 2

解题思路#

本题无复杂思维逻辑，进行代码实现即可

解题代码#

#include<iostream>
using namespace std;
int tentotwo(int n) {
    int res = 0;
    int t = 1;
    while(n) {
        res += (n % 2) * t;
        t *= 10;
        n /= 2;
    }
    return res;
}
bool AorB(int res) {
    int cnt1 = 0;
    int cnt2 = 0;
    while(res) {
        if(res % 10 == 1) {
            cnt1++;
        } else {
            cnt2++;
        }
        res /= 10;
    }
    if(cnt1 > cnt2) {
        return true;
    } else {
        return false;
    }
}
int main() {
    int n;
    cin >> n;
    int res = tentotwo(n);
    int cnta = 0;
    int cntb = 0;
    for (int i = 1; i <= n; i++) {
        int temp = tentotwo(i);
        if(AorB(temp)) {
            cnta++;
        } else {
            cntb++;
        }
    }
    cout << cnta << " " << cntb << endl;
    return 0;
}

B3639 T2 点亮灯笼#

题目背景#

请尽量在 20min 之内写完题目。这是指「写代码」的时间；「读题」时间不计算在内。

题目描述#

有

nn

n

个灯笼环形摆放。最开始，这些灯笼都是关闭的状态。

操作台上有

nn

n

个按钮，按下第

xx

x

个按钮时，会反转灯笼

xx

x

以及相邻两个灯笼的状态。「反转」是指关闭变成点亮、点亮变成关闭。

举一个例子：如果按下第

55

5

个按钮，则

44

4

、

55

5

、

66

6

号灯笼都会反转；如果按下第

nn

n

个按钮，则

n−1,n,1n-1, n, 1

n

−

1

,

n

,

1

这三个灯笼状态反转。这是因为灯笼放置为环形，

n−1n-1

n

−

1

和

11

1

是与

nn

n

相邻的灯笼。

我们依次按下了一些按钮。你需要编程求出当我们的操作完成后，最终这些灯笼的状态。

输入格式#

第一行，两个正整数

n,mn, m

n

,

m

，分别表示共有

nn

n

个灯笼、我们按了

mm

m

次按钮。

接下来

mm

m

行，每行一个正整数，表示我们在那一次操作中按下了哪个按钮。

输出格式#

仅一行，

nn

n

个整数，依次表示

nn

n

个灯笼的状态，用空格隔开。以 0 代表灯笼关闭，以 1 代表灯笼点亮。

输入输出样例 #1#

输入 #1#
5 4
1
3
1
2
##### 输出 #1

1 0 0 1 0

说明/提示#

样例解释#

灯笼序列的状态如下：

0 0 0 0 0  # 初始状态
1 1 0 0 1  # 按下 1 之后的状态
1 0 1 1 1  # 按下 3 之后的状态
0 1 1 1 0  # 按下 1 之后的状态
1 0 0 1 0  # 按下 2 之后的状态

因此你应当输出 1 0 0 1 0。

数据规模与约定#

对于

100%100%

100%

的数据，有

n≤1000n\leq 1000

n

≤

1000

，

m≤1000m\leq 1000

m

≤

1000

。

解题思路#

我们可以用一个长度为 n 的数组来记录每个灯笼的状态，初始全部为 0。每次按下一个按钮时，我们就将对应灯笼以及它的左右相邻灯笼的状态取反（0 变 1，1 变 0）。由于是环形排列，需要注意边界处理，比如第一个灯笼的“左边”是第 n 个灯笼。

解题代码#

#include<iostream>
using namespace std;


int main() {
    int n, m;
    cin >> n >> m;


    int lanterns[1005] = {0};


    for (int i = 0; i < m; i++) {
        int x;
        cin >> x;
        int left = (x - 2 + n) % n;
        int mid = (x - 1);
        int right = x % n;


        lanterns[left] ^= 1;
        lanterns[mid] ^= 1;
        lanterns[right] ^= 1;
    }


    for (int i = 0; i < n; i++) {
        cout << lanterns[i];
        if (i != n - 1) {
          cout << " ";
        }
    }
    cout << endl;
    return 0;
}
### 补充




#### 关于位运算




题中取反操作也就是：0变成1， 1变成0 。代码中我们用到的是这个   ^=      符号，这叫做按位异或。


假设 a 是一个灯笼状态，只有两个可能值：




a 1 a^1 说明 0 1 1 0^1 = 1 1 1 0 1^1 = 0


所以 a ^= 1 的效果刚好就是“取反”。若实在不理解，以下方式依旧可以：（只是不够优雅）




```cpp
if (lanterns[i] == 0)
    lanterns[i] = 1;
else
    lanterns[i] = 0;

P2249 【深基13.例1】查找#

题目描述#

输入

nn

n

个不超过

10910^9

1

0

9

的单调不减的（就是后面的数字不小于前面的数字）非负整数

a1,a2,…,ana_1,a_2,\dots,a_{n}

a

1

​

,

a

2

​

,

…

,

a

n

​

，然后进行

mm

m

次询问。对于每次询问，给出一个整数

qq

q

，要求输出这个数字在序列中第一次出现的编号，如果没有找到的话输出

−1-1

−

1

。

输入格式#

第一行

22

2

个整数

nn

n

和

mm

m

，表示数字个数和询问次数。

第二行

nn

n

个整数，表示这些待查询的数字。

第三行

mm

m

个整数，表示询问这些数字的编号，从

11

1

开始编号。

输出格式#

输出一行，

mm

m

个整数，以空格隔开，表示答案。

输入输出样例 #1#

输入 #1#
11 3
1 3 3 3 5 7 9 11 13 15 15
1 3 6
##### 输出 #1

1 2 -1

说明/提示#

数据保证，

1≤n≤1061 \leq n \leq 10^6

1

≤

n

≤

1

0

6

，

0≤ai,q≤1090 \leq a_i,q \leq 10^9

0

≤

a

i

​

,

q

≤

1

0

9

，

1≤m≤1051 \leq m \leq 10^5

1

≤

m

≤

1

0

5

本题输入输出量较大，请使用较快的 IO 方式。

解题思路#

题中给出数列单增不减的条件，这个特性让我们想到可以使用二分法来高速查找第一次出现的位置。且题中给出本题输入输出量较大，请使用较快IO方式，从侧面反映需要一种高效查找方式。

解题代码#

#include<iostream>
#include <vector>
using namespace std;


int main(){
    int n,m;
    cin >> n >> m;
    vector<int>nums(n);
    for (int i = 0; i < n; i++) {
        cin >> nums[i];
    }
    vector<int>ask(m);
    for (int i = 0; i < m; i++) {
        cin >> ask[i];
    }
    for (int i = 0; i < m; i++) {
        int l = 0;
        int r = n - 1;
        while (l < r) {
            int mid = l + r >> 1;
            if (nums[mid] >= ask[i]) {
                r = mid;
            } else {
                l = mid + 1;
            }
        }
        if (nums[l] == ask[i]) {
            cout << l + 1 << " ";
        } else {
            cout << -1 << " ";
        }
    }
    return 0;
}
### 补充




#### 1. 关于输入输出的优化。




```cpp
ios::sync_with_stdio(false);  // 关闭C++流和C流的同步
cin.tie(0);                   // 解除cin与cout的绑定

默认情况下，cin 和 cout 与 stdio.h 库中的 scanf 和 printf 是同步的。

这种同步会导致额外的性能开销。如果你不需要同时使用 cin 和 scanf 或 cout 和 printf，你可以关闭这种同步。

哥们，你这个办法还是太吃操作了，有没有跟简单的方法？

有的兄弟有的。

// 使用 scanf 和 printf
int n;
scanf("%d", &n);  // 输入
printf("%d\n", n); // 输出
#### 2.二分法




二分模板奉上




```cpp
#include <iostream>
#include <vector>
using namespace std;


int lower_bound1(vector<int>& nums, int target) {
    int l = 0, r = (int) nums.size() - 1;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (nums[mid] < target) {
          l = mid + 1;
        }
        else {
          r = mid - 1;
        }
    }
    return l;
}


int lower_bound2(vector<int>& nums, int target) {
    int l = 0, r = (int) nums.size();   //左闭右开
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (nums[mid] < target) {
          l = mid + 1;
        }
        else {
          r = mid;
        }
    }
    return l;  //return right也可以
}


int lower_bound3(vector<int>& nums, int target) {
    int l = -1, r = (int) nums.size();  //开区间
    while (l + 1 < r){
        int mid = (l + r) >> 1;
        if (nums[mid] < target) {
          l = mid;
        }
        else {
          r = mid;
        }
    }
    return l;
}

P1223 排队接水#

题目描述#

有

nn

n

个人在一个水龙头前排队接水，假如每个人接水的时间为

TiT_i

T

i

​

，请编程找出这

nn

n

个人排队的一种顺序，使得

nn

n

个人的平均等待时间最小。

输入格式#

第一行为一个整数

nn

n

。

第二行

nn

n

个整数，第

ii

i

个整数

TiT_i

T

i

​

表示第

ii

i

个人的接水时间

TiT_i

T

i

​

。

输出格式#

输出文件有两行，第一行为一种平均时间最短的排队顺序；第二行为这种排列方案下的平均等待时间（输出结果精确到小数点后两位）。

输入输出样例 #1#

输入 #1#
10
56 12 1 99 1000 234 33 55 99 812
##### 输出 #1

3 2 7 8 1 4 9 6 10 5 291.90

说明/提示#

1≤n≤10001\le n \leq 1000

1

≤

n

≤

1000

，

1≤ti≤1061\le t_i \leq 10^6

1

≤

t

i

​

≤

1

0

6

，不保证

tit_i

t

i

​

不重复。

解题思路#

使n个人平均等待时间最少，也就是要使等待的总时间最少。因此，应该优先让接水时间短的人接水，这样就能避免较长的等待时间。

这个策略背后就是“先短后长”的贪心策略，类似于“最短作业优先”调度算法。

此题是一个经典的入门贪心问题。

解题代码#

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<pair<int,int> > nums(n); // 也可定义一个struct结构体来代替
    for (int i = 0; i < n; i++) {
        cin >> nums[i].first;
        nums[i].second = i + 1;
    }
    sort(nums.begin(), nums.end());
    long long total_wait = 0;
    long long sum = 0;
    for (int i = 0; i < n; i++) {
        total_wait += sum;
        sum += nums[i].first;
    }
    double avg = (double)total_wait / n;
    for (int i = 0; i < n; i++) {
        cout << nums[i].second << " ";
    }
    cout << endl;
    printf("%.2f\n", avg);    //注意：输出结果精确到小数点后两位
    return 0;
}

原文发布于 CSDN：西邮移动应用开发实验室二面题解

西邮移动应用开发实验室二面题解
https://www.tommywutong.cn/posts/csdn-import/csdn-146986318/
作者
TommyWu
发布于
2025-04-04
许可协议
CC BY-NC-SA 4.0
C++ 中二分查找库函数
链表&&栈&&队列（顺序/链式）
© 2026 TommyWu. All Rights Reserved. / RSS / Sitemap
Powered by Astro & Fuwari