京东2019春招编程题参考代码

数内排序

分析

字符串读入,逆序排序即可。

时间复杂度

O(len(x)*log(len(x)))

参考代码

#include <bits/stdc++.h>

using namespace std;

int main() {
    string x;
    cin >> x;
    sort(x.begin(), x.end());
    reverse(x.begin(), x.end());
    cout << x << endl;
    return 0;
}

幸运时刻

分析

按题意模拟即可。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>

using namespace std;

int n;
int main() {
    cin >> n;
    string s;
    int cnt = 0;
    int flag;
    for(int i = 0; i < n; i++) {
        cin >> s;
        flag = 0;
        if(s[0] == s[3] && s[1] == s[4]) flag = 1;
        if(s[0] == s[1] && s[3] == s[4]) flag = 1;
        if(s[0] == s[4] && s[1] == s[3]) flag = 1;
        if(flag) cnt++;
    }
    cout << cnt << endl;
}

有趣的硬币

分析

根据有趣硬币的定义，挨着判断统计即可。

时间复杂度

O(n)

参考代码

#include <bits/stdc++.h>

using namespace std;

string s;
int main() {
    cin >> s;
    s = s[0] + s;
    s = s + s[s.size() - 1];
    int cnt = 0;
    for(int i = 1; i < s.size() - 1; i++) {
        if(s[i] != s[i - 1] || s[i] != s[i + 1]) {
            cnt++;
        }
    }
    cout << cnt << endl;
    return 0;
}

整除

分析

本质是找1~n的最小公倍数,
根据唯一分解定理和最小公倍数的定义。。。
求每个素因子的最大个数相乘即可。

时间复杂度

O(n*sqrt(n))

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 100000 + 5;
int tmp[maxn];
int n;
int main() {
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int k = i;
        for(int j = 2; j * j <= n; j++) {
            int s = 0;
            while(k % j == 0) {
                s++;
                k /= j;
            }
            tmp[j] = max(tmp[j], s);
        }
        if(k > 1) tmp[k] = max(tmp[k], 1);
    }
    long long res = 1;
    for(int i = 1; i <= 100000; i++) {
        for(int j = 0; j < tmp[i]; j++) {
            res = res * i % 987654321;
        }
    }
    cout << res << endl;
    return 0;
}

牛牛下象棋

分析

dp[i][a][b]表示i次移动后，马位于坐标(a，b)的情况数。
考虑下一步的八种移动方式对应的8个坐标分别为(a1，b1)...(a8，b8)，则状态转移方程如下：
dp[i+1][a1][b1] += dp[i][a][b]
dp[i+1][a2][b2] += dp[i][a][b]
...
dp[i+1][a8][b8] += dp[i][a][b]
初始状态为除了dp[0][0][0] = 1，其余都为0。答案就是dp[K][X][Y]。

时间复杂度

O(81*K)

参考代码

#include <bits/stdc++.h>

using namespace std;

long long dp[100005][10][10];
int d[10][2] = {{1, 2}, {1, -2}, {-1, 2}, {-1, -2}, {2, 1}, {2, -1}, {-2, 1}, {-2, -1}};
int main() {
    int k, X, Y, tx, ty;
    scanf("%d%d%d", &k, &X, &Y);
    dp[0][0][0] = 1;
    for(int i = 0; i < k; i++) {
        for(int x = 0; x <= 8; x++) {
            for(int y = 0; y <= 8; y++) {
                for(int j = 0; j < 8; j++) {
                    tx = x + d[j][0];
                    ty = y + d[j][1];
                    if(0 <= tx && tx <= 8 && 0 <= ty && ty <= 8)
                        dp[i+1][tx][ty] = (dp[i + 1][tx][ty] + dp[i][x][y]) % 1000000007;
                }
            }
        }
    }
    printf("%lld\n", dp[k][X][Y]);
    return 0;
}

牛牛的括号匹配

分析

考虑如何判断一个串是否合法的过程：
依次处理字符，若是'('则入栈，若是')'则从栈中弹出一个'('. 若没有'('则不合法.
那么此题就是上述过程的变种，在处理过程中允许两次变换.可以只考虑')'->'('的方向.
1、如果当前是'('，直接入栈.
2、如果当前是')'，如果栈非空，则弹出一个'('; 如果栈空就把当前的')'变成'('入栈. (标记最多只能变化一次).
用flag标记是否有将')'变为'('的操作. 结果栈要么为空，要么全是'('.

1. 如果整个字串没有被处理完，那么肯定是"No".
2. 如果flag=0, 那么要求没有'('剩下.
3. 如果flag=1, 那么结果栈中的'('只能是两个. "((" -> "()".

时间复杂度

O(len(s))

参考代码

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

char str[maxn];
stack<char> s;

int main() {
    int t;
    cin >> t;
    while(t--) {
        while(!s.empty()) s.pop();
        scanf("%s", str);
        int n = strlen(str);
        if(n == 2) {
            if(str[0] == '(' && str[1] == ')') {
                puts("No");
                continue;
            }
        }
        int i;
        int flag1 = 0;
        for(i = 0; i < n; i++) {
            if(str[i] == '(') {
                s.push('(');
            } else {
                if(!s.empty()) s.pop();
                else {
                    if(flag1) break;
                    flag1 = 1;
                    s.push('(');
                }
            }
        }
        if(i == n) {
            if(!flag1) {
                if(s.empty()) puts("Yes");
                else puts("No");
            }
            else {
                if(s.size() != 2) puts("No");
                else puts("Yes");
            }
        }
        else puts("No");
    }
    return 0;
}

分解整数

分析

范围巨大。。
但是直觉上觉得可以很快出答案，
于是答案枚举一个数,判断另外一个数的合法性。
就跑过了。。

时间复杂度

O(跑得过)

参考代码

#include <bits/stdc++.h>

int main() {
    int t;
    long long n, x, y;
    scanf("%d", &t);
    while(t--) {
        scanf("%lld", &n);
        if(n & 1)
            printf("No\n");
        else {
            for(y = 2; y <= n; y += 2) {
                if(n % y == 0 && ((n / y) & 1)) {
                    x = n / y;
                    break;
                }
            }
            printf("%lld %lld\n", x, y);
        }
    }
    return 0;
}

生成回文串

分析

dp[l][r]表示区间 [l, r] 内的回文串数目。
于是dp[l][r] = dp[l][r - 1] + dp[l + 1][r],
根据s[l] ?= s[r], 来看是+1还是减掉重复的部分。

时间复杂度

O(n^2)

参考代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;
const int maxn = 50 + 5;
LL dp[maxn][maxn];
char s[maxn];
int main() {
    scanf("%s", s + 1);
    int len = strlen(s + 1);
    memset (dp, 0, sizeof(dp));
    for(int i = 1; i <= len; i++) {
        for(int l = 1; l + i - 1 <= len; l++) {
            int r = l + i - 1;
            dp[l][r] += dp[l + 1][r];
            dp[l][r] += dp[l][r - 1];
            if (s[l] == s[r]) dp[l][r] += 1;
            else dp[l][r] -= dp[l + 1][r - 1];
        }
    }
    printf ("%lld\n", dp[1][len]);
    return 0;
}