Leetcode 1101-1200

1106. Parsing A Boolean Expression (Hard)

给出如下规则的布尔表达式，解析出值

• t代表true，f代表false
• &(e1,e2,e3,...,en)表示e1到en这些表达式与起来的值
• |(e1,e2,e3,...,en)表示e1到en或起来的值
• !(e)表示e表达式的值取非的结果
• 表达式不含空格

栈

对每个运算符维护一个栈，扫描到左括号后对栈中所有元素进行计算，结果加到上一个栈上

32ms(14.79%)

bool parseBoolExpr(string expression) {
    stack<char> ops;
    stack<stack<bool>> vals;
    vals.push(stack<bool>());
    bool first = true;
    for (auto c : expression) {
        if (c == '!' || c == '&' || c == '|') {
            ops.push(c);
            vals.push(stack<bool>());
        } else if (c == 't' || c == 'f') {
            bool r = (c == 't') ? true : false;
            vals.top().push(r);
        } else if (c == ')') {
            bool r;
            if (ops.top() == '!') r = !vals.top().top();
            else {
                r = vals.top().top();
                while (vals.top().size() > 1) {
                    vals.top().pop();
                    if (ops.top() == '|') {
                        r |= vals.top().top();
                        if (r) break;
                    } else if (ops.top() == '&') {
                        r &= vals.top().top();
                        if (!r) break;
                    }
                }
            }
            vals.pop();
            vals.top().push(r);
            ops.pop();
        }
    }
    return vals.top().top();
}

递归

实现evaluate函数，每次解析一个表达式，然后线性扫描即可

8ms(83.66%)

class Solution {
public:
    bool parseBoolExpr(string expression) {
        int ptr = 0;
        return evaluate(expression, ptr);
    }
    bool evaluate(const string& expression, int& ptr) {
        if (expression[ptr] == 'f') return false;
        if (expression[ptr] == 't') return true;
        char op = expression[ptr];
        ptr += 2;
        bool val = evaluate(expression, ptr);
        while (expression[++ptr] != ')') {
            ptr++;
            if (op == '|') val |= evaluate(expression, ptr);
            else if (op == '&') val &= evaluate(expression, ptr);
        }
        if (op == '!') val = !val;
        return val;
    }
};

1125. Smallest Sufficient Team (Hard)

有一个技能列表req_skills，以及一些人people，每个人掌握若干个技能，完成一个项目要求团队里的人要掌握全部技能，求需要的最少人数，给出符合这个人数的任一方案即可

Input: req_skills = ["java","nodejs","reactjs"], people = [["java"],["nodejs"],["nodejs","reactjs"]]
Output: [0,2]

+ 1 <= req_skills.length <= 16 + 1 <= people.length <= 60 + 1 <= people[i].length, req_skills[i].length, people[i][j].length <= 16 + Elements of req_skills and people[i] are (respectively) distinct. + req_skills[i][j], people[i][j][k] are lowercase English letters. + It is guaranteed a sufficient team exists.

动归

首先想到的是用动归来做，题目中技能不多于16个，可以用16个bit位来表示，最多也就是$2^{16}=65536$，可以开一个这么长的数组dp，dp[i]表示i对应的技能最少需要几个人才能凑齐

开始先将每个技能映射为从0开始的整数skills_map，然后将每个人掌握的技能映射成一个int的低16位

再之后对每个人逐个开始动归，用vector<int> combinations记录过程中所有出现过的多人组合起来的技能，然后每个人对之前的这些数做更新

vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
    vector<int> dp(70000, 0);
    unordered_map<string, int> skills_map;
    int rank = 0;
    for (string& s : req_skills) skills_map[s] = rank ++;
    int target = (1 << rank) - 1;
    unordered_map<int, vector<int>> peoples;
    vector<int> combinations;
    unordered_set<int> num_set;
    vector<int> p;
    for (auto& v : people) {
        int skill_num = 0;
        for (auto& s : v) skill_num |= (1 << skills_map[s]);
        p.push_back(skill_num);
    }
    for (int i = 0; i < p.size(); i ++) {
        int num = p[i];
        if (num == target) return {i};
        int size = combinations.size();
        if (!num_set.count(num)) {
            combinations.push_back(num);
            num_set.insert(num);
        }
        peoples[num] = {i};
        dp[num] = 1;
        for (int j = 0; j < size; j ++) {
            int n = combinations[j];
            if (dp[target] > 0 && dp[n] + 1 >= dp[target]) continue;
            if (n == num) continue;
            int r = n | num;
            if (r > target) r = target;
            if (dp[r] == 0 || dp[r] > dp[n] + 1) {
                dp[r] = dp[n] + 1;
                if (!num_set.count(r)) {
                    num_set.insert(r);
                    combinations.push_back(r);
                }
                peoples[r] = peoples[n];
                peoples[r].push_back(i);
            }
        }
    }
    return peoples[target];
}

DFS

以上算法时间64ms，以下思路更快，而且用dfs写起来更方便，等于用调用栈代替自己来维护一些中间信息

dfs相比动归本身是要慢的，但这里可以剪枝去掉一部分计算，以上动归等于是遍历所有人员组合可能，下面是从第一个技能开始，先遍历拿出有第一个技能的人，先后递归，递归后数现在最先缺少的是哪个技能，然后只找有这个技能的人。这样不但减少了计算量，同时也不用进行去重，因为找到的人在之前方案里一定没有出现过，因此时间更快

以下代码时间为12ms (99.79%)

vector<int> smallestSufficientTeam(vector<string>& req_skills, vector<vector<string>>& people) {
    unordered_map<string, int> skill_map;
    for (int i = 0; i < req_skills.size(); i ++) skill_map[req_skills[i]] = i;
    vector<int> p;
    for (auto& v : people) {
        int num = 0;
        for (auto& s : v) num |= (1 << skill_map[s]);
        p.push_back(num);
    }
    vector<int> temp, result;
    dfs(0, (1 << req_skills.size()) - 1, 0, p, temp, result);
    return result;
}
void dfs(int skills, int target, int req_skill, const vector<int>& people, vector<int>& temp, vector<int>& result) {
    if (skills == target) {
        if (result.size() == 0 || result.size() > temp.size()) {
            result = temp;
            return;
        }
    }
    if (result.size() > 0 && temp.size() >= result.size()) return;
    while ((skills >> req_skill) & 1 == 1) req_skill ++;
    for (int i = 0; i < people.size(); i ++) {
        if ((people[i] >> req_skill) & 1 == 1) {
            temp.push_back(i);
            dfs(skills | people[i], target, req_skill, people, temp, result);
            temp.pop_back();
        }
    }
}

---

1147. Longest Chunked Palindrome Decomposition (Hard)

给一个字符串，求能拆解成以下格式的子字符串a_1, a_2,...,a_k的最长长度 + 每个子字符串a_i非空 + a_1+a_2+...+a_k=a + a_1=a_k, a_2=a_k-1, 以此类推

思路

贪心即可，长度逐渐增长，判断前面子串和末尾子串是否相等，如果相等直接拆开即可

这里可以将字符串转成int来判断相等，更快，模1e9+7

int longestDecomposition(string text) {
    int MOD = 1000000007, base = 26;
    int p1 = 0, p2 = text.size() - 1, result = 0;
    long long n1 = 0, n2 = 0, pow = 1;
    while (p1 <= p2) {
        n1 = (n1 * base + (text[p1] - 'a')) % MOD;
        n2 = (n2 + (text[p2] - 'a') * pow) % MOD;
        pow = pow * base % MOD;
        if (n1 == n2) {
            result += (p1 == p2) ? 1 : 2;
            pow = 1;
            n1 = n2 = 0;
        }
        p1++;
        p2--;
    }
    if (n1 + n2 > 0) result++;
    return result;
}

---

1157. Online Majority Element In Subarray (Hard)

给一个数组arr，长度范围为$[1, 20000]$，之后进行若干次查询，查询格式为$(left,right,threshold)$，询问arr[left]到arr[right]内，有没有一个数出现次数大于等于threshold，保证$2*threshold>right-left+1$，即threshold超过数组长度的一半

