微软笔试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;
} 
莉莉丝游戏二面18人在聊
