Background
A text string can be encoded into a digits string with a Square like below:
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | A | B | C | D | E |
| 2 | F | G | H | I/J | K |
| 3 | L | M | N | O | P |
| 4 | Q | R | S | T | U |
| 5 | V | W | X | Y | Z |
The 26 letters of the English alphabet do not fit in a 5 × 5 square, I and J are combined.
For example, "BAT" becomes "121144" because B -> 12, A -> 11, T -> 44.
"JEDI" becomes "24151424" because J -> 24, E -> 15, D -> 14, I -> 24.
A key could be used to reorder the alphabet in the square, with the letters (without duplicates) of the key being placed at the beginning and the remaining letters following it in alphabetical order. For example, the key phrase "RIPPLE" would lead to the reordered square below.
| 1 | 2 | 3 | 4 | 5 | |
|---|---|---|---|---|---|
| 1 | R | I/J | P | L | E |
| 2 | A | B | C | D | F |
| 3 | G | H | K | M | N |
| 4 | O | Q | S | T | U |
| 5 | V | W | X | Y | Z |
With this Square, "MAP" becomes "342113" because M -> 34, A -> 21, P -> 13.
By adding fixed mappings below, we can encode some real text.
-
Space -> 00
-
New Line -> 10
-
, -> 01 //Comma
-
. -> 02 //Period
With key phrase "RIPPLE" and text below
NO WAR, NO PAIN LOVE AND PEACE
The encoded digits will be
354100522111010035410013211235101441511500213524001315212315
Question
With key phrase "FINAL FANTASY" and digits string
533432133252324500221413330041230022421333221042130021343200222114333201004213004123004253131053343213325232450022141231004123005342453来分析分析：
需要注意实现的点：
1、我们需要实现一个链表让它能够通过两个数字去定位到链表中的某一元素（链表插入快，删除也快，我们最下面的要求就是实现重排矩阵，至于搜索速度慢我们暂且不论，纯java手搓，有优化的兄弟可以来分享一下你的想法）
2、需要实现初始矩阵的List实现，每一个字母存在一个结点对象里，需要实现坐标与索引的换算，需要实现一整串数字串的每两个数字的成组运算。
3、在输入英文文本重排矩阵的时候，需要判断有没有已经操作过的字符或者待插入的字符是否不存在了？如果输入FASTA那么A重复了就不能二次插入直接忽略。
重要的点就这几个啦，因为5X5的矩阵最多放25个元素，这里的I和J他给到一个位置里了，至于你判断输出I还是J？得靠自己的英语水平，程序毕竟不会有感情的根据英文输出的意思给你替换I与J。
手写java代码干它！ 首先我做一个基本结点的类：Node.java（考虑到I与J在同一个结点里，我给结点设置两种有参构造，左右我嫌太麻烦就直接不用它们了）
class Node {
int left;
int right;
char value;
char value1;
public Node( char value) {
this.value = value;
}
public Node(char value, char value1) {
this.value = value;
this.value1 = value1;
}
}
然后我们由于需要基于List去做，但是List提供的方法和我们需要的还是有差别的，我来封装一个新的NodeList去解决这个问题，应对我们自己的场景需要：
NodeList.java
class NodeList {
public static List nodeList = new LinkedList<>();
public static Boolean insertNode(Node node) {
return nodeList.add(node);
}
public static void insertNodeByIndex(Node node, int index) {
try {
nodeList.add(index, node);
}catch (Exception e){
e.printStackTrace();
}
}
public static Boolean deleteNode(char value) {
return nodeList.removeIf(n -> (n.value == value || n.value1 == value));
}
public static Boolean containsValue(char value) {
boolean sign = false;
for (Node node : nodeList) {
if (node.value == value || node.value1 == value) {
sign = true;
break;
}
}
return sign;
}
public static Boolean clearNode(String charSqueue) {
boolean sign = true;
for (char i : charSqueue.toCharArray()) {
if (containsValue(i))
sign = sign && deleteNode(i);
}
return sign;
}
public static void insertNodeByEnglishString(String charSqueue){
int index = 0;
for (char i : charSqueue.toCharArray()){
if (!containsValue(i)){
Node node = new Node(i);
insertNodeByIndex(node, index);
index++;
}
}
}
public static char getNodeValueByIndex(int index) {
if (index == -1)
return ' ';
if (index == -2)
return '/';
if (index == -3)
return ',';
if (index == -4)
return '.';
if (nodeList.get(index - 1).value1 == 'J')
return 'J';
return nodeList.get(index - 1).value;
}
}
最后我们还需要在具体的实现类里写一些简单的工具方法，实现代码的复用，减少重复代码:
Quiz.java
public class Quiz {
public static List getInitNodeList() {
for (int i = 65; i <= 90; i++) {
Node node;
if (i == 73) {
node = new Node( (char) i, (char) ++i);
} else {
node = new Node((char) i);
}
try {
Boolean insertNode = NodeList.insertNode(node);
} catch (Exception e) {
e.printStackTrace();
}
}
return NodeList.nodeList;
}
public static int getIndexByXY(int X, int Y) {
if (X > 5 || Y > 5)
return 0;
if (X == 0 && Y == 0)
return -1;
if (X == 1 && Y == 0)
return -2;
if (X == 0 && Y == 1)
return -3;
if (X == 0 && Y == 2)
return -4;
return (X - 1) * 5 + Y;
}
public static List getBeforeHandleString(String numericSqueue) {
char[] charArray = numericSqueue.toCharArray();
List newCharArray = new ArrayList<>();
for (char i : charArray) {
newCharArray.add(((int) i) - 48);
}
return newCharArray;
}
public static String getUserInPutString() {
System.out.println("输入你想输入的字串!");
Scanner scanner = new Scanner(System.in);
return scanner.nextLine();
}
public static void transferNumericSqueue(String cherSqueue) {
List beforeHandleString = getBeforeHandleString(cherSqueue);
int X = 0;
int Y = 1;
while (Y <= beforeHandleString.size()) {
int index = getIndexByXY(beforeHandleString.get(X), beforeHandleString.get(Y));
char nodeChar = NodeList.getNodeValueByIndex(index);
if (nodeChar == '/') {
System.out.println();
} else
System.out.print(nodeChar);
X = X + 2;
Y = Y + 2;
}
}
public static void updateInitNodeList(String charSqueue){
NodeList.nodeList = getInitNodeList();
for(Node node : NodeList.nodeList)
System.out.print(node.value);
System.out.println();
Boolean clearNode = NodeList.clearNode(charSqueue);
NodeList.insertNodeByEnglishString(charSqueue);
for(Node node : NodeList.nodeList)
System.out.print(node.value);
}
public static void main(String[] args) {
String inPutString = getUserInPutString();
System.out.println();
if ((int)inPutString.charAt(0) >= 65 && (int)inPutString.charAt(0) <90 ){
updateInitNodeList(inPutString);
System.out.println("你的矩阵重排成功!再次输入你想要解码的数字序列，注意需要是偶数个！");
String towInPutString = getUserInPutString();
transferNumericSqueue(towInPutString);
}else {
getInitNodeList();
transferNumericSqueue(inPutString);
}
}
}
算法的最终答案？来看看测试结果：
WHENEVER SANG MY SONGS
ON THE STAGE, ON MY OWN
WHENEVER SAID MY WORDS
WISHING THEY WOULD BE HEARD
I SAW YOU SMILING AT ME
WAS IT REAL OR JUST MY FANTASY
