【数据结构与算法之面试题】线性结构类面试题

灰太狼 2024-03-25 21:20 130阅读 0赞

#### 【数据结构与算法之面试题】线性结构类面试题 ####

#### 文章目录 ####

*   *   *  【数据结构与算法之面试题】线性结构类面试题
         *   *   *  1 约瑟夫环
                 *  2 单链表的逆置
                 *  3 判断链表中是否存在循环结构
                 *  4 判断两个链表是否相交
                 *  5 判断回文链表
                 *  6 最小栈问题
                 *  7 每日温度
                 *  8 LRU缓存的设计
                 *  9 线性结构类面试题解题技巧
                 *   *  【1】根据应用场景选择适合的数据结构
                     *  【2】熟练掌握经典的数据结构算法
                     *  【3】快慢指针
                     *  【4】高级的数据结构实现

线性结构包含数组(顺序表)、链表以及基于数组和链表实现的栈和队列。

###### 1 约瑟夫环 ######

【题目描述】编号为1 - N的N 个人顺时针围成一个圈，每个人都持有一个密码(正整数)，开始时任选一个正整数作为报数 上限值M，从编号为1 的人开始沿着顺时针方向从1 报数，报到M 时停止，报M 的人出列，并将他手中的密码作为新的报数上限，从他顺时针方向的下一个人开始从1 报数，如此下去，直到所有人全部出列。

编写一个程序，求出这些人的出列顺序。

约瑟夫环是经典的数据结构问题，最简单的解法：使用一个循环链表来存储约瑟夫环中每个人的编号和手中的密码，然后按照规则执行报数和出列的动作。其中，报数对应的是循环链表的循环遍历操作，出列对应的是循环链表的删除节点操作。

首先确定链表节点的结构：

class Node {
        
    
        int id; // 成员编号
        int key; // 成员手中的密码
        Node next; //指针域, 指向下一个节点
    
        public Node(int id, int key) {
        
            this.id = id;
            this.key = key;
            this.next = null;
        }
    }

创建一个约瑟夫环的代码如下：

public class JosephRing {
        
    
        Node mHead = null; // 循环链表的头指针
    
        public void createJosephCircle(HashMap<Integer, Integer> members) {
        
    
            Node p;
            p = mHead = new Node(1, members.get(1)); // 创建约瑟夫环的第1个节点
    
            for (int i = 2; i <= members.size(); i++) {
        
                p.next = new Node(i, members.get(i)); // 创建约瑟夫环的其他节点
                p = p.next;
            }
    
            p.next = mHead; // 最后一个节点的next指向头节点，构成循环链表
        }
    
    }

HashMap members 的key 表示循环链表节点的成员编号，与之对应的value 表示循环链表节点中成员手中的密码。

接下来就是要对这个约瑟夫环执行报数、出列、重置报数上限等操作了。

public void run(int m) {
        
        Node p = mHead;
        Node q = mHead;
    
        // 通过循环使得q 指向头节点的前一个节点
        while (q.next != mHead) {
        
            q = q.next;
        }
    
        while (p != q) {
        
            // 通过for循环使 p指向最终要删除的节点, q指向p 的前一个节点
            for (int i = 1; i < m; i++) {
        
                q = p; // q 指向p 指向的节点
                p = p.next;
            }
    
            System.out.print(p.id + " ");  // 打印p节点(出队节点) 的id
            m = p.key;  // 将p 节点的密码作为下一次的报数上限
            q.next = p.next; // 删除p 指向的节点
            p = q.next;
        }
    
        System.out.print(p.id + " "); // 打印最后一个出队节点的id
    }

初始状态，以【1,3】、【2,1】、【3,7】、【4，2】、【5,4】、【6,8】、【7,4】，开始时的报数上限为 6。

![在这里插入图片描述][120eafeab5804023867a186be2de8955.png_pic_center]

测试

import java.lang.reflect.Member;
    import java.util.HashMap;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: JosephRing
     * @Author: Ding Jiaxiong
     * @Data:2023/3/16 15:18
     */
    
    public class JosephRing {
        
    
        Node mHead = null; // 循环链表的头指针
    
        public void createJosephCircle(HashMap<Integer, Integer> members) {
        
    
            Node p;
            p = mHead = new Node(1, members.get(1)); // 创建约瑟夫环的第1个节点
    
            for (int i = 2; i <= members.size(); i++) {
        
                p.next = new Node(i, members.get(i)); // 创建约瑟夫环的其他节点
                p = p.next;
            }
    
            p.next = mHead; // 最后一个节点的next指向头节点，构成循环链表
        }
    
        public void run(int m) {
        
            Node p = mHead;
            Node q = mHead;
    
            // 通过循环使得q 指向头节点的前一个节点
            while (q.next != mHead) {
        
                q = q.next;
            }
    
            while (p != q) {
        
                // 通过for循环使 p指向最终要删除的节点, q指向p 的前一个节点
                for (int i = 1; i < m; i++) {
        
                    q = p; // q 指向p 指向的节点
                    p = p.next;
                }
    
                System.out.print(p.id + " ");  // 打印p节点(出队节点) 的id
                m = p.key;  // 将p 节点的密码作为下一次的报数上限
                q.next = p.next; // 删除p 指向的节点
                p = q.next;
            }
    
            System.out.print(p.id + " "); // 打印最后一个出队节点的id
        }
    
        public static void main(String[] args) {
        
    
            HashMap<Integer, Integer> members = new HashMap<Integer, Integer>();
    
            members.put(1, 3);
            members.put(2, 1);
            members.put(3, 7);
            members.put(4, 2);
            members.put(5, 4);
            members.put(6, 8);
            members.put(7, 4);
    
            JosephRing josephRing = new JosephRing();
            josephRing.createJosephCircle(members);
    
            josephRing.run(6);
    
        }
    
    }
    
    class Node {
        
    
        int id; // 成员编号
        int key; // 成员手中的密码
        Node next; //指针域, 指向下一个节点
    
        public Node(int id, int key) {
        
            this.id = id;
            this.key = key;
            this.next = null;
        }
    }

运行结果

![在这里插入图片描述][d9d7cb9d239a4235bd24538d9e166e15.png_pic_center]

我们来模拟一下整个执行流程：

【0】初始状态时，

