2018年京东春招笔试题

2018年京东春招笔试题（2018.04.09）

题目一 整数分解

题目描述

小Q的数学老师给小Q一个整数N，问小Q能否将W分解为两个整数X和Y相乘，并且满足X为奇数，Y为偶数。即能否找到奇数X和偶数Y满足X*Y=N。
小Q被这个问题难住了，希望你能来帮助他计算。

输入描述

输入的第一行包含一个正整数 t (1<=t<=1000)，表示测试样例数。
接下来的t行，每行一个正整数N（2<=N<2^63），表示给出的N，保证N不是2的幂次。

输出描述

若存在满足条件的X*Y=N，输出 X Y，若不存在，输出 No.

样例输入

2
10
5

样例输出

5 2
No

思路

首先奇数肯定不满足条件，然后将输入N一直除以2直到得到奇数为止即可。

AC代码

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

int main(){
    int t;
    cin>>t;
    vector<long long> array;
    while(t>0){
        long long x;
        cin>>x;
        array.push_back(x);
        t--;
    }

    for(int i = 0;i<array.size();i++){
        long long number = array[i];
        if( (number & 0x1) == 1)
            cout<<"No"<<endl;
        else{
            long long d = number;
            while( (number & 0x1) == 0){
                number = number >> 1;
            }
            cout<<number<<" "<<(d/number)<<endl;
        }
    }

    return 0;
}

---

题目二 回文串

题目描述

对于一个字符串，从前开始读和从后开始读是一样的，我们就称这个字符串是回文串。例如ABCBA，AA，A是回文串，ABCD，AAB不是回文串。
牛牛特别喜欢回文串，他手中有一个字符串s，牛牛在思考能否从s中移除部分（0个或多个）字符使其变为回文串，并且牛牛认为空串不是回文。
牛牛发现移除的方案可能有很多种，希望你来帮他计算一下一共有多少种移除方案可以使s变为回文串。
对于两种移除方案，如果移除的字符依次构成的序列不一样就是不同方案。

输入描述

字符串s

输出描述

移除方法

样例输入1

XXY

样例输出1

4

样例输入2

ABA

样例输出2

5

思路

动态规划。
子问题：
设 dp[i,j]$dp[i,j]$ 表示字符串从位置 i$i$ 到 j$j$ 的子串变成回文串的方法数，比如样例2的ABA，dp[0,1]$dp[0,1]$表示子串 AB 变成回文串的方法数（它等于2）。
转移方程：
若 s[i]≠s[j]$s[i]\ne s[j]$，（例如 ABCD 这个串首尾字符不同，下面也以此为例），那么考虑两种情况：
（1）将 s[i]$s[i]$ （A）丢掉，此时变成回文串的方法数等于 BCD 变成回文串的方法数，即 dp[i+1,j]$dp[i+1,j]$
（2）将 s[j]$s[j]$ （D）丢掉，此时变成回文串的方法数等于 ABC 变成回文串的方法数，即 dp[i,j−1]$dp[i,j-1]$
以上两种情况有重合的部分，他们都包含了“同时去掉s[i]$s[i]$和s[j]$s[j]$”的所有情况，即 BC 变成回文串的方法数，即 dp[i+1,j−1]$dp[i+1,j-1]$。
故 s[i]≠s[j]$s[i]\ne s[j]$ 时状态转移方程是：

dp[i,j]=dp[i+1,j]+dp[i,j−1]−dp[i+1,j−1]$$dp[i,j]=dp[i+1,j]+dp[i,j-1]-dp[i+1,j-1]$$

若 s[i]=s[j]$s[i]=s[j]$时，（例如ABCA这个串首尾字符相同，下面也以此为例），那么同上考虑两种情况：
（1）将 s[i]$s[i]$ （A）丢掉，此时变成回文串的方法数等于 BCA 变成回文串的方法数，即 dp[i+1,j]$dp[i+1,j]$
（2）将 s[j]$s[j]$ （A）丢掉，此时变成回文串的方法数等于 ABC 变成回文串的方法数，即 dp[i,j−1]$dp[i,j-1]$
以上两种情况有重合的部分，他们都包含了“同时去掉s[i]$s[i]$和s[j]$s[j]$”的所有情况，即 BC 变成回文串的方法数，即 dp[i+1,j−1]$dp[i+1,j-1]$。
此外还有两种情况：
（3）将中间部分s[i+1:j−1]$s[i+1:j-1]$丢掉，此时变成回文串的方法数等于 AA 变成回文串的方法数，就是1（AA本身）。（有人问不是3吗？另外两种分别被包含在情况1和2中了）
（4）头尾都不丢，ABCA变成回文串的方法数，就是BC变成回文串的方法数，即 dp[i+1,j−1]$dp[i+1,j-1]$
由于（4）填补了（1）和（2）重合部分的惩罚，所以s[i]=s[j]$s[i]=s[j]$时的状态转移方程是：

dp[i,j]=dp[i+1,j]+dp[i,j−1]+1$$dp[i,j]=dp[i+1,j]+dp[i,j-1]+1$$

AC代码

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

