Leetcode 1001-1100

1049. Last Stone II (Medium)

有多个石头，每个石头有对应重量，每次可以选取两块石头碰撞

• 如果重量相同，两块石头都被销毁
• 如果不一样重，轻的石头被销毁，重的石头减去轻石头的重量

限制：石头数量不多于30，重量不大于100

Input: [2,7,4,1,8,1]
Output: 1

思路一

最后重量即由所有石头相加减而得，所以对每个石头的重量尝试加、减，最后得到的最小重量即答案

如下代码，用一个vector存储当前所有重量，然后每次加入一个石头，所得的可能重量也乘2

int lastStoneWeightII(vector<int>& stones) {
    if (stones.size() == 0) return 0;
    vector<int> q;
    q.push_back(stones.front());
    q.push_back(-stones.front());
    for (int i = 1; i < stones.size(); i ++) {
        unordered_set<int> s;
        vector<int> temp;
        for (int j = 0; j < q.size(); j ++) {
            int n0 = q[j] + stones[i];
            int n1 = q[j] - stones[i];
            if (!s.count(n0)) {
                temp.push_back(n0);
                s.insert(n0);
            }
            if (!s.count(n1)) {
                temp.push_back(n1);
                s.insert(n1);
            }
        }
        q.swap(temp);
    }
    int mx = q.front();
    for (int n : q) {
        if (n < 0) continue;
        if (mx < 0) mx = n;
        mx = min(mx, n);
    }
    return mx;
}

思路二

在能消除所有石头的情况下，方案就是找石头凑出恰好为总重一半的重量

在不能消除所有石头的情况下，最小重量就是找出能凑出的最接近一半重量的方案，然后用多的一半减去少的一半，如题目例子，总和为23，能凑出来最接近一半的方案是2+8+1=11，最后结果是(23-11)-11=1

代码如下，weights[i]表示石头能凑出的小于等于i的最大重量，对各石头来更新动归方案即可，这里注意要从大向小更新，因为从小向大更新会导致一个石头被算多次

int lastStoneWeightII(vector<int>& stones) {
    int sum = 0;
    for (auto s : stones) sum += s;
    int half = sum / 2;
    vector<int> weights(half + 1, 0);
    for (int s : stones) {
        for (int i = half; i > 0; i --) {
            if (i >= s)
                weights[i] = max(weights[i], weights[i-s] + s);
        }
    }
    return sum - 2 * weights[half];
}

---

1092. Shortest Common Supersequence (Hard)

给两个字符串，求最短的、包含这两个字符串为子串的字符串

Input: str1 = "abac", str2 = "cab"
Output: "cabac"

+ 1 <= str1.length, str2.length <= 1000 + str1 and str2 consist of lowercase English letters.

思路

先求两个字符串的最长公共子串，然后向前后填不是公共子串的字符即可，将两个字符串扫描一遍即可

对例子而言，最长公共子串是ab

非lst的字符: c
lst的字符: ca
lst的字符: cab
剩余非lst的字符: cabac

求公共子串的方法就是先构建二维的length表，同时记录二维prev表，记录方向，最后恢复字符串

string shortestCommonSupersequence(string str1, string str2) {
    if (str1.size() == 0) return str2;
    if (str2.size() == 0) return str1;
    string s = lst(str1, str2);
    string res(str1.size() + str2.size() - s.size(), ' ');
    int p1 = 0, ps1 = 0, p2 = 0, ps2 = 0, rank = 0;
    while (rank < res.size()) {
        while (str1[p1] != s[ps1]) res[rank ++] = str1[p1 ++];
        while (str2[p2] != s[ps2]) res[rank ++] = str2[p2 ++];
        res[rank ++] = s[ps1];
        ps1 ++; ps2 ++; p1 ++; p2 ++;
        if (ps1 == s.size()) {
            while (p1 < str1.size()) res[rank ++] = str1[p1 ++];
            while (p2 < str2.size()) res[rank ++] = str2[p2 ++];
        }
    }
    return res;
}
string lst(const string& str1, const string& str2) {
    int n = str1.size(), m = str2.size();
    vector<vector<int>> length(n + 1, vector<int>(m + 1, 0));
    vector<vector<int>> prev(n + 1, vector<int>(m + 1, -1));
    for (int i = 1; i <= n; i ++) {
        for (int j = 1; j <= m; j ++) {
            if (str1[i - 1] == str2[j - 1]) {
                length[i][j] = length[i - 1][j - 1] + 1;
                prev[i][j] = 2;
            } else if (length[i - 1][j] >= length[i][j - 1]) {
                length[i][j] = length[i - 1][j];
                prev[i][j] = 1;
            } else {
                length[i][j] = length[i][j - 1];
                prev[i][j] = 0;
            }
        }
    }
    string s = "";
    int i = n, j = m;
    while (prev[i][j] != -1) {
        if (prev[i][j] == 2) {
            s = str1[i - 1] + s;
            i --; j --;
        }
        else if (prev[i][j] == 1) i --;
        else j --;
    }
    return s;
}