![在这里插入图片描述][245170eae9f2489fb2897778d9f102f0.png_pic_center]

【2】开始执行流程，初始报数上限为6，

![在这里插入图片描述][812a5d5de8474a888d3cef01eeba04b5.png_pic_center]

p 和 q 都指向mHead，经过循环后

![在这里插入图片描述][9388ad846c374b04b7bd30efadd5d65b.png_pic_center]

现在q 来到了【7,4】时，判断结果为false，q 就不会再next了，即q 指向了头节点的前一个节点

![在这里插入图片描述][d7f31257ad2541ecb39851c2b6696925.png_pic_center]

接着通过for循环使得p 指向最终要删除的节点，报名上限为6，

![在这里插入图片描述][94d1dca73abe4dd58ede627540e4ff8d.png_pic_center]

【说明6、8】该出列了，这个时候，因为是小于m，所以这个时候p 指向【5,4】，

接着q = p、p = p.next，

![在这里插入图片描述][3fd73f8f65e1469dae2379b12985221e.png_pic_center]

就成了这个样子，然后就可以打印p 的id 了，即6，而且m 更新为8，

![在这里插入图片描述][4d10522678404af795e62904559cd3d5.png_pic_center]

接着删除p指向的节点，q.next = p.next；  
![在这里插入图片描述][89434277443c430fad788e562e3da696.png_pic_center]

然后让p = q.next。

![在这里插入图片描述][54b9a7a15f9645db949f6fb506262a8f.png_pic_center]

OK，再来演示一次报数，当前报数上限已经更新为8了

![在这里插入图片描述][5e5abe1d939442a38db6411ae66bd1b0.png_pic_center]

说明当前要出列的就是节点【1,3】 了，

![在这里插入图片描述][8126ba4243774cf0a81ee34a6d612b95.png_pic_center]

接着下去就是循环了，

最终的出列顺序就是运行结果

![在这里插入图片描述][4ba4a132eab2442e8cf172dd69be18b8.png_pic_center]

![在这里插入图片描述][96f8c6dc5a03435e93aa6c868b6ea73a.png_pic_center]

![在这里插入图片描述][cd4b7e21e24f456eb71714a8d133ef16.png_pic_center]

![在这里插入图片描述][4c3cce4ad30b4ccd8349ee38f0307f6c.png_pic_center]

其实如果只剩下一个节点的时候，p和q都指向同一个节点了，直接打印就行了

没问题。

###### 2 单链表的逆置 ######

【题目描述】编写一个程序，实现单链表的逆置，原链表的数据元素为  ( a 1 , a 2 , a 3 , . . . , a n − 1 , a n ) (a\_1,a\_2,a\_3,...,a\_\{n-1\},a\_n) (a1,a2,a3,...,an−1,an)，链表逆置后为 ( a n , a n − 1 , . . . , a 3 , a 2 , a 1 ) (a\_n,a\_\{n-1\},...,a\_3,a\_2,a\_1) (an,an−1,...,a3,a2,a1) 。要求不增加新的链表节点空间。

单链表的逆置其实也是一个非常经典的算法，通过3个指向不同节点的指针完成链表的逆置。

算法Java 实现如下：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyLinkedList
     * @Author: Ding Jiaxiong
     * @Data:2023/3/16 16:13
     */
    
    class Node {
        
    
        int data; // 数据域
        Node next; // 指针域，指向下一个节点
    
        public Node(int data) {
        
            this.data = data;
        }
    
    }
    
    public class MyLinkedList {
        
    
        Node mHead;
        int mLength;
    
        public MyLinkedList() {
        
            mHead = null;
            mLength = 0;
        }
    
        // 向链表的第index位置上插入一个结点，结点数据为data（这里是int类型）
        public boolean insertNode(int data, int index) {
        
            //向链表的第index位置上插入一个结点，结点数据为data（这里是int类型）
    
            if (index < 1 || index > (mLength + 1)) {
        
                //这种情况说明插入结点的位置不合法
                System.out.println("插入位置不合法");
                return false;
            }
            //要插入结点的位置为1，这时的操作有些特殊
            if (index == 1) {
        
                if (mHead == null) {
        
                    mHead = new Node(data); //创建第一个结点，并赋值给head
                } else {
        
                    Node node = new Node(data); //创建一个新结点node
                    node.next = mHead;    //将head值赋值给node的next域
                    mHead = node;            //再将node赋值给head
                }
                mLength++;
                return true;
            }
    
            //要插入的结点位置不是1，此时
            // 1、将指针p指向要插入位置的前一个结点上
            // 2、创建新的结点，并插入到p结点后面
    
            Node p = mHead;  //p指向链表的第一个结点
            int i = 1;
            while (i < index - 1 && p != null) {
        
                p = p.next;
                i++;
            }
    
            Node node = new Node(data); //创建该结点
            Node q = p.next;
            p.next = node;
            node.next = q;
            mLength++;
            return true;
        }
    
        void reverseLinkList() {
        
            Node p, q, r;
            p = mHead;
            q = null;
            r = null;
            while (p != null) {
        
                r = q;
                q = p;
                p = p.next;
                q.next = r;
            }
            mHead = q;
        }
    
        public void printLinkedList() {
        
            //打印链表内容
            Node p = mHead;
            while (p != null) {
         //遍历链表每一个结点，并打印data域值
                System.out.print(p.data + " ");
                p = p.next;
            }
        }
    
        public static void main(String[] args) {
        
            MyLinkedList list = new MyLinkedList();
            list.insertNode(5, 1);
            list.insertNode(4, 2);
            list.insertNode(3, 3);
            list.insertNode(2, 4);
            list.insertNode(1, 5);
            list.printLinkedList();
            System.out.println();
            list.reverseLinkList();
            list.printLinkedList();
        }
    
    }

运行结果

![在这里插入图片描述][99cfa62f966e4efbb179ac260471018c.png_pic_center]

###### 3 判断链表中是否存在循环结构 ######

【题目描述】给定一个链表，可能是以null 结尾的非循环链表，也可能是带有循环结构的的循环链表( 当然循环结构是指链表中的某个节点的next 指向它之前的某个节点，并不一定是第1个节点)。

已知这个链表的头指针，请编写一个函数来判断该链表是否存在循环结构。要求函数不得修改链表本身。

