首页 > 京东笔试-2道题都AC

京东笔试-2道题都AC

1.最长公共子序列
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
// dp[i,j]=0  i=0 j=0
//            dp[i-1,j-1]+1 ai==bj 
//            max(dp(i,j-1),dp(i-1,j))

int main()
{
    int N;
    while(cin>>N)
    {
        vector< vector<int> >dp(N+1,vector<int>(N+1,0));
        string a="";
        string b="";
        char c;
        for(int i=0;i<N;i++)
        {
            cin>>c;
            a.push_back(c);
        }

        for(int i=0;i<N;i++)
        {
            cin>>c;
            b.push_back(c);
        }
        for(int i=0;i<N;i++)
        {
            dp[i][0]=0;
            dp[0][i]=0;
        }
        for(int i=1;i<=N;i++)
            for(int j=1;j<=N;j++)
            {
                if(a[i-1]==b[j-1])
                dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i][j-1],dp[i-1][j]);
            }
        int max_length=0;
        for(int i=0;i<=N;i++)
        max_length=max(max_length,*max_element(dp[i].begin(),dp[i].end()) );
        double result=double(max_length)/double(N);
        cout.setf(ios::fixed);
        if(result<=0.5)
        {
            cout << setprecision(2) << result;
            cout<<" "<<"Yes"<<endl;
        }
        else 
        {
            cout << setprecision(2) << result;
            cout<<" "<<"No"<<endl;
        }
    }
}

2.。回文素数
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <unordered_map>
#include <vector>
#define fir first
#define se second
#define ll long long
#define pb push_back
#define mp make_pair
#define ull unsigned long long
#define cl(a, b) memset(a, b, sizeof(a))
#define quickio(a) ios::sync_with_stdio(a)
#define datatest() freopen("data.in", "r", stdin)
#define makeans() freopen("data.out", "w", stdout)
#define makedata() freopen("data.in", "w", stdout)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define pdd pair<double, double>
using namespace std;
const int maxn = 1e6 + 10;
const int maxm = 1e6 + 10;
const int inf = 0x3f3f3f3f;
const ll mod = 1e9 + 7;
const int maxblock = sqrt(maxn) + 10;
const double eps = 1e-7;
const ll INF = 1e16;
bool vis[maxn];
int prime[maxn], cnt;
void init() {
  cnt = 0;
  memset(vis, 0, sizeof vis);
  for (int i = 2; i < maxn; i++) {
    if (!vis[i]) {
      prime[cnt++] = i;
    }
    for (int j = 0; j < cnt; j++) {
      if (1LL * i * prime[j] >= maxn) break;
      vis[i * prime[j]] = 1;
      if (i % prime[j] == 0) {
        break;
      } else {
      }
    }
  }
}
bool check(std::string str) {
  for (int i = 0; i < str.size(); i++) {
    if (str[i] != str[str.size() - i - 1]) return false;
  }
  return true;
}
int n, m;
int is[maxn];
int sum[maxn];
void build() {
  init();
  for (int i = 0; i < cnt; i++) {
    if (check(to_string(prime[i]))) {
      is[prime[i]] = 1;
    }
  }
  for (int i = 11; i <= m; i++) {
    string str = to_string(i);
    for (int j = 0; j < str.size(); j++) {
      int num = 0;
      for (int k = 0; k < str.size(); k++) {
        if (k == j) continue;
        num = num * 10 + str[k] - '0';
      }
      // cout << "i=" << i << " num=" << num << endl;
      if (is[num]) {
        sum[i] = 1;
        break;
      }
    }
    // cout << i << " " << sum[i] << endl;
  }
  for (int i = 1; i < maxn; i++) sum[i] += sum[i - 1];
}
int main() {
  scanf("%d %d", &n, &m);
  build();
  printf("%d\n", sum[m] - sum[n - 1]);
  return 0;
}


全部评论

(2) 回帖
加载中...
话题 回帖

相关热帖

历年真题 真题热练榜 24小时
技术(软件)/信息技术类
查看全部

近期精华帖

热门推荐