罗任

编辑于 05-21 18:21

各大企业校招笔试真题汇总（软件开发）

1.13.1 分词结果修改

【题目描述】

一个已经用分词算法分好词的中文句子，由于分词算法有一定错误率使得某些词汇没有正确分词，所以希望用一个词典中的词去进行匹配并把句中所有能完全匹配上的字符串强行改成一个词，但其它不受影响的分词结果不改变，请实现满足这个要求这样的算法。（注：测试数据中不出现中文字符，均使用类似样例2的字符，且不会出现多解、匹配词相互有冲突的情况）

输入描述：

第一行是分好词的一句话（字符串），词与词间由空格分开；第二行是若干个需要匹配的词，词与词间由空格分开

输出描述：

修改后的分词结果（一个字符串），词与词间由空格分开

输入样例1：

可今日小主要参加殿选小主殿选

输出样例1：

可今日小主要参加殿选

输入样例2：

aa bcd edf deda ded

输出样例2：

aa bc ded f ded a

输入样例3：

娘娘谬赞，臣妾愧不敢当愧不敢当

输出样例3：

娘娘谬赞，臣妾愧不敢当

【解题思路】

使用基本数组结构记录每个字符后是否切割即可。
【参考代码】
import sys
def solution(seged_sent, dictionary):
seged_sent = seged_sent.split()
dictionary = dictionary.split()
sent = list('x'.join(['o'.join(list(word)) for word in seged_sent]) + 'x')
for k in dictionary:
for i in range(int(len(sent) / 2)):
match = ''
if len(k) <= int(len(sent[i * 2:]) / 2):
for j in range(len(k)):
match += sent[(i + j) * 2]
if match == k:
for l in range(j):
sent[(i + l) * 2 + 1] = 'o'
sent[(i + j) * 2 + 1] = 'x'
sent[i * 2 - 1] = 'x'
res_sent = []
word = ''
for i in range(int(len(sent) / 2)):
word += sent[i * 2]
if sent[i * 2 + 1] == 'x':
res_sent.append(word)
word = ''
return ' '.join(res_sent)
if __name__ == '__main__':
seged_sent, dictionary = sys.stdin.readlines()
print(solution(seged_sent, dictionary))

1.13.2 联谊会

【题目描述】

某IT公司举办部门间的相亲会，A部门出了n女生，B部门出了m个男生，要求被男女生配对年龄必须相同（如25岁的女生要求配对25岁的男生，21岁的女生要求配对21岁的男生）。联谊会举办前，举办人突然发现，两边人数不同，年龄也不都配对。现在要求B部门调整男生安排，可以做的操作包括添加新的男生，去除某男生，或者替换某个男生。怎么做操作步骤最少？

输入描述：

输入女生年龄数组，输入男生年龄数组

输出描述：

最小的操作数

输入样例：

21 23 24 29

20 23 25 28 30

输出样例：

4

【解题思路】