其实如果是传统循环链表，即最后一个节点的next指向头结点的链表，这种好办，只需要用一个指针p 指向链表的头结点，用另一个指针q 遍历链表，如果遍历过程中 q.next = null， 那就没循环，如果遍历过程中q.next = p，那就有循环，而且q 节点就是循环节点。但是对于这个题中这种“广义”的循环链表，我们压根儿不能知道循环节点的next 到底指向谁，所以旧办法就不行了。

其实我们可以用一个动态数组来记录下每次访问到的节点地址，每访问一个节点，都在这个动态数组中查找当前访问节点的next ，如果地址存在，则说明当前节点就是循环节点，如果不存在，继续访问下一个节点，直到找到循环节点或者遇到 null。

这个算法空间复杂度为 O ( n ) O(n) O(n)，但是如果链表很长而环又很小，这种方法就会消耗大量的非必要内存空间。

【经典算法】快慢指针。这种算法不需要占用额外内存空间，而且时间复杂度为 O ( n ) O(n) O(n)。

采用指针fast 和 slow 分别指向链表的两个节点，在开始时，slow指向链表第一个节点，fast指向其下一个节点。然后两个指针顺序向后遍历链表，在遍历过程中slow 一次只访问一个节点，而fast 一次访问两个链表节点，每完成一次访问都判断slow 是否等于fast，或者fast 是否为null，如果slow = fast，则是循环链表。如果fast 走到null了，则很明显该链表不是循环链表。

打个比喻，fast 和 slow 在赛跑，两个人保持各自速度不变，fast每秒跑两步，slow每秒跑一步，如果赛道是个环，那么fast 一定可以超过slow 刚好一圈，如果赛道是直的，那么fast 会直接跑完，即null。

Java 实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: DeterminesWhetherThereIsALoopStructureInTheLinkedList
     * @Author: Ding Jiaxiong
     * @Data:2023/3/16 16:59
     */
    
    class Node {
        
        int data;
        Node next;
    
        public Node(int data) {
        
            this.data = data;
            next = null;
        }
    }
    
    
    public class MyLinkedList {
        
        Node mHead = null;
    
        // 创建循环链表
        public void createLinkedListWithCircle() {
        
    
            mHead = new Node(1);
            Node p = mHead;
    
            for (int i = 2; i <= 5; i++) {
        
                p.next = new Node(i);
                p = p.next;
            }
    
            // 最终p 指向链表的最后一个节点
            p.next = mHead.next; // 形成循环链表
        }
    
        // 创建一个非循环链表
        public void createLinkedList() {
        
            mHead = new Node(1);
            Node p = mHead;
            for (int i = 2; i <= 5; i++) {
        
                p.next = new Node(i);
                p = p.next;
            }
        }
    
        public boolean isLoopLinkList() {
        
    
            Node fast, slow;
            fast = mHead.next;
            slow = mHead;
    
            while (true) {
        
                if (fast == null || fast.next == null) {
        
                    return false;
                } else if (fast == slow || fast.next == slow) {
        
                    return true;
                } else {
        
                    fast = fast.next.next;
                    slow = slow.next;
                }
            }
        }
    
        public static void main(String[] args) {
        
    
            MyLinkedList linkedList_1 = new MyLinkedList();
            linkedList_1.createLinkedListWithCircle();
    
            MyLinkedList linkedList_2 = new MyLinkedList();
            linkedList_2.createLinkedList();
    
            System.out.println(linkedList_1.isLoopLinkList());
            System.out.println(linkedList_2.isLoopLinkList());
    
        }
    
    
    }

运行结果

![在这里插入图片描述][677f397cd85b4e0d843217b242c17f90.png_pic_center]

###### 4 判断两个链表是否相交 ######

【题目描述】编写一个程序判断两个单链表是否相交，如果相交，则返回相交节点的指针，否则返回null。

【可以清楚的点】如果两个单链表是相交的，那么从相交节点开始，后续的链表段只能是一条，两个链表共享这个一条链表段。

其实我们很容易想到的是使用两个指针同时从两链表的头节点开始向后遍历，如果指针相等，则说明已经遍历到了相交节点，返回该节点的指针即可。但是其实这个想法有点问题，因为我们没办法确定这两个链表在相交之前是一样长的。

所以，如果从较长的链表头部开始遍历一些节点，使得两个指针从两链表相交节点之前等长的地方开始同时向后遍历就可以确保两个遍历指针同时到达相交节点了。

Java 实现描述：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyLinkedLists
     * @Author: Ding Jiaxiong
     * @Data:2023/3/16 17:21
     */
    
    class Node {
        
        int data;
        Node next;
    
        public Node(int data) {
        
            this.data = data;
            next = null;
        }
    }
    
    public class MyLinkedLists {
        
    
        Node head1 = null;
        Node head2 = null;
    
        // 创建两个相交的链表，他们的头节点分别是head1和head2
        public void createIntersectionLinkedLists() {
        
            Node cross = null;
            head1 = new Node(1);
            Node p = head1;
    
            for (int i = 2; i <= 10; i++) {
        
                p.next = new Node(i);
                p = p.next;
                if (i == 6) {
        
                    cross = p;
                }
            }
    
            head2 = new Node(1);
            p = head2;
            for (int i = 2; i <= 5; i++) {
        
                p.next = new Node(i);
                p = p.next;
            }
    
            p.next = cross;
        }
    
        public Node getFirstIntersectionNode() {
        
    
            if (head1 == null || head2 == null) {
        
                return null;
            }
    
            Node p1 = head1;
            Node p2 = head2;
    
            int len1 = 0;
            int len2 = 0;
    
            // 通过while循环计算出链表head1的长度
            while (p1.next != null) {
        
                p1 = p1.next;
                len1++;
            }
    
            // 通过while循环计算出链表head2的长度
            while (p2.next != null) {
        
                p2 = p2.next;
                len2++;
            }
    
            // 如果p1和p2 最后没有指向同一个节点，那肯定也不相交
            if (p1 != p2) {
        
                return null;
            }
    
            if (len1 == len2) {
        
                p1 = head1;
                p2 = head2;
            } else if (len1 > len2) {
        
                // p1 先向后遍历len1 - len2 个节点
                p2 = head2;
                p1 = head1;
                for (int i = 1; i <= len1 - len2; i++) {
        
                    p1 = p1.next;
                }
            } else {
        
                p1 = head1;
                p2 = head2;
                for (int i = 1; i <= len2 - len1; i++) {
        
                    p2 = p2.next;
                }
            }
    
            while (p1 != p2) {
        
                p1 = p1.next;
                p2 = p2.next;
            }
    
            return p1;
        }
    
        public static void main(String[] args) {
        
    
            MyLinkedLists myLinkedLists = new MyLinkedLists();
    
            myLinkedLists.createIntersectionLinkedLists();
            Node intersectionNode = myLinkedLists.getFirstIntersectionNode();
    
            System.out.println(intersectionNode.data);
    
        }
    
    
    }

