算法的深入浅出--10.面试基础问题（3）

女爷i 2021-11-05 02:18 182阅读 0赞

**目录**

一、复制含有随机指针节点的链表

二、两个单链表相交的一系列问题

三、实现二叉树的先序（深度优先遍历）、 中序、 后序遍历， 包括递归方式和非递归方式

四、树的广度优先遍历就是层序遍历（递归和非递归方式）。

四、在二叉树中找到一个节点的后继节点

五、介绍二叉树的序列化和反序列化

--------------------

# 一、复制含有随机指针节点的链表 #

一种特殊的链表节点类描述如下：  
public class Node \{ public int value; public Node next; public  
Node rand;  
public Node(int data) \{ this.value = data; \}  
\} N  
ode类中的value是节点值， next指针和正常单链表中next指针的意义  
一 样， 都指向下一个节点， rand指针是Node类中新增的指针， 这个指  
针可 能指向链表中的任意一个节点， 也可能指向null。 给定一个由  
Node节点类型组成的无环单链表的头节点head， 请实现一个 函数完成  
这个链表中所有结构的复制， 并返回复制的新链表的头节点。 进阶：  
不使用额外的数据结构， 只用有限几个变量， 且在时间复杂度为 O(N)  
内完成原问题要实现的函数。

public class CopyListWithRandom {
        public static class Node {
            public int value;
            public Node next;
            public Node rand;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static Node copyListWithRand1(Node head) {
            HashMap<Node, Node> map = new HashMap<Node, Node>();
            Node cur = head;
            while (cur != null) {
                map.put(cur, new Node(cur.value));
                cur = cur.next;
            }
            cur = head;
            while (cur != null) {
                map.get(cur).next = map.get(cur.next);
                map.get(cur).rand = map.get(cur.rand);
                cur = cur.next;
            }
            return map.get(head);
        }
    
        public static Node copyListWithRand2(Node head) {
            if (head == null) {
                return null;
            }
            Node cur = head;
            Node next = null;
            // copy node and link to every node
            while (cur != null) {
                next = cur.next;
                cur.next = new Node(cur.value);
                cur.next.next = next;
                cur = next;
            }
            cur = head;
            Node curCopy = null;
            // set copy node rand
            while (cur != null) {
                next = cur.next.next;
                curCopy = cur.next;
                curCopy.rand = cur.rand != null ? cur.rand.next : null;
                cur = next;
            }
            Node res = head.next;
            cur = head;
            // split
            while (cur != null) {
                next = cur.next.next;
                curCopy = cur.next;
                cur.next = next;
                curCopy.next = next != null ? next.next : null;
                cur = next;
            }
            return res;
        }
    
        public static void printRandLinkedList(Node head) {
            Node cur = head;
            System.out.print("order: ");
            while (cur != null) {
                System.out.print(cur.value + " ");
                cur = cur.next;
            }
            System.out.println();
            cur = head;
            System.out.print("rand:  ");
            while (cur != null) {
                System.out.print(cur.rand == null ? "- " : cur.rand.value + " ");
                cur = cur.next;
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            Node head = null;
            Node res1 = null;
            Node res2 = null;
            printRandLinkedList(head);
            res1 = copyListWithRand1(head);
            printRandLinkedList(res1);
            res2 = copyListWithRand2(head);
            printRandLinkedList(res2);
            printRandLinkedList(head);
            System.out.println("=========================");
    
            head = new Node(1);
            head.next = new Node(2);
            head.next.next = new Node(3);
            head.next.next.next = new Node(4);
            head.next.next.next.next = new Node(5);
            head.next.next.next.next.next = new Node(6);
    
            head.rand = head.next.next.next.next.next; // 1 -> 6
            head.next.rand = head.next.next.next.next.next; // 2 -> 6
            head.next.next.rand = head.next.next.next.next; // 3 -> 5
            head.next.next.next.rand = head.next.next; // 4 -> 3
            head.next.next.next.next.rand = null; // 5 -> null
            head.next.next.next.next.next.rand = head.next.next.next; // 6 -> 4
    
            printRandLinkedList(head);
            res1 = copyListWithRand1(head);
            printRandLinkedList(res1);
            res2 = copyListWithRand2(head);
            printRandLinkedList(res2);
            printRandLinkedList(head);
            System.out.println("=========================");
    
        }
    }

# 二、两个单链表相交的一系列问题 #

在本题中， 单链表可能有环， 也可能无环。 给定两个单链表的头节点 head1和head2， 这两个链表可能相交， 也可能不相交。 请实现一个函数， 如果两个链表相交， 请返回相交的第一个节点； 如果不相交， 返回null 即可。 要求： 如果链表1的长度为N， 链表2的长度为M， 时间复杂度请达到 O(N+M)， 额外空间复杂度请达到O(1)。

public class FindFirstIntersectNode {
        public static class Node {
            public int value;
            public Node next;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static Node getIntersectNode(Node head1, Node head2) {
            if (head1 == null || head2 == null) {
                return null;
            }
            Node loop1 = getLoopNode(head1);
            Node loop2 = getLoopNode(head2);
            if (loop1 == null && loop2 == null) {
                return noLoop(head1, head2);
            }
            if (loop1 != null && loop2 != null) {
                return bothLoop(head1, loop1, head2, loop2);
            }
            return null;
        }
    
