首页 / 算法 / C++中的分治算法及常见题目汇总

C++中的分治算法及常见题目汇总

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了C++中的分治算法及常见题目汇总，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含6319字，纯文字阅读大概需要10分钟。

内容图文

目录

一、分治法基本原理

  1. 分治算法基本介绍
  2. 分治算法通俗解释

二、Leecode刷题题解

  1. 最大子序和

 

一、分治法基本介绍

1. 分治算法基本介绍

　　分治算法即分而治之，就是把一个复杂的问题分解成两个或多个相同或相似的子问题，再把子问题分解成更小的问题。。。直到最后子问题可以简单地直接求解，原问题即子问题的合并。分治算法主要分为三个步骤：

  • 分解：将问题划分成一系列子问题，子问题的形式和原问题一样，只是规模更小
  • 解决：递归地求出子问题。如果子问题的规模足够小，即停止递归，直接求解
  • 合并：步骤将子问题的解组合成原问题的解

2. 分治算法通俗解释

(此例子引用连接如下：https://www.zhihu.com/search?type=content&q=%E5%88%86%E6%B2%BB%E7%AE%97%E6%B3%95)　　

　　有这样一个经典的问题：有100枚硬币，其中1枚重量与众不同，是假币，更轻一些。如果用天平秤，请问至少称多少次一定能找到这枚假币

　　加入我们用传统的枚举法，显然至少需要比较50次

      C++中的分治算法及常见题目汇总 - 文章图片

 

而假设我们采用分治法的话 ，流程如下：1. 将100硬币分成3份，33,33,34。

2.称量1、2份，若天平平衡，则假币必在另外34枚中。若不平衡，假币在轻的那33枚里。

3.将34枚分为11/11/12枚（或将33枚分成11*3）。

4.称量两组11枚的硬币，若平衡，假币在12枚里（或另外的11枚）若不平衡，假币在轻的11里。

5.将11（或12）枚分成3/4/4（或4/4/4），称量4/4，方法同上。

6.将剩下的3（或4）分为1/1/1（或1/1），称量1/1，若平衡，则剩下的一枚是假币，若不平衡，轻的是假币。 若还剩4枚，出现1/1平衡，剩下2枚则称量，显然轻的是假币。

这种方法只需要5次就能解决这个问题。

分治算法的流程： C++中的分治算法及常见题目汇总 - 文章图片

 

 

二、Leecode刷题详解 1. 最大子序和

　　C++中的分治算法及常见题目汇总 - 文章图片

 

  •  问题分析

　　解决此问题有两种方法：

    • 方法一：传统暴力解决方法，需要遍历整个数组，其时间复杂度为 O(n)

　　　　　设置一个当前最大值和全局最大值，遍历整个数组，当此时的最大值小于0时，则前面的都不要，否则，将下一个数相加即可　

 1 class Solution {
 2 public:
 3     int FindGreatestSumOfSubArray(vector<int> array) {
 4         /*
 5         要实现求得连续子数组的最大和,我们可以
 6         */
 7         if(array.empty())
 8             return 0;
 9         int cursum=0;
10         int maxsum=array[0];
11         for(int i=0;i<array.size();++i)
12         {
13             if(cursum<=0)
14                 cursum=array[i];
15             else
16             {
17                 cursum+=array[i];
18             }
19             if(cursum>=maxsum)
20                 maxsum=cursum;
21         }
22         return maxsum;
23     }
24 };
    • 方法二：使用分治算法

　　　　要找到最大连续和的子数组，我们可以用分治算法，设最左边为left,最右边为right，中间节点为mid，则最大子数组可以分为以下三种情况：

　　　　1. 最大连续子数组都左边子数组[left, mid]

　　　　2. 最大连续子数组都在右边子数组[mid+1,right]

　　　　3. 最大连续子数组跨越了中点，一部分在左边子数组中，一部分在右边子数组中

　　　　最大连续子数组一定是三种情况中的最大值

 1 class Solution {
 2     /*
 3         要找到连续最大子序和，我们可以用分治算法，设最左边为left, 最右边为right,中间节点为mid，则最大连续子数组可能情况为以下三种：
 4         1. 最大连续子数组都在[left, mid]中
 5         2. 最大连续子数组都在[mid+1, right]中
 6         3. 最大连续子数组跨越了中点，因此left<=i<=mid<=j<=right
 7     */
 8     //只需要在这三种情况中找出最大值即可
 9     //首先是求出mid在子数组中间的情况
10     /*
11         我们的目的是找出mid在子数组中的子数组的和
12     */
13     int INT_MIN=-2147483648; 
14     public int find_max_cross_substr(int[] nums,int left,int mid,int right)
15     {
16         int maxleft=0,maxright=0;
17         int sum=0;
18         int leftsum=INT_MIN,rightsum=INT_MIN;
19         //首先找到左半边子数组的最大值
20         for(int i=mid;i>=left;--i)
21         {
22             sum+=nums[i];
23             leftsum=Math.max(sum,leftsum);
24         }
25         //然后找到右半边子数组的最大值
26         sum=0;
27         for(int j=mid+1;j<=right;++j)
28         {
29             sum+=nums[j];
30             rightsum=Math.max(sum,rightsum);
31         }
32         return (leftsum+rightsum);
33     }
34     //然后进行递归查找，比较三种情况，找出最大值
35     public int find_max_substr(int[]nums,int left,int right)
36     {
37         if(left==right)
38             return nums[left];//找到递归结束条件，结束递归
39         else
40         {
41             int mid=left+(right-left)/2;
42             int maxleftsum,maxrightsum,maxcrosssum;
43             maxleftsum=find_max_substr(nums,left,mid);
44             maxrightsum=find_max_substr(nums,mid+1,right);
45             maxcrosssum=find_max_cross_substr(nums,left,mid,right);
46             return Math.max(Math.max(maxleftsum,maxrightsum),maxcrosssum);
47         }
48         
49     }
50     public int maxSubArray(int[] nums) {
51         return find_max_substr(nums,0,nums.length-1);
52     }
53 }
 1 class Solution {
 2     /*
 3         要找到连续最大子序和，我们可以用分治算法，设最左边为left, 最右边为right,中间节点为mid，则最大连续子数组可能情况为以下三种：
 4         1. 最大连续子数组都在[left, mid]中
 5         2. 最大连续子数组都在[mid+1, right]中
 6         3. 最大连续子数组跨越了中点，因此left<=i<=mid<=j<=right
 7     */
 8     //只需要在这三种情况中找出最大值即可
 9     //首先是求出mid在子数组中间的情况
10     /*
11         我们的目的是找出mid在子数组中的子数组的和
12     */
13     int INT_MIN=-2147483648; 
14     public int find_max_cross_substr(int[] nums,int left,int mid,int right)
15     {
16         int maxleft=0,maxright=0;
17         int sum=0;
18         int leftsum=INT_MIN,rightsum=INT_MIN;
19         //首先找到左半边子数组的最大值
20         for(int i=mid;i>=left;--i)
21         {
22             sum+=nums[i];
23             leftsum=Math.max(sum,leftsum);
24         }
25         //然后找到右半边子数组的最大值
26         sum=0;
27         for(int j=mid+1;j<=right;++j)
28         {
29             sum+=nums[j];
30             rightsum=Math.max(sum,rightsum);
31         }
32         return (leftsum+rightsum);
33     }
34     //然后进行递归查找，比较三种情况，找出最大值
35     public int find_max_substr(int[]nums,int left,int right)
36     {
37         if(left==right)
38             return nums[left];//找到递归结束条件，结束递归
39         else
40         {
41             int mid=left+(right-left)/2;
42             int maxleftsum,maxrightsum,maxcrosssum;
43             maxleftsum=find_max_substr(nums,left,mid);
44             maxrightsum=find_max_substr(nums,mid+1,right);
45             maxcrosssum=find_max_cross_substr(nums,left,mid,right);
46             return Math.max(Math.max(maxleftsum,maxrightsum),maxcrosssum);
47         }
48         
49     }
50     public int maxSubArray(int[] nums) {
51         return find_max_substr(nums,0,nums.length-1);
52     }
53 }

 

?

内容总结

以上是互联网集市为您收集整理的C++中的分治算法及常见题目汇总全部内容，希望文章能够帮你解决C++中的分治算法及常见题目汇总所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

扫描二维码推送至手机访问。

本文链接：https://qyyshop.com/info/595067.html

来源：【匿名】