运行结果

![在这里插入图片描述][ebdae6c12ad042159dc09587fa279fdf.png_pic_center]

###### 5 判断回文链表 ######

【题目描述】编写一个程序，判断一个链表是否具有回文结构，回文结构指的是正着看和反着看的顺序都相同的结构。

例如 1 → 2 → 1，1 → 2 → 3 → 2 → 1。

如果是判断一个数组是否具有回文结构，可以使用数组下标low 和 high，其中low 指向数组的头部，high 指向数组的尾部，然后直接开始比较：

*  如果相等，low ++ ，high --操作，使双指针向数组中间靠拢。
 *  如果不相等，就不具有。
 *  循环执行，如果在low< high的条件下它们指向的元素都相等，则可判定该数组具有回文结构。

而链表本身不支持随机访问，即无法通过下标的方式直接访问到链表中指定位置的元素。这里直接给出巧妙的办法 ——利用栈判定回文结构，栈结构的特点是数据的入栈顺序和出栈顺序相反，利用这个特点我们可以判断一个序列的正序和逆序是否相同，从而判断这个序列是否具有回文结构。

Java 实现描述：

import java.util.Stack;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyLinkedList
     * @Author: Ding Jiaxiong
     * @Data:2023/3/16 19:18
     */
    
    class Node {
        
        int data;
        Node next;
    
        public Node(int data) {
        
            this.data = data;
            next = null;
        }
    }
    
    public class MyLinkedList {
        
    
        Node head = null;
    
        public boolean isPalindrome() {
        
            Stack<Integer> stack = new Stack<>();
            Node p = head;
    
            while (p != null) {
        
                stack.push(p.data);
                p = p.next;
            }
    
            p = head;
            while (!stack.isEmpty()) {
        
                if (stack.pop() != p.data) {
        
                    return false;
                }
    
                p = p.next;
            }
            return true;
        }
    
    }

测试

public static void main(String[] args) {
        
    
        MyLinkedList list = new MyLinkedList();
        list.insertNode(1, 1);
        list.insertNode(2, 2);
        list.insertNode(3, 3);
        list.insertNode(3, 4);
        list.insertNode(2, 5);
        list.insertNode(1, 6);
    
        System.out.println(list.isPalindrome());
    
    }

运行结果

![在这里插入图片描述][a61420ee0b83476d82d75f1ef92f0585.png_pic_center]

当然这种方法也实现了要求，但是还存在优化的空间，如果一个序列是回文的，那么这个序列的前半部分的正序应该与后半部分的逆序相同。

所以我们在判断回文链表时，其实并不需要将完整的链表保存到栈中，只需要将链表的后半部分压入栈中，这样从栈中取出的序列就是链表后半部分序列的逆序列。

现在的问题就是如何比较快的找到链表后半部分头指针，比较常规的做法就是遍历一遍链表，拿到链表的长度，然后长度计算出来，这里介绍一种更加巧妙的获取链表后半部分头指针的方法 —— 快慢指针。

设置指针变量 slow 和 fast，初始状态 slow = fast 都指向链表头节点，然后每次slow 向后移动一个节点的位置 slow = slow.next，指针fast 每次向后移动两个节点的位置 fast = fast.next.next，当指针fast 指向链表最后一个节点或倒数第2个节点时，slow 指向的就是链表后半部分的前一个节点。这样就好办了，

优化后的实现：

import java.util.LinkedList;
    import java.util.Stack;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MyLinkedList
     * @Author: Ding Jiaxiong
     * @Data:2023/3/16 19:18
     */
    
    class Node {
        
        int data;
        Node next;
    
        public Node(int data) {
        
            this.data = data;
            next = null;
        }
    }
    
    public class MyLinkedList {
        
    
        Node head = null;
        int mLength = 0;
    
        // 向链表的第index位置上插入一个结点，结点数据为data（这里是int类型）
        public boolean insertNode(int data, int index) {
        
            //向链表的第index位置上插入一个结点，结点数据为data（这里是int类型）
    
            if (index < 1 || index > (mLength + 1)) {
        
                //这种情况说明插入结点的位置不合法
                System.out.println("插入位置不合法");
                return false;
            }
            //要插入结点的位置为1，这时的操作有些特殊
            if (index == 1) {
        
                if (head == null) {
        
                    head = new Node(data); //创建第一个结点，并赋值给head
                } else {
        
                    Node node = new Node(data); //创建一个新结点node
                    node.next = head;    //将head值赋值给node的next域
                    head = node;            //再将node赋值给head
                }
                mLength++;
                return true;
            }
    
            //要插入的结点位置不是1，此时
            // 1、将指针p指向要插入位置的前一个结点上
            // 2、创建新的结点，并插入到p结点后面
    
            Node p = head;  //p指向链表的第一个结点
            int i = 1;
            while (i < index - 1 && p != null) {
        
                p = p.next;
                i++;
            }
    
            Node node = new Node(data); //创建该结点
            Node q = p.next;
            p.next = node;
            node.next = q;
            mLength++;
            return true;
        }
    
        public boolean isPalindrome() {
        
            Stack<Integer> stack = new Stack<>();
            Node fast = head;
            Node slow = head;
    
            while (fast != null && fast.next != null) {
        
                fast = fast.next.next;
                slow = slow.next;
            }
    
            Node p = slow.next;
            while (p != null) {
        
                stack.push(p.data);
                p = p.next;
            }
    
            p = head;
            while (!stack.isEmpty()) {
        
                if (stack.pop() != p.data) {
        
                    return false;
                }
    
                p = p.next;
            }
    
            return true;
    
        }
    
        public static void main(String[] args) {
        
    
            MyLinkedList list = new MyLinkedList();
            list.insertNode(1, 1);
            list.insertNode(2, 2);
            list.insertNode(3, 3);
            list.insertNode(3, 4);
            list.insertNode(2, 5);
            list.insertNode(1, 6);
    
            System.out.println(list.isPalindrome());
    
        }
    
    }

