首页 > 京东笔试0806, C++开发
头像
offer快到碗里来1005
编辑于 2020-08-07 14:40
+ 关注

京东笔试0806, C++开发

基因问题
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
using namespace std;

int solution(const string& s1, const string& s2){
    if(s1.empty() || s2.empty()) return 0;
    
    int N = s1.size();
    vector<vector<int>> dp(N+1,  vector<int>(N+1, 0));
    for(int i=0; i<N; ++i){
        for(int j=0; j<N; ++j){
            if(s1[i] == s2[j]){
                dp[i+1][j+1] = dp[i][j] + 1;
            }else{
                dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1]);
            }
        }
    }
    return dp[N][N];

}

int main()
{
    int len;
    while(cin >> len){
        char c;
        string s1, s2;
        for(int i=0; i<len; ++i){
            cin >> c;
            s1 += c;
        }
        for(int i=0; i<len; ++i){
            cin >> c;
            s2 += c;
        }
        int common =  solution(s1, s2);
        printf("%.2f ", (double)common/len);
        if(common > len/2)
            cout<<"No "<<endl;
        else 
            cout<<"Yes "<<endl;
    }
}
   回文素数, 纯暴力。。。不带任何技巧的那种
#include <iostream>
#include <vector>
#include <string>
#include <cstdio>
#include <cmath>
using namespace std;

class Solution{
public:
    int solution(int low, int high){
        int ans = 0;
        for(int i=low; i<=high; ++i){
            if(helper(i)){
                ++ ans;
            }
        }
        return ans;
    }
    bool helper(int num){
        for(int k=1; k<=num; k*=10){
            int t = (num/k/10*k + num%k);
            if(isHuiwen(t) && isSushu(t)){
                return true;
            }
        }
        return false;
    }
    bool isSushu(int num){
        if(num<=1) return false;
        
        int sqt = sqrt(num);
        for(int i=2; i<=sqt; ++i){
            if(num % i == 0)
                return false;
        }
        return true;
    }
    bool isHuiwen(int num){
        string s = to_string(num);
        for(int i=0, j=s.size()-1; i<j; ++i, --j){
            if(s[i] != s[j])
                return false;
        }
        return true;
    }
};

int main(){
    Solution sol;
    int low, high;
    while (cin>>low>>high){
        cout<<sol.solution(low, high)<<endl;
    }
}


全部评论

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

相关热帖

近期热帖

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

近期精华帖

热门推荐