京东 2020秋招笔试真题

1、最优打字策略

【题目描述】在英文的输入中，我们经常会遇到大小写切换的问题，频繁切换大小写会增加我们的按键次数，也会降低我们的打字效率。

众所周知，切换大小写有两种方式，一种是按下“caps locks”，也就是大写锁定键，这样一来，之后的输入模式都会被切换。另一种是同时按下shift和需要打印的字母，可以临时切换大小写（算作按下两个键）。

已知初始状态下，打字模式是小写，现在给出需要打印的字符串（区分大小写），请你计算出最少需按键多少次才能打印出来。

输入描述：

输入第一行仅包含一个正整数n，表示字符串的长度（1<=n<=1000000）。

输入第二行包含一个长度为n的字符串，仅包含大小写字母。

输出描述：

输出仅包含一个正整数，即最少的按键次数。

输入样例：

6
AaAAAA

输出样例：

8

【解题思路】

1.遍历字符串，判断连续2个输入的状态

2.只在本次输入为大写且未锁定状态下按键次数times++，如果下一个输入为大写，就让本次按键为lock，修改lock标记为true，如果下一个输入为小写，让本次按键为shift，保持lock为false状态；

3. 同样的，只有当输入为小写且锁定状态，按键次数times++，如果下一个输入为小写，就让本次按键为lock，修改lock标记为false，如果下一个输入为大写，让本次按键为shift，保持lock为true状态

【参考代码】

#include <bit/stdc++.h>
char a[1000005];
int main() {
    int n, t;
    scanf("%d", &n);
    getchar();
    scanf("%s", a, 201);
    int len = strlen(a), k = 0;
    int sum = 0;
    for (int i = 0; i < len; i++) {
        sum++;
        if (k == 0) {
            if (a[i] >= 'A' && a[i] <= 'Z') {
                sum++;
                if (a[i + 1] >= 'A' && a[i + 1] <= 'Z')
                    k = 1;
            }
        }
        if (k == 1) {
            if (a[i] >= 'a' && a[i] <= 'z') {
                sum++;
                if (a[i + 1] >= 'a' && a[i + 1] <= 'z')
                    k = 0;
            }
        }
    }
    printf("%d\n", sum);
    return 0;
}

2、消消乐

【题目描述】消消乐是当下十分火爆的一个脑力游戏。

游戏是这样的，有一个5*5的正方形网格，每个格子中有一个大于0且小于4的整数，对于一个确定的局面，若一个格子与它上下左右四个方向的某个格子（如果存在） 数字相同，则称这两个格子是连通的，并且这种连通具有传递性。

每次，你可以选择一个格子，若与这个格子连通的格子（包括自己）数大于等于 3，你就可以选择消掉这个格子，与此同时，与这个格子连通的所有格子会一起消失。

如果仅仅是这样，那太简单了，因为无论如何消，最后的结果都是一样的，所以我们引入了重力系统，每次选择消掉某个格子，并将与那个格子相连通的所有格子都消掉后将会有一些格子失去支撑，此时那些格子就会因重力而下落。

那么怎样玩才能使得最后剩下的不能消掉的格子尽量少。

样例解释：

31211      3x2xx      xxxxx      xxxxx      xxxxx

11113       xxxx3      xxxxx      xxxxx      xxxxx

11111       xxxxx      xxxxx      xxxxx       xxxxx

11111       xxxxx      3x2x3      3xxx3      3xxxx

31222     3x222      3x222      3xxxx      3xxx3

X表示空缺，每个连通块用相同的颜色标记，此过程演示样例

输入描述

一个5*5的矩阵描述正方形网格，数字之间用空格隔开。

输出描述

一个数表示最后剩下的不能消掉的格子最少是多少。

输入样例

3 1 2 1 1
1 1 1 1 3
1 1 1 1 1
1 1 1 1 1
3 1 2 2 2

输出样例

3

【参考代码】

#include <bits/stdc++.h>
using namespace std;
const int fx[5] = {0, -1, 1, 0, 0};
const int fy[5] = {0, 0, 0, -1, 1};
int b[6][6], a[7][7], c[6][6], i, j, ans, p, q;
 
int flood(int x, int y) {
    int i, xx, yy, ans = 0, color = a[x][y];
    ans++;
    b[x][y] = true;
    a[x][y] = 0;
    for (i = 1; i <= 4; i++) {
        xx = x + fx[i];
        yy = y + fy[i];
        if ((a[xx][yy] == color) && (!b[xx][yy]))
            ans += flood(xx, yy);
    }
    a[x][y] = color;
    return ans;
}
void fill(int x, int y) {
    int i, xx, yy, color = a[x][y];
    a[x][y] = 0;
    for (i = 1; i <= 4; i++) {
        xx = x + fx[i];
        yy = y + fy[i];
        if (a[xx][yy] == color)
            fill(xx, yy);
    }
}
void fall() {
    int k;
    for (i = 1; i <= 5; i++)
        for (j = 4; j >= 1; j--)
            if (a[j][i] != 0) {
                k = j;
                while ((k <= 4) && (a[k + 1][i] == 0)) {
                    a[k + 1][i] = a[k][i];
                    a[k][i] = 0;
                    k++;
                }
            }
}
void work() {
    int k, i, cant = 0, can = 0, c[6][6], d[6][6];
    memset(b, false, sizeof(b));
    for (p = 1; p <= 5; p++)
        for (q = 1; q <= 5; q++)
            c[p][q] = a[p][q];
    for (i = 1; i <= 5; i++)
        for (j = 1; j <= 5; j++)