字母交换
字母交换
http://www.nowcoder.com/questionTerminal/8da0ea4b4853464795f5c32634a1b06f
题解
题目难度:中等
知识点:动态规划
分析:
- 设置一个大小为26*N的二维矩阵存放字母及字母在字符串中出现的位置,26行表示26个字母,N列表示对应字母出现的位置
vector< vector<int> > vec(26); for(int i=0; i<str.size(); ++i) { vec[str[i]-'a'].push_back(i); }
- 逐次取出每个字母出现次数的行vec[k]
2-1 计算当前字母,相邻两个位置移动到一起所需要的次数,存放到m*m的矩阵dp中,dp[0][1]表示当前字母第一次出现移动到第二次出现需要的次数,dp[0][1]=abs(v[1]-v[0])-1int n = vec.size(); vector< vector<int> > dp(n, vector<int>(n, 0)); for(int i=0; i<n-1; ++i) { dp[i][i+1] = abs(vec[i+1] - vec[i]) - 1; }
2-2 最快实现将相同字母排在一起的方法就是从两边往中间靠,dp[i][j]是当前状态,表示第i个数到第j个数移动的次数,那么当前状态只跟dp[i+1][j-1]有关,由于将i位置与j位置移动到一起需要(v[j]-v[i]-1)次,但是由于区间内已经有了移动好的(j-i-1)个字母,所以可以少移动这么多次,固需要减去这个数字,所以动态转移方程可以写作:dp[i][j] = dp[i+1][j-1]+(v[j]-v[i]-1)-(j-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(vec[col] - vec[row]) - (col-row); } }
2-3 在这个最小次数满足满足约束条件的前提下,筛选出最大的连续字母的个数int Max = 0; for(int i=0; i<n; ++i) { for(int j=i; j<n; ++j) { if (dp[i][j] <= m) { Max = max(Max, j-i+1); } } }
- 比较所有字母的最大连续个数,输出其中的最大值即可
int Max = 0; for(int k=0; k<26; ++k) { Max = max(Max, cnt(vec[k])); }
动态规划实现如下:#include <iostream> #include <stdio.h> #include <vector> #include <queue> #include <algorithm> #include <string.h> #include <string> #include <math.h> using namespace std; string str; //输入字符串 int m; //交换次数 int cnt(const vector<int>& vec) { int n = vec.size(); vector< vector<int> > dp(n, vector<int>(n, 0)); for(int i=0; i<n-1; ++i) { dp[i][i+1] = abs(vec[i+1] - vec[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(vec[col] - vec[row]) - (col-row); } } int Max = 0; for(int i=0; i<n; ++i) { for(int j=i; j<n; ++j) { if (dp[i][j] <= m) { Max = max(Max, j-i+1); } } } return Max; } int main() { cin >> str >> m; vector< vector<int> > vec(26); for(int i=0; i<str.size(); ++i) { vec[str[i]-'a'].push_back(i); } int Max = 0; for(int k=0; k<26; ++k) { Max = max(Max, cnt(vec[k])); } cout << Max << endl; return 0; }