LeetCode第144场周赛题解

矫情吗；* 2021-12-11 10:43 326阅读 0赞

竞赛链接：[https://leetcode-cn.com/contest/weekly-contest-144/][https_leetcode-cn.com_contest_weekly-contest-144]

**1.IP地址无效化**

给你一个有效的 [IPv4][] 地址 `address`，返回这个 IP 地址的无效化版本。

所谓无效化 IP 地址，其实就是用 `"[.]"` 代替了每个 `"."`。

**示例 1：**

输入：address = "1.1.1.1"
    输出："1[.]1[.]1[.]1"

**示例 2：**

输入：address = "255.100.50.0"
    输出："255[.]100[.]50[.]0"

**提示：**

*  给出的 `address` 是一个有效的 IPv4 地址

**思路：**

**遍历字符串，遇到字符是'.'的元素就先将'\['加入数组，再将'.'加入数组，最后将'\]'加入数组；遇到其他字符正常加入数组即可。**

**上AC代码：**

char * defangIPaddr(char * address){
        int len1=strlen(address);
        int len2=len1+7;
        char *ret=(char *)malloc(len2*sizeof(char));
        int cnt=0;
        int i;
        for(i=0;i<len1;i++)
        {
            if(address[i]=='.')
            {
                ret[cnt++]='[';
                ret[cnt++]=address[i];
                ret[cnt++]=']';
            }
            else
            {
                ret[cnt++]=address[i];
            }
        }
        ret[cnt]='\0';
        return ret;
    }

**2.航班预定统计**

这里有 `n` 个航班，它们分别从 `1` 到 `n` 进行编号。

我们这儿有一份航班预订表，表中第 `i` 条预订记录 `bookings[i] = [i, j, k]` 意味着我们在从 `i` 到 `j` 的每个航班上预订了 `k` 个座位。

请你返回一个长度为 `n` 的数组 `answer`，按航班编号顺序返回每个航班上预订的座位数。

**示例：**

输入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
    输出：[10,55,45,25,25]

**提示：**

*  `1 <= bookings.length <= 20000`
 *  `1 <= bookings[i][0] <= bookings[i][1] <= n <= 20000`
 *  `1 <= bookings[i][2] <= 10000`

**思路：**

**区间操作。开一个大小为n+1的dp数组，将dp数组的所有元素初始化为0。遍历bookings数组，dp数组上i对应的位置（dp\[i-1\]）加上k，j对应的下一个位置（dp\[j\]）减去k，最后遍历一遍dp数组，用初始化为0的整型变量now累加，每次遍历都将累加后的now加入返回值数组。这一块可能比较难理解，但是算法很简单，代码也比较少，试着手写感受一下就能理解了。**

**上AC代码：**

class Solution {
    public:
        vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
            vector<int> dp(n+1);
            vector<int> ret;
            int len=bookings.size();
            int i;
            for(i=0;i<len;i++)
            {
                int first=bookings[i][0];
                int last=bookings[i][1];
                int num=bookings[i][2];
                dp[first-1]+=num;
                dp[last]-=num;
            }
            int now=0;
            for(i=0;i<n;i++)
            {
                now+=dp[i];
                ret.push_back(now);
            }
            return ret;
        }
    };

**3.删点成林**

给出二叉树的根节点 `root`，树上每个节点都有一个不同的值。

如果节点值在 `to_delete` 中出现，我们就把该节点从树上删去，最后得到一个森林（一些不相交的树构成的集合）。

返回森林中的每棵树。你可以按任意顺序组织答案。

**提示：**

*  树中的节点数最大为 `1000`。
 *  每个节点都有一个介于 `1` 到 `1000` 之间的值，且各不相同。
 *  `to_delete.length <= 1000`
 *  `to_delete` 包含一些从 `1` 到 `1000`、各不相同的值。

**思路：**

**使用队列实现层次遍历二叉树，标记需要删除的值，需要注意的是，删除时置为NULL即可，不要delete，因为后期的遍历还需要依赖被删除的节点（该结点不是叶子节点），否则会执行出错。先将当前节点的左孩子和右孩子加入队列（保证后面的正常遍历），如果当前遍历到的结点需要被删除，而其孩子不需要被删除，则将其孩子加入返回数组ret；如果当前遍历到的结点不需要被删除，而其孩子需要被删除，则如果左孩子需要被删除就将now->left置为NULL，如果右孩子需要被删除就将now->right置为NULL。根节点需要特判，如果根节点不需要被删除，则先将根节点加入返回值数组ret；如果根节点需要被删除，无需做任何操作直接进行层次遍历即可。**

**上AC代码：**