本题为动态规划算法中的最短编辑距离算法。
从两队人马中最后一个人开始考察即30和29。显然二者不配对，那么我们有以下三种处理办法：
(1) 新叫一个人：男生队伍中新叫来一个29岁男生，那么男生变成了20 23 25 28 30 29，女生仍然是21 23 24 29，由于此时末尾人员配对成功，那么就变成了比较20 23 25 28 30和21 23 24的操作数，即d(20 23 25 28 30, 21 23 24 29) = d(20 23 25 28 30, 21 23 24) + 1。可以写成d(I，j) = d(i，j - 1) +1。表示下次比较的女生队伍长度减少了1，而加1表示当前进行了一次操作。
(2) 去掉：去掉男生队伍中最后的30岁男生，考察剩下的男生与女生队伍的匹配方法。即d(20 23 25 28 30, 21 23 24 29) = d(20 23 25 28, 21 23 24 29) + 1。可以写成d(i，j) = d(i – 1，j) +1。表示下次比较的男生队伍长度减少了1，而加1表示当前进行了一次操作。
(3) 替换：把男生队伍中最后的30岁男生换为一个29岁的男生，这样末尾人员配对成功了，那么接下来就要考察除了末尾人员剩下的队伍，即d(20 23 25 28 30, 21 23 24 29) = d(20 23 25 28, 21 23 24) + 1。写成d(i，j) = d(i -1，j-1) + 1表示男生和女生的长度均减少了1。但如果是最后一个男生年龄和最后一个女生的年龄相同则：d(i，j) = d(i -1，j-1)
根据以上方程，我们能快速写出递归代码，但由于递归包含了大量的重复计算，并且如果初始字符串过长，会造成递归层次过深，容易造成栈溢出的问题，所以我们这里可以用动态规划来实现。**如果说递归是自顶向下的运算过程，那么动态规划就是自底向上的过程。**它从i和j的最小值开始，不断地增大i和j，同时对于一个i和j都会算出当前地最短距离，因为下一个i和j的距离会与当前的有关，所以通过一个数组来保存每一步的运算结果来避免重复的计算过程，当i和j增加到最大值length时，结果也就出来了，即d[length][length]为A、B的最短编辑距离。
【参考代码】
package com.example.lib;
import java.util.Arrays;
import java.util.Scanner;
public class TestJavaFunc {
private static int minimum(int a,int b,int c){
return Math.min(Math.min(a,b),c);
}
public static int computeLevenshteinDistance(int[] src, int[] dst){
int[][] distance = new int[src.length + 1][dst.length + 1];
for (int i = 0;i <= src.length;i++)
distance[i][0] = i;
for (int j = 0;j <= dst.length;j++)
distance[0][j] = j;
for (int i = 1;i <= src.length;i++){
for (int j = 1;j <= dst.length;j++){
int flag = (src[i - 1] == dst[j - 1]) ? 0 : 1;
distance[i][j] = minimum(
distance[i - 1][j] + 1,
distance[i][j - 1] + 1,
distance[i - 1][j - 1] + flag);
}
}
System.out.println();
return distance[src.length][dst.length];
}
public static int[] convert(String src) {
String[] splited = src.split(" ");
int[] numbers = new int[splited.length];
for(int i = 0; i < splited.length; i++) {
numbers[i] = Integer.parseInt(splited[i]);
}
return numbers;
}
public static void main(String args[]){
String strGrils = "21 23 24 29";
String strBoys = "20 23 25 28 30";
int[] grils;
int[] boys;
Scanner scan = new Scanner(System.in);
if (scan.hasNextLine()) {
strGrils = scan.nextLine();
strBoys = scan.nextLine();
}
scan.close();
grils = convert(strGrils);
boys = convert(strBoys);
System.out.println("min operate count："+ computeLevenshteinDistance(boys,grils));
}
}

1.13.3 n的阶乘问题

【题目描述】

正整数n的阶乘(n!)中的末尾有多少个0?

例如：n = 5, n! = 120.末尾有1个0

实现：int CountZero(int n);

输入描述：

一个正整数

输出描述：

一个自然数

输入样例：

31

输出样例：

7

【解题思路】

本题更多考察分析能力和数据能力，对于相乘数字进行2和5的质因子分解，编程实现部分相对简单。
【参考代码】
#include <iostream>
int CountZero(int n) {
int c = 0;
for (int i = n; i > 1; --i) {
for (int j = i; j % 5 == 0; j /= 5) {
++c;
}
}
return c;
}
int main(int argc, char *argv[]) {
int n;
std::cin >> n;
std::cout << CountZero(n) << std::endl;
}

1.14.1 多多的数字组合

【题目描述】

给定一个整数N，求一个最小值，要求：

1)各个数位的数字之和等于N

2)各个数位的数字各不相同

【解题思路】

由于每个数字0～9只能用一次，且要求为最小值，所以优先保证数字的位数最少。
同时对于相同的位数，由于和均为N的情况下，位数越小数字应该越大，因此可以使用贪心的方法。
从低位到高位，从9～0倒序依次枚举可以使用的数字，直到满足和等于N，否则无解。
考虑点：数位，贪心
【参考代码】
#include<bits/stdc++.h>
using namespace std;
int main() {
int n;
while (cin >> n) {
int ans = 0, p = 1;
for (int i = 9; i > 0; i--) {
if (n >= i) {
n -= i;
ans += p * i;
p *= 10;
}
}
if (n > 0) {
cout << -1 << endl;
} else {
cout << ans << endl;
}
}
return 0;
}

