分治法 Divide and Conquer

1.分治法

分治法（Divide and Conquer）是一种常见的算法设计思想，它将一个大问题分解成若干个子问题，递归地解决每个子问题，最后将子问题的解合并起来得到整个问题的解。分治法通常包含三个步骤：

• 1. Divide：将问题分解成若干个子问题。
• 2. Conquer：递归地解决每个子问题。
• 3. Combine：将子问题的解合并起来得到整个问题的解。

分治法的主要思想是将问题分解成若干个相互独立的子问题，通过递归地解决每个子问题，最后将子问题的解合并起来得到整个问题的解。这种思想可以应用于许多问题的解法中，如排序、搜索、图论、数学计算等等。

一些常见的使用分治法的算法包括：归并排序、快速排序、二分搜索、线性时间选择、Karatsuba 算法等等。

2.练习题

1）

力扣https://leetcode.cn/problems/different-ways-to-add-parentheses/解题思路：

依次遍历字符串的每个字符，如果是运算符，就递归计算左边和右边的值。

class Solution {
public:vector<int> diffWaysToCompute(string expression) {int n = expression.size();vector<int> res;for(int i=0;i<n;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(auto l:left){for(auto r:right){switch(c){case '+':   res.push_back(l+r);break;case '-':   res.push_back(l-r);break;case '*':   res.push_back(l*r);break;}}}}}if(res.empty()) res.push_back(stoi(expression));return res;}};

2)

力扣https://leetcode.cn/problems/beautiful-array/description/

解题思路：

首先确定一点，怎么满足这个条件：

• 对于每个 0 <= i < j < n ，均不存在下标 k（i < k < j）使得 2 * nums[k] == nums[i] + nums[j] 。

最简单的方法就是让右边的nums[i] + nums[j] 这个表达式的值为奇数，因为2 * nums[k]肯定是偶数。这样我们可以假设i<j，且nums[i]为奇数，nums[j]为偶数。也就是让数组左边为奇数，右边为偶数。

又因为如果A是漂亮数组，那么a*A+b还是漂亮数组。

所有我们可以用分治法，将问题从大到小拆解，先满足每个长度为1、2、3......的数组都是漂亮数组，这样最后长度为n的数组也是漂亮数组。

代码：

class Solution {
public:vector<int> beautifulArray(int n) {vector<int> res(n,1);part(0,n-1,res);return res;}void part(int left, int right, vector<int>& res){if(left>=right) return;int mid = left + (right-left)/2;part(left, mid, res);part(mid+1, right, res);for(int i=left;i<=mid;i++){res[i] = 2*res[i]-1;}for(int i=mid+1;i<=right;i++){res[i] = 2*res[i];}}
};