运行结果

![在这里插入图片描述][11f2853b70a34abeb6781f040dbafac9.png_pic_center]

没毛病。

###### 6 最小栈问题 ######

【题目描述】设计一个支持push()、pop() 函数的栈，同时要支持 getMinValue() 函数，该函数能在常数时间内检索到栈的最小值。

一个比较经典的做法是维护一个辅助栈(helperStack)，用来保存当前数据栈中的最小值。

Java 实现描述：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MinStack
     * @Author: Ding Jiaxiong
     * @Data:2023/3/16 19:55
     */
    
    public class MinStack {
        
    
        int[] dataStack; // 数据栈
        int[] helperStack; // 辅助栈
        int top; // 栈顶索引
        int capacity;
    
        public MinStack(int capacity) {
        
            dataStack = new int[capacity];
            helperStack = new int[capacity];
            top = 0;
            this.capacity = capacity;
        }
    
        public void push(int elem) {
        
            if (top == capacity) {
        
                increaseCapacity();
            }
    
            dataStack[top] = elem;
            if (top == 0 || elem < helperStack[top - 1]) {
        
                helperStack[top] = elem;
            } else {
        
                helperStack[top] = helperStack[top - 1];
            }
    
            top++;
        }
    
        public void increaseCapacity() {
        
            //将数据栈和辅助栈扩容
            int[] dataStackTmp = new int[dataStack.length * 2];
            System.arraycopy(dataStack, 0, dataStackTmp, 0, dataStack.length);
            dataStack = dataStackTmp;
            capacity = dataStack.length;
            int[] helperStackTmp = new int[helperStack.length * 2];
            System.arraycopy(helperStack, 0, helperStackTmp, 0, helperStack.length);
            helperStack = helperStackTmp;
        }
    
        public int pop() {
        
    
            if (top == 0) {
        
                System.out.println("栈空,没法儿弹");
                return -111;
            }
            top--;
            return dataStack[top];
        }
    
        public int getMinValue() {
        
            return helperStack[top - 1];
        }
    
        public static void main(String[] args) {
        
    
            MinStack stack = new MinStack(15);
            stack.push(0);
            stack.push(-1);
            stack.push(-2);
            stack.push(3);
            stack.push(-5);
    
            System.out.println(stack.getMinValue());
            stack.pop();
            System.out.println(stack.getMinValue());
    
        }
    
    }

运行结果

![在这里插入图片描述][158bd23abc184e5bba48ce07aea9d9dc.png_pic_center]

这样虽然也是实现了我们的需求，但是其实我们仔细思考会发现，healerStack 中会存在很多重复元素。改进一下，我们可以直接用helperStack 去保存dataStack的当前最小值。

*  当向dataStack中push元素时，如果该元素小于或等于helperStack的栈顶元素，就将该元素同步push到helperStack的栈顶，表示当前数据栈中的最小值已经更新，
 *  如果该元素大于helperStack的栈顶元素，则不动。
 *  在pop数据时，
    
     *  如果从dataStack 中取出的元素不等于helperStack的栈顶元素，不动
     *  如果等于，则将helperStack 的栈顶元素弹出

这样就保证了helperStack的栈顶始终是dataStack的最小元素。

Java 实现：

/**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: MinStack
     * @Author: Ding Jiaxiong
     * @Data:2023/3/16 19:55
     */
    
    public class MinStack {
        
    
        int[] dataStack; // 数据栈
        int[] helperStack; // 辅助栈
        int dataStackTop = 0; // 数据栈顶top
        int helperStackTop = 0; // 辅助栈top
        int capacity;
    
        public MinStack(int capacity) {
        
            dataStack = new int[capacity];
            helperStack = new int[capacity];
            dataStackTop = 0;
            helperStackTop = 0;
            this.capacity = capacity;
        }
    
        public void push(int elem) {
        
            if (dataStackTop == capacity) {
        
                increaseCapacity();
            }
    
            dataStack[dataStackTop] = elem;
            dataStackTop++;
            if (helperStackTop == 0 || elem <= helperStack[helperStackTop - 1]) {
        
                helperStack[helperStackTop] = elem;
                helperStackTop++;
            }
        }
    
        public void increaseCapacity() {
        
            //将数据栈和辅助栈扩容
            int[] dataStackTmp = new int[dataStack.length * 2];
            System.arraycopy(dataStack, 0, dataStackTmp, 0, dataStack.length);
            dataStack = dataStackTmp;
            capacity = dataStack.length;
            int[] helperStackTmp = new int[helperStack.length * 2];
            System.arraycopy(helperStack, 0, helperStackTmp, 0, helperStack.length);
            helperStack = helperStackTmp;
        }
    
        public int pop() {
        
    
            if (dataStackTop == 0) {
        
                System.out.println("栈空,没法儿弹");
                return -111;
            }
            if (dataStack[dataStackTop - 1] == helperStack[helperStackTop - 1]) {
        
                helperStackTop--;
            }
    
            dataStackTop--;
            return dataStack[dataStackTop];
        }
    
        public int getMinValue() {
        
            return helperStack[helperStackTop - 1];
        }
    
        public static void main(String[] args) {
        
    
            MinStack stack = new MinStack(15);
            stack.push(0);
            stack.push(-1);
            stack.push(-2);
            stack.push(3);
            stack.push(-5);
            stack.push(-5);
    
            System.out.println(stack.getMinValue());
            stack.pop();
            System.out.println(stack.getMinValue());
    
        }
    
    }

运行结果

![在这里插入图片描述][ad4383b899474a2da010c36f13a72f7a.png_pic_center]

###### 7 每日温度 ######

【题目描述】请根据每日气温列表重新生成一个列表，新列表的内容是观测更高气温需要等待的天数。如果气温在某天之后不再升高，则在对应位置填0 。

举个栗子：给定的气温列表为\{23,24,25,21,19,22,26,23\}，输出的新列表应该是 \{1,1,4,2,1,1,0,0\}。