1.14.2 多多的字符变换

【题目描述】

给定两个长度相同的字符串，支持两种变换方式：

1)交换任意两个相邻的字符，代价为0。

2)将任意一个字符a修改成字符b，代价为 |a - b|（绝对值）。

要求将两个字符串变成一样的字符串最小需要的代价之和。

【解题思路】

从两种变换方式的组合来看，由于方式(1)的代价为0，即可以无代价多次重复使用。
于是可以通过排序的方式，先将两个字符串变成有序字符串。
在排序后两个字符串对应位置的字符距离分别为最小值，且任意交互两组位置后的差值会大于等于原差值，因此排序后的差值即为最小值。
考虑点：字符串，比较，贪心
【参考代码】
#include <bits/stdc++.h>
using namespace std;
int main() {
int N;
string X, Y;
while (cin >> N) {
cin >> X >> Y;
sort(X.begin(), X.end());
sort(Y.begin(), Y.end());
int ans = 0;
for (int i = 0; i < N; i++) {
ans += abs(X[i] - Y[i]);
}
cout << ans << endl;
}
return 0;
}

1.14.3 多多的骰子组合

【题目描述】

给出N个骰子（N≤1,000）, 要求将这个骰子进行分类

两个骰子属于同类的定义是：

将其中一个骰子通过若干次上下、左右或前后翻转后，其与另一个骰子对应的6面数字均相等

【解题思路】

两两枚举每个骰子是否同类
因为骰子的变换方向只有3个：上下、左右和前后，并且每个方向翻转4次后会回归原本的状态
即最多进行4*4*4=64次旋转即可遍历到所有状态
判断同类后，进行归类的方法则可以自由选择：
选择其中一个骰子作为代表
最小表示法，以同类骰子最小的编号作为代表
并查集
等等
时间复杂度: O(N^2)
优化一：
实际上由于骰子的同构变换只有24种，6面骰子最多的状态为6!=720
于是本质不同的骰子个数为：720 / 24 = 30种
所以与骰子代表进行比较时间复杂度可以降低为: O(N)
也可以通过预处理的方式计算出30种不同的骰子，对输入的骰子进行匹配

优化二：
另外一种检查是否同类的方法：固定其中一面为某个数字，检查其他面是否匹配
比如将数字1旋转到上方（步长最远为2）
然后检查其对应面下方的数字是否相同（判断对面）
以及中间的4个数字是否顺时针旋转等价（旋转4次分别进行判断）
可以将旋转的次数从最多64次减少到约6次
考察点：组合计数，模拟，实现，分类，排序
【参考代码】
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

// 记录骰子每个面以及每个方向的旋转操作
class Dice {
public:
Dice(const vector<int>& data): data(data) {}
void rollX() { data = {data[0], data[5], data[6], data[3], data[4], data[2], data[1]}; }
void rollY() { data = {data[0], data[4], data[3], data[1], data[2], data[5], data[6]}; }
void rollZ() { data = {data[0], data[1], data[2], data[5], data[6], data[4], data[3]}; }
bool operator==(const Dice& other) { return this->data == other.data; }
private:
vector<int> data;
};

// 检查两个骰子属否同类
int check(const Dice& A, const Dice& B) {
// 3个方向分别进行模拟旋转
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
for (int k = 0; k < 4; k++) {
Dice C = A;
for (int ti = 0; ti < i; ti++) C.rollX();
for (int tj = 0; tj < j; tj++) C.rollY();
for (int tk = 0; tk < k; tk++) C.rollZ();
if (C == B) return true;
}
}
}
return false;
}