        public static Node getLoopNode(Node head) {
            if (head == null || head.next == null || head.next.next == null) {
                return null;
            }
            Node n1 = head.next; // n1 -> slow
            Node n2 = head.next.next; // n2 -> fast
            while (n1 != n2) {
                if (n2.next == null || n2.next.next == null) {
                    return null;
                }
                n2 = n2.next.next;
                n1 = n1.next;
            }
            n2 = head; // n2 -> walk again from head
            while (n1 != n2) {
                n1 = n1.next;
                n2 = n2.next;
            }
            return n1;
        }
    
        public static Node noLoop(Node head1, Node head2) {
            if (head1 == null || head2 == null) {
                return null;
            }
            Node cur1 = head1;
            Node cur2 = head2;
            int n = 0;
            while (cur1.next != null) {
                n++;
                cur1 = cur1.next;
            }
            while (cur2.next != null) {
                n--;
                cur2 = cur2.next;
            }
            if (cur1 != cur2) {
                return null;
            }
            cur1 = n > 0 ? head1 : head2;
            cur2 = cur1 == head1 ? head2 : head1;
            n = Math.abs(n);
            while (n != 0) {
                n--;
                cur1 = cur1.next;
            }
            while (cur1 != cur2) {
                cur1 = cur1.next;
                cur2 = cur2.next;
            }
            return cur1;
        }
    
        public static Node bothLoop(Node head1, Node loop1, Node head2, Node loop2) {
            Node cur1 = null;
            Node cur2 = null;
            if (loop1 == loop2) {
                cur1 = head1;
                cur2 = head2;
                int n = 0;
                while (cur1 != loop1) {
                    n++;
                    cur1 = cur1.next;
                }
                while (cur2 != loop2) {
                    n--;
                    cur2 = cur2.next;
                }
                cur1 = n > 0 ? head1 : head2;
                cur2 = cur1 == head1 ? head2 : head1;
                n = Math.abs(n);
                while (n != 0) {
                    n--;
                    cur1 = cur1.next;
                }
                while (cur1 != cur2) {
                    cur1 = cur1.next;
                    cur2 = cur2.next;
                }
                return cur1;
            } else {
                cur1 = loop1.next;
                while (cur1 != loop1) {
                    if (cur1 == loop2) {
                        return loop1;
                    }
                    cur1 = cur1.next;
                }
                return null;
            }
        }
    
