001--算法之"高手过招"[分治算法专题]

作者: CC老师(刘依)

著作权归作者所有; 未经作者授权,不得商业转载/非商业转载;
算法之"高手过招"知识付费系列下的视频/文章/源码/资料已申请版权保护.
最终解释权归逻辑教育所有;

算法之"高手过招"

1.1 什么是分治策略算法?

在计算机科学中,分治策略是非常重要的算法思想. 字面上的意思就是把一个复杂问题分解成2个或者多个相同或者相似的子问题. 再子问题的分解成更小的子问题; 直到最后的子问题可以简单的直接求解. 再将子问题的结果合并得到原问题的结果;

这样的方式,比如常用的排序算法中, 快速排序以及归并排序都是利用了分治策略算法的思想实现的. 在分治策略中, 我们递归地求解一个问题, 在每层递归中应用如下三个步骤:

  • 分解(Divide)步骤, 将问题划分为一些子问题. 子问题的形式与原问题一样. 只是规模更小;
  • 解决(Conquer)步骤,递归地求解出子问题,如果子问题的规模足够小,即停止递归.直接求解;
  • 合并(Combine)步骤,将子问题的解组合成原问题的解;
image.png

当子问题足够大, 需要递归求解时. 我们就称之为"递归情况". 当子问题变的足够小, 不再需要递归时, 这时递归就已经"触底". 进入了基本情况;

并不是所有的问题都能化解成完全一样的子问题. 也会出现需要求解与原问题不完全一样的子问题. 接下来在这一阶段的课程,我们会看到更多基于分治策略的算法.

分治策略,在理解以及设计分治策略的算法的能力需要一定时间去掌握.它需要运用归纳法去证明一个理论. 为了使得递归能够被推行. 很多时候需要用一个较为概括或复杂的问题去取代原有问题,而且并没有一个系统性的方法去适当的概括问题;

分治算法需要不错的数学归纳能力.因为分治策略的算法通常需要以数学归纳法来验证, 它的计算成本则多数以求解的递归关系式来判定;

由于分治策略的特性, 它最直接的表现形式常常以递归出现.

1.2 连续数列

  • 难度系数: ☆☆☆

  • 题目来源: LeetCode 下分治策略专题

  • 题目描述: 给定一个整数数组,找出总和最大的连续数列, 并返回总和;

  • 输入: [-2,1,-3,4,-1,2,1,-5,4]

  • 输出: 6

  • 解释: 连续子数组[4,-1,2,-1];

  • 题目解读:

  • 实际上, 这个题目就是单纯的获取从一个数组中,找出连续索引值下元素相加的总和最大的序列; 例如题目描述的例子. 从头到尾进行查找, 使得连续的元素相机得到一个最大的总和;

  • 关键词: 连续数列, 最大, 整数数组. 总和;

  • 出现过企业面试题: 百度

1.2.1 暴力法

LeetCode 执行结果

image.png

暴力算法思路

  • 判断数组中的元素个数, 如果元素个数为0,则直接返回0;

  • 判断数组中的元素个数, 如果元素个数为1,则直接返回索引为0下的元素值;

  • 定义临时变量: i,temp,maxValue; 默认将maxValue 设置一个极小的值作为初始化值;

  • 开始循环,

  • 循环起始值i = 0;

  • 循环结束条件: 当i从头到尾都遍历了一次;

  • 循环递增条件: i每次自增1;

  • 在循环体中;

  • 将临时变量temp 记录从0~i的和的累积;

  • 判断当前的temp 是否大于 maxVaue. 如果大于MaxValue 则更新maxValue;

  • 判断当前的temp如果小于0的情况出现,则将temp 赋值为0;

  • 最后返回maxValue;

暴力算法代码实现

int maxSubArray(int* nums, int numsSize){
    if(numsSize==0) return 0;
    if(numsSize==1) return nums[0];
    int i=0,temp=0,maxValue=-1024;
    for(i=0;i<numsSize;i++)
    {
        temp=temp+nums[i];
        if(temp>maxValue) maxValue=temp;
        if(temp<0) temp=0;
    }
    return maxValue;
}

执行过程动画效果

连续数列(暴力法).gif

温馨提示: 上图为动图效果. 网页阅读更佳

1.2.2 分治策略

站在分治策略的角度下思考, 求最大连续数组. 我们可以预估到最大连续数组的和 有可能出现的3个位置如下:

  1. 数组的左半部分的最大连续数组和;
  2. 数组的右半部分的最大连续数组和;
  3. 横跨数组的左半部分和右半部分得到最大连续数组和;
  4. 三者比较大小, 最大者即为我们所求的最大连续数组的和.

LeetCode 执行结果

image.png

接下来,我们分析案例中提供的数组. 来推演 分治策略的算法思想;

如果推演过程,数组中元素太多.可能会造成大家对于 分治策略中提出的 关于有可能出现最大连续数组和的3个猜想造成理解负担;

所以我们假设此时 数组中只有2个元素. 数组nums[2] = {-2,1}; 其中-2和1只是随机设计的数字.