int main() {
// 记录每个种类的骰子的代表
vector<Dice> sample;
vector<int> counter;

int N;
cin >> N;
for (int i = 0; i < N; i++) {
vector<int> data(7);
for (int t = 1; t <= 6; t++) cin >> data[t];
Dice dice = Dice(data);

bool isMatched = false;
for (int j = 0; j < sample.size(); j++) {
if (check(data, sample[j])) {
// 如果与某个种类的代表同类，则计数+1
isMatched = true;
counter[j]++;
break;
}
}
if (!isMatched) {
// 记录当前骰子属于新的种类
sample.push_back(data);
counter.push_back(1);
}
}

// 将分类结果按题目要求排序输出
cout << counter.size() << endl;
sort(counter.begin(), counter.end(), greater<int>());
for (int i = 0; i < counter.size(); i++) {
if (i > 0) cout << " ";
cout << counter[i];
}
cout << endl;

return 0;
}

1.15.1 ab串

【题目描述】

小明得到一个只包含a,b两个字符的字符串，但是小明不希望在这个字符串里a出现在b左边。现在他可以将“ab”这样的子串替换成“bba”，在原串中的相对位置不变。输出小明最少需要操作多少次才能让一个给定字符串所有a都在b的右边。

输入描述：

一个只包含a,b字符的字符串，长度不超过100000。

输出描述：

最小的操作次数。结果对1000000007取模。

输入样例1：

ab

输出样例1：

1

说明1：

ab到bba

输入样例2：

aab

输出样例2：

3

说明2：

aab到abba到bbaba到bbbbaa

【解题思路】

从右往左做操作，每次操作后，操作位置左边所有的a其右边的b的数量相当于增加了。那么就从右往左遍历字符串，维护一下每次操作右边有多少个b即可，然后统计答案。
【参考代码】
#include <bits/stdc++.h>
using namespace std;
#define modo 1000000007
int main() {
char s[1000005];
scanf("%s", s + 1);
int n = strlen(s + 1);
long long ans = 0;
long long b = 0;
for (int i = n; i >= 1; i--) {
if (s[i] == 'b')
b++;
else if (s[i] == 'a') {
ans += b;
b *= 2;
ans %= modo;
b %= modo;
}
}
cout << ans << endl;
}

1.15.2 神枪手

【题目描述】

小马最近找到了一款打气球的游戏。

每一回合都会有n个气球，每个气球都有对应的分值，第i个气球的分值为ai。

这一回合内，会给小马两发子弹，但是由于小马的枪法不准，一发子弹最多只能打破一个气球，甚至小马可能一个气球都打不中。

现给出小马的得分规则：

1)若小马一只气球都没打中，记小马得0分。

2)若小马打中了第i只气球，记小马得ai分。

3)若小马打中了第i只气球和第j只气球（i<j），记小马得ai|aj分。

（其中 | 代表按位或，按位或的规则如下：

参加运算的两个数，按二进制位进行或运算，只要两个数中的一个为1，结果就为1。

即0|0-0，1|0=1，0|1=1，1|1=1.

例：2|4即00000010 | 00000100 = 00000110，所以2|4=6 ）

现在请你计算所有情况下小马的得分之和。

输入描述：

第一行，一个整数n，表示此回合的气球数量。

第二行，用空格分开的n个整数，第i个整数为ai，表示每个气球对应的分值。

对于其中60%的数据，1≤n≤1000，1≤ai≤100000

对于另外40%的数据，1≤n≤50000，1≤ai≤100000

输出描述：

一行一个整数，代表所有情况下小马的得分之和。

输入样例：

3

1 2 3

输出样例：

15

【解题思路】

暴力解法：O(n^2)
所有情况有三种，
一个气球没打破，0分。
打破一个气球，枚举打破了哪个气球，O(n)。
打破两个气球，枚举打破了哪两个气球，O(n^2)。
因此总时间复杂度为 O(n^2)。
优化解法：O(n log |最大值| )
在二进制上考虑，按位计算。
我们求二进制下，得分的每一位，在【分数和】中共出现了多少次，计算出至少含有一次的次数，再乘以对应的二进制数，即为对答案的总贡献。
枚举二进制下的每一位，O(logn)。
枚举每个气球，O(n)。
因此总时间复杂度为 O(n logn)。
【参考代码】
#include <bits/stdc++.h>
using namespace std;
const int N = 200000 + 10;
int a[N], cnt[40];
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++)
cin >> a[i];
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= 30; j++) {
if ((1 << j) & a[i]) {
cnt[j]++;
}
}
}
long long ans = 0;
for (int i = 0; i <= 30; i++) {
cnt[i] = n - cnt[i];
ans += (1LL * n * (n + 1) / 2 - 1LL * cnt[i] * (cnt[i] + 1) / 2) *
(1LL << i);
}
cout << ans;
return 0;
}

