算法

每日leetcode-297

序列化是将一个数据结构或者对象转换为连续的比特位的操作，进而可以将转换后的数据存储在一个文件或者内存中，同时也可以通过网络传输到另一个计算机环境，采取相反方式重构得到原数据。

请设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

示例: 

你可以将以下二叉树：

1

/
2 3
/
4 5

序列化为 “[1,2,3,null,null,4,5]”
提示: 这与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。

说明: 不要使用类的成员 / 全局 / 静态变量来存储状态，你的序列化和反序列化算法应该是无状态的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

尝试

这道题最先想到的是直接把每一层每一个位置都编码，做成一个堆，这样就可以直接用下标/2得到父亲节点的位置：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        map<int, TreeNode*> nodes;
        nodes[0] = root;
        int len = 1;
        bool now_have_nodes = !!root;
        string ans;
        while (now_have_nodes) {
            for (int i = 0; i < len; i++) {
                if (nodes[i]) {
                    stringstream ss;
                    ss << nodes[i]->val;
                    string temp;
                    ss >> temp;
                    ans += temp + ";";
                }
                else {
                    ans += ";";
                }
            }
            now_have_nodes = false;
            for (int i = len - 1; i >= 0; i--) {
                if (nodes[i]) {
                    if (nodes[i]->left || nodes[i]->right) {
                        now_have_nodes = true;
                    }
                    nodes[2 * i + 1] = nodes[i]->right;
                    nodes[2 * i] = nodes[i]->left;
                }
                else {
                    nodes[2 * i] = NULL;
                    nodes[2 * i + 1] = NULL;
                }
            }
            len *= 2;
        }
        return ans;
    }

    int readNumber(const string & data, const int len, int & now_char_index, bool & now_have_number) {
        now_have_number = false;
        int now_data = 0;
        bool negative = false;
        if (data[now_char_index] == '-') {
            negative = true;
            now_char_index ++;
        }
        while (now_char_index < len) {
            if (data[now_char_index] >= '0' && data[now_char_index] <= '9') {
                now_data = now_data * 10 + data[now_char_index] - '0';
                now_have_number = true;
                now_char_index++;
            }
            else if (data[now_char_index] == ';') {
                now_char_index++;
                break;
            }
            else {
                now_char_index++;
            }
        }
        return negative ? -now_data : now_data;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int len = data.size();
        int now_char_index = 0;  // 当前的字符串字符的下标
        int now_level_size = 1;  // 当前这一层的节点一共有多少个
        int now_data = 0;  // 当前的读取的数字
        bool now_have_number = false;
        if (len == 0) {
            return NULL;
        }
        map<int, TreeNode*> nodes;
        map<int, TreeNode*> nodes2;
        now_data = readNumber(data, len, now_char_index, now_have_number);
        if (!now_have_number) {
            return NULL;
        }
        TreeNode* ans = new TreeNode(now_data);
        nodes[0] = ans;
        // 读入下面一层的
        while (now_char_index < len) {
            now_level_size *= 2;
            int now_node_index = 0;
            while (now_node_index < now_level_size) {
                now_data = readNumber(data, len, now_char_index, now_have_number);
                if (now_have_number) {
                    nodes2[now_node_index] = new TreeNode(now_data);
                }
                else {
                    nodes2[now_node_index] = NULL;
                }
                if (nodes[now_node_index / 2]) {
                    if (now_node_index % 2 == 0) {
                        nodes[now_node_index / 2]->left = nodes2[now_node_index];
                    }
                    else {
                        nodes[now_node_index / 2]->right = nodes2[now_node_index];
                    }
                }
                now_node_index++;
            }
            nodes = nodes2;
        }
        return ans;
    }
};

但是这样会超时，因为这样做的话比如

1

/
3
/
4 5

就会被写成”1;;3;;;4;5;”，但是第三层前两个空的节点是没有必要存下来的。

解决

