做微软笔试题了吗!

4 answer(s)

0

有人贴一下第二题通过的代码么

2
string s, t;
int n;
int res;
void work(int p, int c) {
    if(p >= n) {
        res = min(res, c);
        return;
    }
    if(s[p] == t[p]) work(p + 1, c);
    else {
        for (int j = p + 1; j < n; j++) {
            if(s[j] == t[p]) {
                swap(s[p], s[j]);
                work(p + 1, c + 1);
                swap(s[p], s[j]);
            }
        }
    }
}
void solve() {
    cin >> s >> t;
    n = s.size();
    res = s.size();
    work(0, 0);
    cout << res << endl;
}
0

第一题有ac 代码吗?

0

第一题AC的代码

#include <iostream>
#include <vector>

using namespace std;

#define MAX_COUNT 100001
int nums[MAX_COUNT];
int sums[MAX_COUNT];

int cal_sum(int i, int j){
    // included i, j
    return sums[j] - sums[i] + nums[i];
}
int binary_search(vector<int> &nums, int target){
    // sorted assced
    // find last idx where > target
    if(nums.size() == 0)    return -1;
    int l = 0, r = nums.size() - 1;
    while(l + 1 < r){
        int mid = (l + r) / 2;
        if(nums[mid] > target){
            l = mid;
        }else{
            r = mid - 1;
        }
    }
    if(l+1 >= 0 and l + 1 < nums.size() and nums[l+1] > target){
        return l + 1;
    }
    if(l >=0 and l < nums.size() and nums[l] > target){
        return l;
    }
    return -1;
}

int main(){
    int t;
    cin >> t;
    int pre_sum = 0;
    for(int i = 0; i < t; i++){
        cin >> nums[i];
        pre_sum += nums[i];
    }
    if(pre_sum < 0){
        for(int i = 0; i < t; i++){
            nums[i] = -1 * nums[i];
        }
    }

    sums[0] = nums[0];
    for(int i = 1; i < t; i++){
        sums[i] = nums[i] + sums[i-1];
    }
    int res = 0;
    int all_sum = cal_sum(0, t-1);
    int avg_sum = all_sum / 3;
    int left_num = all_sum % 3;

    vector<int> left_avg_idxs;
    vector<int> left_one_idxs;
    vector<int> right_avg_idxs;
    vector<int> right_one_idxs;

    for(int i=1; i < t; i++){
        int s1 = cal_sum(0, i-1);
        if(s1 == avg_sum){
            left_avg_idxs.push_back(i);
        }else if(s1 == avg_sum + 1){
            left_one_idxs.push_back(i);
        }
    }

    for(int i=t-1; i > 0; i--){
        int s1 = cal_sum(i, t-1);
        if(s1 == avg_sum){
            right_avg_idxs.push_back(i);
        }else if(s1 == avg_sum + 1){
            right_one_idxs.push_back(i);
        }
    }
    int same_avg_count = 0;
    for(int i = 0; i < left_avg_idxs.size(); i++){
        int idx = binary_search(right_avg_idxs, left_avg_idxs[i]);
        if(idx >= 0){
            same_avg_count += (idx + 1);
        }
    }
    int diff_avg_count = 0;
    for(int i = 0; i < left_one_idxs.size(); i++){
        // binary search find last position left_one_idxs[i] < right...
        int idx = binary_search(right_avg_idxs, left_one_idxs[i]);
        if(idx >= 0){
            diff_avg_count += (idx + 1);
        }
    }
    for(int i = 0; i < left_avg_idxs.size(); i++){
        int idx = binary_search(right_one_idxs, left_avg_idxs[i]);
        if(idx >= 0){
            diff_avg_count += (idx + 1);
        }
    }
    int one_one_count = 0;
    for(int i = 0; i < left_one_idxs.size(); i++){
        int idx = binary_search(right_one_idxs, left_one_idxs[i]);
        if(idx >= 0){
            one_one_count += (idx + 1);
        }
    }

    if(left_num == 0){
        res += same_avg_count;
    }else if(left_num == 1){
        res += same_avg_count;
        res += diff_avg_count;
    }else{
        res += diff_avg_count;
        res += one_one_count;
    }
    cout << res << endl;
}

write answer 切换为英文 切换为中文


转发分享