*  第1天温度是23，第2天是24，所以23对应1，表示等待1天温度会更高
 *  第3天是25，但是下一个气温更高的是26，所以25对应的是4
 *  第7天26，后面没有比26更高的气温了，所以对应0

最直观暴力，二重循环，用i 指向 第i 天的温度，然后用j 扫描列表后面的温度，一旦出现大于第i 天温度的值就立即停止，j - i 的值就是i 对应的天数，即再等待j - i 天就会出现比第i 天更高的气温。

暴力确实简单直观，但是时间复杂度太高了，这里介绍一种更为巧妙的解决办法 —— 单调递减栈。

在单调递减栈中，从栈底到栈顶的元素必须保证单调递减。

*  当向栈中压入元素时，如果要压入的元素比栈顶元素小，就直接push到栈顶
 *  如果要压入的元素比栈顶元素大，则不压入并pop 出当前栈顶元素，然后再次比较，直到栈为空或者要压入的元素比栈顶元素小，才压入该元素。

在这道题中，将温度列表的下标i 依次压入单调递减栈中

*  如果压入的下标i 对应的温度temperatures\[i\] 比栈顶元素 stack.peek() 对应的温度 temperatures\[stack.peek()\] 低，或者栈为空，就直接将下标i 入栈
 *  如果压入的下标i 对应的温度temperatures\[i\] 比栈顶元素 stack.peek() 对应的温度 temperatures\[stack.peek()\] 高，则将栈顶元素pop 出来并赋值给变量j ，i - j就是列表中temperatures\[j\] 对应的等待天数。

Java代码实现：

import java.util.Stack;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: DailyTemperature
     * @Author: Ding Jiaxiong
     * @Data:2023/3/16 20:54
     */
    
    public class DailyTemperature {
        
    
        public static int[] dailyTemperatures(int[] temperatures) {
        
    
            int[] days = new int[temperatures.length];
            Stack<Integer> stack = new Stack<Integer>();
    
            int i = 0;
            while (i < temperatures.length) {
        
    
                if (stack.isEmpty() || temperatures[i] < temperatures[stack.peek()]) {
        
                    stack.push(i);
                    i++;
                } else {
        
                    int j = stack.pop();
                    days[j] = i - j;
                }
            }
    
            return days;
        }
    
        public static void main(String[] args) {
        
    
            int[] temperatures = {
        18, 19, 10, 21, 27, 18, 26, 31};
            int[] days = dailyTemperatures(temperatures);
    
            for (int temperature : temperatures) {
        
                System.out.print(temperature + " ");
            }
            System.out.println();
            for (int day : days) {
        
                System.out.print(day + "  ");
            }
    
        }
    
    }

运行结果

![在这里插入图片描述][d940041ea03a4b0f9bf816d557e55102.png_pic_center]

没毛病。

###### 8 LRU缓存的设计 ######

【题目描述】设计一个LRU缓存(cache)结构，要求LRU 缓存大小固定，同时要实现以下两个功能。

1.  set(key , value)：将记录(key , value) 插入LRU 缓存结构
2.  get(key)：返回关键字key 对应的值value。

LRU 缓存要满足以下要求：

1.  set() 和 get() 时间复杂度均为O(1)
2.  在执行set() 和 get()后，操作的记录应该变成"最常使用记录"
3.  当缓存的大小超过最大限度时，要移除"最不常使用记录"，也就是最久没有被执行set() 或 get() 的记录。

举个栗子，一个缓存容量为4的LRU，状态变化如下：

<table> 
 <thead> 
  <tr> 
   <th align="center">set()或get()操作</th> 
   <th align="center">LRU的状态</th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td align="center">set(‘A’,1)</td> 
   <td align="center">LRU中只有一个记录，最常使用记录： (‘A’,1)</td> 
  </tr> 
  <tr> 
   <td align="center">set(‘B’,2)</td> 
   <td align="center">LRU中有2个记录，最常使用记录： (‘B’,2)，最不常使用记录：(‘A’,1)</td> 
  </tr> 
  <tr> 
   <td align="center">get(‘A’)</td> 
   <td align="center">LRU中有2个记录，最常使用记录： (‘A’,1)，最不常使用记录：(‘B’,2)</td> 
  </tr> 
  <tr> 
   <td align="center">set(‘C’,3)</td> 
   <td align="center">LRU中有3个记录，最常使用记录： (‘C’,3)，最不常使用记录：(‘B’,2)</td> 
  </tr> 
  <tr> 
   <td align="center">set(‘D’,4)</td> 
   <td align="center">LRU中有4个记录，最常使用记录： (‘D’,4)，最不常使用记录：(‘B’,2)</td> 
  </tr> 
  <tr> 
   <td align="center">get(‘B’)</td> 
   <td align="center">LRU中有4个记录，最常使用记录：(‘B’,2)，最不常使用记录：(‘A’,1)</td> 
  </tr> 
  <tr> 
   <td align="center">set(‘E’,5)</td> 
   <td align="center">超过LRU容量，移除最不常使用记录(‘A’,1)，插入(‘E’,5)，此时最常使用记录变为(‘E’,5)，最不常使用记录变为 (‘C’,3)</td> 
  </tr> 
 </tbody> 
</table>

所谓缓存就是内存中一块空间，用来快速读取和写入数据。

这道题中要设计的LRU 是一种常见的缓存结构，它使用最少最近使用(LRU)缓存淘汰策略对数据进行淘汰，当缓存已满优先删除最不常使用记录。

因为缓存中插入和删除数据的操作比较频繁，所以通常使用双向链表作为数据的载体，对于LRU 载体，可规定双向链表的表头head 保存最不常用记录，表尾tail 保存最常使用记录。

*  当执行set() 将一条记录插入LRU 时，可将该数据节点插入双向链表的表尾，此时该记录为最常使用记录。
 *  当执行get() 从LRU中读取一个记录时，除了找到包含该记录的链表节点并将其返回，还要将该节点调整到双向链表的尾部，使其成为最常使用记录
 *  当执行set() 将一条记录插入LRU 缓存，而LRU 缓存已达最大容量时，可将双向链表的表头节点移除，因为表头是最不常用记录。

Java 实现LRU 双向链表类：

class Node<V> {
        