        public static void main(String[] args) {
            // 1->2->3->4->5->6->7->null
            Node head1 = new Node(1);
            head1.next = new Node(2);
            head1.next.next = new Node(3);
            head1.next.next.next = new Node(4);
            head1.next.next.next.next = new Node(5);
            head1.next.next.next.next.next = new Node(6);
            head1.next.next.next.next.next.next = new Node(7);
    
            // 0->9->8->6->7->null
            Node head2 = new Node(0);
            head2.next = new Node(9);
            head2.next.next = new Node(8);
            head2.next.next.next = head1.next.next.next.next.next; // 8->6
            System.out.println(getIntersectNode(head1, head2).value);
    
            // 1->2->3->4->5->6->7->4...
            head1 = new Node(1);
            head1.next = new Node(2);
            head1.next.next = new Node(3);
            head1.next.next.next = new Node(4);
            head1.next.next.next.next = new Node(5);
            head1.next.next.next.next.next = new Node(6);
            head1.next.next.next.next.next.next = new Node(7);
            head1.next.next.next.next.next.next = head1.next.next.next; // 7->4
    
            // 0->9->8->2...
            head2 = new Node(0);
            head2.next = new Node(9);
            head2.next.next = new Node(8);
            head2.next.next.next = head1.next; // 8->2
            System.out.println(getIntersectNode(head1, head2).value);
    
            // 0->9->8->6->4->5->6..
            head2 = new Node(0);
            head2.next = new Node(9);
            head2.next.next = new Node(8);
            head2.next.next.next = head1.next.next.next.next.next; // 8->6
            System.out.println(getIntersectNode(head1, head2).value);
    
        }
    }

# 三、实现二叉树的先序（深度优先遍历）、 中序、 后序遍历， 包括递归方式和非递归方式 #

public class PreInPosTraversal {
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static void preOrderRecur(Node head) {
            if (head == null) {
                return;
            }
            System.out.print(head.value + " ");
            preOrderRecur(head.left);
            preOrderRecur(head.right);
        }
    
        public static void inOrderRecur(Node head) {
            if (head == null) {
                return;
            }
            inOrderRecur(head.left);
            System.out.print(head.value + " ");
            inOrderRecur(head.right);
        }
    
        public static void posOrderRecur(Node head) {
            if (head == null) {
                return;
            }
            posOrderRecur(head.left);
            posOrderRecur(head.right);
            System.out.print(head.value + " ");
        }
    
        public static void preOrderUnRecur(Node head) {
            System.out.print("pre-order: ");
            if (head != null) {
                Stack<Node> stack = new Stack<Node>();
                stack.add(head);
                while (!stack.isEmpty()) {
                    head = stack.pop();
                    System.out.print(head.value + " ");
                    if (head.right != null) {
                        stack.push(head.right);
                    }
                    if (head.left != null) {
                        stack.push(head.left);
                    }
                }
            }
            System.out.println();
        }
    
        public static void inOrderUnRecur(Node root) {
            System.out.print("in-order: ");
            iif (root==null){
                return;
            }
            Stack stack=new Stack();
            while (root!=null || !stack.isEmpty()){
                if (root!=null){
                    stack.add(root);
                    root=root.left;
                }else {
                    root= (Node) stack.pop();
                    System.out.println(root.value);
                    root=root.right;
                }
            }
            System.out.println();
        }
    
        public static void posOrderUnRecur1(Node head) {
            System.out.print("pos-order: ");
            if (head != null) {
                Stack<Node> s1 = new Stack<Node>();
                Stack<Node> s2 = new Stack<Node>();
                s1.push(head);
                while (!s1.isEmpty()) {
                    head = s1.pop();
                    s2.push(head);
                    if (head.left != null) {
                        s1.push(head.left);
                    }
                    if (head.right != null) {
                        s1.push(head.right);
                    }
                }
                while (!s2.isEmpty()) {
                    System.out.print(s2.pop().value + " ");
                }
            }
            System.out.println();
        }
    
        public static void posOrderUnRecur2(Node h) {
            System.out.print("pos-order: ");
            if (h != null) {
                Stack<Node> stack = new Stack<Node>();
                stack.push(h);
                Node c = null;
                while (!stack.isEmpty()) {
                    c = stack.peek();
                    if (c.left != null && h != c.left && h != c.right) {
                        stack.push(c.left);
                    } else if (c.right != null && h != c.right) {
                        stack.push(c.right);
                    } else {
                        System.out.print(stack.pop().value + " ");
                        h = c;
                    }
                }
            }
            System.out.println();
        }
    