所以修改存储的方式：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        vector<TreeNode*> nodes;
        nodes.push_back(root);
        int len;
        bool now_have_nodes = !!root;
        string ans;
        while (now_have_nodes) {
            len = nodes.size();
            for (int i = 0; i < len; i++) {
                if (nodes[i]) {
                    stringstream ss;
                    ss << nodes[i]->val;
                    string temp;
                    ss >> temp;
                    ans += temp + ";";
                }
                else {
                    ans += ";";
                }
            }
            now_have_nodes = false;
            vector<TreeNode*> nodes2;
            for (int i = 0; i < len; i++) {
                if (nodes[i]) {
                    if (nodes[i]->left || nodes[i]->right) {
                        now_have_nodes = true;
                    }
                    nodes2.push_back(nodes[i]->left);
                    nodes2.push_back(nodes[i]->right);
                }
            }
            nodes = nodes2;
        }
        return ans;
    }

    int readNumber(const string & data, const int len, int & now_char_index, bool & now_have_number) {
        now_have_number = false;
        int now_data = 0;
        bool negative = false;
        if (data[now_char_index] == '-') {
            negative = true;
            now_char_index ++;
        }
        while (now_char_index < len) {
            if (data[now_char_index] >= '0' && data[now_char_index] <= '9') {
                now_data = now_data * 10 + data[now_char_index] - '0';
                now_have_number = true;
                now_char_index++;
            }
            else if (data[now_char_index] == ';') {
                now_char_index++;
                break;
            }
            else {
                now_char_index++;
            }
        }
        return negative ? -now_data : now_data;
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        int len = data.size();
        int now_char_index = 0;  // 当前的字符串字符的下标
        int now_data = 0;  // 当前的读取的数字
        bool now_have_number = false;
        if (len == 0) {
            return NULL;
        }
        vector<TreeNode*> nodes;
        now_data = readNumber(data, len, now_char_index, now_have_number);
        if (!now_have_number) {
            return NULL;
        }
        TreeNode* ans = new TreeNode(now_data);
        nodes.push_back(ans);
        int len_n = 1;
        // 读入下面一层的
        while (now_char_index < len) {
            vector<TreeNode*> nodes2;
            int parent_index = 0;
            while (parent_index < len_n) {
                if (!nodes[parent_index]) {
                    parent_index ++;
                }
                else {
                    break;
                }
            }
            for (int i = 0; parent_index < len_n; i++) {
                while (parent_index < len_n) {
                    if (!nodes[parent_index]) {
                        parent_index ++;
                    }
                    else {
                        break;
                    }
                }
                if (parent_index >= len_n) {
                    break;
                }
                now_data = readNumber(data, len, now_char_index, now_have_number);
                TreeNode* now_node = NULL;
                if (now_have_number) {
                    now_node = new TreeNode(now_data);
                }
                nodes2.push_back(now_node);
                if (i % 2 == 0) {
                    nodes[parent_index]->left = now_node;
                }
                else {
                    nodes[parent_index]->right = now_node;
                    parent_index += 1;
                }
            }
            nodes = nodes2;
            len_n = nodes.size();
            if (len_n == 0) {
                break;
            }
        }
        return ans;
    }
};

这样可以通过，但是时间不是最优。

最优

看到的一个20ms的提交代码，使用queue，避免了我刚才用vector的复制操作；用换行作为分隔符，直接就可以用getline读取：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
class Codec {
public:

    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        queue<TreeNode *> q;
        q.push(root);
        ostringstream oss;
        while(!q.empty()) {
            TreeNode *cur = q.front();
            q.pop();
            if(cur == nullptr) {
                oss << "null" << endl;
            } else {
                oss << cur->val << endl;
                q.push(cur->left);
                q.push(cur->right);
            }
        }
        // cout << oss.str();
        return oss.str();
    }

    TreeNode *decodeNode(const string &data) {
        if(data == "null")
            return nullptr;
        else
            return new TreeNode(stoi(data.c_str()));
    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        string buffer;
        istringstream iss(data);
        TreeNode *root;
        getline(iss, buffer);
        root = decodeNode(buffer);
        if(root == nullptr)
            return root;
        queue<TreeNode *> q;
        q.push(root);
        while(!q.empty()) {
            TreeNode *cur = q.front();
            q.pop();
            getline(iss, buffer);
            cur->left = decodeNode(buffer);
            getline(iss, buffer);
            cur->right = decodeNode(buffer);
            if(cur->left) q.push(cur->left);
            if(cur->right) q.push(cur->right);
        }
        return root;
    }
};
领域—人工智能神经网络

信息熵

一句话里面包含的信息有大有小，提供的信息就可以用信息熵来衡量。

比如抛硬币，结果提供的信息就比摇骰子得到的结果的信息量要少。

