微软笔试3.25场讨论(附代码)

微软笔试题,根据讨论区内容写了一下前2题,第3题如果之后写出来会再更新
第1题:给定N个数,要求把N个数分为M组,每组内不能有重复的数,求每组最大的数和最小的数差,求所有的差求和最小的结果。
其实没有想到特别直观的方法,如果有比较好的思路请指导。
思路:先去除不可行情况,再最小到大排序、记录每个数的值和出现的次数,然后先从小到大简单贪心,再对后面出现的无法处理的情况贪心的做调整。
/*
1. 讨论去除不可行条件:1. N无法整除M,2. N中存在某个数字出现次数大于M
2. 对于可行条件,先排序,从小到大记录数字和其出现次数
3. 对于M个组,贪心生成每个组,从小到大选取还剩下的数字(每次选了数字,其剩余次数-1),具体为:
   1. 如果选够了N/M个数字,这组先保留;
   2. 如果没有选够,比如选了K个,还需要再选N/M - K个数字,则对于剩下的可选数字,一定和这一组的K个数字重复
   所以,我们把剩下的可选数字从小到大与前面选好的组进行元素置换,对于数字V:
   从下向上进行搜索(贪心),找到第一个不包含V的组,从后先前选取出第1个不在已选的K个数里的数字,置换这两个数
*/

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

struct prs {
    int val;
    int count;
};


bool preprocess(vector<int> &sco, vector<prs> &v, int M) {
    sort(sco.begin(), sco.end());
    prs ptmp;
    int i;
    ptmp.val = sco[0]-1;
    ptmp.count = 0;
    
    for(i = 0; i < sco.size(); i++) {
        if(ptmp.val != sco[i]) {
            if(i != 0) {
                if(ptmp.count > M) {
                    return 0;
                }
                v.push_back(ptmp);
            }
            ptmp.val = sco[i];
            ptmp.count = 1;
        }
        else {
            ptmp.count = ptmp.count + 1;
        }
    }
    v.push_back(ptmp);
    return 1;
}

bool find_val(vector<int> v, int val) {
    int l = 0, r = int(v.size() - 1);
    int mid;
    while(l <= r) {
        mid = (l+r)/2;
        if(v[mid] == val) {
            return 1;
        }
        else if(v[mid] > val){
            r = mid - 1;
        }
        else {
            l = mid + 1;
        }
    }
    return 0;
}

void single_step_up(vector<vector<int> > &grps, vector<int> &tmp, int val) {
    int i, j;
    bool flag = 0;
    for(i = int(grps.size()-1); i >= 0 && flag == 0; i--) {
        if(find_val(grps[i], val) == 0) {
            for(j = int(grps[i].size() - 1); j >= 0 && flag == 0; j--) {
                if(find_val(tmp, grps[i][j]) == 0) {
                    tmp.push_back(grps[i][j]);
                    grps[i].erase(grps[i].begin()+j, grps[i].begin()+j+1);
                    grps[i].push_back(val);
                    flag = 1;
                }
            }
        }
    }
    return;
}

void update(vector<vector<int> > &grps, vector<int> &tmp, vector<prs> &v) {
    int i, cc = 0;
    int steps = int(grps[0].size() - tmp.size());
    for(i = 0; i < steps; i++) {
        while(v[cc].count == 0) {
            cc++;
        }
        single_step_up(grps, tmp, v[cc].val);
        sort(tmp.begin(), tmp.end());
        v[cc].count--;
    }
    return;
}

int bestgroup(vector<int> &sco, int M) {
    if(sco.size()%M != 0) {
        return -1;
    }
    vector<prs> v;
    bool flag = preprocess(sco, v, M);
    if(flag == 0) {
        return -1;
    }
    vector<vector<int> > grps;
    vector<int> tmp;
    int sum = 0;
    
    int i,j,cc;
    for(i = 0; i < M; i++) {
        cc = 0;
        j = 0;
        while(tmp.size() < sco.size()/M && cc < v.size()) {
            if(v[cc].count != 0) {
                tmp.push_back(v[cc].val);
                v[cc].count = v[cc].count - 1;
            }
            cc++;
        }
        if(tmp.size() != sco.size()/M) {
            update(grps, tmp, v);
        }
        grps.push_back(tmp);
        
        tmp.clear();
    }
    
    for(i = 0; i < M; i++) {
        sum = sum + grps[i][sco.size()/M - 1] - grps[i][0];
    }
    return sum;
}

int main() {
    int N, M;
    cin>>N>>M;
    int stmp;
    vector<int> sco;
    int i;
    
    for(i = 0; i < N; i++) {
        cin>>stmp;
        sco.push_back(stmp);
    }
    
    cout<<bestgroup(sco, M)<<endl;
    return 0;
}

第2题:给定一个字符串,每次可以选择消除字符串中的一段回文子串,中间的子串消除后,剩下的左、右的子串会再拼起来,求最少次数课删除整个串。
思路:参考了讨论区代码,动态规划:
/*
 dp[i][j]表示第i~j位的字符串被消除需要的最小次数,则:
 如果s[i] != s[j],那么dp[i][j] = min(dp[i][k] + dp[k+1][j])
 如果s[i] == s[j]:dp[i][j]还有一种额外的情况 = dp[i+1][j-1] ,可以理解为最后一次满足回文直接消除
 也就是一定是可以分为两个分离的字符串段消除,求所有分离处理情况中最小的值
 (根据不同题意有两种情况,即偶数长度的回文是否可以一次消除,会影响不同的初始化条件,本代码假设可以)
 */

#include<iostream>
using namespace std;

int minelim(string s1) {
    if(s1.length() <= 1) {
        return s1.length();
    }
    int dp[s1.length()][s1.length()];
    int i, j, k;
    
    for(i = 0; i < s1.length(); i++) {
        dp[i][i] = 1;
    }
    for(i = 0; i < s1.length()-1; i++) {
        if(s1[i] == s1[i+1]) {
            dp[i][i+1] = 1;
        }
        else {
            dp[i][i+1] = 2;
        }
    }
    
    for(i = 2; i < s1.length(); i++) {
        for(j = 0; i+j < s1.length(); j++) {
            if(s1[j] == s1[i+j]) {
                dp[j][i+j] = dp[j+1][i+j-1];
            }
            else {
                dp[j][i+j] = i+1;
            }
            for(k = j; k < i+j; k++) {
                dp[j][i+j] = min(dp[j][i+j], dp[j][k] + dp[k+1][i+j]);
            }
        }
    }
    
    return dp[0][s1.length()-1];
}

int main() {
    string s1;
    cin>>s1;
    cout<<minelim(s1)<<endl;
}
#微软笔试##微软##笔经##实习##阿里巴巴##笔试题目#
全部评论
能用IDE 么
1 回复
分享
发布于 2020-09-21 17:51
第二题似乎有误,考虑数据1 2 1 1 4 4 1,正确答案应该是2,而按照答主如果s[i] == s[j]:dp[i][j] = dp[i+1][j-1]这个思路,结果是3
点赞 回复
分享
发布于 2020-04-01 21:26
阿里巴巴
校招火热招聘中
官网直投

相关推荐

2 29 评论
分享
牛客网
牛客企业服务