CSDN周赛第十二期题解

题解"/>

CSDN周赛第十二期题解

总结：

这次我第一次参加周赛，竞赛挺不错的，难度适中，bug的话好像并没有。总的来说，给我的感受还是很不错的！比赛页面：

1、豚鼠排名榜

已知字符A.B,C。每个字符都有自己的权值q。现不知道权值q，只知道A,B,C的三次比较结果。

输入描述：

输入三个字符串表示三次比较的结果

输出描述：

输出结果，如果不存在输出”Impossible”

输入样例：

A<B

B>C

C>A

输出样例：

ACB

题解：

这道题是初一看觉得好像很简单的样子，但是其实输入都是字符串，好像没那么简单的样子，得用到合适的数据结构才可以解开这个题目。这里我是使用了HashMap来保存所有的状态，比如： Map("A<B",true) Map("B>A",true) Map("B>C",true) Map("C<B",true) Map("C>A",true)Map("A<C",true) 这样子保存，然后再根据ABC、ACB、BCA、BAC、CAB、CBA 这六个进行查找HashMap就ok了，如代码：

public static String solution(String exp1, String exp2, String exp3){String result = "";HashMap<String,Boolean> map = new HashMap<>();map.put(exp1,true);String new1 = exp1.charAt(1) == '>' ? ""+exp1.charAt(2)+"<"+exp1.charAt(0) :""+exp1.charAt(2)+">"+exp1.charAt(0) ;map.put(new1,true);map.put(exp2,true);String new2 = exp2.charAt(1) == '>' ? ""+exp2.charAt(2)+"<"+exp2.charAt(0) :""+exp2.charAt(2)+">"+exp2.charAt(0) ;map.put(new2,true);map.put(exp3,true);String new3 = exp3.charAt(1) == '>' ? ""+exp3.charAt(2)+"<"+exp3.charAt(0) :""+exp3.charAt(2)+">"+exp3.charAt(0) ;map.put(new3,true);
// TODO: 请在此编写代码String a[] = {"ABC","ACB","BAC","BCA","CAB","CBA"};for(int i = 0;i<a.length;i++){String s = a[i];String pp1 = ""+a[i].charAt(0)+"<"+a[i].charAt(1);String pp2 = ""+a[i].charAt(1)+"<"+a[i].charAt(2);String pp3 = ""+a[i].charAt(0)+"<"+a[i].charAt(2);if(map.containsKey(pp1) && map.containsKey(pp2) && map.containsKey(pp3)){result = s;}}if(result.equals("")){return "Impossible";}return result;}

2、字符串转换

题目描述
已知一个字符串a，b。 字符串b中包含数量不等的特殊符号“.”,“*”（字符串存在没有特殊符号或者全由特殊符号组成的情 况）。 “.”表示该字符可以变成任意字符，“* ”表示该字符的前一个字符可以变成任意多个。 现在我们想知道b可否通过特 殊符号变成a。 a* 可以转化为a,aa,aaa,aaaa…

题解：

这个题在某扣上面做过，叫做正则表达式，可以用递归来解决这个问题，每次递归减短 a和 b 的长度，如果最后a和b 同时为空，那么输出yes，否则输出no.然后如果b的第二个字符是'*'的话，可以去掉*和其前面的字符与a递归一下,对比还有将a的首个字符去掉与b进行递归，如果两个最后返回true也是yes

    public static boolean ok(String a,String b){if(b.length() == 0){return a.length()==0;}boolean nowOk = a.length()>0 && (a.charAt(0) == b.charAt(0) || b.charAt(0) == '.');if(b.length() >= 2 && b.charAt(1) == '*'){String bb = 2 < b.length() ? b.substring(2) : "";String aa = 1 < a.length() ? a.substring(1) : "";return ok(a,bb) || nowOk && ok(aa,b);}else{String a1 = 1<a.length() ? a.substring(1) : "";String b1 = 1<b.length() ? b.substring(1) : "";return nowOk && ok(a1,b1);}}public static String solution(String a, String b) {String result = "";if (ok(a, b)) {result = "yes";} else {result = "no";}
// TODO: 请在此编写代码return result;}

3. 蚂蚁家族

题目描述
小蚂蚁群是一个庞大的群体，在这个蚂蚁群中有n只小蚂蚁 ，为了保证所有蚂蚁在消息传送的时候都能接收到消息，需要在他们之间建立通信关系。就是要求小蚂蚁都可以通过多只或者直接联系到其他人。
已知几条小蚂蚁之间有通信关系，请问还需要再新建至少多少条关系？

输入描述：

第一行输入整数n，m；n为小蚂蚁总数；m为关系数。(1<=n,m<=1000)
以下m行每行m对整数x，y。(代表x与y有联系)

输出描述：

输出最少需要新建关系数。

输入样例：

4 3
1 2
2 3
3 4

输出样例：

0

题解：

这个题是我最先做出来的，并查集模板，直接过，找到有多少个没连到一起的块，数量-1就是需要连接的数量了！

public static int get(int x){if(x == fa[x]){return x;}return fa[x] = get(fa[x]);}public static void merge(int x,int y){int fx = get(x);int fy = get(y);if(fx != fy){fa[fx] = fy;}}public static int fa[];public static int solution(int n, int m, ArrayList<ArrayList<Integer>> vector){int result = 0;fa = new int[1001];for(int i = 1;i<=n;i++){fa[i] = i;}for(int i = 0;i<m;i++){ArrayList<Integer> as = vector.get(i);merge(as.get(0),as.get(1));}for(int i = 1;i<=n;i++){if(fa[i] == i){result++;}}
// TODO: 请在此编写代码result--;return result;}

4.小股炒股

题目描述
已知n天后的股票行情，现在已有的本金是m，
规定只能入手一次股票和抛售一次股票。
最大收益是？

输入描述：

第一行输入整数n，m。(1<=n<=1000,1<=m<=10000)
第二行输入n个整数表示某股票单股价格p。(1<=p<=1000)

输出描述：

输出小最大收益

输入样例：

2 4
3 7

输出样例：

8

题解：

直接模拟买卖股票就好了，最后在对比大小得到最大收益。

public static int solution(int n, int m, ArrayList<Integer> arr){int result = 0;for(int i = 0;i < n;i++){int num1 = arr.get(i);if(m < num1){continue;}int chu = m/num1;int sheng = m - chu*num1;int maxn = -1;for(int j = i+1;j<n;j++){int num2 = arr.get(j);maxn = Math.max(maxn,num2);}result = Math.max(result,maxn*chu+sheng);}
// TODO: 请在此编写代码return result;}