MajorityChecker majorityChecker = new MajorityChecker([1,1,2,2,1,1]);
majorityChecker.query(0,5,4); // returns 1
majorityChecker.query(0,3,3); // returns -1
majorityChecker.query(2,3,2); // returns 2

思路一

对每个数，将其出现的位置记录在一个vector中，那么查询这个数从left到right出现次数，只需要进行两次二分搜索即可，可以使用lower_bound函数完成

要确定对哪个数进行查询，再记录到每个位置为止当前数出现过的次数，然后从arr[right]开始向左扫，只有出现次数大于等于threshold的数才进行查询

时间比较长，花费1128 ms

class MajorityChecker {
private:
    vector<vector<int>> array;
    unordered_map<int, vector<int>> sets;
public:
    MajorityChecker(vector<int>& arr) {
        unordered_map<int, int> nums;
        for (int i = 0; i < arr.size(); i ++) {
            nums[arr[i]] ++;
            array.push_back({arr[i], nums[arr[i]]});
            sets[arr[i]].push_back(i);
        }
    }

    int query(int left, int right, int threshold) {
        while (right - left + 1 >= threshold) {
            while (right >= left && array[right][1] < threshold) right --;
            if (right < left) break;
            auto& s = sets[array[right][0]];
            // int l = *s.lower_bound(left);
            int l = *lower_bound(s.begin(), s.end(), left);
            if (array[right][1] - array[l][1] + 1 >= threshold) return array[right][0];
            right --;
        }
        return -1;
    }
};

思路二

使用线段树查询一个区间内出现次数最多的数，然后对这个数按照上面的方法进行二分搜索即可

线段树每个节点记录当前范围出现最多的数，和这个数比其它数多出的delta，这样是因为查询只是对超过一半的数进行的，如果存在这样的数，那么这个数的出现次数减去其它数后仍为正，即区间一定显示的是这个数，如果出现次数最多的数次数不到一半，那么可能不显示这个数，但对本题来讲不会影响结果

写代码时注意的点

• lower_bound搜索右节点时，给右节点加一，这样直接相减即是区间长度

class Segment {
public:
    int num, cnt;
    Segment() : num(0), cnt(0) {}
    void join(const Segment& other) {
        if (num == other.num) cnt += other.cnt;
        else if (cnt > other.cnt) cnt -= other.cnt;
        else {
            cnt = other.cnt - cnt;
            num = other.num;
        }
    }
    void join(Segment& a, Segment& b) {
        num = a.num; cnt = a.cnt;
        join(b);
    }
};
void build(vector<Segment>& tree, int rank, const vector<int>& arr) {
    int nodesNum = 1, length = arr.size();
    while (nodesNum < length) nodesNum *= 2;
    tree.assign(nodesNum * 2, Segment());
    for (int i = 0; i < length; i ++) {
        tree[nodesNum + i].num = arr[i];
        tree[nodesNum + i].cnt = 1;
    }
    for (int i = nodesNum - 1; i >= 1; i --)
        tree[i].join(tree[i * 2], tree[i * 2 + 1]);
}
void _query(const vector<Segment>& tree, int rank, int l, int r, int left, int right, Segment& result) {
    if (left >= l && right <= r) {
        result.join(tree[rank]);
        return;
    }
    if (l > right || r < left) return;
    int mid = (left + right) / 2;
    _query(tree, rank * 2, l, r, left, mid, result);
    _query(tree, rank * 2 + 1, l, r, mid + 1, right, result);
}
Segment queryTree(const vector<Segment>& tree, int l, int r) {
    Segment result;
    int N = tree.size() / 2;
    _query(tree, 1, l + 1, r + 1, 1, N, result);
    return result;
}

class MajorityChecker {
private:
    vector<Segment> tree;
    unordered_map<int, vector<int>> maps;
public:
    MajorityChecker(vector<int>& arr) {
        build(tree, 1, arr);
        for (int i = 0; i < arr.size(); i ++) maps[arr[i]].push_back(i);
    }

    int query(int left, int right, int threshold) {
        Segment result = queryTree(tree, left, right);
        auto& s = maps[result.num];
        int dis = lower_bound(s.begin(), s.end(), right + 1) - \
            lower_bound(s.begin(), s.end(), left);
        if (dis >= threshold) return result.num;
        return -1;
    }
};

