笔试刷题-头条2018-07-06

题目描述：

/**
【编码题】
字符串S由小写字母构成，长度为n。定义一种操作，
每次都可以挑选字符串中任意的两个相邻字母进行交换。
询问在至多交换m次之后，字符串中最多有多少个连续的位置上的字母相同？
输入描述:
第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)
输出描述:
一个非负整数，表示操作之后，连续最长的相同字母数量。
输入例子1:
abcbaa 2
输出例子1:
2
例子说明1:
使2个字母a连续出现，至少需要3次操作。即把第1个位置上的a移动到第4个位置。
所以在至多操作2次的情况下，最多只能使2个b或2个a连续出现。
*/

思路如下：

维护一个表每个
每行存放同样字符之间的位置(按原来顺序摆放)
在位置向量中
dp[i][j] = dp[i+1][j-1] + abs(posVec[j] - posVec[i]) - (j-i);
dp[i][j]第i个数->第j个数移动的次数
base case:
dp[i][i]=0
dp[i][i+1]= abs(posVec[i+1] - posVec[i]) - 1
i<=j
这里只枚举i<=j是因为 j<=i时候其实是对称的情况

代码如下：

#include<stdio.h>
#include<iostream>
#include<vector>
 
#define MAX_ROW 26
 
using namespace std;
 
vector<int> posTable[MAX_ROW];
 
int DP(const vector<int> &posVec, int K)
{
    int n = posVec.size();
    vector< vector<int> > dp(n, vector<int>(n, 0));
    for(int i=0; i<n-1; ++i)
    {
        dp[i][i+1] = abs(posVec[i+1] - posVec[i]) - 1;
    }
    for(int j=2; j<n; ++j)
    {
        for(int i=0; i<n-j; ++i)
        {
            int row = i, col = i+j;
            dp[row][col] = dp[row+1][col-1] + abs(posVec[col] - posVec[row]) - (col-row);
        }
    }
    int Max = 0;
    for(int i=0; i<n; ++i)
    {
        for(int j=i; j<n; ++j)
        {
            if (dp[i][j] <= K)
            {
                Max = max(Max, j-i+1);
            }
        }
    }
    return Max;
}
int main()
{
    //建立posTable;
    string line;
    int K;
    cin>>line>>K;
    for(int i=0; line[i]!='\0'; i++)
    {
        if(line[i]<'a' || line[i]>'z')
            return -1;
        posTable[line[i]-'a'].push_back(i);
    }
    //找最大滑动窗口
    int maxSize=0;
    for(int i=0; i<MAX_ROW; i++)
    {
        vector<int> &pos=posTable[i];
        maxSize=max(maxSize, DP(pos, K));
    }
    printf("%d", maxSize);
    return 0;
}