【编码题】字符串S由小写字母构成,长度为n。定义一种操作,每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后,字符串中最多有多少个连续的位置上的字母相同?
【编码题】字符串S由小写字母构成,长度为n。定义一种操作,每次都可以挑选字符串中任意的两个相邻字母进行交换。询问在至多交换m次之后,字符串中最多有多少个连续的位置上的字母相同?
第一行为一个字符串S与一个非负整数m。(1 <= |S| <= 1000, 1 <= m <= 1000000)
一个非负整数,表示操作之后,连续最长的相同字母数量。
abcbaa 2
2
使2个字母a连续出现,至少需要3次操作。即把第1个位置上的a移动到第4个位置。 所以在至多操作2次的情况下,最多只能使2个b或2个a连续出现。
#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; } /* lufhkcyqnnheshcogbovclcxrfneppkxdvolqtstdkmgsscvfvnnigltgyardkfvavrrwbblzcxzwmteonksiaswfvfsgpxwosev 200 hkdbqojqvxlfulshrhpysezhlyzolb 20 ooxnwetkuvpqjuabmovhkpypxbgpxzemuupqvavonyfscmkrvsvixcejdrutwwfndzkdxbrwgptievanpqfzlprwyqupidspcgrw 200 */动态规划状态转移方程dp[i][j] = dp[i+1][j-1] + abs(vec[j] - vec[i]) - (j-i); dp[i][j]第i个数到第j个数移动的次数
def cal(p,m): dp = [[0 for i in range(len(p))] for j in range(len(p))] for i in range(0,len(p)-1): dp[i][i+1] = p[i+1]-p[i]-1 for le in range(2,len(p)): for i in range(0,len(p)-le): j = i+le dp[i][j] = dp[i+1][j-1]+(p[j]-p[i])-(j-i) res = 0 for i in range(len(p)): for j in range(i,len(p)): if dp[i][j]<=m: res = max(res,j-i+1) return res inp = input().split() s,m = inp[0],int(inp[1]) positions = [[] for i in range(26)] for i in range(len(s)): positions[ord(s[i])-ord('a')].append(i) res = 0 for i in range(26): res = max(res,cal(positions[i],m)) print(res)
while True: try: line = input().split() s = list(line[0]) n = int(line[1]) # 将字符去重复 ss = set(s) maxsub = 1 for i in ss: # 记录字符出现的位置 pos = [] for j in range(len(s)): if s[j] == i: pos.append(j) ll = len(pos) if ll < maxsub: continue temp = 1 dp = [[1 for _ in range(ll)] for _ in range(ll)] for lens in range(2,ll+1): for j in range(ll+1-lens): k = j + lens - 1 dp[j][k] = dp[j+1][k-1] + pos[k] - pos[j] + 1 - lens if dp[j][k] <= n: temp = lens maxsub = max(maxsub, temp) print(maxsub) except: break
package main import ( "fmt" ) func main(){ var s string var m int64 fmt.Scan(&s, &m) arrs := [26][]int64{} for i, chr := range s { arrs[int32(chr) - 'a'] = append(arrs[int32(chr) - 'a'], int64(i)) } var ans int64 for _, arr := range arrs { n := len(arr) if int64(n) <= ans { continue } dp := make([][]int64, n) for i := 0; i < n;i++ { dp[i] = make([]int64, n) } for i := n - 1; i >= 0; i-- { for j := i + 1; j < n; j++ { if j == i + 1 { dp[i][j] = arr[j] - arr[i] - 1 }else { //dp[i][j] = dp[i + 1][j - 1] + arr[j] - arr[i] - 1 - (j - i - 1) dp[i][j] = dp[i + 1][j - 1] + arr[j] - arr[i] - int64(j) + int64(i) } if dp[i][j] <= m { if int64(j - i + 1) > ans { ans = int64(j - i + 1) } } } } } fmt.Println(ans) }
#include <bits/stdc++.h> using namespace std; bool F(vector<vector<int>> &v, int n, int m){ bool flag = false; for(int i=0;i<v.size();i++){ if(v[i].size() < n) continue; for(int j=0;j<v[i].size();j++){ if(j+n > v[i].size()) break; int s = 0, t = j+n/2; for(int k=j;k<j+n;k++){ if(k<=t) s += (v[i][t] - (t-k) - v[i][k]); else s += (v[i][k] - v[i][t] - (k-t)); } if(s <= m) flag = true; } } return flag; } int main(){ string s; int m, cnt=0; cin>>s; scanf("%d", &m); map<char, int> mp; for(auto &c: s) mp[c] = cnt++; vector<vector<int>> v; for(int i=0;i<cnt;i++){ vector<int> t; v.push_back(t); } for(int i=0;i<s.size();i++) v[mp[s[i]]].push_back(i); int l=0, r=s.size()+1; while(l<r){ int k = (l+r)>>1; if(F(v, k, m)) l = k+1; else r = k; } if(l==0) puts("0"); else printf("%d\n", l-1); return 0; }
public static void main(String[] args) { Scanner sc=new Scanner(System.in); String str=sc.nextLine(); String s=str.split(" ")[0]; //用于接收待处理的字符串 int m=Integer.parseInt(str.split(" ")[1]); //用来接收处理字符串的的次数m int res=0; //建立列表,装接收置,待处理的是26个字母a-z,每接收一个字母都要建立相应的ArrayList for(char ch='a';ch<='z';ch++) { ArrayList<Integer> positions=new ArrayList<Integer>(); for(int i=0;i<s.length();i++) { if(ch==s.charAt(i)) { //键盘接收来的字符刚好与ch表示的字符相同,则为键盘接收来的字符添加下标 positions.add(i); } } //如果只有1个字符或没有则跳出当前循环 if(positions.size()<2) { continue; } //建立动态规划dp,一维装字母,另一维装位置,其维度与前面建立的positions的大小相等 int size=positions.size(); int dp[][]=new int[size][size]; //dp[i][j]表示,把位置positions[i],,,positions[j]的字母移动到一起所需要的最少移动次数 for(int j=0;j<size;j++) { dp[j][j+1]=positions.get(j+1)-positions.get(j)-1; } //当相同的字母在字符串中多次出现且不连续时,从两边网中间移动,保证移动次数最少。 for(int len=2;len<size;len++) { for(int left=0;left<size-len;left++) { int right=left+len; dp[left][right]=dp[left+1][right-1]+positions.get(right)-positions.get(left)-1-(right-left-1); } } //最后比较 for(int i=0;i<size;i++) { for(int j=i+1;j<size;j++) { if(dp[i][j]<=m) { res=Math.max(res, j-i+1); } } } } System.out.println(res); }
#include <bits/stdc++.h> using namespace std; const int maxn = 1e6 + 10; // 1e3 + 10一直段错误 char s[maxn]; vector<int> pos[30]; int main() { int n, m; scanf("%s%d", s, &m); n = strlen(s); for (int i = 0; i < n; i++) { pos[s[i] - 'a'].push_back(i); } int res = 0; for (int i = 0; i < n; i++) { int x = s[i] - 'a', left = m, cnt = 1; int l = i-1, r = i+1; int p = lower_bound(pos[x].begin(), pos[x].end(), i) - pos[x].begin(); int le = p-1, ri = p+1; while (left > 0 && (le >= 0 || ri < pos[x].size())) { if (le < 0) { left -= pos[x][ri] - r; ++r; ++ri; ++cnt; } else if (ri >= pos[x].size()) { left -= l - pos[x][le]; --l; --le; ++cnt; } else { if (pos[x][ri]-r < l-pos[x][le]) { left -= pos[x][ri] - r; r++; ri++; cnt++; } else { left -= l - pos[x][le]; l--; le--; cnt++; } } } if (left < 0) cnt--; res = max(res, cnt); } cout << res << endl; }
""" # 动态规划题。 # 首先题目说只有小写字母,字符的类型的只有26种,为了简化问题我们只要讨论a字符,其他字符只要重复这个过程即可 # 对于a字符,只需要记下他的位置char[c],就是把这些位置转换成连续的最少转换次数,这就可以dp了。 # 设dp[i][j]表示把i到j这一段合在一起最少需要的次数,根据不等式|x−a|+|x−b|a), 可以推导出其状态转移方程为: # dp[i][j]=dp[i+1][j−1]+char[j]−char[i]−(leng-1) # 枚举的时候是先枚举小区间然后再枚举大区间。 """ def exchange(char,m): n = len(char) ans = 0 dp = [[0]*n for i in range(n)] for i in range(n-1): dp[i][i+1] = char[i+1] - char[i] - 1 # 相邻两个的交换的最小次数 if dp[i][i+1] < m: ans = 2 for leng in range(2,n): for i in range(0,n-leng): j = leng + i dp[i][j] = dp[i+1][j-1] + (char[j]-char[i]) - (j-i-1) if dp[i][j] < m: ans = leng + 1 return ans s, m = input().split() m = int(m) char = [[] for _ in range(26)] # 记录字符串中每一字母的位置 for i in range(len(s)): char[ord(s[i])-97].append(i) res = 0 for i in range(26): if char[i]: res = max(res,exchange(char[i],m)) print(res)
这一题我觉得作为笔试题,还是有些难度的。
思路是这样的,我们对每一个字母分别求可能连接的成的最大距离。
这时候就需要用26个列表,来分别保存每个字母的出现在原字符串中的位置(代码中v表示)。
我们下面针对一个字母考虑:
dp[i][j]:表示v中第i到第j个位置的字母如果需要移动到在一起,需要移动的次数。
那么转移方程就有了
dp[left][right] = dp[left+1][right-1] + (v[right] - v[left] - 1) - (right - left - 1)
这里做一下说明:
对于最左边位置left和最右边位置right字符串,如果只需要将这俩字符移动在一起,则需要固定的(v[right] - v[left] - 1)次移动,但是这个区间内已经有了移动好的(right - left - 1)个字母,所以可以少移动这么多次,固需要减去这个数字。
s, m = input().split() m = int(m) from collections import defaultdict d = defaultdict(list) for i,c in enumerate(s): d[c].append(i) res = 0 for k,v in d.items(): n = len(v) dp = [[0] * n for _ in range(n)] for i in range(1,n): dp[i-1][i] = v[i]-v[i-1]-1 for k in range(2,n): for i in range(n-k): left, right = i, k+i dp[left][right] = dp[left+1][right-1] + (v[right] - v[left] - 1) - (right - left - 1) for i in range(n): for j in range(i,n): if dp[i][j] <= m: res = max(res, j-i+1) print(res)
s, m = input().split() m = int(m) s = list(s) arr = {} for i in range(0,len(s)): if s[i] not in arr: arr[s[i]] = [] arr[s[i]].append(i) Max = 0 for i in arr: if len(arr[i])>Max: for j in range (Max,len(arr[i])): Sum = 0 for k in range(0,j+1): Sum += abs(arr[i][(j//2)]-arr[i][k]) - abs((0+j//2)-k) if Sum <= m: Max = max(Max,j+1) print(Max)
#include <bits/stdc++.h> #include <vector> using namespace std; vector<int>c[30];//一种字母出现的所有位置记在一个数组 int main() { string str; int M; int ans=1; cin >> str >> M; //在交换次数m内,使最多连续的位置上的字母相同 for (int i = 0; i < str.size(); i++) { char temp = str[i]; c[temp - 'a'].push_back(i); } //选一个字母 for (int ii = 'a'; ii <= 'z'; ii++) { int i = ii - 'a'; int maxx = c[i].size(); //选一个中心点 m for (int m = 0; m < maxx; m++) { int lianXu = 1;//至少连续1(自己) int sheng[2] = {1, 1};//靠在一起变长后对于后面的移动就会省距离 int dire[2] = {m - 1, m + 1};//左右双指针走到的位置 int have = M; while (dire[0] >= 0 || dire[1] < maxx) { int index; int dist[2]; if(dire[0] >= 0) dist[0] = c[i][m] - c[i][dire[0]] - sheng[0]; else dist[0]=0x3f3f3f3f; if(dire[1] < maxx) dist[1] = c[i][dire[1]] - c[i][m] - sheng[1]; else dist[1]=0x3f3f3f3f; index = dist[0] <= dist[1] ? 0 : 1; have -= dist[index]; if (have >= 0) {//还有剩余步数吗? dire[index]=index==0?dire[index]-1:dire[index]+1; sheng[index]++; lianXu++; } else { break; } } ans=max(ans,lianXu); lianXu=1; } } cout<<ans; }
#include <iostream> #include <vector> #include <cmath> #include <deque> using namespace std; int max_move(deque<int>& x, int m){ int len = x.size(); int med, total = 0; if(len % 2 == 1){ // med -> median med = x[len/2]; for(int pos=0; pos<len; pos++) total += abs(x[pos] - med) - abs(len/2 - pos); } else{ // as for even, center&nbs***bsp;median maybe a float, nevermind, // you can also write med as (x[len/2] + x[len/2-1])/2 + 1 total += len/2; med = (x[len/2] + x[len/2-1])/2; for(int pos=0; pos<len; pos++) total += abs(x[pos] - (x[len/2] + x[len/2-1])/2) - abs(len/2 - pos); } //now total is optimized solution to aggregate all of a certain char if(total <= m) return len; else{ // discard the most biased value technically: head&nbs***bsp;tail abs(x.front() - med) >= abs(x.back() - med) ? x.pop_front(): x.pop_back(); return max_move(x, m); } } int main(){ vector<deque<int> > str(26); string temp; int m; cin >> temp >> m; int result = 0; for(int i=0; i<temp.size(); i++) str[temp[i]-'a'].push_back(i); for(int i=0; i<26; i++){ if(!str[i].empty()) result = max(result, max_move(str[i], m)); } cout << result << endl; return 0; }
import java.util.*; public class Main{ static int res = 1; public static void main(String[] args){ Scanner scanner = new Scanner(System.in); String input = scanner.nextLine(); String str = input.split(" ")[0]; int m = Integer.parseInt(input.split(" ")[1]); HashMap<Character, List<Integer>> map = new HashMap<>(); char[] chars = str.toCharArray(); int len = chars.length; for(int i = 0; i < len; i++){ List<Integer> list = map.getOrDefault(chars[i], new ArrayList<>()); list.add(i); map.put(chars[i], list); } for(int i = 0; i < len; i++){ char c = chars[i]; List<Integer> list = map.get(c); moveTogether(list, i, m); /* int lessCount = 0; for(int num : list){ if(num < i){ lessCount++; } else{ break; } } int greatCount = list.size()-1-lessCount; for(int j = 0; j < lessCount; i++){ int cur = list.get(j); // 现在这个节点的位置在cur,要移动到 (0 1 j 3 4 ... lessCount-1)i // lesscount-2的时候对应i-2 // lesscount-1的时候对应i-1 int target = i + j - lessCount; int times = } } */ } System.out.println(res); } // 在times步内,尽可能把list里面的数字移动到mid周围 public static void moveTogether(List<Integer> list, int mid, int times){ int len = list.size(); int mid_index = 0; for(int i = 0; i < len; i++){ if(list.get(i) == mid){ mid_index = i; break; } } int left_index = mid_index-1; int right_index = mid_index+1; int count = 1; // mid为中心的左右边界 int left_mid = mid-1; int right_mid = mid+1; while(times > 0){ if(left_index < 0 && right_index >= len){ break; } // 看一下左边和右边哪个更近一点 int left_dist; if(left_index < 0) left_dist = Integer.MAX_VALUE / 2; else left_dist = left_mid - list.get(left_index); int right_dist; if(right_index >= len) { right_dist = Integer.MAX_VALUE / 2; } else { right_dist = list.get(right_index) - right_mid; } if(left_dist > right_dist){ // 右边靠更加近一点 if(times < right_dist) break; times -= right_dist; right_mid++; count++; right_index++; } else{ if(times < left_dist) break; times -= left_dist; left_mid--; left_index--; count++; } } res = Math.max(count, res); } }
using System; using System.Collections.Generic; namespace CSExercise { class Program { static int maxTurn; static Dictionary<char, List<int>> dict; static int MaxLength(List<int> list) { if (list.Count == 0) return 0; List<int> sortedList = new List<int>(); int centerIndex = list.Count / 2; int moveToIndex = list[centerIndex]; for (int i = 0; i < list.Count; i++) { list[i] = Math.Abs(moveToIndex - list[i]) - Math.Abs(centerIndex - i); } list.Sort(); int result = 0; int turn = maxTurn; foreach (int item in list) { if (item > turn) { break; } result++; turn -= item; } return result; } static void Main(string[] args) { dict = new Dictionary<char, List<int>>(); string[] str = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); string original = str[0]; maxTurn = int.Parse(str[1]); for (int i = 0; i < original.Length; i++) { if (dict.TryGetValue(original[i], out List<int> list)) { list.Add(i); } else { List<int> l = new List<int>(); l.Add(i); dict.Add(original[i], l); } } int maxLength = 0; foreach (var item in dict) { maxLength = Math.Max(maxLength, MaxLength(item.Value)); } Console.WriteLine(maxLength); } } }
import java.util.*; public class Main { private static int m; private static int res=0; private static Map<Character,ArrayList<Integer>> mymap=new TreeMap<>(); public static void main(String []args) { Scanner cin=new Scanner(System.in); String s=cin.next(); m=cin.nextInt(); for(int i=0;i<s.length();i++) { char c=s.charAt(i); if(mymap.containsKey(c)) { ArrayList<Integer> list=mymap.get(c); list.add(i); mymap.put(c,list); } else { ArrayList<Integer> list=new ArrayList<Integer>(); list.add(i); mymap.put(c,list); } } execute(); System.out.print(res); } public static void execute() { for(char c:mymap.keySet()) { ArrayList<Integer> list=mymap.get(c); int n=list.size(); int [][]dp=new int[n][n]; for(int l=2;l<=n;l++) for(int left=0;left+l<=n;left++) { dp[left][left+l-1]=dp[left+1][left+l-2]+list.get(left+l-1)-list.get(left)-1-(l-2); if(dp[left][left+l-1]<=m) { res=Math.max(res,l); } } } } }
public static void main(String[] args){ Scanner in = new Scanner(System.in); int res = 1; String str = in.nextLine(); String s = str.split(" ")[0]; int m = Integer.parseInt(str.split(" ")[1]); for(char ch = 'a'; ch <= 'z'; ch++){ ArrayList<Integer> indexal = new ArrayList<>(); for(int i = 0; i < s.length(); i++){ if(ch == s.charAt(i)){ //添加下标 indexal.add(i); } } if(indexal.size() < 2){ //只有一个连续字符或没有 continue; } int size = indexal.size(); int[][] dp = new int[size][size]; for(int j = 1; j < size; j++){ dp[j-1][j] = indexal.get(j) - indexal.get(j-1) - 1; } //区间大小从2到size,至少三个字符 for(int length = 2; length < size; length++){ for(int left = 0; left < size - length; left++){ int right = left + length ; //例如 //abcdaadegca //对于a来说 //indexal中存放的index: 0 5 6 11 //遍历0-2,1-3 等区间 dp[left][right] = dp[left + 1][right- 1] + indexal.get(right) - indexal.get(left) - 1 -(right - left -1); //m次操作内可以完成 if(dp[left][right] <= m){ res = Math.max(res,right - left + 1); } } } } System.out.println(res); }