Leetcode 刷题笔记-Leetcode 101 第8章 分治法

Leetcode 刷题笔记-Leetcode 101 第8章 分治法

分治法

顾名思义，分治问题由“分”（divide）和“治”（conquer）两部分组成，通过把原问题分为子问题，再将子问题进行处理合并，从而实现对原问题的求解。我们在排序章节展示的归并排序就是典型的分治问题，其中“分”即为把大数组平均分成两个小数组，通过递归实现，最终我们会得到多个长度为1的子数组；“治”即为把已经排好序的两个小数组合成为一个排好序的大数组，从长度为1 的子数组开始，最终合成一个大数组。

表达式问题

Leetcode 241

给定一个只包含加、减和乘法的数学表达式，求通过加括号可以得到多少种不同的结果

class Solution {
public:
    vector<int> diffWaysToCompute(string expression) {
        vector<int> ways;
        for(int i=0;i<expression.size();++i){
            char c = expression[i];
            if(c == '+' || c == '-' || c == '*'){
                vector<int> left = diffWaysToCompute(expression.substr(0,i));
                vector<int> right = diffWaysToCompute(expression.substr(i+1));
                for(const int &l : left){
                    for(const int &r : right){
                        if(c == '+'){
                            ways.push_back(l+r);
                        }
                        else if(c == '-'){
                            ways.push_back(l-r);
                        }
                        else{
                            ways.push_back(l*r);
                        }
                    }
                }
            }
        }
        if (ways.empty()){
            ways.push_back(stoi(expression));
        }
        return ways;
    }
};

分析：利用分治思想，我们可以把加括号转化为，对于每个运算符号，先执行处理两侧的数学表达式，再处理此运算符号。注意边界情况，即字符串内无运算符号，只有数字。

错误：想不通的

练习

Leetcode 932

class Solution {
public:
    vector<int> beautifulArray(int n) {
        vector<int> ans;
        if(n==1){
            ans.push_back(1);
            return ans;
        }
        int odd_num=(n+1)/2;
        int even_num=n/2;
        vector<int> left_arry=beautifulArray(odd_num);
        vector<int> right_arry=beautifulArray(even_num);
        //将左侧数组映射为奇数
        for(auto &val:left_arry){
            ans.push_back(val*2-1);
        }
        //将右侧数组映射为偶数
        for(auto &val:right_arry){
            ans.push_back(val*2);
        }
        return ans;
    }
};

分析：不懂

错误：不懂

Leetcode 312

class Solution {
public:
    int maxCoins(vector<int>& nums) {
        int n = nums.size();
        vector<vector<int>> rec(n + 2, vector<int>(n + 2));
        vector<int> val(n + 2);
        val[0] = val[n + 1] = 1;
        for (int i = 1; i <= n; i++) {
            val[i] = nums[i - 1];
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = i + 2; j <= n + 1; j++) {
                for (int k = i + 1; k < j; k++) {
                    int sum = val[i] * val[k] * val[j];
                    sum += rec[i][k] + rec[k][j];
                    rec[i][j] = max(rec[i][j], sum);
                }
            }
        }
        return rec[0][n + 1];
    }
};

分析：不懂

错误：不懂

总结

不懂不懂不懂啊啊啊啊啊