首页 > 代码库 > 算法笔记_153:算法提高 判断名次(Java)
算法笔记_153:算法提高 判断名次(Java)
目录
1 问题描述
2 解决方案
1 问题描述
问题描述
某场比赛过后，你想要知道A~E五个人的排名是什么，于是要求他们每个人说了一句话。（经典的开头……-_-!）得了第1名的人23，说了假话；得了第5名的人不好意思，也说了假话；为了使求解问题简单，第3名同样说了假话。（奇数名次说假话）
输入格式
共5行，各行依次表示A~E说的话。
每行包含一个形如“A>=3”的名次判断，即一个大写字母+关系运算符+一个数字，不包含空格。
大写字母A~E，关系运算<、<=、=、>=、>、!=，数字1~5。注意：等于是“=”不是“==”！
每行包含一个形如“A>=3”的名次判断，即一个大写字母+关系运算符+一个数字，不包含空格。
大写字母A~E，关系运算<、<=、=、>=、>、!=，数字1~5。注意：等于是“=”不是“==”！
输出格式
可能有多解，请按照字典序输出排名序列，每个解一行
最后一行输出解的数量
最后一行输出解的数量
样例输入
A=2
D=5
E>3
A>2
B!=1
D=5
E>3
A>2
B!=1
样例输出
ACDEB
AECBD
BADCE
BCADE
BDACE
CEADB
CEBDA
7
AECBD
BADCE
BCADE
BDACE
CEADB
CEBDA
7
2 解决方案
具体代码如下：
import java.util.ArrayList; import java.util.Collections; import java.util.Scanner; public class Main { public static String[] say = new String[5]; public static ArrayList<String> temp = new ArrayList<String>(); public static ArrayList<String> result = new ArrayList<String>(); public void swap(char[] A, int i, int j) { char s = A[i]; A[i] = A[j]; A[j] = s; } public void dfs(char[] A, int step) { if(step == A.length) { StringBuilder s = new StringBuilder(""); for(int i = 0;i < A.length;i++) s.append(A[i]); temp.add(s.toString()); } else { for(int i = step;i < A.length;i++) { swap(A, i, step); dfs(A, step + 1); swap(A, i, step); } } } public boolean judge(int a, String o, int p, int b) { if(b == 1) { //此次说话为真 if(o.equals(">")) { if(a > p) return true; else return false; } else if(o.equals(">=")) { if(a >= p) return true; else return false; } else if(o.equals("=")) { if(a == p) return true; else return false; } else if(o.equals("!=")) { if(a != p) return true; else return false; } else if(o.equals("<")) { if(a < p) return true; else return false; } else if(o.equals("<=")) { if(a <= p) return true; else return false; } } else if(b == 0) { //此次说话为假 if(o.equals(">")) { if(a <= p) return true; else return false; } else if(o.equals(">=")) { if(a < p) return true; else return false; } else if(o.equals("=")) { if(a != p) return true; else return false; } else if(o.equals("!=")) { if(a == p) return true; else return false; } else if(o.equals("<")) { if(a >= p) return true; else return false; } else if(o.equals("<=")) { if(a > p) return true; else return false; } } return false; } public void getResult(int i, int j) { for(int t = 0;t < temp.size();t++) { String s = temp.get(t); boolean judge1 = true; for(int m = 0;m < 5;m++) { char a = say[m].charAt(0); String o = ""; int p = say[m].charAt(say[m].length() - 1) - ‘0‘; if(say[m].length() == 3) { o = o + say[m].substring(1, 2); } else { o = o + say[m].substring(1, 3); } if(i == m || j == m) { judge1 = judge(s.indexOf(a) + 1, o, p, 1); } else { judge1 = judge(s.indexOf(a) + 1, o, p, 0); } if(judge1 == false) break; } if(judge1 == false) continue; int a1 = s.indexOf((‘A‘+i)); int a2 = s.indexOf((‘A‘+j)); if((a1 == 1 && a2 == 3) || (a1 == 3 && a2 == 1)) { judge1 = true; } else { judge1 = false; } if(judge1 == true) { if(!result.contains(s)) result.add(s); } } } public static void main(String[] args) { Main test = new Main(); String A = "ABCDE"; char[] B = A.toCharArray(); test.dfs(B, 0); Scanner in = new Scanner(System.in); for(int i = 0;i < 5;i++) say[i] = in.next(); for(int i = 0;i < 5;i++) { for(int j = i + 1;j < 5;j++) test.getResult(i, j); } Collections.sort(result); for(int i = 0;i < result.size();i++) System.out.println(result.get(i)); System.out.println(result.size()); } }
算法笔记_153:算法提高 判断名次(Java)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。