当前位置:网站首页>Number of exchanges in the 9th Blue Bridge Cup finals
Number of exchanges in the 9th Blue Bridge Cup finals
2022-07-07 16:59:00 【@Little safflower】
Problem description
IT The demand for industrial talents is rising . Industry giant Baidu 、 Alibaba 、 tencent ( abbreviation BAT) Recruitment activities on a beach .
The recruitment department is lined up . Because it is free to seize the seat , The seats of the three major companies are staggered randomly , Form like :
ABABTATT, This makes the candidate very uncomfortable .
therefore , Exchange positions as required by the management of the recruitment department , Make the seats of each group close together . That is, the final shape is like :
BBAAATTT This shape , Of course , It could be :
AAABBTTT etc. .Now? , Suppose you can only exchange 2 seats , And know the current seat distribution ,
Your task is to calculate : How many exchanges are needed to make the recruitment seats of each group close together .Input is one line n Characters ( Contains only letters B、A or T), Indicates the current seat distribution .
The output is an integer , Indicates at least the number of exchanges .such as , Input :
TABTABBTTTTThe program should output :
3Another example , Input :
TTAAABBThe program should output :
0We have an agreement , The length of the input string n No more than 10 ten thousand
Resource Convention :
Peak memory consumption ( Including virtual machines ) < 256M
CPU Consume < 1000ms
Please output strictly as required , Don't print like that :“ Please input ...” Extra content of .All code in the same source file , After debugging , Copy and submit the source code .
Do not use package sentence . Do not use jdk1.7 And above .
The name of the main class must be :Main, Otherwise, it will be treated as invalid code .
Java
import java.util.Scanner;
public class Number of exchanges {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
char[] ss = scanner.next().toCharArray();
// Six permutation schemes
char[][] c = {
{'B','A','T'},
{'B','T','A'},
{'A','B','T'},
{'A','T','B'},
{'T','A','B'},
{'T','B','A'}
};
int ans = Integer.MAX_VALUE;
for(int i = 0;i < 6;i++) {
ans = Math.min(ans,fun(ss,c[i][0],c[i][2],c[i][2]));
}
System.out.println(ans);
}
// Divide the whole string into three regions
public static int fun(char[] ss,char A,char B,char C) {
//A In the region a The number of
int a = 0;
//B In the region b The number of
int b = 0;
//A Regional Central Africa a The number of
int Abc = 0;
//A In the region b The number of
int Ab = 0;
//B In the region a The number of
int Ba = 0;
//B In the region c The number of
int Bc = 0;
int len = ss.length;
// Find out A and B The size of the two areas
for(int i = 0;i < len;i++) {
if(ss[i] == A) a++;
if(ss[i] == B) b++;
}
for(int i = 0;i < a;i++) {
if(ss[i] != A) Abc++;
if(ss[i] == B) Ab++;
}
for(int i = a;i < a + b;i++) {
if(ss[i] == A) Ba++;
if(ss[i] == C) Bc++;
}
// The minimum number of exchanges is : take A Regional non a Exchange out ,B Regional non b Exchange out
// because A There are... In the area b,B There are... In the area a, They can exchange directly , Then subtract the number of repeated exchanges
return Abc + Bc + Ba - Math.min(Ba, Ab);
}
}
边栏推荐
- LeetCode 300. 最长递增子序列 每日一题
- 掌握这个提升路径,面试资料分享
- Localstorage and sessionstorage
- [designmode] facade patterns
- 两类更新丢失及解决办法
- Process from creation to encapsulation of custom controls in QT to toolbar (I): creation of custom controls
- Have fun | latest progress of "spacecraft program" activities
- 数据中台落地实施之法
- Direct dry goods, 100% praise
- 蓝桥杯 决赛 异或变换 100分
猜你喜欢
Pisa-Proxy SQL 解析之 Lex & Yacc
AutoLISP series (2): function function 2
模块六
null == undefined
3000 words speak through HTTP cache
DNS 系列(一):为什么更新了 DNS 记录不生效?
最新2022年Android大厂面试经验,安卓View+Handler+Binder
Record the migration process of a project
The latest interview experience of Android manufacturers in 2022, Android view+handler+binder
skimage学习(3)——Gamma 和 log对比度调整、直方图均衡、为灰度图像着色
随机推荐
直接上干货,100%好评
QML beginner
Master this promotion path and share interview materials
Vs2019 configuration matrix library eigen
os、sys、random标准库主要功能
AutoLISP series (2): function function 2
【Seaborn】组合图表、多子图的实现
谈谈 SAP 系统的权限管控和事务记录功能的实现
全网“追杀”钟薛高
偶然升职的内心独白
LeetCode 1186. Delete once to get the sub array maximum and daily question
LeetCode 1049. Weight of the last stone II daily question
The difference and working principle between compiler and interpreter
LeetCode 403. 青蛙过河 每日一题
LeetCode 120. Triangle minimum path and daily question
QT 图片背景色像素处理法
[designmode] flyweight pattern
QT中自定义控件的创建到封装到工具栏过程(一):自定义控件的创建
Imitate the choice of enterprise wechat conference room
Opencv personal notes