        public static void main(String[] args) {
            Node head = new Node(5);
            head.left = new Node(3);
            head.right = new Node(8);
            head.left.left = new Node(2);
            head.left.right = new Node(4);
            head.left.left.left = new Node(1);
            head.right.left = new Node(7);
            head.right.left.left = new Node(6);
            head.right.right = new Node(10);
            head.right.right.left = new Node(9);
            head.right.right.right = new Node(11);
    
            // recursive
            System.out.println("==============recursive==============");
            System.out.print("pre-order: ");
            preOrderRecur(head);
            System.out.println();
            System.out.print("in-order: ");
            inOrderRecur(head);
            System.out.println();
            System.out.print("pos-order: ");
            posOrderRecur(head);
            System.out.println();
    
            // unrecursive
            System.out.println("============unrecursive=============");
            preOrderUnRecur(head);
            inOrderUnRecur(head);
            posOrderUnRecur1(head);
            posOrderUnRecur2(head);
    
        }
    }

# 四、树的广度优先遍历就是层序遍历（递归和非递归方式）。 #

层次遍历请集合该视频观看：[https://www.bilibili.com/video/av45744561?from=search&seid=4507345960920035797][https_www.bilibili.com_video_av45744561_from_search_seid_4507345960920035797]（将代码复制了一遍讲解，不过博主很热心）

public class LeverTraversal {
        public static class TreeNode{
            public TreeNode left;
            public TreeNode right;
            public int value;
            public TreeNode(int value){
                this.value=value;
            }
        }
    
        /**
         *
         * 非递归方式实现广度优先遍历（层次优先遍历）
         */
        public static List<List<Integer>> leverTraversal(TreeNode root){
            List<List<Integer>> res=new LinkedList<>();
            if (root==null){
                return res;
            }
            LinkedList<TreeNode> queue=new LinkedList<>();
            queue.add(root);
            while (!queue.isEmpty()){
                int size=queue.size();
                List<Integer> levelVal=new LinkedList<>();
    
                while (size>0){
                    TreeNode current=queue.poll();
                    if (current.left!=null){
                        queue.add(current.left);
                    }
    
                    if (current.right!=null){
                        queue.add(current.right);
                    }
                    levelVal.add(current.value);
                    size--;
                }
    //            res.add(0,levelVal);
                res.add(levelVal);
            }
            return res;
        }
    
        /**
         *
         * 递归方式实现层次遍历（广度优先遍历
         */
        public List<List<Integer>> levelOrder(TreeNode root) {
            List<List<Integer>> res = new ArrayList<>();
            if (root == null){
                return res;
            }
            levelOrder(root, res, 0);
            return res;
        }
        /**
         *递归的核心之处所在，首先通过res来添加入所有的层级的节点放入，相当于每一层就是一个 
         *List<Integer>，然后递归回来将每一层的中的节点放入按顺序放入到
         * 每一层的List<Integer>中。 
         */
        public void levelOrder(TreeNode root, List<List<Integer>> res,Integer depth){
            if (root == null){
                return;
            }
            if (res.size() == depth){
                res.add(new LinkedList<>());
            }
            List<Integer> current = res.get(depth);
            levelOrder(root.left, res, depth+1);
            levelOrder(root.right, res, depth+1);
            current.add(root.val);
        }
    
    
        public static void main(String [] args){
            TreeNode root=new TreeNode(0);
            root.left=new TreeNode(1);
            root.right=new TreeNode(2);
            root.left.left=new TreeNode(3);
            root.left.right=new TreeNode(4);
            root.right.left=new TreeNode(5);
            root.right.right=new TreeNode(6);
            List<List<Integer>> lists = levelTraversal_recursion(root);
    
            for (int i = 0; i < lists.size(); i++) {
                System.out.println(lists.get(i));
            }
        }
    }

# 四、在二叉树中找到一个节点的后继节点 #

现在有一种新的二叉树节点类型如下：

public class Node { 
        public int value; 
        public Node left;
        public Node right; 
        public Node parent;
        public Node(int data) { 
            this.value = data; 
            }
    }

该结构比普通二叉树节点结构多了一个指向父节点的parent指针。 假设有一 棵Node类型的节点组成的二叉树， 树中每个节点的parent指针都正确地指向 自己的父节点， 头节点的parent指向null。 只给一个在二叉树中的某个节点 node， 请实现返回node的后继节点的函数。 在二叉树的中序遍历的序列中， node的下一个节点叫作node的后继节点。

public class SuccessorNode {
        public static class Node {
            public int value;
            public Node left;
            public Node right;
            public Node parent;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static Node getSuccessorNode(Node node) {
            if (node == null) {
                return node;
            }
            if (node.right != null) {
                return getLeftMost(node.right);
            } else {
                Node parent = node.parent;
                while (parent != null && parent.left != node) {
                    node = parent;
                    parent = node.parent;
                }
                return parent;
            }
        }
    
        public static Node getLeftMost(Node node) {
            if (node == null) {
                return node;
            }
            while (node.left != null) {
                node = node.left;
            }
            return node;
        }
    
        public static void main(String[] args) {
            Node head = new Node(6);
            head.parent = null;
            head.left = new Node(3);
            head.left.parent = head;
            head.left.left = new Node(1);
            head.left.left.parent = head.left;
            head.left.left.right = new Node(2);
            head.left.left.right.parent = head.left.left;
            head.left.right = new Node(4);
            head.left.right.parent = head.left;
            head.left.right.right = new Node(5);
            head.left.right.right.parent = head.left.right;
            head.right = new Node(9);
            head.right.parent = head;
            head.right.left = new Node(8);
            head.right.left.parent = head.right;
            head.right.left.left = new Node(7);
            head.right.left.left.parent = head.right.left;
            head.right.right = new Node(10);
            head.right.right.parent = head.right;
    
            Node test = head.left.left;
            System.out.println(test.value + " next: " + getSuccessorNode(test).value);
            test = head.left.left.right;
            System.out.println(test.value + " next: " + getSuccessorNode(test).value);
            test = head.left;
            System.out.println(test.value + " next: " + getSuccessorNode(test).value);
            test = head.left.right;
            System.out.println(test.value + " next: " + getSuccessorNode(test).value);
            test = head.left.right.right;
            System.out.println(test.value + " next: " + getSuccessorNode(test).value);
            test = head;
            System.out.println(test.value + " next: " + getSuccessorNode(test).value);
            test = head.right.left.left;
            System.out.println(test.value + " next: " + getSuccessorNode(test).value);
            test = head.right.left;
            System.out.println(test.value + " next: " + getSuccessorNode(test).value);
            test = head.right;
            System.out.println(test.value + " next: " + getSuccessorNode(test).value);
            test = head.right.right; // 10's next is null
            System.out.println(test.value + " next: " + getSuccessorNode(test));
        }
    }

# 五、介绍二叉树的序列化和反序列化 #

请实现两个函数，分别用来序列化和反序列化二叉树

二叉树的序列化是指：把一棵二叉树按照某种遍历方式的结果以某种格式保存为字符串，从而使得内存中建立起来的二叉树可以持久保存。序列化可以基于先序、中序、后序、层序的二叉树遍历方式来进行修改，序列化的结果是一个字符串，序列化时通过 某种符号表示空节点（\#），以 ！ 表示一个结点值的结束（value!）。  
二叉树的反序列化是指：根据某种遍历顺序得到的序列化字符串结果str，重构二叉树。

public class SerializeAndReconstructTree {
        public static class Node {
            public int value;
            public Node left;
            public Node right;
    
            public Node(int data) {
                this.value = data;
            }
        }
    
        public static String serialByPre(Node head) {
            if (head == null) {
                return "#!";
            }
            String res = head.value + "!";
            res += serialByPre(head.left);
            res += serialByPre(head.right);
            return res;
        }
    
        public static Node reconByPreString(String preStr) {
            String[] values = preStr.split("!");
            Queue<String> queue = new LinkedList<String>();
            for (int i = 0; i != values.length; i++) {
                queue.offer(values[i]);
            }
            return reconPreOrder(queue);
        }
    
        public static Node reconPreOrder(Queue<String> queue) {
            String value = queue.poll();
            if (value.equals("#")) {
                return null;
            }
            Node head = new Node(Integer.valueOf(value));
            head.left = reconPreOrder(queue);
            head.right = reconPreOrder(queue);
            return head;
        }
    
        public static String serialByLevel(Node head) {
            if (head == null) {
                return "#!";
            }
            String res = head.value + "!";
            Queue<Node> queue = new LinkedList<Node>();
            queue.offer(head);
            while (!queue.isEmpty()) {
                head = queue.poll();
                if (head.left != null) {
                    res += head.left.value + "!";
                    queue.offer(head.left);
                } else {
                    res += "#!";
                }
                if (head.right != null) {
                    res += head.right.value + "!";
                    queue.offer(head.right);
                } else {
                    res += "#!";
                }
            }
            return res;
        }
    
        public static Node reconByLevelString(String levelStr) {
            String[] values = levelStr.split("!");
            int index = 0;
            Node head = generateNodeByString(values[index++]);
            Queue<Node> queue = new LinkedList<Node>();
            if (head != null) {
                queue.offer(head);
            }
            Node node = null;
            while (!queue.isEmpty()) {
                node = queue.poll();
                node.left = generateNodeByString(values[index++]);
                node.right = generateNodeByString(values[index++]);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            return head;
        }
    
        public static Node generateNodeByString(String val) {
            if (val.equals("#")) {
                return null;
            }
            return new Node(Integer.valueOf(val));
        }
    
        // for test -- print tree
        public static void printTree(Node head) {
            System.out.println("Binary Tree:");
            printInOrder(head, 0, "H", 17);
            System.out.println();
        }
    
        public static void printInOrder(Node head, int height, String to, int len) {
            if (head == null) {
                return;
            }
            printInOrder(head.right, height + 1, "v", len);
            String val = to + head.value + to;
            int lenM = val.length();
            int lenL = (len - lenM) / 2;
            int lenR = len - lenM - lenL;
            val = getSpace(lenL) + val + getSpace(lenR);
            System.out.println(getSpace(height * len) + val);
            printInOrder(head.left, height + 1, "^", len);
        }
    
        public static String getSpace(int num) {
            String space = " ";
            StringBuffer buf = new StringBuffer("");
            for (int i = 0; i < num; i++) {
                buf.append(space);
            }
            return buf.toString();
        }
    
        public static void main(String[] args) {
            Node head = null;
            printTree(head);
    
            String pre = serialByPre(head);
            System.out.println("serialize tree by pre-order: " + pre);
            head = reconByPreString(pre);
            System.out.print("reconstruct tree by pre-order, ");
            printTree(head);
    
            String level = serialByLevel(head);
            System.out.println("serialize tree by level: " + level);
            head = reconByLevelString(level);
            System.out.print("reconstruct tree by level, ");
            printTree(head);
    
            System.out.println("====================================");
    
            head = new Node(1);
            printTree(head);
    
            pre = serialByPre(head);
            System.out.println("serialize tree by pre-order: " + pre);
            head = reconByPreString(pre);
            System.out.print("reconstruct tree by pre-order, ");
            printTree(head);
    
            level = serialByLevel(head);
            System.out.println("serialize tree by level: " + level);
            head = reconByLevelString(level);
            System.out.print("reconstruct tree by level, ");
            printTree(head);
    
            System.out.println("====================================");
    
            head = new Node(1);
            head.left = new Node(2);
            head.right = new Node(3);
            head.left.left = new Node(4);
            head.right.right = new Node(5);
            printTree(head);
    
            pre = serialByPre(head);
            System.out.println("serialize tree by pre-order: " + pre);
            head = reconByPreString(pre);
            System.out.print("reconstruct tree by pre-order, ");
            printTree(head);
    
            level = serialByLevel(head);
            System.out.println("serialize tree by level: " + level);
            head = reconByLevelString(level);
            System.out.print("reconstruct tree by level, ");
            printTree(head);
    
            System.out.println("====================================");
    
            head = new Node(100);
            head.left = new Node(21);
            head.left.left = new Node(37);
            head.right = new Node(-42);
            head.right.left = new Node(0);
            head.right.right = new Node(666);
            printTree(head);
    
            pre = serialByPre(head);
            System.out.println("serialize tree by pre-order: " + pre);
            head = reconByPreString(pre);
            System.out.print("reconstruct tree by pre-order, ");
            printTree(head);
    
            level = serialByLevel(head);
            System.out.println("serialize tree by level: " + level);
            head = reconByLevelString(level);
            System.out.print("reconstruct tree by level, ");
            printTree(head);
    
            System.out.println("====================================");
    
        }
    }

[https_www.bilibili.com_video_av45744561_from_search_seid_4507345960920035797]: https://www.bilibili.com/video/av45744561?from=search&seid=4507345960920035797