牛客题霸题解
题目：字符串距离计算
题解：
这个题暴力就好了，三层循环枚举哪个字符转换成哪个字符，然后将第一个串中的所有该字符替换，再比较两个串中不同的字符有多少个，每次更新最小值就好了。
代码：
class Solution {
public:
/**
* 计算最少的距离
* @param S1 string字符串 第一个字符串
* @param S2 string字符串 第二个字符串
* @return int整型
*/
int GetMinDistance(string S1, string S2) {
// write code here
int ans=0x3f3f3f;
for(int k=0;k<26;k++){
for(int l=0;l<26;l++){
int cnt=0;
string s=S1;
for(int i=0;i<s.size();i++){
if(s[i]-'a'==k) s[i]='a'+l;
if(s[i]!=S2[i]) cnt++;
}
ans=min(ans,cnt);
}
}
return ans;
}
};
题目：牛妹的蛋糕
题解：
因为每天吃掉剩余的1/3+1，到n天只剩1，所以倒推相当于前一天吃掉的是当天的（x+1）*3/2，公式推出来直接求解即可，不会爆long long。 。
代码：
class Solution {
public:
/**
*
* @param n int整型 只剩下一只蛋糕的时候是在第n天发生的．
* @return int整型
*/
int cakeNumber(int n) {
// write code here
int ans=1;
for(int i=1;i<n;i++){
ans++;
ans*=3;
ans/=2;
}
return ans;
}
}; 题目： 最少素数拆分
题解：
如果本身就是素数的话，那么直接输出1就好了；
按照哥德巴赫的猜想：
如果这个数是偶数，那么输出2；
奇数的情况可以分成2+N-2，如果N-2是一个质数的话，那么输出2，否则输出3。
代码：
class Solution {
public:
/**
* 判断给定的正整数最少能表示成多少个素数的和
* @param N int整型 给定的正整数
* @return int整型
*/
int MinPrimeSum(int N) {
// write code here
int n=sqrt(N);
int flag=1;
for(int i=2;i<=n;i++){
if(N%i==0){
flag=0;
break;
}
}
if(flag) return 1;
flag=1;
for(int i=2;i<=n;i++){
if((N-2)%i==0){
flag=0;
break;
}
}
if(flag||N%2==0) return 2;
return 3;
}
};
题目： 神奇的数字
题解：
一开始看成了偶数位，，导致一直过不去样例...
就将偶数存起来，然后翻转偶数串，再遍历一遍原串，遇到偶数就将翻转后的位置的字符放上去。
代码：
class Solution {
public:
/**
*
* @param number string字符串
* @return string字符串
*/
string change(string number) {
// write code here
string ans;
for(int i=0;i<number.size();i++){
if((number[i]-'0')%2==0) ans+=number[i];
}
reverse(ans.begin(),ans.end());
int k=0;
for(int i=0;i<number.size();i++){
if((number[i]-'0')%2==0) number[i]=ans[k++];
}
return number;
}
}; 题目：远亲不如近邻
题解：
看数据范围n*m复杂度肯定是不行的，所以要用二分，变成mlogn就可以了。先给a数组排个序，因为二分得是有序的数组才行。然后二分第一个比他大的位置坐标和第一个比他小的位置坐标，取两个位置和x[i]差值的最小值，将每次的答案存入vector中。
代码：
class Solution {
public:
/**
* 远亲不如近邻
* @param n int整型 居民个数
* @param m int整型 方案个数
* @param a int整型vector 居民的位置
* @param x int整型vector 方案对应的位置
* @return int整型vector
*/
vector<int> solve(int n, int m, vector<int>& a, vector<int>& x) {
// write code here
sort(a.begin(),a.end());
vector<int>ans;
for(int i=0;i<m;i++){
int l=0,r=n-1;
int res=n-1;
while(l<=r){
int mid=l+r>>1;
if(a[mid]>=x[i]){
r=mid-1;
res=mid;
}
else l=mid+1;
}
int p=abs(a[res]-x[i]);
l=0,r=n-1;
res=0;
while(l<=r){
int mid=l+r>>1;
if(a[mid]<=x[i]){
l=mid+1;
res=mid;
}
else r=mid-1;
}
p=min(p,abs(a[res]-x[i]));
ans.push_back(p);
}
return ans;
}
};
题目： 打字
题解：
用栈模拟就好了，每次遇到'<' 判断一下栈是否为空，不为空就栈顶出栈，如果字符不为'<'就往战力
代码：
class Solution {
public:
/**
*
* @param s string字符串
* @return string字符串
*/
string Typing(string s) {
// write code here
stack<char>q;
string ans;
for(int i=0;i<s.size();i++){
if(s[i]=='<') {if(!q.empty()) q.pop();}
else q.push(s[i]);
}
while(!q.empty()){
ans+=q.top();
q.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}
}; 题目： 车站建造问题
题解：
如果本身就是素数或者1的话，那么答案+1；
按照哥德巴赫的猜想：
如果这个数是偶数，那么答案+2；
奇数的情况可以分成2+N-2，如果N-2是一个质数的话，那么答案+2，否则答案+3。
这不就是上边的素数分解题目!
最后答案要加一个车站，因为算的是区间的距离，比车站个数少一个。
代码：
class Solution {
public:
/**
*
* @param n int整型
* @param a int整型一维数组
* @param aLen int a数组长度
* @return int整型
*/
int MinPrimeSum(int N) {
// write code here
int n=sqrt(N);
int flag=1;
for(int i=2;i<=n;i++){
if(N%i==0){
flag=0;
break;
}
}
if(flag||N==1) return 1;
flag=1;
for(int i=2;i<=n;i++){
if((N-2)%i==0){
flag=0;
break;
}
}
if(flag||N%2==0) return 2;
return 3;
}
int work(int n, int* a, int aLen) {
// write code here
int ans=n;
for(int i=0;i<n-1;i++){
int p=a[i+1]-a[i];
ans+=MinPrimeSum(p);
ans--;
}
return ans;
}
}; 题目： 牛妹的礼物
题解：
简单dp。
状态转移方程为dp[i][j]=min(dp[i][j], dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
如果dp从1开始的话就要初始化一下dp[0][i]和dp[i][0]为前缀和，当然从0开始的话只要判断边界能不能走就好了。
代码：
class Solution {
public:
/**
*
* @param presentVolumn int整型vector<vector<>> N*M的矩阵，每个元素是这个地板砖上的礼物体积
* @return int整型
*/
int dp[310][310];
int selectPresent(vector<vector<int> >& presentVolumn) {
// write code here
int n=presentVolumn.size();
int m=presentVolumn[0].size();
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=0x3f3f3f;
}
}
for(int i=1;i<=n;i++) dp[i][0]=dp[i-1][0]+presentVolumn[i-1][0];
for(int i=1;i<=m;i++) dp[0][i]=dp[0][i-1]+presentVolumn[0][i-1];
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
dp[i][j]=min(dp[i][j],dp[i-1][j]+presentVolumn[i-1][j-1]);
dp[i][j]=min(dp[i][j],dp[i][j-1]+presentVolumn[i-1][j-1]);
dp[i][j]=min(dp[i][j],dp[i-1][j-1]+presentVolumn[i-1][j-1]);
}
}
return dp[n][m];
}
}; 题目：牛牛算数
题解：
用从小到大排序的优先队列就可以快速的解决问题了。当优先队列的大小大于1时，就不断从中取出两个数，计算他们的和，再放入队列中，答案加上c*(x+y)，直到队列大小为1，返回答案；
代码：
class Solution {
public:
/**
* 返回一个数字表示输出计算n个数字和的最小花费的时间。
* @param n int整型 表示有n个数。
* @param c int整型 参数c
* @param a int整型vector ai表示第i个数的大小
* @return long长整型
*/
long long solve(int n, int c, vector<int>& a) {
// write code here
long long ans=0;
priority_queue<long long,vector<long long>,greater<long long > >q;
for(int i=0;i<n;i++) q.push((long long )a[i]);
while(q.size()>1){
long long x=q.top();
q.pop();
long long y=q.top();
q.pop();
ans+=c*(x+y);
q.push(x+y);
}
return ans;
}
}; 题目： 分组
题解：
二分最大值就好了，二分判断的时候一直加数字直到大于等于最大值，组数+1，累计数值清零。如果最后组数大于k组，那么返回1，否则返回0。
代码：
class Solution {
public:
/**
* 分组
* @param n int整型
* @param k int整型
* @param a int整型vector
* @return int整型
*/
bool check(int k,int n,vector<int>a)
{
int cnt=0;
int p=0;
for(int i=0;i<a.size();i++){
p+=a[i];
if(p>=k) p=0,cnt++;
}
return cnt>=n;
}
int solve(int n, int k, vector<int>& a) {
// write code here
int l=0,r=1e9;
int ans=0;
while(l<=r){
int mid=l+r>>1;
if(check(mid,k,a)){
l=mid+1;
ans=mid;
}
else r=mid-1;
}
return ans;
}
}; 
