[LeetCode]分治算法的核心原理及其编程实现

原本一直想再系统地回顾一遍基本的数据结构与算法，正好借着Datawhale八月份组队学习的契机，总结一下经典的算法思想，本篇文章主要介绍分治算法的原理，并解决LeetCode上三道可以用递归思想解决的题目。

【LeetCode】系列文章
LeetCode分治算法的原理和编程实践 发布于20200819
LeetCode动态规划法的原理和编程实践 发布于20200822

文章结构概览

• • • • 一、分治策略的基本原理
    • 二、编程实践应用
    • • 2.1 第169题：寻找数组中的多数元素
      • 2.2 第53题：计算最大连续子数组和
      • 2.3 第50题：实现幂运算函数Pow(x,n)

一、分治思想的原理

• 核心理念

分治算法的核心理念在于通过递归方式将原始问题划分为多个子问题，直至这些子问题符合终止条件，从而停止递归过程。通过对每个子问题逐一解决（通常采用相同策略），再将已解决的子问题结果进行整合，最终通过逐层合并的方式获得原始问题的解。

• 实施步骤

1. 分：将原问题递归地拆解为若干个具有相同性质且相互独立的子问题；
2. 治：对这些规模较小的子问题分别进行求解；
3. 合：将已经求解完