比如一个数字可能是1～4，最少要用两个判断来说明到底是几。所以就是2bit

https://zhuanlan.zhihu.com/p/89958871

https://blog.csdn.net/weixin_38381682/article/details/79843060

https://blog.csdn.net/saltriver/article/details/53056816

算法

每日leetcode-488

回忆一下祖玛游戏。现在桌上有一串球，颜色有红色(R)，黄色(Y)，蓝色(B)，绿色(G)，还有白色(W)。 现在你手里也有几个球。

每一次，你可以从手里的球选一个，然后把这个球插入到一串球中的某个位置上（包括最左端，最右端）。接着，如果有出现三个或者三个以上颜色相同的球相连的话，就把它们移除掉。重复这一步骤直到桌上所有的球都被移除。

找到插入并可以移除掉桌上所有球所需的最少的球数。如果不能移除桌上所有的球，输出 -1 。

示例:
输入: “WRRBBW”, “RB”
输出: -1
解释: WRRBBW -> WRR[R]BBW -> WBBW -> WBB[B]W -> WW （翻译者标注：手上球已经用完，桌上还剩两个球无法消除，返回-1）

输入: “WWRRBBWW”, “WRBRW”
输出: 2
解释: WWRRBBWW -> WWRR[R]BBWW -> WWBBWW -> WWBB[B]WW -> WWWW -> empty

输入:”G”, “GGGGG”
输出: 2
解释: G -> G[G] -> GG[G] -> empty

输入: “RBYYBBRRB”, “YRBGB”
输出: 3
解释: RBYYBBRRB -> RBYY[Y]BBRRB -> RBBBRRB -> RRRB -> B -> B[B] -> BB[B] -> empty
标注:

你可以假设桌上一开始的球中，不会有三个及三个以上颜色相同且连着的球。
桌上的球不会超过20个，输入的数据中代表这些球的字符串的名字是 “board” 。
你手中的球不会超过5个，输入的数据中代表这些球的字符串的名字是 “hand”。
输入的两个字符串均为非空字符串，且只包含字符 ‘R’,’Y’,’B’,’G’,’W’。

解决

简单的深搜：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
class Solution
{
public:
    string simplify(const string &s1, const string &s2)
    {
        int len1 = s1.size();
        int len2 = s2.size();
        if (len1 == 0) {
            return s2;
        }
        if (len2 == 0) {
            return s1;
        }
        if (s1[len1 - 1] == s2[0]) {
            if (len1 > 1 && s1[len1 - 2] == s1[len1 - 1] && len2 > 1 && s2[0] == s2[1]) {
                return simplify(s1.substr(0, len1 - 2), s2.substr(2, len2 - 2));
            }
            if (len1 > 1 && s1[len1 - 2] == s1[len1 - 1]) {
                return simplify(s1.substr(0, len1 - 2), s2.substr(1, len2 - 1));
            }
            if (len2 > 1 && s2[0] == s2[1]) {
                return simplify(s1.substr(0, len1 - 1), s2.substr(2, len2 - 2));
            }
        }
        return s1 + s2;
    }

    int myMin(int a, int b) {
        unsigned int ua = a, ub = b;
        return int(ua < ub ? ua : ub);
    }

    int findMinStep(string board, string hand)
    {
        int len = board.size();
        if (len == 0) {
            return 0;
        }
        int handlen = hand.size();
        if (handlen == 9) {
            return -1;
        }
        set<char> ans;
        int min_ans = -1;
        for (int i = 0; i < handlen; i++)
        {
            char c = hand[i];
            if (ans.count(c) == 0)
            {
                // check
                ans.insert(c);
                for (int index = 0; index < len; index++)
                {
                    if (board[index] == c)
                    {
                        string temp_ans = simplify(board.substr(0, index + 1), board.substr(index, len - index));
                        string temp_hand = hand.substr(0, i) + hand.substr(i + 1, handlen - i - 1);
                        int now_min = findMinStep(temp_ans, temp_hand) + 1;
                        if (now_min > 0) {
                            min_ans = myMin(now_min, min_ans);
                        }
                        // avoid extra checks
                        if (index < len - 1 && board[index] == board[index + 1])
                        {
                            index++;
                        }
                    }
                }
            }
        }
        // cout << min_ans << ": " << board << "   " << hand << endl;
        return min_ans;
    }
};