也就是 这2个数字最多组成3个可能性;

  • -2; 表示数组左半部分的有可能是最大连续数组的和;
  • -2 + 1 ; 表示数组横跨左半部分和右半边部分有可能是连续数组的和;
  • 1 ; 表示数组右半部分有可能是最大连续数组的和;
  • 最后, 比较这3个数字,取最大就能获得最大连续数组的和;
image.png

分治策略算法思路

分析: 分治策略在开篇,我们就谈过. 分治策略的本质就是将问题拆解成最小子问题, 再将子问题的结合进行合并; 而连续数列问题, 其实就可以用到分治策略中的递归的方式来进行解决; 刚刚我们通过对2个元素的数列进行小基数数据的推演. 我们需要将数列拆解左右2个半部分, 依次递归拆解. 直到只剩下一个数字时就触碰到递归的底线; 那么现在我们捋顺一下这个问题的思路;

思路:

  • 将数列一分为二. 求解mid = left + (right - left)/2 ; 那么为什么要这么计算mid 是因为数列在不断拆解的过程,数列本身就被折断了. 但是我们不能记录错误的mid; mid 还是基于nums 原始数组的index ;
  • 递归求解数列左半部分的和 则调用 subMaxValue(nums, left, mid);
  • 求出左半部分和之后, 则继续求解从left 跨越mid 到 right 这横跨中间部分的和; MidValue(nums,left,mid,right);
  • 继续递归求解数列右半部分的和.则调用 subMaxValue(nums, mid+1,right);
  • 最后在每一次递归回调上层之前,判断 left_sum,mid_sum,right_sum**** 谁的值更大,则返回上一层递归
  • 继续递归回滚. 直到所有的递归都回滚到入口时,就求解出来 连续数列的最大和

image.png

分治策略代码实现

//
//  main.c
//  001--连续数组(分治策略)
//
//  Created by CC老师 on 2020/9/7.
//  Copyright © 2020 CC老师. All rights reserved.
//

#include <stdio.h>
//宏定义无穷小
#define INF -2147483647
//求a和b的最大值
#define max( a , b ) ( a > b ? a : b )

//求跨越中点mid的最小子数组和
int MidValue( int * nums , int left , int mid , int right ){

    int left_sum = INF , right_sum = INF;
    int sum = 0;

    //求中点最半部分和
    for( int i = mid ; i >= left ; i-- ){

        sum += *( nums + i );

        if( sum > left_sum ){

            left_sum = sum;

        }

    }

    sum = 0;

    //求中点右半部分和
    for( mid++ ; mid <= right ; mid++ ){

        sum += *( nums + mid );

        if( sum > right_sum ){

            right_sum = sum;

        }

    }

    return right_sum + left_sum;

}

int subMaxValue( int * nums , int left , int right ){

    if( left >= right ){

        return *( nums + left );

    }

    int mid = left + ( right - left ) / 2;
    //仅求中点左部分和
    int left_sum = subMaxValue( nums , left , mid );
    //求跨越中点的和
    int mid_sum = MidValue( nums , left , mid , right );
    //求中点右部分和
    int right_sum = subMaxValue( nums , mid + 1 , right );
    
    return max( left_sum , max( right_sum , mid_sum ) );

}

int maxSubArray( int * nums , int numsSize ){

    return subMaxValue( nums , 0 , numsSize - 1 );

}

int main(int argc, const char * argv[]) {
    // insert code here...
    printf("Hello, World!\n");
    //int nums[] = {-2,1,-3};
    int nums[] = {-2,1,-3,4,-1,2,1,-5,4};
    int maxSum = maxSubArray(nums, 9);
    printf("%d\n",maxSum);
    return 0;
}


总结与分析

连续数列这个问题, 我们实现了2种方法. 第一种是暴力法, 第二种是分治策略; 但是从代码实现的结果以及他们的执行时间和内存空间占用上,可以发现第一种方法更有优势. 所以在解决算法问题时, 并不是单纯的认为分治策略的解决的方案就会比暴力法高级. 其实算法重要的还是比较他们的时间/空间复杂度. 更重要的是从不同的解决策略去实现算法, 最大的收益是开拓的解决问题的思维方式;

实际该问题,还有一种解决方案. 是动态规划. 因为该篇章的主角是 "分治策略" 所以我们就不在这篇中 来进行喧宾夺主的事情. 后续会有专门关于 动态规划的篇章,我们在继续延伸学习.

算法之"高手过招" 专栏会以 几大算法策略为主题的进行不断更新. 后续会继续更新"分治策略"篇章.

致谢!

该文章,仅献给在编程路上, 持续热爱算法的开发者

文章如有错误,欢迎指正

著作权归作者所有; 未经作者授权,不得商业转载/非商业转载

算法之"高手过招"知识付费系列下的视频/文章/源码/资料已申请版权保护

致谢(1).jpg
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 206,013评论 6 481
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 88,205评论 2 382
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 152,370评论 0 342
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 55,168评论 1 278
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 64,153评论 5 371
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 48,954评论 1 283
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,271评论 3 399
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 36,916评论 0 259
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 43,382评论 1 300
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 35,877评论 2 323
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 37,989评论 1 333
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 33,624评论 4 322
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,209评论 3 307
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,199评论 0 19
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,418评论 1 260
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 45,401评论 2 352
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 42,700评论 2 345