• 分享一道手搓链表玩矩阵的算法题

    ！！！用java开发思维写算法，不喜勿喷，本人没有强化过自己的算法水平，属于算法菜鸟一只。

    先来看看题目：（我做的时候看见全英的我也有点上头，不过还好不是英盲哈哈哈哈哈）

    Background

    A text string can be encoded into a digits string with a Square like below:

    12345
    1ABCDE
    2FGHI/JK
    3LMNOP
    4QRSTU
    5VWXYZ

    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.

    12345
    1RI/JPLE
    2ABCDF
    3GHKMN
    4OQSTU
    5VWXYZ

    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

    1. NO WAR, NO PAIN
    2. 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在同一个结点里，我给结点设置两种有参构造，左右我嫌太麻烦就直接不用它们了）

    1. /**
    2.  * 定义每个节点的结构
    3.  */
    4. class Node {
    5.     int left;
    6.     int right;
    7.     char value;
    8.     char value1;
    9.  
    10.     public Node( char value) {
    11.         this.value = value;
    12.     }
    13.  
    14.     public Node(char value, char value1) {
    15.         this.value = value;
    16.         this.value1 = value1;
    17.     }
    18. }

    然后我们由于需要基于List去做，但是List提供的方法和我们需要的还是有差别的，我来封装一个新的NodeList去解决这个问题，应对我们自己的场景需要：

    NodeList.java

    1. /**
    2.  * 封装节点到简单的链表中
    3.  */
    4. class NodeList {
    5.     public static List nodeList = new LinkedList<>();
    6.  
    7.     /**
    8.      * 在尾部插入元素
    9.      *
    10.      * @param node 节点
    11.      * @return 是否成功
    12.      */
    13.     public static Boolean insertNode(Node node) {
    14.         return nodeList.add(node);
    15.     }
    16.  
    17.     /**
    18.      * 在指定索引处插入节点
    19.      *
    20.      * @param node  新节点
    21.      * @param index 索引
    22.      */
    23.     public static void insertNodeByIndex(Node node, int index) {
    24.        try {
    25.            nodeList.add(index, node);
    26.  
    27.        }catch (Exception e){
    28.           e.printStackTrace();
    29.        }
    30.     }
    31.  
    32.     /**
    33.      * 删除值为某个字符的节点
    34.      *
    35.      * @param value 指定值
    36.      * @return 是否成功
    37.      */
    38.     public static Boolean deleteNode(char value) {
    39.         /*如果节点的值一样就会直接删除*/
    40.         return nodeList.removeIf(n -> (n.value == value || n.value1 == value));
    41.     }
    42.  
    43.     /**
    44.      * 判断我们的链表中是否存在某一值为value的节点
    45.      *
    46.      * @param value 指定值
    47.      * @return 是否存在
    48.      */
    49.     public static Boolean containsValue(char value) {
    50.         boolean sign = false;
    51.         for (Node node : nodeList) {
    52.             if (node.value == value || node.value1 == value) {
    53.                 sign = true;
    54.                 break;
    55.             }
    56.         }
    57.         return sign;
    58.     }
    59.  
    60.     /**
    61.      * 根据输入的英文文本删除链表中它所含有的字符的节点
    62.      *
    63.      * @param charSqueue 英文文本的字符序列
    64.      * @return 是否删除成功
    65.      */
    66.     public static Boolean clearNode(String charSqueue) {
    67.         boolean sign = true;
    68.         for (char i : charSqueue.toCharArray()) {
    69.             if (containsValue(i))
    70.                 sign = sign && deleteNode(i);
    71.         }
    72.         return sign;
    73.     }
    74.  
    75.     /**
    76.      * 将输入的英文文本按顺序插到链表左侧按照原文本的序列
    77.      * @param charSqueue  英文文本的字符序列
    78.      */
    79.     public static void insertNodeByEnglishString(String charSqueue){
    80.         int index = 0;
    81.         for (char i : charSqueue.toCharArray()){
    82.             if (!containsValue(i)){
    83.                 Node node = new Node(i);
    84.                 insertNodeByIndex(node, index);
    85.                 index++;
    86.             }
    87.         }
    88.     }
    89.  
    90.     /**
    91.      * 根据转换过来的索引获取某个字母或者特殊字符
    92.      *
    93.      * @param index 转换的索引
    94.      * @return 大写字母或者是特殊字符
    95.      */
    96.     public static char getNodeValueByIndex(int index) {
    97.         if (index == -1)
    98.             return ' ';
    99.         if (index == -2)
    100.             return '/';
    101.         if (index == -3)
    102.             return ',';
    103.         if (index == -4)
    104.             return '.';
    105.         if (nodeList.get(index - 1).value1 == 'J')
    106.             return 'J';
    107.         return nodeList.get(index - 1).value;
    108.     }
    109. }

    最后我们还需要在具体的实现类里写一些简单的工具方法，实现代码的复用，减少重复代码:

    Quiz.java

    1. /**
    2.  * 利用链表实现，自定义节点对象，暂无优化，存在I/J的冲突
    3.  */
    4. public class Quiz {
    5.     /**
    6.      * 获取初始化链表
    7.      *
    8.      * @return 初始化正常排序的链表
    9.      */
    10.     public static List getInitNodeList() {
    11.         for (int i = 65; i <= 90; i++) {
    12.             Node node;
    13.             if (i == 73) {
    14.                 node = new Node( (char) i, (char) ++i);
    15.             } else {
    16.                 node = new Node((char) i);
    17.             }
    18.             try {
    19.                 Boolean insertNode = NodeList.insertNode(node);
    20.             } catch (Exception e) {
    21.                 e.printStackTrace();
    22.             }
    23.         }
    24.         return NodeList.nodeList;
    25.     }
    26.  
    27.     /**
    28.      * 转换矩阵坐标为链表索引
    29.      *
    30.      * @param X 行数 从1开始到5结束
    31.      * @param Y 列数 从1开始到5结束
    32.      * @return 链表中的索引与特殊含义数字
    33.      */
    34.     public static int getIndexByXY(int X, int Y) {
    35.         /*规定只能在五乘五的矩阵中由坐标翻译成链表中的索引*/
    36.         if (X > 5 || Y > 5)
    37.             return 0;
    38.         if (X == 0 && Y == 0)
    39.             return -1;
    40.         if (X == 1 && Y == 0)
    41.             return -2;
    42.         if (X == 0 && Y == 1)
    43.             return -3;
    44.         if (X == 0 && Y == 2)
    45.             return -4;
    46.         return (X - 1) * 5 + Y;
    47.     }
    48.  
    49.     /**
    50.      * 将输入的字符串数字队列转换成数字队列放在链表里
    51.      *
    52.      * @param numericSqueue 字符串数字队列
    53.      * @return 整型的数字链表
    54.      */
    55.     public static List getBeforeHandleString(String numericSqueue) {
    56.         char[] charArray = numericSqueue.toCharArray();
    57.         List newCharArray = new ArrayList<>();
    58.         for (char i : charArray) {
    59.             newCharArray.add(((int) i) - 48);
    60.         }
    61.         return newCharArray;
    62.     }
    63.  
    64.     /**
    65.      * 判断输入的是英文文本还是数字序列并获取输入信息
    66.      *
    67.      * @return 输入的字串
    68.      */
    69.     public static String getUserInPutString() {
    70.         System.out.println("输入你想输入的字串!");
    71.         Scanner scanner = new Scanner(System.in);
    72.         return scanner.nextLine();
    73.     }
    74.  
    75.     /**
    76.      * 处理输入的是数字序列信息的情况
    77.      */
    78.     public static void transferNumericSqueue(String cherSqueue) {
    79.         List beforeHandleString = getBeforeHandleString(cherSqueue);
    80.         int X = 0;
    81.         int Y = 1;
    82.         while (Y <= beforeHandleString.size()) {
    83.             int index = getIndexByXY(beforeHandleString.get(X), beforeHandleString.get(Y));
    84.             char nodeChar = NodeList.getNodeValueByIndex(index);
    85.             if (nodeChar == '/') {
    86.                 System.out.println();
    87.             } else
    88.                 System.out.print(nodeChar);
    89.             X = X + 2;
    90.             Y = Y + 2;
    91.         }
    92.     }
    93.  
    94.     /**
    95.      * 根据英文文本序列更改链表 先删在插
    96.      * @param charSqueue 英文文本的字符序列
    97.      */
    98.     public static void updateInitNodeList(String charSqueue){
    99.         NodeList.nodeList = getInitNodeList();
    100.         for(Node node : NodeList.nodeList)
    101.             System.out.print(node.value);
    102.         System.out.println();
    103.         Boolean clearNode = NodeList.clearNode(charSqueue);
    104.         NodeList.insertNodeByEnglishString(charSqueue);
    105.         for(Node node : NodeList.nodeList)
    106.             System.out.print(node.value);
    107.  
    108.     }
    109.  
    110.     public static void main(String[] args) {
    111.         String inPutString = getUserInPutString();
    112.         System.out.println();
    113.         if ((int)inPutString.charAt(0) >= 65 && (int)inPutString.charAt(0) <90 ){
    114.             updateInitNodeList(inPutString);
    115.             System.out.println("你的矩阵重排成功!再次输入你想要解码的数字序列，注意需要是偶数个！");
    116.             String towInPutString = getUserInPutString();
    117.             transferNumericSqueue(towInPutString);
    118.         }else {
    119.             getInitNodeList();
    120.             transferNumericSqueue(inPutString);
    121.         }
    122.     }
    123. }

    算法的最终答案？来看看测试结果：

     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

     所以这个算法题的大哥还是很幽默的，做完了！258行代码，不建议专业的算法大佬们学习，这么长的代码也就玩玩而已啦。

  • 相关阅读:
    small synopsis - MYSQL for beginners
    Unity ECS最新DOTS环境搭建教程
    HyperLynx（二十八）板层噪声分析和SI/PI联合仿真实例
    vue3+TS前端JS实现 搜索关键词变红
    Jenkins pipeline中的全局变量
    Go语言类库-reflect(反射)
    SpringBoot--中间件技术-3：整合mongodb，整合ElasticSearch，附案例含代码(简单易懂)
    【算法挨揍日记】day14——724. 寻找数组的中心下标、238. 除自身以外数组的乘积
    NIO Channel（通道）类
    Java-GUI编程之菜单组件
  • 原文地址：https://blog.csdn.net/m0_59588838/article/details/126233798