1.15.3 回文数变换

【题目描述】

所谓回文数就是一个数字，从左边读和从右边读的结果都是一样的，例如12321。

现在有一个只包含1、2、3、4的数字，你可以通过在任意位置增加一位数字或者删除一位数字来将其变换成一个回文数。但是增加或删除不同数字所需要的代价是不一样的。

已知增加和删除每个数字的代价如下：

增加一个1，代价：100；删除一个1，代价：120。

增加一个2，代价：200；删除一个2，代价：350。

增加一个3，代价：360；删除一个3，代价：200。

增加一个4，代价：220；删除一个4，代价：320。

请问如何通过最少的代价将一个数字变换为一个回文数。当然，如果一个数字本身已经是一个回文数（包括一位数，例如：2），那么变换的代价为0。

输入描述：

单组输入。

输入一个由1、2、3、4组成的正整数，正整数位数<=100位。【提示：采用字符串输入】

输出描述：

输出一个整数，表示将输入数字变换为一个回文数所需的最少代价。

输入样例：

12322

输出样例：

300

说明：

增加一个1并增加一个2，将输入正整数变为1223221或者2123212，所需代价最小，为：100+200=300。

【解题思路】

动态规划。
删除或增加某个数字都对应着相应的代价，于是可以直接区间dp，考虑删除两端点、删除左端点、删除右端点、增加左端点、增加右端点这五种情况。
最后对dp[1][n][i](i：1~4表示端点是什么数字)取最小值即可。
【参考代码】
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn = 1e5 + 5;
const int inf = 0x3f3f3f3f;
int a[5] = {0, 100, 200, 360, 220}, b[5] = {0, -120, -350, -200, -320};
char s[105];
int dp[105][105][5];
int main() {
scanf("%s", s + 1);
int ls = strlen(s + 1);
memset(dp, inf, sizeof(dp));
for (int i = 1; i <= ls; ++i) {
dp[i][i][s[i] - '0'] = 0;
}
for (int len = 2; len <= ls; ++len) {
for (int i = 1; i + len - 1 <= ls; ++i) {
int j = i + len - 1;
int le = s[i] - '0';
int ri = s[j] - '0';
if (len == 2) {
if (le == ri)
dp[i][j][le] = 0;
else {
dp[i][j][le] = -b[le];
dp[i][j][ri] = -b[ri];
}
// continue;
}
if (le == ri) {
for (int k = 1; k <= 4; ++k) {
dp[i][j][le] = min(dp[i][j][le], dp[i + 1][j - 1][k]);
// if(len==6)
// cout<<i<<" "<<j<<" "<<le<<" "<<dp[i][j][le]<<endl;
}
}
//删两边
for (int k = 1; k <= 4; ++k)
dp[i][j][k] =
min(dp[i][j][k], dp[i + 1][j - 1][k] - b[le] - b[ri]);
//删左边
for (int k = 1; k <= 4; ++k)
dp[i][j][k] = min(dp[i][j][k], dp[i + 1][j][k] - b[le]);
//删右边
for (int k = 1; k <= 4; ++k)
dp[i][j][k] = min(dp[i][j][k], dp[i][j - 1][k] - b[ri]);
//加左边
for (int k = 1; k <= 4; ++k)
dp[i][j][ri] = min(dp[i][j][ri], dp[i][j - 1][k] + a[ri]);
//加右边
for (int k = 1; k <= 4; ++k)
dp[i][j][le] = min(dp[i][j][le], dp[i + 1][j][k] + a[le]);
}
}
int ans = inf;
for (int i = 1; i <= 4; ++i) {
ans = min(ans, dp[1][ls][i]);
// cout<<dp[1][ls][i]<<" ";
}
// cout<<endl;
printf("%d\n", ans);
// 121124
return 0;
}

1.16.1 无助的产品经理

【题目描述】