        public V data;
        public Node<V> prior; // 指向前驱节点的指针
        public Node<V> next; // 指向后继节点的指针
    
        public Node(V data) {
        
            this.data = data; // 节点中的数据
        }
    }
    
    class DoubleLinkedList<V> {
        
        private Node<V> head; // 双向链表的表头
        private Node<V> tail; // 双向链表的表尾
    
        public DoubleLinkedList() {
        
            this.head = null;
            this.tail = null;
        }
    
        // 向链表的尾部插入节点, 使其成为最常使用记录
        public void addNode(Node<V> node) {
        
            if (node == null) {
        
                return;
            }
            if (head == null) {
        
                // 双向队列为空
                head = node;
                tail = node;
            } else {
        
                tail.next = node;  // 将node节点插入到尾部
                node.prior = tail; // 建立相互连接
                tail = node; // 修改tail 指针
            }
        }
    
        // 将node节点移到链表尾部，使其成为最常使用记录
        public void moveNodeToTail(Node<V> node) {
        
            if (tail == node) {
        
                return;  // node已经在了，不进行任何操作
            }
            if (head == node) {
        
                // 要移动的节点是head 位置的节点
                head = node.next;
                head.prior = null; // 将node节点删除
            } else {
        
                // 删除链表中间的某节点
                node.prior.next = node.next;
                node.next.prior = node.prior;  // 将node节点删除
            }
    
            // 将删除的node 插入tail位置
            node.prior = tail;
            node.next = null;
            tail.next = node;
            tail = node;
        }
    
        // 删除表头节点, 移除最不常用记录
        public Node<V> removeHead() {
        
            if (head == null) {
        
                return null; // 链表中根本没有节点
            }
    
            Node<V> res = head; // res指向头结点
            if (head == tail) {
        
                // 链表中仅有一个节点，head和tail 都是它，那就将它俩都置为null就行了
                head = null;
                tail = null;
            } else {
        
                // 删除head节点, 让head 指向原head节点的后继
                head = res.next;
                res.next = null;
                head.prior = null;
            }
    
            return res;
        }
    
        // 打印双向链表
        public void printDoubleLinkedList() {
        
            Node<V> list = head;
            while (list != null) {
        
                System.out.print(list.data + " ");
                list = list.next;
            }
            System.out.println();
        }
    
    }

这样的双向链表类和基本操作就基本构成了LRU 缓存的数据结构。

现在的问题就是如何尽可能高效的在缓存中读取和写入数据：

*  对于set()，可通过调用addNode() 函数将节点插入双向链表尾部，时间复杂度为O(1)
 *  对于get()，则需要通过通过关键字key 找到指定记录，然后将其移动到双向链表尾部，使其变为最常使用记录，时间复杂度规定为O(1)，我们就可以使用HashMap 来辅助实现。
    
     *  使用两个HashMap 将关键字key 和双向链表中的node节点一一对应。其中一个HashMap 以key 为关键字，这样可以通过指定的key 在O(1) 的时间内找到对应的node 节点引用，也就是在双向链表上建立一个索引；另一个HashMap 以node 为关键字，这样可以通过给定的node 在O(1) 的时间内找到该节点对应的key，它的作用主要就是在删除双向链表中的节点时找到对应的key，从而删除HashMap 中的索引。

LRUCache 的定义：

import java.util.HashMap;
    
    /**
     * @Projectname: JavaData_StructureAndAlgorithm
     * @Classname: DesignOfTheLRUCache
     * @Author: Ding Jiaxiong
     * @Data:2023/3/17 9:52
     */
    
    class Node<V> {
        
        public V data;
        public Node<V> prior; // 指向前驱节点的指针
        public Node<V> next; // 指向后继节点的指针
    
        public Node(V data) {
        
            this.data = data; // 节点中的数据
        }
    }
    
    class DoubleLinkedList<V> {
        
        private Node<V> head; // 双向链表的表头
        private Node<V> tail; // 双向链表的表尾
    
        public DoubleLinkedList() {
        
            this.head = null;
            this.tail = null;
        }
    
        // 向链表的尾部插入节点, 使其成为最常使用记录
        public void addNode(Node<V> node) {
        
            if (node == null) {
        
                return;
            }
            if (head == null) {
        
                // 双向队列为空
                head = node;
                tail = node;
            } else {
        
                tail.next = node;  // 将node节点插入到尾部
                node.prior = tail; // 建立相互连接
                tail = node; // 修改tail 指针
            }
        }
    
        // 将node节点移到链表尾部，使其成为最常使用记录
        public void moveNodeToTail(Node<V> node) {
        
            if (tail == node) {
        
                return;  // node已经在了，不进行任何操作
            }
            if (head == node) {
        
                // 要移动的节点是head 位置的节点
                head = node.next;
                head.prior = null; // 将node节点删除
            } else {
        
                // 删除链表中间的某节点
                node.prior.next = node.next;
                node.next.prior = node.prior;  // 将node节点删除
            }
    
            // 将删除的node 插入tail位置
            node.prior = tail;
            node.next = null;
            tail.next = node;
            tail = node;
        }
    
        // 删除表头节点, 移除最不常用记录
        public Node<V> removeHead() {
        
            if (head == null) {
        
                return null; // 链表中根本没有节点
            }
    
            Node<V> res = head; // res指向头结点
            if (head == tail) {
        
                // 链表中仅有一个节点，head和tail 都是它，那就将它俩都置为null就行了
                head = null;
                tail = null;
            } else {
        
                // 删除head节点, 让head 指向原head节点的后继
                head = res.next;
                res.next = null;
                head.prior = null;
            }
    
            return res;
        }
    
        // 打印双向链表
        public void printDoubleLinkedList() {
        
            Node<V> list = head;
            while (list != null) {
        
                System.out.print(list.data + " ");
                list = list.next;
            }
            System.out.println();
        }
    
    }
    
    public class LRUCache<K, V> {
        
    
        private DoubleLinkedList<V> doubleLinkedList; // 双向链表
        private HashMap<Node<V>, K> nodeKeyMap; // (node, key)
        private HashMap<K, Node<V>> keyNodeMap; // (key, node)
    
        private int capacity;
    
        public LRUCache(int capacity) {
        
            keyNodeMap = new HashMap<K, Node<V>>();
            nodeKeyMap = new HashMap<Node<V>, K>();
            doubleLinkedList = new DoubleLinkedList<V>();
            this.capacity = capacity;
        }
    
        public V get(K key) {
        
            // 通过key 获取LRU中的数据并返回
            if (keyNodeMap.containsKey(key)) {
        
                Node<V> res = keyNodeMap.get(key); // 获取该节点在链表中的指针
                // 把该节点移到队列尾部, 变为最常访问节点
                doubleLinkedList.moveNodeToTail(res);
                return res.data;
            }
    
            return null;
        }
    
        public void set(K key, V value) {
        
            if (keyNodeMap.containsKey(key)) {
        
                // 如果set 的(key , value) 已经在LRU中了，这样就更新
                // 通过keyNodeMap 获取key对应的节点引用
                Node<V> node = keyNodeMap.get(key);
                node.data = value;
                doubleLinkedList.moveNodeToTail(node);
            } else {
        
                // 插入一个新的节点
                Node<V> node = new Node<V>(value);  // 创建一个新的节点
                keyNodeMap.put(key, node);
                nodeKeyMap.put(node, key);
                doubleLinkedList.addNode(node);
    
                if (keyNodeMap.size() > capacity) {
        
                    // 若LRUCache 已到最大容量, 则删除最不常使用记录
                    removeMostUnusedRecord();
                }
            }
        }
    
        private void removeMostUnusedRecord() {
        
            Node<V> node = doubleLinkedList.removeHead();  // 删除双向链表头结点
            K key = nodeKeyMap.get(node); // 获取对应节点的key
            nodeKeyMap.remove(node);
            keyNodeMap.remove(key);
        }
    
        public void printCache() {
        
            doubleLinkedList.printDoubleLinkedList();
        }
    
        public static void main(String[] args) {
        
    
            LRUCache<Character, Integer> cache = new LRUCache<Character, Integer>(4);
            cache.set('A', 1);
            cache.set('B', 2);
            cache.get('A');
            cache.set('C', 3);
            cache.set('D', 4);
            cache.printCache();
            cache.get('B');
            cache.set('E', 5);
            cache.printCache();
    
        }
    
    }

