[leetcode/lintcode 题解]大厂算法面试高频题: 序列化和反序列N叉树

简介: [leetcode/lintcode 题解]大厂算法面试高频题: 序列化和反序列N叉树

描述
序列化是将一个数据结构或对象转换成比特流的过程,以便将其存储在文件或内存缓冲区中,或通过网络连接链路传输,以便稍后在同一或另一计算机环境中重建。
设计一个算法来序列化和反序列化一个N叉树。一棵N叉树是一棵有根树,其中每个节点的子节点不超过N个。序列化/反序列化算法的实现方式没有限制。您只需要确保N叉树可以序列化为字符串,并且该字符串可以反序列化为原始树结构。
例如,你可以序列化如下的3叉树

为 [1 [3[5 6] 2 4]]。你不一定要遵循这种格式,发挥创意,自己想出不同的方法。
图模型说明: https://www.lintcode.com/help/graph

image.png

在线评测地址:领扣题库官网

样例1
输入:{1,3,2,4#2#3,5,6#4#5#6}
输出:{1,3,2,4#2#3,5,6#4#5#6}
解释:如上图
样例2
输入:{1,3,2#2#3}
输出:{1,3,2#2#3}
解释:
          1
         / \
        3   2

解题思路
题解:基本是dfs分治即可解决,对输入的有向图从1节点开始遍历构造字符串,遍历儿子节点前加入左括号,完成后加入右括号。还原N叉树同样,遇到左括号开始搜索,读取数字存入,遇到右括号退出。

源代码

/**
 * Definition for Directed graph.
 * class DirectedGraphNode {
 *     int label;
 *     ArrayList<DirectedGraphNode> neighbors;
 *     DirectedGraphNode(int x) { label = x; neighbors = new ArrayList<DirectedGraphNode>(); }
 * };
 */

public class Solution {
    public int pos = 1;
    public String dfs(DirectedGraphNode root) {
        String ans="";
        if(root == null)
            return ans;
        ans += "[";
        ans += String.valueOf(root.label);
        for(int i = 0; i < root.neighbors.size() ; i++) {
                ans += dfs(root.neighbors.get(i));
        }
        ans += "]";
        return ans;
        
    }
    public UndirectedGraphNode solve(String data) {
        int num = 0;
            while(data.charAt(pos) >= '0' && data.charAt(pos) <= '9') {
                num *= 10;
                num += data.charAt(pos) - '0';
                pos++;
            }
            UndirectedGraphNode node =  new UndirectedGraphNode(num);
            while(pos < data.length()) {
                if(data.charAt(pos) == '[' ) {
                    ++pos;
                    node.neighbors.add(solve(data));
                }
                else if(data.charAt(pos) == ']') {
                    pos++;
                    return node;
                }
            }
        return null;
    }
    public String serialize(ArrayList<DirectedGraphNode> nodes) {
        String ans="";
        if(nodes.size() == 0)
            return ans;
        return dfs(nodes.get(0));
    }
    public UndirectedGraphNode deserialize(String data) {
       if(data.length() == 0)
            return null;
        return solve(data);
    }
}

更多题解参考:九章官网solution

相关文章
|
存储 Java
【IO面试题 四】、介绍一下Java的序列化与反序列化
Java的序列化与反序列化允许对象通过实现Serializable接口转换成字节序列并存储或传输,之后可以通过ObjectInputStream和ObjectOutputStream的方法将这些字节序列恢复成对象。
|
存储 人工智能 算法
从零掌握贪心算法Java版:LeetCode 10题实战解析(上)
在算法世界里,有一种思想如同生活中的"见好就收"——每次做出当前看来最优的选择,寄希望于通过局部最优达成全局最优。这种思想就是贪心算法,它以其简洁高效的特点,成为解决最优问题的利器。今天我们就来系统学习贪心算法的核心思想,并通过10道LeetCode经典题目实战演练,带你掌握这种"步步为营"的解题思维。
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
316 0
|
JSON 算法 Java
Nettyの网络聊天室&扩展序列化算法
通过本文的介绍,我们详细讲解了如何使用Netty构建一个简单的网络聊天室,并扩展序列化算法以提高数据传输效率。Netty的高性能和灵活性使其成为实现各种网络应用的理想选择。希望本文能帮助您更好地理解和使用Netty进行网络编程。
370 12
|
算法
测试工程师的技能升级:LeetCode算法挑战与职业成长
这篇文章通过作者亲身体验LeetCode算法题的过程,探讨了测试工程师学习算法的重要性,并强调了算法技能对于测试职业成长的必要性。
568 1
测试工程师的技能升级:LeetCode算法挑战与职业成长
|
存储 算法 Java
leetcode算法题-有效的括号(简单)
【11月更文挑战第5天】本文介绍了 LeetCode 上“有效的括号”这道题的解法。题目要求判断一个只包含括号字符的字符串是否有效。有效字符串需满足左括号必须用相同类型的右括号闭合,并且左括号必须以正确的顺序闭合。解题思路是使用栈数据结构,遍历字符串时将左括号压入栈中,遇到右括号时检查栈顶元素是否匹配。最后根据栈是否为空来判断字符串中的括号是否有效。示例代码包括 Python 和 Java 版本。
564 4
|
算法
每日一道算法题(Leetcode 20)
每日一道算法题(Leetcode 20)
448 2
|
XML 存储 JSON
【IO面试题 六】、 除了Java自带的序列化之外,你还了解哪些序列化工具?
除了Java自带的序列化,常见的序列化工具还包括JSON(如jackson、gson、fastjson)、Protobuf、Thrift和Avro,各具特点,适用于不同的应用场景和性能需求。
|
JSON Java 数据格式
【IO面试题 七】、 如果不用JSON工具,该如何实现对实体类的序列化?
除了JSON工具,实现实体类序列化可以采用Java原生序列化机制或第三方库如Protobuf、Thrift、Avro等。
|
存储 算法 Java
LeetCode经典算法题:打家劫舍java详解
LeetCode经典算法题:打家劫舍java详解
391 2

热门文章

最新文章