2020年京东精选50面试题及答案

2020年京东精选50面试题及答案

1.

求此N的最小公倍数。把每个数字分解质因数，算他们 每

个质因数的贡献，然后乘起来。我的代码没写好（算质因 数不用这么慢的)。

#include using namespace std; typedef long long 11; #define maxn 100009 int fact [maxn]; bool prime [maxn]; 11 mod = 987654321; int cal (int t, int p) {

int ent = 0;

while(t % p == 0) { cnt++;

t /= P； return ent; void first () {

memset (prime, true, sizeof (prime)); prime[1] = false; for(int i = 2; i <= 100000; i++： { int top = sqrt(i);

for(int j = 2; j <= top; j—) { if(i % j == 0){ prime[i] = false; break;

void solve(int Limit) { first ();

for (int i = 2; i <= Limit; i++' { int top = sqrt(i);

for (int j = 2; j <= top; ji) { if(prime[j] && i % j == 0) {

fact[j] = max (fact [j], cal (i, j));

I

if(prime[i])

fact [i] = max (fact [i], 1);

}

}

int main() {

11 n; cin^^n; solve (n); 11 ans = 1;

for(11 i = 1; i <= n; i++) {

for (11 j = 1； j <= fact[i]; j++) {

ans = ans * i % mod; } }

cout<

2. 去掉字符串构成回文。其实是经典的求回文子序列个数。

# inc lude using namespace std; typedef long long 11; 11 f[59] [59]; string str;

11 dfs(int i, int j) {

i￡(i > j) {

return 0; }

if(i == j) {

f[i] [j] = 1; return f [i] [j]; }

[j] != 0){ return f [i] [j];

f [i] [j] = dfs (i, j - 1) + dfs(i + 1, j) - dfs(i + 1, j - 1); if (str [i] == str[j])

f [i] [j] += dfs(i + 1, j - 1： + 1; return f [i] [j]; int main。{

cin>>sh;

int len = str.length(); cout?dfs(0, len - l)?endl; return 0;

3. 象棋的马走K步之后到(X,Y)的方案数。直接递推。

#include using namespace std; typedef long long 11; 11 dp[10][10] [3]; 11 mod = le9 + 7;

int dx[8] = {~2, -1, L 2, 2, L -L -2}; int dy[8] = {-1, -2, -2, -1, L 2, 2, 1}； int check(int x, int

y) {

>=0 && y <= 8) if (x >= 0 && x <= 8 && y

return true;

return false;

void cal (int x, int y, int state) { dp [x] [y] [state]: for(int i = 0; i

int tx = x +

0；

int ty = y +< 8; i++)

dp[x] [y]

{ dx[i];

[state] =

dyti]；

i￡ (check (tx. ty)) {

(dp[x] [y] [state] + dp[tx] [ty] [state 1]) % mod;

int main() {

int K; cin>> K;

int state = 0, nowstate; dp[0] [0] [0] = 1;

while (K—) {

state = state \

for(int i = 0; i <= 8; i++) {

for(int j = 0; j <= 8; j++) {

cal (i, j, state);

int x, y; cin^>x>>y;

cout?dp[x] [y] [state] ?endl; return 0;

4. 如何验证图的连通性？

#include

#include ffinclude using namespace std; ffdefine MAX_VNUM 10 typedef struct {

int weight;

}Adj,AdjMatrix[MAX_VNUM][MAX_VNUM]; typedef struct {

AdjMatrix adjM; i nt vNum; }adjGraph;

〃创建一个图,节点从。幵始，注意传入引用 void CreateGraph(adjGraph &G)

{

cout<<\输入节点个数:\ cout<<\输入图的邻接矩阵:\ for (int i=0;i

for (int j=0;j

} } }

/瀚出一个图

void print(adjGraph G) {

for(int i=0;i

for(int j =0;j

cout<

cout?endl;//1寻换行流写入输出流，清空输出緩冲区 } }

//war shall算法判断图的连通性 bool connectivityWarshall(adjGraph G) {

adjGraph temp;//临时判断矩阵 temp.vNum = G.vNum;

〃初始化临时判断矩阵

for (int i =0;i

for(int j =0;j

If (G.adjM[l][J].weight)

temp.adjM[i][j].weight = 1; else temp.adjM[i][j].weight = 0;

}

temp.adjM[i][i].weight = 1;

〃矩阵乘法算法Marshall, R(a)

for (int a =0;a

for (int b=0;b

if(temp.adjM[a][b].weight) {

for (int c = 0;c