---

1095. Find in Mountain Array (Hard)

思路

二分搜素即可

int findInMountainArray(int target, MountainArray &mountainArr) {
    int l = 0, r = mountainArr.length() - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (mountainArr.get(m) > mountainArr.get(m + 1)) r = m - 1;
        else l = m + 1;
    }
    int pivot = l; // [0, pivot], [pivot+1, length-1]
    l = 0, r = pivot;
    while (l <= r) {
        int m = (l + r) / 2;
        if (mountainArr.get(m) >= target) r = m - 1;
        else l = m + 1;
    }
    if (l <= pivot && mountainArr.get(l) == target) return l;
    l = pivot + 1, r = mountainArr.length() - 1;
    while (l <= r) {
        int m = (l + r) / 2;
        if (mountainArr.get(m) <= target) r = m - 1;
        else l = m + 1;
    }
    if (l < mountainArr.length() && mountainArr.get(l) == target) return l;
    return -1;
}

---

1096. Brace Expansion II (Hard)

对模式串，实现展开函数R，按照一定规则生成字符串集合

• 对单独字母，直接生成只包含这个字母的集合，R(x)={x}
• 对以逗号分隔的表达式e1,e1,...,ek，R({e_1,e_2,...}) = R(e_1) ∪ R(e_2) ∪ ...
• 对直接相连的表达式e1e2...ek，R(e_1 + e_2) = {a + b for (a, b) in R(e_1) × R(e_2)}
• 表达式只包含小写字母，逗号和大括号

Input: "{a,b}{c,{d,e}}"
Output: ["ac","ad","ae","bc","bd","be"]

最后输出要求是字典序

思路

从前向后线性扫描求集合即可，定义这两个函数

f1 求一个单独表达式的值

f2 求多个相乘表达式的值

则f1的实现就是调用多次f2，然后将集合加起来，直到扫描到后括号或者表达式结束，如果只是一个小写字母，则直接返回

f2的实现就是调用多次f1，然后进行相乘，直到遇到,或者}或者表达式结束

将整个式子再括起来，这样外层调用一次f1即可得到答案

可以用unordered_set和vector来完成查重，最后进行排序，也可以直接用set进行记录，可以同时完成记录和查重

class Solution {
public:
    vector<string> braceExpansionII(string expression) {
        int ptr = 0;
        vector<string> res;
        unordered_set<string> s;
        expression = "{" + expression + "}";
        f1(expression, res, s, ptr);
        sort(res.begin(), res.end());
        return res;
    }
    void f1(const string& expression, vector<string>& eles, unordered_set<string>& dict, int& ptr) {
        if (expression[ptr] != '{') {
            string str(1, expression[ptr]);
            eles.push_back(str);
            dict.insert(str);
            return;
        }
        ptr++;
        f2(expression, eles, dict, ptr);
        while (ptr < expression.size() - 1 && expression[++ptr] != '}') {
            vector<string> v;
            unordered_set<string> s;
            f2(expression, v, s, ptr);
            for (auto& str : v) {
                if (dict.count(str)) continue;
                dict.insert(str);
                eles.push_back(str);
            }
        }
    }
    void f2(const string& expression, vector<string>& eles, unordered_set<string>& dict, int& ptr) {
        if (expression[ptr] == ',' || expression[ptr] == '}') return;
        f1(expression, eles, dict, ptr);
        while (ptr < expression.size() - 1 && expression[ptr+1] != ',' && expression[ptr+1] != '}') { // '{' or letter
            ptr++;
            vector<string> v;
            unordered_set<string> s;
            f1(expression, v, s, ptr);
            dict.clear();
            vector<string> temp;
            for (auto& s1 : eles) {
                for (auto& s2 : v) {
                    if (dict.count(s1 + s2)) continue;
                    temp.push_back(s1 + s2);
                    dict.insert(s1 + s2);
                }
            }
            eles.swap(temp);
        }
    }
};