中小企业网站推广,鞋子网站模板,陕西因酷网站建设,百度不收录网站首页1.分治法
分治法#xff08;Divide and Conquer#xff09;是一种常见的算法设计思想#xff0c;它将一个大问题分解成若干个子问题#xff0c;递归地解决每个子问题#xff0c;最后将子问题的解合并起来得到整个问题的解。分治法通常包含三个步骤#xff1a;
1. Divid…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:vectorint diffWaysToCompute(string expression) {int n expression.size();vectorint res;for(int i0;in;i){char c expression[i];if(c||c-||c*){vectorint left diffWaysToCompute(expression.substr(0,i));vectorint right diffWaysToCompute(expression.substr(i1));for(auto l:left){for(auto r:right){switch(c){case : res.push_back(lr);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 均不存在下标 ki k j使得 2 * nums[k] nums[i] nums[j] 。
最简单的方法就是让右边的nums[i] nums[j] 这个表达式的值为奇数因为2 * nums[k]肯定是偶数。这样我们可以假设ij且nums[i]为奇数nums[j]为偶数。也就是让数组左边为奇数右边为偶数。
又因为如果A是漂亮数组那么a*Ab还是漂亮数组。
所有我们可以用分治法将问题从大到小拆解先满足每个长度为1、2、3......的数组都是漂亮数组这样最后长度为n的数组也是漂亮数组。 代码
class Solution {
public:vectorint beautifulArray(int n) {vectorint res(n,1);part(0,n-1,res);return res;}void part(int left, int right, vectorint res){if(leftright) return;int mid left (right-left)/2;part(left, mid, res);part(mid1, right, res);for(int ileft;imid;i){res[i] 2*res[i]-1;}for(int imid1;iright;i){res[i] 2*res[i];}}
};
