2019-10-31 223 views 评论

leetcode题目解析（191031）

标签：leetcode

Leetcode 301：删除无效的括号

题目描述

删除最小数量的无效括号，使得输入的字符串有效，返回所有可能的结果。
说明: 输入可能包含了除 ( 和 ) 以外的字符。

示例

示例1：
输入: "()())()"
输出: ["()()()", "(())()"]

示例2：
输入: "(a)())()"
输出: ["(a)()()", "(a())()"]

示例3：

输入: ")("
输出: [""]

代码实现

class Solution {
public:
void DFS(string s, char ch, int last) {
        for (int i = 0,cnt = 0; i &lt; s.size();i++)
        {
            if (s[i] == '(' || s[i] == ')')
                s[i] == ch ? cnt++ : cnt--;
            if (cnt &lt;= 0)
                continue;
            for (int j = last; j &lt;= i; j++)
            {
                if (s[j] == ch &amp;&amp; (j == last || s[j - 1] != ch))
                    DFS(s.substr(0, j) + s.substr(j + 1), ch, j);
            }
            return;
        }
        reverse(s.begin(), s.end());
        if (ch == ')')
            return DFS(s, '(', 0);
        ans.push_back(s);
    }
    vector&lt;string&gt; removeInvalidParentheses(string s)
    {
        DFS(s, ')', 0);
        return ans;
    }

private:
    vector&lt;string&gt; ans;
};

class Solution {

public:

void DFS(string s, char ch, int last) {

for (int i = 0,cnt = 0; i < s.size();i++)

{

if (s[i] == '(' || s[i] == ')')

s[i] == ch ? cnt++ : cnt--;

if (cnt <= 0)

continue;

for (int j = last; j <= i; j++)

{

if (s[j] == ch && (j == last || s[j - 1] != ch))

DFS(s.substr(0, j) + s.substr(j + 1), ch, j);

}

return;

}

reverse(s.begin(), s.end());

if (ch == ')')

return DFS(s, '(', 0);

ans.push_back(s);

}

vector<string> removeInvalidParentheses(string s)

{

DFS(s, ')', 0);

return ans;

}

private:

vector<string> ans;

};

代码参考自：
https://blog.csdn.net/qq508618087/article/details/50408894

代码性能

复杂度配图

Leetcode 297：二叉树的序列化与反序列化

题目描述

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

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

示例

你可以将以下二叉树：

1

/ \
2 3
/ \
4 5

序列化为 "[1,2,3,null,null,4,5]"

解题思路

代码实现

class Codec {
public:
    // Encodes a tree to a single string.
    string serialize(TreeNode* root) {
        ostringstream result;
        serialized(root, result);
        return result.str();

    }

    // Decodes your encoded data to tree.
    TreeNode* deserialize(string data) {
        istringstream ideserialized(data);
        return deserialized(ideserialized);

    }
private:
    void serialized(TreeNode* root, ostringstream&amp; out)
    {
        if (root) {
            out &lt;&lt; root-&gt;val &lt;&lt; ' ';
            serialized(root-&gt;left, out);
            serialized(root-&gt;right, out);
        }
        else {
            out &lt;&lt; "# ";
        }
    }


    TreeNode* deserialized(istringstream&amp; in)
    {
        string val;
        in &gt;&gt; val;
        if (val == "#")
            return nullptr;
        TreeNode* root = new TreeNode(stoi(val));
        root-&gt;left = deserialized(in);
        root-&gt;right = deserialized(in);
        return root;
    }
};