运行结果

![在这里插入图片描述][cb37890d7f9c4484b28ee7dac5c68962.png_pic_center]

LRU 缓存内容变化情况：

public static void main(String[] args) {
        
    
        LRUCache<Character, Integer> cache = new LRUCache<Character, Integer>(4);
        cache.set('A', 1); // 1
        cache.set('B', 2); // 1 → 2
        cache.get('A'); // 2 → 1
        cache.set('C', 3); // 2 → 1 → 3
        cache.set('D', 4); // 2 → 1 → 3 → 4
        cache.printCache(); // 2 1 3 4
        cache.get('B'); // 1 → 3 → 4 → 2
        cache.set('E', 5); // 3 → 4 → 2 → 5
        cache.printCache(); // 3 4 2 5
    
    }

###### 9 线性结构类面试题解题技巧 ######

###### 【1】根据应用场景选择适合的数据结构 ######

###### 【2】熟练掌握经典的数据结构算法 ######

###### 【3】快慢指针 ######

###### 【4】高级的数据结构实现 ######

[120eafeab5804023867a186be2de8955.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/2927092618824d55b9b41ed67eb61ad4.png
[d9d7cb9d239a4235bd24538d9e166e15.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a8f663bc11184c24b4842a4f837fb44e.png
[245170eae9f2489fb2897778d9f102f0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/99bb29634e7d44e29e3368b7c81ad835.png
[812a5d5de8474a888d3cef01eeba04b5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/44b610ebd41a4dc79e4644f60f03d1ac.png
[9388ad846c374b04b7bd30efadd5d65b.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/5d9a7c7bd4084fdb97005e47efbc1cc4.png
[d7f31257ad2541ecb39851c2b6696925.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ce14a9d93c104c08854770786e69a511.png
[94d1dca73abe4dd58ede627540e4ff8d.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/ac825e713d534c70959a98d0fab3b1b2.png
[3fd73f8f65e1469dae2379b12985221e.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d6f31cb7d9de4277ac547066cc2a748d.png
[4d10522678404af795e62904559cd3d5.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/68572a480fc540c39baffa1d9667cac4.png
[89434277443c430fad788e562e3da696.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/459dc47ce87b4c11a782c48c0868f9dd.png
[54b9a7a15f9645db949f6fb506262a8f.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/30d6b084729c412290066ef70a4fbb16.png
[5e5abe1d939442a38db6411ae66bd1b0.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/d8074c98508e4c989d01a6c440746b01.png
[8126ba4243774cf0a81ee34a6d612b95.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e28147e8c7cc43a4b05cad7828a30258.png
[4ba4a132eab2442e8cf172dd69be18b8.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/c39ea27c01bf42ed92ee2a1e0bda8a72.png
[96f8c6dc5a03435e93aa6c868b6ea73a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/dddaf6d93e0a497aa1a1a3c74c840404.png
[cd4b7e21e24f456eb71714a8d133ef16.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1954e3ec92ad4c318dab1b0bb96e0c8f.png
[4c3cce4ad30b4ccd8349ee38f0307f6c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/a146d2d9ae0047d08fa2a5cd39365b50.png
[99cfa62f966e4efbb179ac260471018c.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/faf22e66ea1347138ea738812c050071.png
[677f397cd85b4e0d843217b242c17f90.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/779347fd7e654517870700dd239868f1.png
[ebdae6c12ad042159dc09587fa279fdf.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/95e87418c0e6496ca86c0e12ef52e2c8.png
[a61420ee0b83476d82d75f1ef92f0585.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/b29754e730924074a4ae3299139961ed.png
[11f2853b70a34abeb6781f040dbafac9.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e15007ce5b8741dc855a59e612f70f6a.png
[158bd23abc184e5bba48ce07aea9d9dc.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/e87be84b46324ed696dbadd6bae62156.png
[ad4383b899474a2da010c36f13a72f7a.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/9102917d02fa4e71b232fd54fc231a67.png
[d940041ea03a4b0f9bf816d557e55102.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/8c985bf966ff4987a3159a94e8300937.png
[cb37890d7f9c4484b28ee7dac5c68962.png_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/25/1d895eb268e948d8a541475810317f64.png