---

1187. Make Array Strictly Increasing (Hard)

给两个数组，可以将第一个数组的某个数替换为第二个数组的一个数，求将第一个数组变成严格递增数组所需的最少替换次数，如果无法替换返回-1

Input: arr1 = [1,5,3,6,7], arr2 = [1,3,2,4]
Output: 1
Explanation: Replace 5 with 2, then arr1 = [1, 2, 3, 6, 7].
Input: arr1 = [1,5,3,6,7], arr2 = [4,3,1]
Output: 2
Explanation: Replace 5 with 3 and then replace 3 with 4. arr1 = [1, 3, 4, 6, 7].
Input: arr1 = [1,5,3,6,7], arr2 = [1,6,3,3]
Output: -1
Explanation: You can't make arr1 strictly increasing.

arr1和arr2的长度 [1, 2000] arr1和arr2中每个数范围 [0, 10^9]

思路

动归，这个其实从数据范围也能看出，关键是如何定义动归状态，这里定义为

dp[i][j]: 将arr1前i位替换j次变为严格递增后，末尾数字大小

那么对dp[i+1][j]，有两种可能

• 不换，那么判断arr1[i+1]是否大于dp[i][j]，如果大于，更新dp[i+1][j]=arr1[i+1]
• 换，判断arr2中有没有大于arr1[i][j-1]的数，如果有，dp[i+1][j]=arr2[k]

以上两种情况取小者即可，因为要进行从arr2中取略大数的操作，可以预先进行处理，先对arr2排序，然后对arr1和arr2中每个数，二分找出arr2中刚好大于这个数的数

代码如下

int makeArrayIncreasing(vector<int>& arr1, vector<int>& arr2) {
    sort(arr2.begin(), arr2.end());
    unordered_map<int, int> dict;
    for (int num : arr1) {
        auto itr = upper_bound(arr2.begin(), arr2.end(), num);
        if (itr != arr2.end()) dict[num] = *itr;
    }
    for (int num : arr2) {
        auto itr = upper_bound(arr2.begin(), arr2.end(), num);
        if (itr != arr2.end()) dict[num] = *itr;
    }
    // dp process
    vector<int> dp(arr2.size() + 1, numeric_limits<int>::max());
    dp[0] = arr1[0], dp[1] = arr2[0];
    for (int i = 1; i < arr1.size(); i++) {
        for (int j = min(i+1, (int)arr2.size()); j >= 0; j--) {
            if (arr1[i] <= dp[j]) dp[j] = numeric_limits<int>::max();
            else dp[j] = arr1[i];
            if (j > 0 && dict.count(dp[j-1])) dp[j] = min(dp[j], dict[dp[j-1]]);
        }
    }
    for (int i = 0; i <= arr2.size(); i++)
        if (dp[i] < numeric_limits<int>::max()) return i;
    return -1;
}

---

1192. Critical Connections in a Network (Hard)

给一张图，返回所有关键边

思路

Tarjan算法

class Solution {
private:
    int cnt;
public:
    void tarjan(const vector<vector<int>>& graph, vector<int>& low, vector<int>& dfn, vector<vector<int>>& bridge, int father, int u) {
        int child = 0;
        dfn[u] = low[u] = ++cnt;
        for (int v : graph[u]) {
            if (dfn[v] == 0) {
                child++;
                tarjan(graph, low, dfn, bridge, u, v);
                low[u] = min(low[u], low[v]);
                if (low[v] > dfn[u]) bridge.push_back({ u, v });
            } else if (v != father)
                low[u] = min(dfn[v], low[u]);
        }
    }
    vector<vector<int>> criticalConnections(int n, vector<vector<int>>& connections) {
        vector<vector<int>> graph(n, vector<int>());
        for (auto& v : connections) {
            graph[v[0]].push_back(v[1]);
            graph[v[1]].push_back(v[0]);
        }
        vector<int> low(n, 0), dfn(n, 0);
        vector<vector<int>> bridge;
        cnt = 0;
        tarjan(graph, low, dfn, bridge, -1, 0);
        return bridge;
    }
};