1. 题目列表

• IP 地址无效化(一行代码）
• 航班预订统计（问题转换，给定区间数据，求每个点的值，公交车站问题）重要
• 有效括号的嵌套深度（括号深度问题）重要

IP 地址无效化

一行代码。

代码：

class Solution {
    public String defangIPaddr(String address) {
        return address.replace(".", "[.]");
    }
}

3. 航班预订统计

 /*
    题意：
        给出多个区间的加数，求每一个位置的和。可转换为公交车站上下车问题。
    
    思路：
        定义change[i]数组表示到达第i个公交站台上人数的变化
            change[i] > 0，表示在i站台上车change[i]人，
            change[i] < 0，表示在i站台下车change[i]人。
        遍历bookings数组，记录每个存在上下站的公交站台的人数变化情况，则[i, j, k]表示在第i站上车k人，在第j + 1站台下车k人
    然后，每个站台的总人数：
        cnt[i] = cnt[i - 1] + change[i]，i = 1, 2, ..., n - 1，
        cnt[0] = change[0]
        
    收获：
        该题是典型的给出区间数据，求每个点的当前值问题，对于此类问题可类比于公交站上下车问题，
    将公交车站看成是一个大容器，每个点的值即容器当前值，区间数据相当于区间两侧的上下车情况，接着累加求和即可。
*/

代码：

class Solution {
public:
    vector<int> corpFlightBookings(vector<vector<int>>& bookings, int n) {
        int change[20010];
        memset(change, 0, sizeof(change));
        for (vector<int> booking: bookings){
            change[booking[0]] += booking[2];
            change[booking[1] + 1] -= booking[2];
        }
        vector<int> res(n);
        res[0] = change[1];
        for (int i = 1; i < n; i++)
            res[i] = res[i - 1] + change[i + 1]; // 注意下标是从0开始
        return res;
    }
};

4. 有效括号的嵌套深度

    题意:
        给定一个括号字符串S，求一个容量为2的字符串S的划分串，并使得在该划分下max(depth(A), depth(B))达到最小。
    即找出一个划分串，使得两个划分串的深度尽量接近.
    
    思路：
        先求出整个串的深度d, d/2就是其中一个串A的深度， d - d/2是另外一个串B的深度。
    遍历整个S，如果左括号数大于d/2，则分给另一个串B，否则分给串A，如果遇到右括号，那么当前的左括号数-1

代码：

class Solution {
public:
    vector<int> maxDepthAfterSplit(string seq) {
        int d = 0, cnt = 0;
        for (int i = 0; i < seq.length(); i++){
            if (seq[i] == '('){
                cnt ++;
                d = max(d, cnt);
            }else{
                cnt --;
            }
        }
        vector<int> res(seq.length());
        int depthA = d / 2;
        cnt = 0;
        for (int i = 0; i < seq.length(); i++){
            if (seq[i] == '('){
                if (++cnt > depthA){
                    res[i] = 1;
                }
            }else{
                if (cnt > depthA)
                    res[i] = 1;
                cnt --;
            }
        }
        return res;
    }
};