在某厂，产品经理同学的工作职责除了给开发同学提需求，还有一件极其重要的事：对产品运营数据做归因分析。

某天，该产品经理同学接到老板要求：根据在过去一段时间内产品的“每日活跃用户数”，统计出最长的增长总天数，也就是把保持增长势头（可以不连续）的天数抽出来，你可能会得到多个新序列，计算最长的那个序列的总天数。

我们把该产品自上线以来“每日的活跃用户数”，都按照顺序放入一个数组，比如：

[1,5,122,34,45,232,342,34]，以这组数据为例，把其中所有的增长子序列罗列出来：

形成了

第一个子序列： [1,5,122]

第二个子序列：[34,45,232,342]

第三个子序列：[1,5,122,232,342]

第四个子序列：[1,5,34,45,232,342]

这四个序列，其中最长的是第四个，所以这个例子中，最长的增长总天数是：6

因为该产品上线时间有十几年了，产品同学数了1个小时，眼都数花了，最后只好放弃，她决定用请开发同学吃饭，来解决这个问题，你能帮帮她吗？

备注：

如果数据集中有多个“最长“增长序列，只需返回其长度即可。

输入样例：

[10,9,2,5,3,6,101,18]

输出样例：

4

说明：

最长增长的子序列为 [2,3,6,101] 或者 [2,5,6,101]或者[2,3,6,18]或者[2,5,6,18]，所以返回长度 4。

【解题思路】

本质上是最长连续序列问题，动态规划、哈希表。
【参考代码】
package main
func lengthOfLIS(nums []int) int {
if len(nums) == 0 {
return 0
}
dp := make([]int, len(nums))
for i := range dp {
dp[i] = 1
}
max := 1
for i := 1; i < len(nums); i++ {
for j := 0; j < i; j++ {
if nums[i] > nums[j] {
dp[i] = Max(dp[i], dp[j]+1)
}
}
max = Max(dp[i], max)
}
return max
}
func Max(a, b int) int {
if a > b {
return a
}
return b
}

1.16.2 计算派出机器人的数量

【题目描述】

有一个大型仓库使用拣货机器人从不同的货架间取货。

已知：

1、货架呈二维网格排列，网格中的每个货架只会放置一种商品。

2、受这代设备的技术水平所限，机器人只能沿上下左右四个方向移动，还不能沿斜线移动，请理解。

仓库当前使用的拣货算法是这样：

1、一张订单会包含X种商品，分布在X个货架上

2、结合将这X种商品的所在位置，将地图上的商品分解为Y个“商品堆”，然后同时派出Y个机器人，并发取货，每个机器人只负责一个“商品堆”。

3、“商品堆”的定义是上下左右彼此相邻的一组商品。

在订单被分析后，给你一个由 '1'（该货架有待取货物）和 '0'（该货架没有待取货物）组成的的二维网格表示货架地图，请计算需要派出的机器人的数量。

比如，下面的这张货物地图：

在这个例子中，一共有6“堆”商品，共需要同时派出6个机器人。

备注：

m == grid.length，

n == grid[i].length，

1 <= m, n <= 300，

grid[i][j] 的值为 '0' 或 '1'。

输入样例：

[[1,1,1,1,0],[1,1,0,1,0],[1,1,0,0,0],[0,0,1,0,1]]

输出样例：

3

【解题思路】

本质上是无向图的深度优先搜索，类似“岛屿问题”。
【参考代码】
package main
*/func numIslands(grid [][]byte) int {
count := 0
for i := 0; i < len(grid); i++ {
for j := 0; j < len(grid[0]); j++ {
if '1' == grid[i][j] {
AreaOfIsland(grid, i, j)
count++
}
}
}
return count
}
func AreaOfIsland(grid [][]byte, i, j int) {
if 0 <= i && i < len(grid) && 0 <= j && j < len(grid[0]) && '1' == grid[i][j] {
// 当前元素置为 0 ，避免重复计算
grid[i][j] = '0'
AreaOfIsland(grid, i-1, j)
AreaOfIsland(grid, i+1, j)
AreaOfIsland(grid, i, j-1)
AreaOfIsland(grid, i, j+1)
}
}