算法第二周： Divide and Conquer-分治算法

2019-11-06 07:49:25

字体：大中小

来源：转载

供稿：网友

分治算法基本思想：将问题分解为k个子问题，每个子问题相互独立且与原问题性质相同，求得子问题的解即可求得原问题的解。若子问题还较难以解决，就递归的分解子问题，直到可以找到简单的求解方法。

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.For example, given the array [-2,1,-3,4,-1,2,1,-5,4],the contiguous subarray [4,-1,2,1] has the largest sum = 6.

题目描述：寻找数组中值最大的子串和。

既然题目不要求输出子串含有的元素而是只需要和，那么首先可以想到直接遍历数组。

class Solution{public: int maxSubArray(vector<int>& nums) { int maximum=nums[0],maxEnd=nums[0]; for(int i=1;i<nums.size();i++) { if((maxEnd+nums[i])>nums[i])//maxEnd记录当前最大值 maxEnd=maxEnd+nums[i]; else maxEnd=nums[i]; if(maximum<maxEnd) maximum=maxEnd;//maximum记录最终最大值 } return maximum ; }};

但题目要求的是用分治法，那么就需要将数组分割并在字串中找到最大值再合并得到结果。将nums分为两个子串，并递归求出两个子串中最大的子串和，记为left和right，同时要注意再合并时最大值可能会出现在两子串交界处，所以还要加一个middle值来记录出现在中间的最大和，最后在三者间选最大值为结果。

class Solution {public: int dive(int A[], int l, int r) { if (l == r) return A[l]; int m = (l + r) / 2; int left = dive(A, l, m); int right = dive(A, m + 1, r); int middle = A[m]; for (int i = m - 1, tmp = middle; i >= l; i--) { tmp += A[i]; middle = max(middle, tmp); } for (int i = m + 1, tmp = middle; i <= r; i++) { tmp += A[i]; middle = max(middle, tmp); } return max(middle, max(left, right)); } int maxSubArray(int A[], int n) { return dive(A, 0, n - 1); } };

169. Majority Element

Given an array of size n, find the majority element. The majority element is the element that appears more than ⌊ n/2 ⌋ times. You may assume that the array is non-empty and the majority element always exist in the array.

目标：找到出现次数超过⌊ n/2 ⌋的元素。

递归的将数组分为两半，找到左半子串出现次数达到字串元素个数一般的元素lm找到右半子串出现次数达到字串元素个数一般的元素rm，再比较lm和rm那个出现次数多，取出现次数多的那个元素。

class Solution {public: int majorityElement(vector<int>& nums) { return findMajority(nums,0,nums.size()-1); }PRivate: int findMajority(vector<int>& nums,int left,int right) { if(left==right) return nums[left]; int mid=left+(right-left)/2; int lm=findMajority(nums,left,mid); int rm=findMajority(nums,mid+1,right); if(lm==rm) return lm; int numl=0,numr=0; for(int i=left;i<right+1;i++) { if(nums[i]==lm) numl++; else if(nums[i]==rm) numr++; } if(numl>numr) return lm; else return rm; }};

241. Different Ways to Add Parentheses

Given a string of numbers and Operators, return all possible results from computing all the different possible ways to group numbers and operators. The valid operators are +, - and *.

目标：输入一个算式，返回其再所有不同括号组成可能下的取值。

遍历算式，其中每个“+”“-”“*”都是拆分点，将式子递归拆分下去，直到出现最简单的算式，将计算得到的值层层返回，得到答案。遍历之后得到所有不同拆分顺序下的答案。

class Solution {public: vector<int> diffWaysToCompute(string input) { vector<int> result; int size = input.size(); for (int i = 0; i < size; i++) { char cur = input[i]; if (cur == '+' || cur == '-' || cur == '*') { vector<int> result1 = diffWaysToCompute(input.substr(0, i)); vector<int> result2 = diffWaysToCompute(input.substr(i+1)); for(int j=0;j<result1.size();j++) for(int k=0;k<result2.size();k++) { int n1=result1[j]; int n2=result2[k]; if (cur == '+') result.push_back(n1 + n2); else if (cur == '-') result.push_back(n1 - n2); else result.push_back(n1 * n2); } } } if (result.empty()) result.push_back(atoi(input.c_str())); return result; }};

上一篇：CListCtrl控件样式设置时出现的小插曲！

下一篇：xx_OJ_test