【编码题】字符串S由小写字母构成，长度为n。定义一种操作，每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后，字符串中最多有多少个连续的位置上的字母相同？
[编程题]字母交换
- 热度指数：3555 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
输入描述:
第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)
输出描述:
一个非负整数，表示操作之后，连续最长的相同字母数量。
示例1
输入
abcbaa 2
输出
2
说明
使2个字母a连续出现，至少需要3次操作。即把第1个位置上的a移动到第4个位置。 所以在至多操作2次的情况下，最多只能使2个b或2个a连续出现。
/*动态规划虽然很强，但是动态规划还是有一定难度的，其实对于每个字母，
分别记录下他们在的位置，然后分别遍历每一个点，让其左边的点后右边的点同时向它靠拢，
然后记录下最长的链的长度，就可以解决这个问题了。*/
#include<iostream>
#include<vector>
#include<map>
using namespace std;
int main()
{
string s;
int m;
cin>>s>>m;
map<char,vector<int> > loc;
map<char,int> res;
for(int i=0;i<s.size();i++)
{
loc[s[i]].push_back(i);
}
int result=0;
for(map<char,vector<int> >::iterator iter=loc.begin();iter!=loc.end();iter++)
{
char ch=iter->first;
vector<int> v=iter->second;
int k;
int stepl,stepr;
for(int i=0;i<v.size();i++)
{
k=m;
int left=i-1,right=i+1;
while(true)
{
if(left<0&&right>=v.size()) break;
stepl=m+1;
stepr=m+1;
if(left>=0)
{
stepl=(v[i]-v[left])-(i-left);
}
if(right<v.size())
{
stepr=(v[right]-v[i])-(right-i);
}
if(min(stepl,stepr)>k) break;
if(stepl<stepr)
{
k-=stepl;
left--;
}else if(stepr<stepl)
{
k-=stepr;
right++;
}
else
{
k-=stepl;
left--;
}
}
res[ch]=max(res[ch],right-left-1);
}
result=max(result,res[ch]);
}
cout<<result<<endl;
return 0;
}
编辑于 2018-05-04 09:30:31
回复(1)
更多回答
思路：
对于每个字母，将其出现的位置存储在一维数组position[]中。递归遍历这些位置的所有组合（可通过两个for循环嵌套实现，这样就不会重复）。
递归函数dfsSwichCharacter(i,j,position)返回的是实现position[i]到position[j]之间的相同字母连续排列需要移动的次数。这里注意状态转移方程，当j==i+1时说明字符串s中position[i]和position[j]之间不可能再有该字母，所以移动次数就是坐标之差减一；当j>i+1时移动次数相当于是把position[j]的字母移到position[i]隔壁的次数减去这两个位置之间该字母的个数。
如果此时交换次数没有超出限制，则检查此时交换后相同连续出现的字母是不是最长并更新answer = Math.max(answer, q-p+1)。
最后，每个字母在限制内移动次数得到的最大长度保存在length[]数组中。import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String[] strs = sc.nextLine().split(" ");
String s = strs[0];
int count = Integer.parseInt(strs[1]);
int len = s.length();
int[][] record = new int[len][26]; //记录字符串s的每个位置和26个字母的关系
int[] length = new int[26]; //记录每个字母在规定交换次数内最长的相同字母数量
for(int i = 0; i < len; i++){
record[i][s.charAt(i)-'a'] = 1;
}
for(int i = 0; i < 26; i++){
int[] position = new int[len]; //对于每个字母，记录字符串s中出现该字母的位置
int k = 0; //字符串s中出现该字母k次
for(int j = 0; j < len; j++){
if(record[j][i] == 1){
position[k] = j;
k += 1;
}
}
if(k == 0){
length[i] = 0;
}else if(k == 1){
length[i] = 1;
}else{
int answer = Integer.MIN_VALUE;
for (int p = 0; p < k; p++){
for (int q = p+1; q < k; q++){
int res = dfsSwichCharacter(p, q, position);
if(res <= count){ //在规定交换次数内，更新连续的某个相同字母数量
answer = Math.max(answer, q-p+1);
}
}
}
length[i] = answer;
}
}
int result = Integer.MIN_VALUE;
for(int i : length){
result = Math.max(result, i);
}
System.out.println(result);
}
public static int dfsSwichCharacter(int i, int j, int[] position){
if(i == j){
return 0;
}else if(i+1 == j){ //说明字符串s中position[i]和position[j]之间不可能再有该字母，所以移动次数就是坐标之差减一
return position[j] - position[i] - 1;
}else{ //移动次数相当于是把position[j]的字母移到position[i]隔壁的次数减去这两个位置之间该字母的个数
return dfsSwichCharacter(i+1, j-1, position) + position[j]-position[i]-1 - (j-i-1);
}
}
}
发表于 2019-08-13 05:49:18
回复(0)
#include <iostream>
#include <string>
using namespace std;
int main(void)
{
string str;
int step_max = 0;
cin >> str >> step_max;
int i = 0;
int lo = 0, hi = 0;
int step = 0;
int size = str.length();
int result = 0 , max_result = 0;
bool flag1 = true;
bool flag2 = true;
char target;
int step_lo = 0, step_hi = 0;
int ss = 0;
int s = 0;
int base_lo = 0;
int base_hi = 0;
for(i=0; i<size; i++)
{
step = step_max;
lo = hi = i;
target = str[i];
flag1 = true;
flag2 = true;
base_lo = 0;
base_hi = 0;
while(lo > 0 && str[lo-1] == str[lo])
lo--;
while(hi < size-1 && str[hi+1] == str[hi])
hi++;
s = hi - lo + 1;
ss = 0;
while(step > 0)
{
step_lo = step;
step_hi = step;
int temp_lo = lo;
int temp_hi = hi;
while(flag1 == true && step_lo > 0 && lo > 0 && str[lo-1] != target)lo--,step_lo--;
if(flag1 == true && str[lo-1] != target)
flag1 = false;
while(flag2 == true && step_hi > 0 && hi < size-1 && str[hi+1] != target)hi++,step_hi--;
if(flag2 == true && str[hi+1] != target)
flag2 = false;
base_lo += (step - step_lo);
base_hi += (step - step_hi);
if(step - base_lo < 0)
flag1 = false;
if(step - base_hi < 0)
flag2 = false;
if(flag1 == false && flag2 == false)
{
break;
}
if(flag1 == true && step_lo > step_hi)
{
hi = temp_hi;
lo--;
base_hi -= (step - step_hi);
step = step - base_lo;
ss++;
}
else if(flag2 == false)
{
hi = temp_hi;
lo--;
base_hi -= (step - step_hi);
step = step - base_lo;
ss++;
}
else if(flag2 == true && step_lo <= step_hi)
{
lo = temp_lo;
hi++;
base_lo -= (step - step_lo);
step = step - base_hi;
ss++;
}
else if(flag1 == false)
{
lo = temp_lo;
hi++;
ss++;
base_lo -= (step - step_lo);
step = step - base_hi;
}
}
result = s + ss;
if(result > max_result)
max_result = result;
}
cout << max_result;
return 0;
}
暴力方法一个
发表于 2019-03-15 21:11:43
回复(0)
通过率90%😥😥
不知道为啥
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int times = sc.nextInt();
int max = 0;
char[] cs = str.toCharArray();
Map<Character, List<Integer>> map = new HashMap<>();
for (int j = 0; j < cs.length; j++) {
if (!map.containsKey(cs[j])) {
List<Integer> list = new ArrayList<>();
list.add(j);
map.put(cs[j], list);
} else {
List<Integer> list = map.get(cs[j]);
list.add(j);
map.put(cs[j], list);
}
}
for(Character c:map.keySet()){
List<Integer> list = map.get(c);
// int first = 0;
int last = list.size()/2;
// int change = Main.changeTimes(first, last, list);
int change = 0;
if(list.size()%2==0){//判断list长度为奇或偶，
for(int first=list.size()/2-1;first>=0;first--,last++){//若为偶，使first和last为最中间两项
change += list.get(last)-list.get(first)-(last-first);
if(change<=times){
max = (last-first+1)>max?(last-first+1):max;
}
}
}else{
for(int first=list.size()/2;first>=0;first--,last++){//若为奇，使first和last都为最中间一项
change += list.get(last)-list.get(first)-(last-first);
if(change<=times){
max = (last-first+1)>max?(last-first+1):max;
}
}
}
}
System.out.println(max);
}
/*使用递归
public static int changeTimes(int first,int last,List<Integer> list){
int res = 0;
System.out.println("first:"+list.get(first));
System.out.println("last:"+list.get(last));
if(last==first){
return 0;
}else if((last-first)==1){
return list.get(last)-list.get(first)-(last-first);
}else{
return changeTimes(first+1,last-1,list)+list.get(last)-list.get(first)-(last-first);
}
}
*/
}
发表于 2019-02-23 16:43:43
回复(2)
/*
先是上面那位老哥的分析：
提取出相同字符的位置，比如ababa中a的位置为（0，2，4），b的位置为（1，3）。对每个位置向量用动态规划求解。
字符a的位置数组为arr，动态规划过程：
dp(i,j)表示字符a第i个位置到第j个位置的字符要全部相邻，至少要用需要多少次交换。
1. i==j时，表示一个字符，不用交换，dp(i,j)为0；
2. i+1==j时，表示两个字符，位置相差arr[j]-arr[i]；
3.其他情况，dp(i,j) = dp(i+1,j-1) + arr[j]-arr[i] - (j - i)；
思路:
首先思考下第3种转移。因为[i+1,j-1]之间已经成了一个连续的段，所以左右两边都是往中间靠的，不管
怎么靠，交换的次数肯定都一样。然后就非常简单了
*/
#include<bits/stdc++.h>
using namespace std;
#define N 1005
int dp[N][N];//dp[i][j]表示第i个某种字符和相同的第j个字符成为一个连续段的花费
char str[2005];//我开了1005竟然说我越界,怀疑数据有问题
int main()
{
int m, len, ans=1;
scanf("%s %d", str, &m);
len=strlen(str);
for(int ch=0; ch<26; ch++)
{
int siz=0;
vector<int> v;
memset(dp, 63, sizeof(dp));
for(int i=0; i<len; i++)
if(str[i]==(ch+'a'))
{
v.push_back(i);
siz++;
dp[siz][siz]=0;
}
for(int i=siz-1; i>=0; i--)
{
for(int j=i+1; j<siz; j++)
{
int dis=v[j]-v[i]-(j-i);
if(i+1!=j)
dis+=dp[i+1][j-1];
dp[i][j]=min(dp[i][j], dis);
if(dp[i][j]<=m) ans=max(ans, j-i+1);
}
}
}
cout<<ans<<endl;
return 0;
}
发表于 2018-01-27 16:03:55
回复(10)
``` c++
/*
这题是可以做到O(n)的。
首先考虑不同的字符
如样例abcbaa
a的位置是(0,4,5)
假设第一个位置在D，我们需要最小化
|0 - D| + |4 - D - 1| + |5 - D - 2|
变成|0 - D| + |3 - D| + |3 - D|
D取中位数时最优。证明可以考虑把这些数放在数轴上，你取一个D作为点，你发现你每次靠近中位数的时候，差值会不断减少
（打acm的应该很熟悉这个。。）
所以考虑某个字符的位置数组为pos[]
pos[i] = pos[i] - i
这样的话，任意取一个子区间(l,r)都能确定答案就是
|pos[l] - D| + |pos[l + 1] - D| + ... + |pos[r] - D|
处理前缀和，就可以快速求出这一段的最小花费，具体就是知道了D，那就知道绝对值拆开来是怎样。
所以对每个字符进行尺取就行了。
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 2e6 + 15;
vector<int>C[27];
int pre[N];
inline int check(int l, int r) {
int mid = (r + l) >> 1;
int pos = pre[mid] - pre[mid - 1];
return pos * (mid - l) - pre[mid - 1] + pre[l - 1] + pre[r] - pre[mid] - pos * (r - mid);
}
int main() {
#ifdef local
freopen("input", "r", stdin);
// freopen("out.txt","w",stdout);
#endif
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
string s;
int m;
cin >> s >> m;
for(int i = 0; i < (int) s.size(); i++) {
C[s[i] - 'a'].push_back(i);
}
int ans = 0;
for(int id = 0; id < 26; id++) {
int sz = C[id].size();
for(int i = 0; i < sz; i++) {
pre[i + 1] = pre[i] + C[id][i] - i;
}
for(int l = 1, r = 1; l <= sz; l++) {
while(r + 1 <= sz && check(l, r + 1) <= m)++r;
ans = max(ans, r - l + 1);
}
}
cout << ans << endl;
}
```
编辑于 2019-03-25 20:44:47
回复(0)
发表于 2018-03-07 09:13:37
回复(1)
ababab
建一个数组，记录每个a出现的位置arr={0,2,4,6}
设dp(i,j)为：将第i个a-第j个a，之间所有的a调整为连续所需要的***作次数。
则有：
1、如果i=j,则dp(i,j)=0;
2、如果i+1=j,则dp(i,j)=arr[j]-arr[i]-1; 也就是第i个a和第j个a相隔的距离。
3、dp(i,j)=dp(i+1,j-1)+(arr[j]-arr[i]-1)-(j-i-1)
dp(i+1,j-1)-->abbaaba,先把i和j之间的所有a(不包括i和j)调整为连续
然后在把左面的a与中间连续的a相连接，右面的a与中间连续的a相连接，而且可以看出
建一个数组，记录每个a出现的位置arr={0,2,4,6}
设dp(i,j)为：将第i个a-第j个a，之间所有的a调整为连续所需要的***作次数。
则有：
1、如果i=j,则dp(i,j)=0;
2、如果i+1=j,则dp(i,j)=arr[j]-arr[i]-1; 也就是第i个a和第j个a相隔的距离。
3、dp(i,j)=dp(i+1,j-1)+(arr[j]-arr[i]-1)-(j-i-1)
dp(i+1,j-1)-->abbaaba,先把i和j之间的所有a(不包括i和j)调整为连续
然后在把左面的a与中间连续的a相连接，右面的a与中间连续的a相连接，而且可以看出
这一个步骤的步数就是：第i个a和第j个a之间的距离-中间连续的a的个数
即：(arr[j]-arr[i]-1)-(j-i-1) --->(arr[j]-arr[i])-(j-i) 。
编辑于 2018-09-20 17:58:12
回复(1)
#include<bits/stdc++.h>
using namespace std;
int min_step(vector<int>& array, int l, int r){
int mid = (l + r) / 2;
int res = 0;
for(int i = l; i <= r; i++){
res += abs(array[i] - array[mid]) - abs(i - mid);
}
return res;
}
int main(){
string s;
int m;
cin >> s >> m;
unordered_map<char, vector<int>> array;
for(int i = 0; i < s.size(); i++){
array[s[i]].push_back(i);
}
int res = 1;
for(auto i: array){
for(int l = 0, r = 1; r < i.second.size(); r++){
int step = min_step(i.second, l, r);
if(step <= m)
res = max(res, r - l + 1);
else
l++;
}
}
cout << res;
}
发表于 2020-07-17 00:04:02
回复(0)
Java DP。
分别处理每种字符。
dp[i][j] 表示对于某种字符来说，从第 i 个到第 j 个 该字符如果连续，需要最少移动几次。
dp[i][j] =dp[i + 1][j - 1] + ls.get(j) - ls.get(i) - 1 - (j - i - 1);递推式的意思是：从i+1~j-1已经连续好了，再把 i 和 j 也变成连续的，需要这两个位置的差（ls.get(j) - ls.get(i) - 1），减去里面已经有的（i - j - 1）。
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String s = in.next();
int m = in.nextInt();
Map<Character, List<Integer>> map = new HashMap<>();
for (int i = 0; i < s.length(); ++i) {
map.computeIfAbsent(s.charAt(i), k -> new ArrayList<>()).add(i);
}
int ans = 0;
for (List<Integer> ls: map.values()) {
int n = ls.size();
int[][] dp = new int[n][n];
for (int i = n - 1; i >= 0; --i) {
for (int j = i + 1; j < n; ++j) {
dp[i][j] =dp[i + 1][j - 1] + ls.get(j) - ls.get(i) - 1 - (j - i - 1);
if (dp[i][j] <= m) ans = Math.max(ans, j - i + 1);
}
}
}
System.out.println(ans);
}
}
编辑于 2023-12-21 21:52:18
回复(0)
#include <iostream>
#include <string>
#include <vector>
using namespace std;
/*
复杂度O(N)
具体思路：
1、提取出相同字符的位置，比如ababa中a的位置为（0，2，4），b的位置为（1，3）。
然后对每个字符的位置向量单独扫描处理。
2、显然将左右两边向中间靠拢代价最低。
3、当已经知道将[l,r]区间内元素合并的代价时，可以O(1)时间内知道[l,r+1]和[l+1,r]区间内的合并代价。
（参考下方的rpush，lpop函数）
*/
string S;
int N,M;
void rpush(vector<int> &arr,int &l,int &r,int &cost){
r++;
int mid=(l+r)/2;
cost+=arr[r]-arr[mid]-(r-mid);
}
void lpop(vector<int> &arr,int &l,int &r,int &cost){
int mid=(l+1+r)/2;
cost-=arr[mid]-arr[l]-(mid-l);
l++;
}
int check(vector<int> &arr){
if(arr.size()<=1)
return arr.size();
int l=0,r=0;
int cost=0;
int ans=1;
while(r+1<arr.size()){
if(cost>M)
lpop(arr,l,r,cost);
else{
rpush(arr,l,r,cost);
if(cost<=M)
ans = max(ans,r-l+1);
}
}
return ans;
}
int main(){
cin>>S>>M;
N = S.size();
vector< vector<int> > idx(26);
for(int i=0;i<N;++i){
int ch = S[i]-'a';
idx[ch].push_back(i);
}
int ans=1;
for(int i=0;i<26;++i)
ans = max(ans,check(idx[i]));
cout<<ans<<endl;
return 0;
}
编辑于 2022-05-07 22:00:33
回复(0)
二分查找加滑动窗口
#include<bits/stdc++.h>
using namespace std;
int xun(vector<int> v, int l, int mm) {
int n = v.size();
int m = (l + 1) / 2;
int r = 0;
int le = 0;
int re = -1;
for (int i = 0; i < l; i++) {
if (i < m - 1)
r += abs(v[i] - v[m - 1])-abs(m-1-i);
else
le += abs(v[i] - v[m - 1])-abs(m-1-i);
}
re = le + r;
if (le + r <= mm) return le + r;
else {
for (int i = 1; i < n - l + 1; i++) {
m++;
r = r + (v[m-1] - v[m - 2])*((l + 1) / 2) - (v[m-1] - v[i - 1]-(m-i));
le = le - (v[m-1] - v[m - 2])*(l - (l + 1) / 2) + (v[i + l - 1] - v[m-1]-(i+l-m));
re = le + r;
if (le + r <= mm) return re;
}
}
return -1;
}
int main() {
string s;
int m;
cin >> s >> m;
int l = s.length();
if (l == 0) {
cout << 0;
return 0;
}
vector<vector<int>> v(26);
for (int i = 0; i < l; i++) {
v[s[i] - 'a'].push_back(i);
}
int re = 0;
for (int i = 0; i < 26; i++) {
int ll = v[i].size();
if (ll >= 1) {
int ri = ll+1;
int le = 1;
while (le < ri) {
int mi = (ri + le) / 2;
if (xun(v[i], mi, m) == -1) {
ri = mi;
}
else le = mi + 1;
}
if (xun(v[i], le - 1, m) != -1) {
re = max(le - 1, re);
}
}
}
cout << re;
return 0;
}
发表于 2020-09-09 18:51:05
回复(0)
import java.util.*;
/**
* 记录每个字母出现的下标。
* 对每一个字母出现的所有位置，进行滑窗计算移动代价。
* 窗口从一个元素开始扩大，计算代价超过要求，缩小窗口，否则扩大窗口。
*
* 由经验可得，要把滑窗内所有位置移动到连续位置，两边元素靠中间元素移动的代价较小。
* 比如情况[11,13,15,17,19｜21,23,25,30,31]，选取中间靠左的(19, 选中间的任意都行)
* 需要分别计算左右移动到中间元素的代价是多少，左边移动为[15,16,17,18,19]计算得到代价10,
* 右边移动为[19,20,21,22,23,24]代价为21。
* 判断代价是否超过要求。
* 循环所有的字母情况。
*/
public class Main {
static Map<Character, List<Integer>> map = new HashMap<>();
//每个字母出现的下标前缀和，计算代价时就不用再遍历
static Map<Character, List<Integer>> mapPreSum = new HashMap<>();
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
String[] split = s.split(" ");
String str = split[0];
int m = Integer.parseInt(split[1]);
for (int i = 0; i < str.length(); i++) {
List<Integer> idxes = map.getOrDefault(str.charAt(i), new ArrayList<>());
List<Integer> preSum = mapPreSum.getOrDefault(str.charAt(i), new ArrayList<>());
idxes.add(i);
preSum.add(preSum.size() == 0 ? i : preSum.get(preSum.size() - 1) + i);
map.put(str.charAt(i), idxes);
mapPreSum.put(str.charAt(i), preSum);
}
int res = 0;
for (Character c : map.keySet()) {
res = Math.max(res, cost(map.get(c), mapPreSum.get(c), m));
}
System.out.println(res);
}
static int cost(List<Integer> position, List<Integer> preSum, int m) {
int res = 0;
int left = 0, right = 0;
while (right < position.size()) {
int mid = left + (right - left + 1) / 2;
int sumA = cost(position, preSum, left, mid, true);
int sumB = cost(position, preSum, mid, right, false);
int cost = sumB - sumA;
if (cost <= m) {
res = Math.max(res, right - left + 1);
right++;
} else left++;
}
return res;
}
static int cost(List<Integer> pos, List<Integer> preSum, int left, int right, boolean isLeft) {
int count = right - left + 1;
int sum = left == 0 ? preSum.get(right) : preSum.get(right) - preSum.get(left - 1);
int move;
if (isLeft) {
int rightPos = pos.get(right);
move = (rightPos + (rightPos - count + 1)) * count / 2;
} else {
int leftPos = pos.get(left);
move = (leftPos + (leftPos + count - 1)) * count / 2;
}
return sum - move;
}
}
编辑于 2020-08-19 13:53:15
回复(0)
//没有超时，有点意外
/*
记录不同字母出现的下标，得到26个数组；
对每个数组num计算：
dp[i][j]表示num数组i到j位置调整到连续需要的操作数
dp[i][j]=0 (i==j)
=num[j]-num[i]-1 (j-i==1)
=dp[i + 1][j - 1] + num[j] - num[i] - 1 - (j - i - 1) 其他
*/
#include<iostream>
#include<vector>#include<string>
using namespace std;
int main() {
string str;
int N;
cin >> str;
cin >> N;
if (str.empty()) {
cout << 0 << endl;
return 0;
}
vector<vector<int>> res(26,vector<int>());
for (int i = 0; i < str.size(); ++i) {
int t = str[i] - 'a';
res[t].push_back(i);
}
int ans = 1;
for (auto num : res) {
int L = num.size();
vector<vector<int>> dp(L, vector<int>(L, 0));
for (int i = 0; i < L-1; ++i) {
dp[i][i + 1] = num[i + 1] - num[i] - 1;
}
for (int k = 2; k <= L; ++k) {
for (int i = 0; i < L - k; ++i) {
int j = i + k;
dp[i][j] = dp[i + 1][j - 1] + num[j] - num[i] - 1 - (j - i - 1);
if (dp[i][j] <= N && ans < (j - i + 1))
ans = j - i + 1;
}
}
}
cout << ans << endl;
return 0;
}
发表于 2020-08-14 15:53:58
回复(0)
Heap 天 下 第 一
import java.util.*;
public class Main{
public static void main (String[] args) {
Scanner sc = new Scanner(System.in);
String str = sc.next();
int m = sc.nextInt();
HashMap<Character, ArrayList<Integer>> table = new HashMap<>();
for(int i=0;i<str.length();i++){
if(!table.containsKey(str.charAt(i))){
int finalI = i;
table.put(str.charAt(i),new ArrayList<Integer>(){{add(finalI);}});
}else{
table.get(str.charAt(i)).add(i);
}
}
PriorityQueue<Integer> res = new PriorityQueue<Integer>(Comparator.reverseOrder());
for(Character x: table.keySet()){
PriorityQueue<Integer> temp = new PriorityQueue<Integer>(Comparator.reverseOrder());
for(int i = 0;i<table.get(x).size();i++){
int time = m;
int lcount = 1,rcount = 1;
PriorityQueue<Integer> dis = new PriorityQueue<Integer>(new Comparator<Integer>(){
@Override
public int compare(Integer j, Integer k) {
if (Math.abs(j)<Math.abs(k)){
return -1;
}else{
return 1;
}
}
});
for(int j=0;j<table.get(x).size();j++){
dis.add(table.get(x).get(j)-table.get(x).get(i));
}
while (!dis.isEmpty()){
int test = dis.poll();
if(test <0 && Math.abs(test)<=time){
int cost = (test+lcount);
lcount ++;
time += cost;
}else if(test>0 && test <=time){
int cost = (test-rcount);
rcount ++;
time -= cost;
}
}
temp.add(lcount+rcount-1);
}
res.add(temp.poll());
}
System.out.println(res.poll());
}
}
发表于 2020-01-13 17:24:04
回复(0)
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
int m = sc.nextInt();
Map<Character, List> map = new HashMap<>(26); // key为字符串中的每个字母，value记录该字母在字符串中出现的位置
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
List list = map.get(c);
if (list == null)
map.put(c, list = new ArrayList<Integer>(100));
list.add(i);
}
int maxLen = 1; // 记录连续最长的相同字母数量
// 遍历map
for (Map.Entry<Character, List> entry : map.entrySet()) {
List<Integer> arrayList = entry.getValue();
// 遍历字母在字符串中出现的位置
for (int i = 0; i < arrayList.size(); i++) {
int ctr = arrayList.get(i); // 以当前遍历的元素位置为中心，计算其他相同元素到到该中心需移动的步数
int[] move = new int[arrayList.size()];
// 获取 move[]，表示每个相同字母到中心点 ctr 需要移动的最少步数
for (int j = 0; j < arrayList.size(); j++)
move[j] = (Math.abs(arrayList.get(j) - ctr) -
Math.abs(i - j));
// 排序后，选择移动代价最少的前 k + 1 个
Arrays.sort(move);
int sum = 0; // 记录移动步数之和
for (int k = 0; k < move.length; k++) {
sum += move[k];
if (sum > m)
break;
// 每有一个字母移动到中心点，该字母的连续相同数量就增加1
if (k + 1 > maxLen)
maxLen = k + 1;
}
}
}
System.out.println(maxLen);
}
}
发表于 2019-08-08 17:51:17
回复(0)
85%的case 通过，想不明白
import sys line=sys.stdin.readline().strip() #nlikedic={} s,n=line.split() n=int(n) se=set(s)res=1 sdict={} for i in se: sdict[i]=[] for j in range(len(s)): sdict[s[j]].append(j) for c in se: dp=[]*len(sdict[c]) for i in range(len(sdict[c])): dp.append([0]*len(sdict[c])) #for i in range(len(sdict[c])): #dp[i][i]=0 for i in range(0,len(sdict[c])-1): #print(i) for j in range(i+1,len(sdict[c])): rr=sdict[c][j]-sdict[c][i]-(j-i) if i+1!=j: rr+=dp[i+1][j-1] dp[i][j]=rr if dp[i][j]<=n: #print('change',i,j,dp[i][j],res,j-i+1) res=max(res,j-i+1)print(res)
发表于 2019-07-30 16:34:15
回复(0)
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scan=new Scanner(System.in);
String s=scan.next();
int m=scan.nextInt();
char[] chars=s.toCharArray();
Map<Character,ArrayList<Integer>> map=new HashMap<Character,ArrayList<Integer>>();
for(int i=0;i<chars.length;i++)
{
char key=chars[i];
if(map.containsKey(key))
{
ArrayList<Integer> list=map.get(key);
list.add(i);
}
else
{
ArrayList<Integer> list=new ArrayList<Integer>();
list.add(i);
map.put(key,list);
}
}
int count=0;
for(int i=0;i<26;i++)
{
char key=(char) ('a'+i);
ArrayList<Integer> list=map.get(key);
if(list!=null)
{
//j代表新坐标系下标，list.get(j)为第下标为j的字母在原始数组中的下标
//dp为 新坐标系中两个字母对应的原始坐标区间合成连续字母串所需步数
//第一个下标已确定，连续长度len已确定，则第二个下标不可能超过list.size()
//j+1到j所需操作步数（即空格数）为list.get(j+1)-list.get(j)-1
//j+len-2所在字母经操作后已移到原始坐标list.get(j+1)+(len-2-1)处
//j+len-1到j+len-2所需操作步数（即空格数）为list.get(j+len-1)-[list.get(j+1)+(len-2-1)]-1
//list.get(j+1)-list.get(j)-1 + list.get(j+len-1)-[list.get(j+1)+(len-2-1)]-1
//=list.get(j+len-1) - list.get(j) + 1 -len
//或者直接计算空格数，有多少空格，两端字母就移动几次：j+len-1,j区间共有len个字母(包括两端)
//则空格数为： list.get(j+len-1) - list.get(j) + 1 -len;
int[][] dp = new int[list.size()][list.size()];
for(int len=2;len<=list.size();len++) {
for (int j = 0; j + len - 1 < list.size(); j ++) {
dp[j][j+len-1] = dp[j+1][j+len-2] + list.get(j+len-1) - list.get(j) + 1 -len;
if (dp[j][j+len-1] <= m && count < len)
count = len;
}
}
}
}
System.out.println(count);
}
}
编辑于 2019-08-10 16:25:08
回复(1)
问题信息
通过挑战的用户
-
2023-02-22 22:20:41
-
2023-02-07 18:50:58
-
2022-12-17 19:46:17 -
2022-11-02 18:24:12 -
2022-11-02 12:37:59
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
