贝壳找房研发岗笔试20190810

1.举重大赛

使用排序+二分查找的方法
先排序，然后对每个人求出能和他对战的最小体重；
然后对于每个人，二分找到能和他对战的最大体重。 假如二分到的最大下标是r，然后计数器 ans += r - i;即可

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;
int main(){
    int n,ans;
    ll weight;
    vector<ll>person;
    vector<double>minweight;
    while(cin >> n){
        person.clear();
        minweight.clear();
        ans = 0;
        for(int i=0;i<n;i++){
            cin >> weight;
            person.push_back(weight);
        }
        sort(person.begin(),person.end());
        for(int i=0;i<n;i++)
            minweight.push_back(person[i]/10.0*9);
        for(int i=0;i<n;i++){
            int l=i,r=n-1,mid;
            while(l<=r){
                mid = l + ((r-l)>>1);
                //cout << person[i] << ' ' << minweight[mid] << endl;
                if(person[i] < minweight[mid])
                    r = mid-1;
                else if(person[i] > minweight[mid])
                    l = mid+1;
                else {
                    r = mid;
                    break;
                }
            }
            //cout << l << ' ' << r << endl;
            ans += r-i;
        }
        cout << ans << endl;
    }
    return 0;
}

2.最长上升子序列：
dp方法

class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        if(nums.size() == 0) return 0;
        vector<int> dp;
        int ans = 0;
        for(int i=0;i<nums.size();i++)
            dp.push_back(1);
        for(int i=0;i<nums.size();i++){
            for(int j=0;j<i;j++){
                if(nums[i] > nums[j])
                    dp[i] = max(dp[i],dp[j]+1);
            }
            ans = max(ans,dp[i]);     
        }
        return ans;
    }
};

贪心+二分法：

class Solution {
public:
int find(int n, vector<int> help){
    int l = 0, r = help.size()-1;
    while(l <= r){
        int mid = l + ((r - l) >> 1);
        if(n > help[mid]) l = mid + 1;
        else if( n < help[mid]) r = mid -1;
        else return -1;
    }
    return l;
}
int lengthOfLIS(vector<int>& nums) {
    vector<int>help;
    int len = 0;
    for(int i=0;i<nums.size();i++){
        if(help.empty() || help[len-1] < nums[i]){
            help.push_back(nums[i]);
            len++;
        }
        else{
            int loc = find(nums[i],help);
            if(loc != -1)
                help[loc] = nums[i];
        }
    }
    return len;
}
};