TikTok真题第10天 | 1541.平衡括号字符串的最少插入次数、1209.删除字符串中所有相邻重复项、1530.好叶子结点对的数量

发布时间:2023年12月31日

1541.平衡括号字符串的最少插入次数

题目链接:1541.minimum-insertions-to-balance-a-parentheses-string

解法:

官方题解这次写得非常好。参考题解:左右括号匹配

这道题一眼看过去,就是用栈解决。不过可以使用计数代替栈,也就是记录左括号的数量(相当于栈中弹入左括号)。

如果当前为右括号,而左括号的数量为空,那么需要插入一个左括号(result++);如果当前为右括号,且左括号不为空,那么首先左括号数量减1(相当于栈中弹出左括号),表示消消乐,然后如果下一个还是右括号,就继续往下走 (idx+=2),如果下一个不是右括号,那么需要插入右括号 (result++)。

遍历结束后,如果左括号的数量大于1,说明还需要插入右括号来匹配。插入的数量为 leftCount * 2 (result += leftCount * 2)。

下面给出了计数法和栈两种写法,可以对比一下,思路完全一致。

边界条件:无

时间复杂度:O(n)

空间复杂度:O(1)

class Solution {
public:
    int minInsertions(string s) {
        int inserts = 0, leftCount = 0, length = s.size();
        int idx = 0;
        while (idx < length) {
            char c = s[idx];
            if (c=='(') {
                leftCount++;
                idx++;
            } else {
                // 如果当前为右括号,那么必须先消除左括号
                if (leftCount>0) {
                    leftCount--;
                } else {
                    // 没有左括号则添加左括号
                    inserts++;
                }
                // 如果当前为右括号,那么下一个必须也是右括号
                if (idx < length-1 && s[idx+1]==')') {
                    idx+=2;
                } else {
                    inserts++;
                    idx++;
                }
            }
        }
        inserts += 2 * leftCount;
        return inserts;
    }
};
// 栈
class Solution {
public:
    int minInsertions(string s) {
        int inserts = 0, length = s.size();
        stack<char> leftStack;
        int idx = 0;
        while (idx < length) {
            char c = s[idx];
            if (c=='(') {
                leftStack.push(c);
                idx++;
            } else {
                if (!leftStack.empty()) {
                    leftStack.pop();
                } else {
                    inserts++;
                }
                if (idx+1 < length && s[idx+1]==')') {
                    idx+=2;
                } else {
                    inserts++;
                    idx++;
                }
            }
        }
        inserts += 2 * leftStack.size();
        return inserts;
    }
};

1209.删除字符串中所有相邻重复项

题目链接:1209.remove-all-adjacent-duplicates-in-string-ii

解法:

使用栈来处理。

将元素依次入栈并统计元素数量,所以栈中同时放入元素和数量的pair对。每次入栈判断是否和栈顶元素相同:

(1)如果栈为空,或者元素与栈顶元素不同,则入栈并将元素个数记为1

(2)如果与栈顶元素相同,且加入当前元素后仍然没有满k,那么栈顶元素加1

(3)如果与栈顶元素相同,且加入当前元素后满k了,那么将栈顶元素出栈。

(4)遍历完字符串之后,将栈中剩余元素拼接即为答案。

由于栈中的元素是后进先出,那么最后拼接答案时,取出来的元素的顺序和原字符串的顺序是反的,比如abcd,在stack中是[a,b,c,d],那么stack.top() 取出来是[d, c, b, a],所以取出元素进行拼接后,需要翻转一下结果。如果不想翻转,那么可以用vector来替代stack,效率还更高。

参考题解:

边界条件:无

时间复杂度:O(n)

空间复杂度:O(n)

class Solution {
public:
    string removeDuplicates(string s, int k) {
        stack<pair<char, int>> charStack;
        for (char c: s) {
            if (charStack.empty() || charStack.top().first!=c) {
                charStack.push({c, 1});
            } else if (charStack.top().second+1<k) {
                charStack.top().second++;
            } else {
                charStack.pop();
            }
        }
        string res;
        while (!charStack.empty()) {
            pair<char, int> p = charStack.top();
            // 注意这个语法,第一个参数是个数
            res.append(p.second, p.first);
            charStack.pop();
        }
        // 注意要翻转结果
        reverse(res.begin(), res.end());
        return res;
    }
};
// 用vector替代stack
class Solution {
public:
    string removeDuplicates(string s, int k) {
        vector<pair<char, int>> charStack;
        for (char c: s) {
            if (charStack.empty() || charStack.back().first!=c) {
                charStack.push_back({c, 1});
            } else if (charStack.back().second+1<k) {
                charStack.back().second++;
            } else {
                charStack.pop_back();
            }
        }
        string res;
        for(const auto& p: charStack) {
            // 注意这个语法,第一个参数是个数
            res.append(p.second, p.first);
        }
        return res;
    }
};

1530.好叶子结点对的数量

题目链接:1530.https://leetcode.com/problems/number-of-good-leaf-nodes-pairs/

解法:

这个题解比较清晰:递归

遍历这棵树,对于每一个遍历到的节点node,计算node左右子树中叶子节点到node的距离,把这个距离记录为两个向量。

而这个距离又可以分解为node的左孩子到左子树中叶子结点的距离加1,右孩子到右子树中叶子节点的距离加1。

左右子树中的叶子节点对进行组合,也就是两个向量中的元素两两相加,如果它们的距离之和小于等于distance,则结果加1。

对于当前节点的上层节点,左右子树其实是位于上层节点的左子树或者右子树,所以需要合并当前节点node的所有叶子节点距离,传递给上层节点。

边界条件:root为1个元素

时间复杂度:O(N* distnce^2),每个节点都需要遍历,每个节点都有个双重for循环判断左右叶子结点的距离之和是否小于等于distance,

空间复杂度:O(H),H为树的高度。

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int countPairs(TreeNode* root, int distance) {
        int res = 0;
        dfs(root, distance, res);
        return res;
    }

    // 注意 res 的类型为 int&,而不是int,因为是可变的
    vector<int> dfs(TreeNode* root, int distance,int& res) {
        // 返回值为当前节点到叶子节点的距离
        if (root == nullptr) return {};
        if (root->left == nullptr && root->right == nullptr) return {0};
        vector<int> left = dfs(root->left, distance, res);
        vector<int> right = dfs(root->right, distance, res);
        // 当前节点到左子树叶子结点的距离,为左孩子到左子树叶子节点的距离加1
        for (int i=0; i<left.size(); i++) {
            left[i]++;
        }
        for (int i=0; i<right.size(); i++) {
            right[i]++;
        }
        for (int l: left) {
            for (int r: right) {
                if (l+r <= distance) res++;
            }
        }
        // 合并为一个vector,作为当前节点的父节点的左叶子节点或者右叶子节点的距离集合
        // 由于c++中创建新合并的向量比较麻烦,所以直接把right合并到left中
        left.insert(left.end(), right.begin(), right.end());
        // 向上传递给父节点
        return left;
    }
};
文章来源:https://blog.csdn.net/Jack199274/article/details/135313155
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。