int main()
{
    string s;
    cin>>s;
    int n = s.size();

    // 初始化矩阵为0
    vector<vector<long>> dp(100,vector<long>(100,0));

    for (int i = 0; i < n; i++){
        dp[i][i] = 1;
        if (s[i] == s[i+1])
            dp[i][i+1] = 3;
        else
            dp[i][i+1] = 2;
    }

    for (int p = 2; p < n; ++p){
        for (int i = 0, j = p; j < n; ++i, ++j)
            if (s[i] == s[j])
                dp[i][j] = dp[i+1][j] + dp[i][j-1] + 1;
            else
                dp[i][j] = dp[i+1][j] + dp[i][j-1] - dp[i+1][j-1];
    }

    cout<<dp[0][n-1]<<endl;

    return 0;
}

---

题目三 马走棋盘

题目描述

最近牛牛开始向老师学习下中国象棋。老师告诉他，象棋中的“马“只能走日字型。
以棋盘左下角为原点，向上y轴正方向，向右为x轴正方向，建立坐标系。牛牛想知道，棋盘左下角的马，经过K次移动之后，落在坐标（X,Y）的情况有多少种。当任意一次移动后马的位置不同时，两种情况被认为不同。
因为答案可能很大，请输出情况数取模1000000007的结果。

输入描述

第一行是K
第二行是X和Y

输出描述

走法取模1000000007的结果

思路

深搜、广搜或动态规划。尝试了前两种，深搜超时间，广搜超内存，估计AC只能dp了。

广搜代码（超内存）

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

struct point{
public:
    int x;
    int y;
    int step;
    point(int a, int b, int s):x(a),y(b),step(s){};
};

int main()
{
    int K, X, Y;
    cin>>K;
    cin>>X>>Y;

    queue<point> my_queue;
    my_queue.push(point(0, 0, 0));

    int stepArr[][2] = {{-1,2},{1,2},{-2,1},{2,1},{-2,-1},{2,-1},{-1,-2},{1,-2}};

    int counter = 0;

    while(! my_queue.empty()){
        point current_point = my_queue.front();
        my_queue.pop();

        // 终止条件，第K层（从0开始）第一个节点
        if(current_point.step==K+1)
            break;

        for(int i=0; i<8; i++){
            int x = current_point.x + stepArr[i][0];
            int y = current_point.y + stepArr[i][1];
            // 如果未超出棋盘
            if(x>=0 && y>=0 && x<=8 && y<=9){
                if(current_point.step + 1==K){
                    if(x == X && y == Y)
                        counter++;
                }
                my_queue.push(point(x, y, current_point.step+1));
            }
        }
    }
    cout<<(counter%1000000007)<<endl;
    return 0;
}

深搜代码（超时间）

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

struct point{
public:
    int x;
    int y;
    int step;
    point(int a, int b, int s):x(a),y(b),step(s){};
};

int main()
{
    int K, X, Y;
    cin>>K;
    cin>>X>>Y;

    stack<point> my_stack;
    my_stack.push(point(0, 0, 0));

    int stepArr[][2] = {{-1,2},{1,2},{-2,1},{2,1},{-2,-1},{2,-1},{-1,-2},{1,-2}};

    int counter = 0;

    while(! my_stack.empty()){
        point current_point = my_stack.top();
        my_stack.pop();

        for(int i=0; i<8; i++){
            int x = current_point.x + stepArr[i][0];
            int y = current_point.y + stepArr[i][1];
            // 如果未超出棋盘
            if(x>=0 && y>=0 && x<=8 && y<=9){
                if(current_point.step + 1==K){
                    if(x == X && y == Y)
                        counter++;
                }
                if(current_point.step + 1<=K)
                    my_stack.push(point(x, y, current_point.step+1));
            }
        }
    }
    cout<<(counter)<<endl;

    return 0;
}

python实现的广搜，内存消耗应该没那么大

原本的广搜之所以内存消耗大，是因为K越大，队列中的点越多，呈指数爆炸。现在用一个矩阵（8×8）保存每一步之后每个位置上有多少种走法能到达，同时每一步用一个字典保存上一轮所有点的下一步可能到达的位置及其走法。

import numpy as np

def legal(x,y):
    if x>=0 and x<8 and y>=0 and y<8:
        return True
    return False

class point():
    def __init__(self, x, y):
        self.x = x
        self.y = y

K = 2
X = 3
Y = 3

S = np.zeros((8,8),dtype=int)
my_queue_old = {point(0,0):1}

stepArr = [[1,2],[-1,2],[2,1],[-2,1],[1,-2],[-1,-2],[2,-1],[-2,-1]]

for i in range(K):
    my_queue_new = {}
    for p,t in my_queue_old.iteritems():
        for d in stepArr:
            x = p.x + d[0]
            y = p.y + d[1]
            if legal(x,y):
                S[x,y] += t
                new_p = point(x,y)
                if my_queue_new.has_key(new_p):
                    my_queue_new[new_p] += 1
                else:
                    my_queue_new[new_p] = 1

    my_queue_old = my_queue_new

print S[3][3]