/**
     * Definition for a binary tree node.
     * struct TreeNode {
     *     int val;
     *     TreeNode *left;
     *     TreeNode *right;
     *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
     * };
     */
    class Solution {
    public:
        bool dp[1001];
        vector<TreeNode*> ret;
        vector<TreeNode*> delNodes(TreeNode* root, vector<int>& to_delete) {
            if(root==NULL)
                return ret;
            int len=to_delete.size();
            int i;
            memset(dp,0,sizeof(dp));
            for(i=0;i<len;i++)
            {
                dp[to_delete[i]]=true;
            }
            //层次遍历
            queue<TreeNode*> que;
            que.push(root);
            if(dp[root->val]==false)
            {
                ret.push_back(root);
            }
            while(!que.empty())
            {
                TreeNode *now=que.front();
                que.pop();
                if(now==NULL)
                    continue;
                TreeNode *left=now->left;
                TreeNode *right=now->right;
                que.push(left);
                que.push(right);
                if(left!=NULL)
                {
                    if(dp[now->val]==true&&dp[left->val]==false)
                    {
                        ret.push_back(left);
                    }
                    if(dp[left->val]==true)
                    {
                        now->left=NULL;
                    }
                }
                if(right!=NULL)
                {
                    if(dp[now->val]==true&&dp[right->val]==false)
                    {
                        ret.push_back(right);
                    }
                    if(dp[right->val]==true)
                    {
                        now->right=NULL;
                    }
                }
            }
            return ret;
        }
    };

**4.有效括号的嵌套深度**

**有效括号字符串** 仅由 `"("` 和 `")"` 构成，并符合下述几个条件之一：

*  空字符串
 *  连接，可以记作 `AB`（`A` 与 `B` 连接），其中 `A` 和 `B` 都是有效括号字符串
 *  嵌套，可以记作 `(A)`，其中 `A` 是有效括号字符串

类似地，我们可以定义任意有效括号字符串 `s` 的 **嵌套深度** `depth(S)`：

*  `s` 为空时，`depth("") = 0`
 *  `s` 为 `A` 与 `B` 连接时，`depth(A + B) = max(depth(A), depth(B))`，其中 `A` 和 `B` 都是有效括号字符串
 *  `s` 为嵌套情况，`depth("(" + A + ")") = 1 + depth(A)`，其中 A 是有效括号字符串

例如：`""`，`"()()"`，和 `"()(()())"` 都是有效括号字符串，嵌套深度分别为 0，1，2，而 `")("` 和 `"(()"` 都不是有效括号字符串。

给你一个有效括号字符串 `seq`，将其分成两个不相交的子序列 `A` 和 `B`，且 `A` 和 `B` 满足有效括号字符串的定义（注意：`A.length + B.length = seq.length`）。

现在，你需要从中选出 **任意** 一组有效括号字符串 `A` 和 `B`，使 `max(depth(A), depth(B))` 的可能取值最小。

返回长度为 `seq.length` 答案数组 `answer` ，选择 `A` 还是 `B` 的编码规则是：如果 `seq[i]` 是 `A` 的一部分，那么 `answer[i] = 0`。否则，`answer[i] = 1`。即便有多个满足要求的答案存在，你也只需返回 **一个**。

**示例 1：**

输入：seq = "(()())"
    输出：[0,1,1,1,1,0]

**示例 2：**

输入：seq = "()(())()"
    输出：[0,0,0,1,1,0,1,1]

**提示：**

*  `1 <= text.size <= 10000`

**思路：**

**贪心策略。最有利的A或B的括号形状是()()()这样的，因此如果出现(())则可以这样分配(())，这样拆分出来就是()()。与其他括号问题一样，还是使用栈这种数据结构，遇到左括号就入栈，遇到右括号就出栈。如果遇到左括号的时候栈是空的，说明前面的括号都是匹配的，该拆分的也都拆分好了，此时将0入栈将1入栈都无所谓，即当前左括号属于A或者属于B都可以；如果遇到左括号的时候栈不空，就让栈顶元素取反后入栈，原因是栈顶元素是外层左括号的归属，内外层归属于不同的两方才更有利于让括号的嵌套深度最小。如果遇到右括号，栈内必有元素，直接出栈加入返回值数组，因为这样可以保证一个完整的括号()左括号和右括号属于同一方（同为0或者同为1）。**

**上AC代码：**

class Solution {
    public:
        vector<int> maxDepthAfterSplit(string seq) {
            stack<int> st;
            vector<int> ret;
            int len=seq.size();
            int i;
            for(i=0;i<len;i++)
            {
                if(seq[i]=='(')
                {
                    
                    if(!st.empty())
                    {
                        ret.push_back(!st.top());
                        st.push(!st.top());
                    }
                    else
                    {
                        st.push(0);
                        ret.push_back(0);
                    }
                }
                else
                {
                    ret.push_back(st.top());
                    st.pop();
                }
            }
            return ret;
        }
    };

**欢迎大家关注/订阅我的微信公众号Code Art Online，我会在我的公众号分享个人见闻，发现生活趣味；这里不仅有0和1，还有是诗和远方↓↓↓**

![20200227123106884.jpg][]

[https_leetcode-cn.com_contest_weekly-contest-144]: https://leetcode-cn.com/contest/weekly-contest-144/
[IPv4]: https://baike.baidu.com/item/IPv4
[20200227123106884.jpg]: /images/20211211/41aafd8735ab4db8b4ed2455cfb51d86.png