分治.md

分治算法

• 为运算表达式设计优先级 (medium)
• 至少有K个重复字符的最长子串 (medium 递归)

分治算法

至少有K个重复字符的最长子串

LeetCode中文

解法：分治思想，递归解决子问题

https://leetcode.cn/problems/longest-substring-with-at-least-k-repeating-characters/solutions/623432/zhi-shao-you-kge-zhong-fu-zi-fu-de-zui-c-o6ww/

时间复杂度：O(n * 26)

class Solution {
public:
    int longestSubstring(string s, int k) {
        return dfs(s, 0, s.size() - 1, k);
    }
    int dfs(const string& s, int l, int r, int k) {
        if (r - l + 1 < k) return 0;
        vector<int> mp(26, 0);
        for (int i = l; i <= r; ++i) {
            ++mp[s[i] - 'a'];
        }
        char ch = 0;
        for (int i = 0; i < 26; ++i) {
            if (mp[i] > 0 && mp[i] < k) {
                ch = 'a' + i;
                break;
            }
        }
        if (ch == 0) {
            return r - l + 1;
        }
        while (l <= r && s[l] == ch) {
            ++l;
        }
        int idx = l;
        int res = 0;
        while (idx <= r) {
            if (s[idx] == ch) {
                res = max(res, dfs(s, l, idx - 1, k));
                while (idx <= r && s[idx] == ch) {
                    ++idx;
                }
                l = idx;
            } else {
                if (idx == r) {
                    res = max(res, dfs(s, l, idx, k));
                }
                ++idx;
            }
        }
        return res;
    }
};

为运算表达式设计优先级

LeetCode中文

解法：分治，子问题是 num1 op num2

方法1: 递归

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        return recursive(expression, 0, expression.size() - 1);
    }
    vector<int> recursive(const string& exp, int l, int r) {
        vector<int> res;
        if (r - l <= 1) {
            if (res.empty()) {
                int i = l;
                int tmp = 0;
                while (i <= r) {
                    tmp = tmp * 10 + (exp[i] - '0');
                    ++i;
                }
                res.push_back(tmp);
            }
            return res;
        }
        for (int i = l; i <= r; ++i) {
            char op = exp[i];
            if (op == '+' || op == '-' || op == '*') {
                const vector<int>& left = recursive(exp, l, i - 1);
                const vector<int>& right = recursive(exp, i + 1, r);
                for (const int a : left) {
                    for (const int b : right) {
                        int val;
                        if (op == '+') {
                            val = a + b;
                        } else if (op == '-') {
                            val = a - b;
                        } else {
                            val = a * b;
                        }
                        res.push_back(val);
                    }
                }
            }
        }
        return res;
    }
};