在经过了腾讯的洗礼后，这次拼多多的笔试做的还不错。2个小时4道编程题，都做对了。在此凭记忆写下题目并给出解答。
第一题：给一组数，数的个数是偶数，两两配对求和，使得和的最大值减去和的最小值最小。求这个差值。
题目看上去挺难的，当时想了一下感觉就是排序后第一个和最后一个组合，第二个和倒数第二个组合……记录一下最大值和最小值就行了。后来提交上去AC了。改天用数学证明一下这种配对方式是使得最小差值的。
-
#include <iostream>
-
#include <vector>
-
#include <algorithm>
-
using namespace std;
-
-
int main()
-
{
-
int n;
-
cin>>n;
-
vector<int> nums(n);
-
for (int i=0;i<n;i++)
-
{
-
cin>>nums[i];
-
}
-
sort((),nums.end());
-
int max_record=0,min_record=300;
-
for (int i=0;i<n/2;i++)
-
{
-
max_record=max(max_record,nums[i]+nums[n-i-1]);
-
min_record=min(min_record,nums[i]+nums[n-i-1]);
-
}
-
cout << max_record-min_record;
-
return 0;
-
}
第二题：给定0到9十个数字的每个数字的可使用次数，以及A和B两个数的位数，让A和B选择可使用的数字进行组合，使得A*B最小，求这个最小值。
比如 给定0到9的数字各一个: 1 1 1 1 1 1 1 1 1 1 A和B的位数都是2。那么A=01，B=23，可以使得结果最小（A和B都可以有前导0）。
首先有一个点可以肯定的是，A或B拿到数字后，数字肯定是按从小到大的顺序排列的。所以我第一想法是A和B依次拿走剩下数字中最小的那一个。事实上这样不行，上面的例子就是一个反例，按照这种拿法，A=03，B=12，乘积是36，比01*23=23要大。这种方法得了25分。后来又想着说是不是A先拿最小的，A拿完了B再拿，交上去后也不对，只有15分。
把3 4题都做完后再回来做这道题，发现既然A和B都只拿最小的数字，那么其实有很多冗余的给出的数字，这些数字是没有用的。先把这些数字去掉，再进行组合，然后穷举就可以算出A*B的最小值了。这里要用到求组合的算法。
-
#include <iostream>
-
#include <vector>
-
using namespace std;
-
-
// 求0，1，2，…… ,n-1这n个数字中取k个数字的所有组合方式，结果储存在res中
-
void DFS(int n,int k,vector<vector<int>> &res,vector<int>& combination,int step)
-
{
-
if(combination.size()>k)
-
{
-
return;
-
}
-
if(step==k-1)
-
{
-
res.push_back(combination);
-
return;
-
}
-
int start;
-
if(())
-
start=-1;
-
else start=();
-
for(int i=start+1;i<n;i++)
-
{
-
combination.push_back(i);
-
DFS(n,k,res,combination,step+1);
-
combination.pop_back();
-
}
-
}
-
-
int main()
-
{
-
vector<int> counts(10);
-
for(int i=0;i<10;i++)
-
{
-
cin>>counts[i];
-
}
-
int A_len,B_len;
-
cin>>A_len;
-
cin>>B_len;
-
if(counts[0]>=min(A_len,B_len))
-
{
-
cout<<0;
-
return 0;
-
}
-
vector<int> record;
-
for(int i=0;i<A_len+B_len;i++)
-
{
-
for(int j=0;j<counts.size();j++)
-
if(counts[j]!=0)
-
{
-
counts[j]--;
-
record.push_back(j);
-
break;
-
}
-
}
-
vector<vector<int>> index;
-
vector<int> combination;
-
DFS(A_len+B_len,A_len,index,combination,-1);
-
long long res,A,B;
-
for(int i=0;i<index.size();i++)
-
{
-
vector<bool> choose_A(A_len+B_len,false);
-
for(int j=0;j<index[i].size();j++)
-
{
-
choose_A[index[i][j]]=true;
-
}
-
A=0;
-
B=0;
-
for(int j=0;j<A_len+B_len;j++)
-
{
-
if(choose_A[j])
-
A=10*A+record[j];
-
else
-
B=10*B+record[j];
-
}
-
if(i==0) res=A*B;
-
else res=min(A*B,res);
-
}
-
cout<<res;
-
-
-
return 0;
-
}
第三题：给定一个数组，和一个数字d，求数组中两个数之差大于等于d的概率。数组长度1<=L<=100,数字大小1<=s[i]<=50,1<=d<=50。结果保留6位小数。
例如输入：
{1，2，3}
2
输出：0.333333
这个题当时看到就觉得很简单，估计是想考我们会不会输出小数以及解析输入（输入是包括大括号{ }和逗号，的）。我是先用字符串读输入，再转化成数组。
-
#include <iostream>
-
#include <vector>
-
#include <string>
-
using namespace std;
-
-
-
int main()
-
{
-
vector<int> S;
-
string input;
-
cin>>input;
-
int len=input.length();
-
if(len==4)
-
S.push_back((input[1]-'0')*10+input[2]-'0');
-
else
-
S.push_back(input[1]-'0');
-
while(true)
-
{
-
cin>>input;
-
len=input.length();
-
if(len==3)
-
S.push_back((input[0]-'0')*10+input[1]-'0');
-
else
-
S.push_back(input[0]-'0');
-
if(input.back()=='}')
-
break;
-
}
-
int d;
-
cin>>d;
-
int right=0,sum=S.size()*(S.size()-1)/2;
-
for(int i=0;i<S.size();i++)
-
{
-
for(int j=i+1;j<S.size();j++)
-
{
-
if(abs(S[i]-S[j])<=d)
-
{
-
right++;
-
}
-
}
-
-
}
-
printf("%0.6f",double(right)/sum);
-
return 0;
-
-
}
第四题：求一个单词word1到word2的最少操作次数。操作包括增加、删除和修改。
这道题在上次腾讯面试中遇见过，当时没有做出来（并且面试前我还在leetcode中看到过这道题）我的博客：腾讯面试经历
这一次很快的就做出来了，基本思路就是动态规划，其实很简单。
-
#include <iostream>
-
#include <string>
-
#include <vector>
-
using namespace std;
-
-
int main()
-
{
-
string w1,w2;
-
cin>>w1;
-
cin>>w2;
-
int len1=w1.length(),len2=w2.length();
-
vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
-
dp[0][0]=0;
-
int tmp;
-
for(int i=0;i<=len1;i++)
-
{
-
for(int j=0;j<=len2;j++)
-
{
-
tmp=5000;
-
if(i==0&&j==0) continue;
-
if(i>0)
-
{
-
tmp=dp[i-1][j]+1;
-
}
-
if(j>0)
-
{
-
tmp=min(tmp,dp[i][j-1]+1);
-
}
-
if(i>0&&j>0)
-
{
-
if(w1[i-1]==w2[j-1])
-
tmp=min(tmp,dp[i-1][j-1]);
-
else
-
tmp=min(tmp,dp[i-1][j-1]+1);
-
}
-
dp[i][j]=tmp;
-
}
-
}
-
cout<<dp[len1][len2];
-
}
接下来应该有面试机会，加油吧！