题目来源：牛客网https://www.nowcoder.com/profile/7952866/test/7775568/76265
1.字符串编码
给定一个字符串，请你将字符串重新编码，将连续的字符替换成“连续出现的个数+字符”。比如字符串AAAABCCDAA会被编码成4A1B2C1D2A。
输入例子:
AAAABCCDAA
输出例子:
4A1B2C1D2A
思路比较简单，只需要遍历字符串，对每一个单独的字符设置一个初始值为1的计数器，然后比较它和相邻的字符是否相同，如果相同则加1，直到遇到不同的字符，输出当前计数器的值并重置为1。
测试代码如下：
#include <cstdio> #include <string> #include <iostream> using namespace std; string num = "0123456789"; string intToString(int n) { //int转成string，比如 12转为‘12’ string str = ""; while (n) { str = num[n % 10] + str; n = n / 10; } return str; } string solve(string str) { int len = str.size(); int i = 0; char cur; int cnt; string ans = ""; //从字符串头部开始依次遍历 while (i < len) { cur = str[i]; cnt = 0; int j = 0; for (j = i; j < len; j++) { // 从当前位置开始检索 if (str[j] == cur) { cnt++; } else if (str[j] != cur) { ans = ans + intToString(cnt); ans = ans + cur; i = j; // 从i = j这个位置再开始检索 break; } } if (j == len) { ans = ans + intToString(cnt); ans = ans + cur; break; } } return ans; } int main() { string str; while (cin >> str) { string ans = solve(str); cout << ans << endl; } return 0; }
测试结果：
2.赛马
在一条无限长的跑道上，有N匹马在不同的位置上出发开始赛马。当开始赛马比赛后，所有的马开始以自己的速度一直匀速前进。每匹马的速度都不一样，且全部是同样的均匀随机分布。在比赛中当某匹马追上了前面的某匹马时，被追上的马就出局。 请问按以上的规则比赛无限长的时间后，赛道上剩余的马匹数量的数学期望是多少
输入描述:
每个测试输入包含1个测试用例
输入只有一行，一个正整数N
1 <= N <= 1000
输出描述:
输出一个浮点数，精确到小数点后四位数字，表示剩余马匹数量的数学期望
输入例子:
1
2
输出例子:
1.0000
1.5000
思路分析：题目看上去有点费解，个人更感觉像是一道智力题。我们假设有N匹马赛跑，最后剩下的那个是冠军。注意题目中说每个马的速度不一样，这就说明最后只会剩下一个马，不可能出现并列的情况。另外数学期望的意思就是如果这匹马的编号是i，那P（i）表示i是冠军的概率，就是数学期望。可以这样想一下：如果只有一匹马，那么这匹马肯定是冠军，数学期望显然是1。如果有两匹马，那么某一匹马是冠军的概率是0.5，某一时刻其中一个马被淘汰了，那么另一个马的数学期望变成1，相加就是1.5。依次类推，如果刚开始有N匹马，P（i） = 1 / N，某一时刻P（i） = 1 / （N - 1）、1/（N - 2）......所以这道题的答案就是计算1 + 1 / 2 + 1 / 3 + 1 / 4 + ... + 1 / N的和，就是调和级数。
测试代码如下：
#include <cstdio> //调和级数 int main() { int n; while (scanf_s("%d", &n) != EOF) { double sum = 0.0; for (int i = 1; i <= n; i++) { sum = sum + 1.0 / i; } printf("%.4lf ", sum); } return 0; }
测试结果：
3.最大和
在一个N*N的数组中寻找所有横，竖，左上到右下，右上到左下，四种方向的直线连续D个数字的和里面最大的值
输入描述:
每个测试输入包含1个测试用例，第一行包括两个整数 N 和 D :
3 <= N <= 100
1 <= D <= N
接下来有N行，每行N个数字d:
0 <= d <= 100
输出描述:
输出一个整数，表示找到的和的最大值
输入例子:
4 2
87 98 79 61
10 27 95 70
20 64 73 29
71 65 15 0
输出例子:
193
思路：直接从行、列、左上到右下，右上到左下，四种方向暴力搜索
测试代码：
#include <iostream> #define MAX 100 + 10 int Max = 0; bool check1(int x, int y, int d, int n) { if (x + d - 1 > n) return false; if (y + d - 1 > n) return false; return true; } bool check2(int x, int y, int d, int n) { if (x + d - 1 > n) return false; if (y - d < 0) return false; return true; } int main() { int n, d; while (scanf_s("%d%d", &n, &d) != EOF) { Max = 0; int arr[MAX][MAX]; for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { scanf_s("%d", &arr[i][j]); } } // 先从每行开始找 for (int row = 1; row <= n; row++) { for (int i = 1; i <= n - d + 1; i++) { int sum = 0; for (int j = i; j < d + i; j++) { sum = sum + arr[row][j]; } if (sum > Max) Max = sum; } } // 再从每列开始找 for (int col = 1; col <= n; col++) { for (int i = 1; i <= n - d + 1; i++) { int sum = 0; for (int j = i; j < d + i; j++) { sum = sum + arr[j][col]; } if (sum > Max) Max = sum; } } // 再从左上到右下对角线开始找 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // 从i,j起点开始找 int x = i; int y = j; if (check1(x, y, d, n)) { int cnt = 0; int sum = 0; while (cnt < d) { sum = sum + arr[x][y]; cnt++; x++; y++; } if (sum > Max) Max = sum; } } } // 再从右上到左下对角线开始找 for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) { // 从i,j起点开始找 int x = i; int y = j; if (check2(x, y, d, n)) { int cnt = 0; int sum = 0; while (cnt < d) { sum = sum + arr[x][y]; cnt++; x++; y--; } if (sum > Max) Max = sum; } } } printf("%d ", Max); } return 0; }
测试结果如下：
4.推箱子
大家一定玩过“推箱子”这个经典的游戏。具体规则就是在一个N*M的地图上，有1个玩家、1个箱子、1个目的地以及若干障碍，其余是空地。玩家可以往上下左右4个方向移动，但是不能移动出地图或者移动到障碍里去。如果往这个方向移动推到了箱子，箱子也会按这个方向移动一格，当然，箱子也不能被推出地图或推到障碍里。当箱子被推到目的地以后，游戏目标达成。现在告诉你游戏开始是初始的地图布局，请你求出玩家最少需要移动多少步才能够将游戏目标达成。
输入描述:
每个测试输入包含1个测试用例
第一行输入两个数字N，M表示地图的大小。其中0<N，M<=8。
接下来有N行，每行包含M个字符表示该行地图。其中 . 表示空地、X表示玩家、*表示箱子、#表示障碍、@表示目的地。
每个地图必定包含1个玩家、1个箱子、1个目的地。
输出描述:
输出一个数字表示玩家最少需要移动多少步才能将游戏目标达成。当无论如何达成不了的时候，输出-1。
输入例子:
4 4
....
..*@
....
.X..
6 6
...#..
......
#*##..
..##.#
..X...
.@#...
输出例子:
3
11
思路：利用BFS，每一步有4中情况，用四维数组记录每一个人和箱子所在位置的状态，如果之前出现过这种状态，直接跳过，否则计数加一，一直遍历，若队列为空还没有输出，则无法到达。否则可以到达。by：http://blog.csdn.net/njudongchen/article/details/61415043
测试代码如下：
#include <iostream> #include <string> #include <queue> #include <vector> using namespace std; struct humanbox { //创建一个结构体：人和箱子的坐标 int hx, hy, bx, by; humanbox(int x, int y, int bbx, int bby) :hx(x), hy(y), bx(bbx), by(bby) {}; }; int main() { int n, m; cin >> n >> m; vector<vector<int>> map(n, vector<int>(m, 0)); int hx, hy; //玩家起点坐标 int bx, by; //箱子坐标 int endx, endy; //目的地坐标 for (int i = 0; i != n; ++i) { //更新地图map string str; cin >> str; for (int j = 0; j != m; ++j) { if (str[j] == 'X') { map[i][j] = 'X'; hx = i; hy = j; } else if (str[j] == '#') map[i][j] = '#'; else if (str[j] == '@') { map[i][j] = '@'; endx = i; endy = j; } else if (str[j] == '*') { map[i][j] = '*'; bx = i; by = j; } } } //枚举四个方向：向右走、向左走、向下走、向上走 int stepx[4] = { 0, 0, 1, -1 }; int stepy[4] = { 1, -1, 0, 0 }; //更新步数 int count[10][10][10][10] = { 0 }; queue<humanbox> que; que.push(humanbox(hx, hy, bx, by)); count[hx][hy][bx][by] = 1; while (!que.empty()) { humanbox top_que = que.front(); que.pop(); if (top_que.bx == endx&&top_que.by == endy) { //到达终点 cout << (count[top_que.hx][top_que.hy][top_que.bx][top_que.by]) - 1; //输出减1是因为起始从1开始 cout<< endl; return 0; } for (int i = 0; i != 4; ++i) { int hnx = top_que.hx + stepx[i]; int hny = top_que.hy + stepy[i]; if (hnx<0 || hny<0 || hnx >= n || hny >= m || map[hnx][hny] == '#') //当越界或者遇到障碍物 continue; if (hnx == top_que.bx&&hny == top_que.by) { //当玩家遇到箱子 int bnx = top_que.bx + stepx[i]; int bny = top_que.by + stepy[i]; if (bnx<0 || bny<0 || bnx >= n || bny >= m || map[bnx][bny] == '#') //当箱子越界或者遇到障碍物 continue; if (count[hnx][hny][bnx][bny]) continue; count[hnx][hny][bnx][bny] = count[top_que.hx] [top_que.hy][top_que.bx][top_que.by] + 1; que.push(humanbox(hnx, hny, bnx, bny)); } else { if (count[hnx][hny][top_que.bx][top_que.by]) continue; count[hnx][hny][top_que.bx][top_que.by] = count[top_que.hx][top_que.hy][top_que.bx][top_que.by] + 1; que.push(humanbox(hnx, hny, top_que.bx, top_que.by)); } } } cout << -1 << endl; return 0; }
测试结果：