官方学习文档：datawhalechina
往期task01：枚举算法链接：Datawhale Leecode基础算法篇 task01：枚举算法
递归算法
递归简介
递归（Recursion）：指的是一种通过重复将原问题分解为同类的子问题而解决的方法。在绝大数编程语言中，可以通过在函数中再次调用函数自身的方式来实现递归。
举个简单的例子来了解一下递归算法。比如阶乘的计算方法在数学上的定义为：
根据阶乘计算方法的数学定义，我们可以使用调用函数自身的方式来实现阶乘函数 fact(n) ，实现代码可以写作：
def fact(n):
if n == 0:
return 1
return n * fact(n - 1)我们可以把「递归」分为两个部分：「递推过程」和「回归过程」。
- 递推过程：指的是将原问题一层一层地分解为与原问题形式相同、规模更小的子问题，直到达到结束条件时停止，此时返回最底层子问题的解。
- 回归过程：指的是从最底层子问题的解开始，逆向逐一回归，最终达到递推开始时的原问题，返回原问题的解。
「递推过程」和「回归过程」是递归算法的精髓。从这个角度来理解递归，递归的基本思想就是： 把规模大的问题不断分解为子问题来解决。
同时，因为解决原问题和不同规模的小问题往往使用的是相同的方法，所以就产生了函数调用函数自身的情况，这也是递归的定义所在。
从数学归纳法的角度解释递归（比较抽象）
递归的数学模型其实就是「数学归纳法」。这里简单复习一下数学归纳法的证明步骤：
- 证明当 n=b （
为基本情况，通常为 0 或者 1）时，命题成立。
- 证明当 n>b 时，假设 n=k 时命题成立，那么可以推导出 n=k+1 时命题成立。这一步不是直接证明的，而是先假设 n=k 时命题成立，利用这个条件，可以推论出 n=k+1 时命题成立。
通过以上两步证明，就可以说：当 n>=b 时，命题都成立。
我们可以从「数学归纳法」的角度倒推来解释递归：
- 递归终止条件：数学归纳法第一步中的 n=b，可以直接得出结果。
- 递推过程：数学归纳法第二步中的假设部分（假设 n=k 时命题成立），也就是假设我们当前已经知道了 n=k 时的计算结果。
- 回归过程：数学归纳法第二步中的推论部分（根据 n=k 推出 n=k+1），也就是根据下一层的结果，计算出上一层的结果。
事实上，数学归纳法的思考过程也正是在解决某些数列问题时，可以使用递归算法的原因。比如阶乘、数组前 n 项和、斐波那契数列等等。
递归三步走
上面说过，递归的基本思想就是： 把规模大的问题不断分解为子问题来解决。 那么，我们可以按照这个思想来书写递归，具体步骤如下：
1. 写出递推公式：找到将原问题分解为子问题的规律，并且根据规律写出递推公式。
2. 明确终止条件：推敲出递归的终止条件，以及递归终止时的处理方法。
递归的终止条件也叫做递归出口。在写出了递推公式之后，就要考虑递归的终止条件是什么。如果没有递归的终止条件，函数就会无限地递归下去，程序就会失控崩溃了。通常情况下，递归的终止条件是问题的边界值。
3. 将递推公式和终止条件翻译成代码：
- 定义递归函数（明确函数意义、传入参数、返回结果等）。
- 书写递归主体（提取重复的逻辑，缩小问题规模）。
- 明确递归终止条件（给出递归终止条件，以及递归终止时的处理方法）。
根据上述递归书写的步骤，我们就可以写出递归算法的代码了。递归算法的伪代码如下：
def recursion(大规模问题):
if 递归终止条件:
递归终止时的处理方法
return recursion(小规模问题)递归的注意点
避免栈溢出
在程序执行中，递归是利用堆栈来实现的。每一次递推都需要一个栈空间来保存调用记录，每当进入一次函数调用，栈空间就会加一层栈帧。每一次回归，栈空间就会减一层栈帧。由于系统中的栈空间大小不是无限的，所以，如果递归调用的次数过多，会导致栈空间溢出。
为了避免栈溢出，我们可以在代码中限制递归调用的最大深度来解决问题。当递归调用超过一定深度时（比如 100）之后，不再进行递归，而是直接返回报错。
当然这种做法并不能完全避免栈溢出，也无法完全解决问题，因为系统允许的最大递归深度跟当前剩余的栈空间有关，事先无法计算。
如果使用递归算法实在无法解决问题，我们可以考虑将递归算法变为非递归算法（即递推算法）来解决栈溢出的问题。
避免重复运算
在使用递归算法时，还可能会出现重复运算的问题。
比如斐波那契数列的定义是：
其对应的递归过程如下图所示：
从图中可以看出：想要计算 f(5)，需要先计算 f(3) 和 f(4)，而在计算 f(4) 时还需要计算 f(3)，这样 f(3) 就进行了多次计算。同理 f(0)、f(1)、f(2) 都进行了多次计算，就导致了重复计算问题。
为了避免重复计算，我们可以使用一个缓存（哈希表、集合或数组）来保存已经求解过的 f(k) 的结果，这也是动态规划算法中的做法。当递归调用用到 f(k) 时，先查看一下之前是否已经计算过结果，如果已经计算过，则直接从缓存中取值返回，而不用再递推下去，这样就避免了重复计算问题。
递归的应用
斐波那契数
题目链接
描述：给定一个整数 n。
要求：计算第 n 个斐波那契数。
说明：
- 斐波那契数列的定义如下：
- f(0)=0,f(1)=1。
- f(n)=f(n−1)+f(n−2)，其中 n>1。
示例：
- 示例 1：
输入：n = 2 输出：1 解释：F(2) = F(1) + F(0) = 1 + 0 = 1
- 示例 2：
输入：n = 3 输出：2 解释：F(3) = F(2) + F(1) = 1 + 1 = 2
解题思路
根据我们的递推三步走策略，写出对应的递归代码。
- 写出递推公式：
- 明确终止条件：
。
- 翻译为递归代码：
- 定义递归函数：
fib(self, n)表示输入参数为问题的规模 n，返回结果为第 n 个斐波那契数。 - 书写递归主体：
return self.fib(n - 1) + self.fib(n - 2)。 - 明确递归终止条件：
if n == 0: return 0if n == 1: return 1
- 定义递归函数：
代码：
class Solution:
def fib(self, n: int) -> int:
if n == 0:
return 0
if n == 1:
return 1
return self.fib(n - 1) + self.fib(n - 2)复杂度分析
- 时间复杂度：
。具体证明方法参考递归求斐波那契数列的时间复杂度，不要被网上的答案误导了 - 知乎。
- 空间复杂度：
。每次递归的空间复杂度是 O(1)， 调用栈的深度为 n，所以总的空间复杂度就是 O(n)。
二叉树的最大深度
题目链接
描述：给定一个二叉树的根节点 root。
要求：找出该二叉树的最大深度。
说明：
- 二叉树的深度：根节点到最远叶子节点的最长路径上的节点数。
- 叶子节点：没有子节点的节点。
示例：
- 示例 1：
输入：[3,9,20,null,null,15,7]
对应二叉树
3
/ \
9 20
/ \
15 7
输出：3
解释：该二叉树的最大深度为 3
解题思路
根据递归三步走策略，写出对应的递归代码。
- 写出递推公式：当前二叉树的最大深度 = max(当前二叉树左子树的最大深度, 当前二叉树右子树的最大深度) + 1。（即先得到左右子树的高度，在计算当前节点的高度）
- 明确终止条件：当前二叉树为空。
- 翻译为递归代码：
- 定义递归函数：
maxDepth(self, root)表示输入参数为二叉树的根节点 root，返回结果为该二叉树的最大深度。 - 书写递归主体：
return max(self.maxDepth(root.left),self.maxDepth(root.right))+1。 - 明确递归终止条件：
if not root: return 0
- 定义递归函数：
代码
class Solution:
def maxDepth(self, root: Optional[TreeNode]) -> int:
if not root:
return 0
return max(self.maxDepth(root.left), self.maxDepth(root.right)) + 1复杂度分析
- 时间复杂度：
- 空间复杂度：
练习
爬楼梯
题目链接
描述：假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。现在给定一个整数 n。
要求：计算出有多少种不同的方法可以爬到楼顶。
说明：
- 1≤n≤45。
示例：
- 示例 1：
输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶- 示例 2：
输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶代码：
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
return self.climbStairs(n - 1) + self.climbStairs(n - 2)
函数self.climbStairs(n)表示到达n的方法数
这里简单使用递归的代码如上，但因为没有避免大量的重复计算，会导致超时的情况。而使用缓存来保存已经求解过的 f(k) 的结果来避免重复计算的动态规划代码如下：
class Solution:
def climbStairs(self, n: int) -> int:
dp = [0 for _ in range(n + 1)]
dp[0] = 1
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i - 1] + dp[i - 2]
return dp[n]
这段代码的空间复杂度为O(n)，而在此基础上进一步使用滚动数组可将空间复杂度减至O(1)，不需要额外的空间来存储整个数组，其代码如下：
class Solution:
def climbStairs(self, n: int) -> int:
if n == 1:
return 1
if n == 2:
return 2
one_step_before = 2
two_steps_before = 1
for i in range(3, n + 1):
current = one_step_before + two_steps_before
two_steps_before = one_step_before
one_step_before = current
return one_step_beforeone_step_before：表示到达n-1层的方法数。two_steps_before：表示到达n-2层的方法数。
- 计算到达当前层
i的方法数current，等于到达i-1层的方法数加上到达i-2层的方法数。 - 更新
two_steps_before和one_step_before，准备计算下一层。
翻转二叉树
题目链接：
描述：给定一个二叉树的根节点 root。
要求：将该二叉树进行左右翻转。
说明：
- 树中节点数目范围在 [0,100] 内。
- −100≤Node.val≤100。
示例：
- 示例 1：
输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]- 示例 2：
输入：root = [2,1,3]
输出：[2,3,1]根据我们的递推三步走策略，写出对应的递归代码。
-
写出递推公式：
- 递归遍历翻转左子树。
- 递归遍历翻转右子树。
- 交换当前根节点
root的左右子树。
-
明确终止条件：当前节点
root为None。
代码：
class Solution:
def invertTree(self, root: Optional[TreeNode]) -> Optional[TreeNode]:
if not root:
return None
left = self.invertTree(root.left)
right = self.invertTree(root.right)
root.left = right
root.right = left
return root
反转链表
题目链接：
描述：给定一个单链表的头节点 head。
要求：将该单链表进行反转。可以迭代或递归地反转链表。
说明：
- 链表中节点的数目范围是 [0,5000]。
- −5000≤Node.val≤5000。
示例：
- 示例 1：
输入：head = [1,2,3,4,5]
输出：[5,4,3,2,1]
解释：
翻转前 1->2->3->4->5->NULL
反转后 5->4->3->2->1->NULL
思路：
-
使用三个指针
cur、pre和next进行迭代。pre指向cur前一个节点位置。初始时，pre指向None，cur指向head。 -
将
pre和cur的前后指针进行交换，通过next进行中间交替，指针更替顺序为：- 使用
next指针保存当前节点cur的后一个节点，即next = cur.next； - 断开当前节点
cur的后一节点链接，将cur的next指针指向前一节点pre，即cur.next = pre； pre向前移动一步，移动到cur位置，即pre = cur；cur向前移动一步，移动到之前next指针保存的位置，即cur = next。
- 使用
-
继续执行第 2 步。直到
cur遍历到链表末尾，即cur == None，时，pre所在位置就是反转后链表的头节点，返回新的头节点pre。
代码：
class Solution:
def reverseList(self, head: ListNode) -> ListNode:
pre = None
cur = head
while cur != None:
next = cur.next
cur.next = pre
pre = cur
cur = next
return pre
这种方法的优点是空间复杂度比较低，只有O(1)。
反转链表2
描述：给定单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right。
要求：反转从位置 left 到位置 right 的链表节点，返回反转后的链表 。
说明：
- 链表中节点数目为
n。 - 1≤n≤500。
- −500≤Node.val≤500。
- 1≤left≤right≤n。
示例：
- 示例 1：
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]- 示例 2：
输入：head = [5], left = 1, right = 1
输出：[5]
代码：
# Definition for singly-linked list.
class ListNode:
def __init__(self, val=0, next=None):
self.val = val
self.next = next
class Solution:
def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
# 如果left == right，不需要反转
if left == right:
return head
dummy = ListNode(0)
dummy.next = head
prev = dummy
# 移动prev到left-1的位置
for _ in range(left - 1):
prev = prev.next
# 移动cur到left的位置
cur = prev.next
# 反转从left到right之间的节点
for _ in range(right - left):
temp = cur.next
cur.next = temp.next
temp.next = prev.next
prev.next = temp
return dummy.next首先，如果 left 和 right 相等，表示不需要反转，直接返回原链表。
然后创建虚拟头节点
dummy = ListNode(0)
dummy.next = head
prev = dummy 使用 dummy 节点的主要目的是简化边界条件的处理。在反转链表的一部分时，我们可能会涉及到链表的头部。如果没有 dummy 节点，我们需要额外处理这些边界条件，使得代码更加复杂。有了 dummy 节点之后，不管链表的头部是否需要反转，我们都可以统一处理。
最后逐步反转节点
for _ in range(right - left):
temp = cur.next
cur.next = temp.next
temp.next = prev.next
prev.next = temp一开始先保存待反转的节点，然后断开当前节点与待反转节点的连接，最后将 temp 插入到 prev 的后面，以此循环。
第K个语法符号
题目链接：
描述：给定两个整数 n 和 k。我们可以按照下面的规则来生成字符串：
- 第一行写上一个 0。
- 从第二行开始，每一行将上一行的 0 替换成 01，1 替换为 10。
要求：输出第 n 行字符串中的第 k 个字符。
说明：
- 1≤n≤30。
- 1≤k≤2n−1。
示例：
- 示例 1：
输入: n = 2, k = 1
输出: 0
解释:
第一行: 0
第二行: 01Copy to clipboardErrorCopied- 示例 2：
输入: n = 4, k = 4
输出: 0
解释:
第一行：0
第二行：01
第三行：0110
第四行：01101001
代码：
class Solution:
def kthGrammar(self, n: int, k: int) -> int:
if n == 1:
return 0
if k % 2 == 1:
return self.kthGrammar(n - 1, (k + 1) // 2)
else:
return abs(self.kthGrammar(n - 1, k // 2) - 1)
解决这道题，首先必须发现一个重要的数学规律，第 k 个数字是由上一位对应位置上的数字生成的，并且在数值上根据奇偶数位的不同也有相应的联系。
- k 在奇数位时，由上一行 (k+1)/2 位置的值生成。且与上一行 (k+1)/2 位置的值相同；
- k 在偶数位时，由上一行 k/2 位置的值生成。且与上一行 k/2 位置的值相反。
0 对应 01，1 对应10，而每次替换都是相当于乘2，所以替换时前面一定有偶数个数，而替换出的前一位就正是奇数位，观察规律，正与原数相同，而后一位同理，必是偶数位且与原数相反。
分治算法
分治算法简介
分治算法（Divide and Conquer）：字面上的解释是「分而治之」，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
简单来说，分治算法的基本思想就是： 把规模大的问题不断分解为子问题，使得问题规模减小到可以直接求解为止。
从定义上来看，分治算法的思想和递归算法的思想是一样的，都是把规模大的问题不断分解为子问题。
其实，分治算法和递归算法的关系是包含与被包含的关系，可以看做： 递归算法∈分治算法。
分治算法从实现方式上来划分，可以分为两种：「递归算法」和「迭代算法」。
分治算法能够解决的问题，一般需要满足以下 4 个条件：
- 可分解：原问题可以分解为若干个规模较小的相同子问题。
- 子问题可独立求解：分解出来的子问题可以独立求解，即子问题之间不包含公共的子子问题。
- 具有分解的终止条件：当问题的规模足够小时，能够用较简单的方法解决。
- 可合并：子问题的解可以合并为原问题的解，并且合并操作的复杂度不能太高，否则就无法起到减少算法总体复杂度的效果了。
分治算法三步走
使用分治算法解决问题主要分为 3 个步骤：
- 分解：把要解决的问题分解为成若干个规模较小、相对独立、与原问题形式相同的子问题。
- 求解：递归求解各个子问题。
- 合并：按照原问题的要求，将子问题的解逐层合并构成原问题的解。
其中第 1 步中将问题分解为若干个子问题时，最好使子问题的规模大致相同。
第 2 步的「递归求解各个子问题」是指按照同样的分治策略进行求解，即将这些子问题分解为更小的子子问题来进行求解。就这样一直分解直到分解出来的子问题简单到只用常数操作时间即可解决为止。
在完成第 2 步之后，然后我们再按照递归算法中回归过程的顺序，由底至上地将子问题的解合并起来，逐级上推构成原问题的解。
其对应的伪代码为：
def divide_and_conquer(problems_n): # problems_n 为问题规模
if problems_n < d: # 当问题规模足够小时，直接解决该问题
return solove() # 直接求解
problems_k = divide(problems_n) # 将问题分解为 k 个相同形式的子问题
res = [0 for _ in range(k)] # res 用来保存 k 个子问题的解
for problem_k in problems_k:
res[i] = divide_and_conquer(problem_k) # 递归的求解 k 个子问题
ans = merge(res) # 合并 k 个子问题的解
return ans # 返回原问题的解分治算法的复杂度分析
分治算法中，在不断递归后，最后的子问题将变得极为简单，可在常数操作时间内予以解决，其带来的时间复杂度在整个分治算法中的比重微乎其微，可以忽略不计。所以，分治算法的时间复杂度实际上是由「分解」和「合并」两个部分构成的。
一般来讲，分治算法将一个问题划分为 a 个形式相同的子问题，每个子问题的规模为 n/b，则总的时间复杂度的递归表达式可以表示为：
其中，每次分解时产生的子问题个数是 a ，每个子问题的规模是原问题规模的 1/b，分解和合并 a 个子问题的时间复杂度是 f(n)。
这样，求解一个分治算法的时间复杂度，就是求解上述递归表达式。关于递归表达式的求解有多种方法，这里我们介绍一下比较常用的「递推求解法」和「递归树法」。
递推求解法：
根据问题的递归表达式，通过一步步递推分解推导，从而得到最终结果。
以「归并排序算法」为例，接下来我们通过递推求解法计算一下归并排序算法的时间复杂度。
我们得出归并排序算法的递归表达式如下：
根据归并排序的递归表达式，当 n>1 时，可以递推求解：
T(n)=2×T(n/2)+O(n)
=2×(2×T(n/4)+O(n/2))+O(n)
=4×T(n/4)+2×O(n)
=8×T(n/8)+3×O(n)
=……
=×T(n/
)+x×O(n)
递推最终规模为 1，令 ，则
则：
T(n)=n×T(1)+log2n×O(n)
=n+log2n×O(n)
=O(n×log2n)
则归并排序的时间复杂度为 O(n×log2n)。
递归树法：
递归树求解方式其实和递推求解相同，只不过递归树能够更能够形象地表达每层分解的节点和每层产生的时间成本。
使用递归树法计算时间复杂度的公式为：
时间复杂度=叶子数×T(1)+成本和=×T(1)+x×O(n)。
我们还是以「归并排序算法」为例，通过递归树法计算一下归并排序算法的时间复杂度。
归并排序算法的递归表达式如下：
其对应的递归树如下图所示。
因为 n=，则 x=log2n，则归并排序算法的时间复杂度为：
。
分治算法的应用
归并排序
题目链接：
描述：给定一个整数数组 nums。
要求：对该数组升序排列。你必须在 不使用任何内置函数 的情况下解决问题，时间复杂度为 O(nlog(n))，并且空间复杂度尽可能小。
说明：
- 1≤nums.length≤5∗104。
- −5∗104≤nums[i]≤5∗104。
示例：
输入 nums = [5,2,3,1] 输出 [1,2,3,5]
我们使用归并排序算法来解决这道题。
- 分解：将待排序序列中的 n 个元素分解为左右两个各包含 n2 个元素的子序列。
- 求解：递归将子序列进行分解和排序，直到所有子序列长度为 1。
- 合并：把当前序列组中有序子序列逐层向上，进行两两合并。
使用归并排序算法对数组排序的过程如下图所示。
代码
class Solution:
def sortArray(self, nums: List[int]) -> List[int]:
if len(nums)<=1:
return nums
mid = len(nums)//2
mid_left=self.sortArray(nums[0:mid])
mid_right=self.sortArray(nums[mid:])
return self.sortMerge(mid_left,mid_right)
def sortMerge(self,mid_left,mid_right):
arr=[]
while mid_left and mid_right:
if mid_left[0]<=mid_right[0]:
arr.append(mid_left.pop(0))
else:
arr.append(mid_right.pop(0))
while mid_left:
arr.append(mid_left.pop(0))
while mid_right:
arr.append(mid_right.pop(0))
return arr
首先先对数组进行分解，通过计算出给定数组的中心位置mid将数组通过递归分解函数sortArray分为两部分，直到数组长度小于等于1，再通过合并函数sortMerge逐步回推将两部分排序并合并。
pop(index)方法用来移除列表中的某个元素，并返回该元素。默认情况下，如果不指定索引值，pop()不带参数时会移除并返回最后一个元素。但是，在您的例子中，pop(0)指定了索引0，意味着它移除并返回列表的第一个元素。
sortMerge方法的实现逻辑为：
-
初始化一个空列表
arr用于存放最终的排序结果。 -
使用
while循环来处理mid_left 和 mid_right中的元素，当这两个数组都有元素时进入循环。 -
在循环内部，比较 mid_left 和 mid_right 首元素的大小。取较小的那个元素（如果相等，则取 mid_left 的元素）添加到
arr列表的末尾，并从原数组中移除该元素（使用pop(0)方法）。这样可以保证每次都是较小的元素先被添加到arr中，从而保证了arr的有序性。 -
当 mid_left 或 mid_right 中的一个为空时，退出上面的循环。这意味着剩下的另一个数组中的所有元素都比已经合并的元素大，因此可以直接将剩下的元素追加到
arr的末尾。 -
最后，返回排序好的列表
arr。
二分查找
题目链接：
描述：给定一个含有 n 个元素有序的（升序）整型数组 nums 和一个目标值 target。
要求：返回 target 在数组 nums 中的位置，如果找不到，则返回 −1。
说明：
- 假设 nums 中的所有元素是不重复的。
- n 将在 [1,10000] 之间。
- −9999≤nums[i]≤9999。
示例：
输入 nums = [-1,0,3,5,9,12], target = 9 输出 4 解释 9 出现在 nums 中并且下标为 4
与其他分治题目不一样的地方是二分查找最小子问题的解就是原问题的解，所以不用进行合并过程。
其过程如下图所示：
代码：
class Solution:
def search(self, nums: List[int], target: int) -> int:
left,right = 0,len(nums)-1
while left<=right:
mid=(left+right)//2
if nums[mid]<target:
left=mid+1
elif nums[mid]>target:
right=mid-1
else:
return mid
return -1首先将数组分为长度相等的两部分，因为给定的是有序数组，所以可以通过比较target和数组中间位置的值来判断target属于较小还是较大的部分还是等于中间位置的值，这样就可以正确查找target
练习
Pow(x,n)
题目链接： 0050. Pow(x, n)
描述：给定浮点数 x 和整数 n。
要求：计算 x 的 n 次方（即 xn）。
说明：
示例：
- 示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
- 示例 2：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
代码：
class Solution:
def myPow(self, x: float, n: int) -> float:
if x == 0.0:
return 0.0
if n<0:
n=-n
x=1/x
while n!=0:
if n%2==0:
return (self.myPow(x,n/2))*(self.myPow(x,n/2))
if n%2==1:
return x*(self.myPow(x,(n-1)/2))*(self.myPow(x,(n-1)/2))
return 1这段代码的实现逻辑是将n分为奇数偶数两种情况分开讨论，递归求解，但是它会重复计算相同的部分，尤其是在指数较大时，这种重复计算会使得时间复杂度增加，容易造成超时。下面是对它的改进：
class Solution:
def myPow(self, x: float, n: int) -> float:
if x == 0.0:
return 0.0
res = 1
if n < 0:
x = 1/x
n = -n
while n:
if n & 1:
res *= x
x *= x
n >>= 1
return res
关键在于这部分的实现：
while n:
if n & 1:
res *= x
x *= x
n >>= 1解释代码逻辑：
1. while n:
这是主循环，只要 n 不为 0，就会一直运行。每次循环结束时，n 都会被除以 2（实际上是右移一位），因此最终 n 会减小至 0，循环也就结束了。
2. if n & 1:
这里使用了位运算符 & 来检测 n 是否为奇数。n & 1 的结果只有两种情况：
- 如果
n是奇数，那么n的二进制表示的最右边一位是1，n & 1的结果就是1，条件成立。 - 如果
n是偶数，那么n的二进制表示的最右边一位是0，n & 1的结果就是0，条件不成立。
3. res *= x
如果 n 是奇数，那么需要将当前的 x 乘入结果 res 中。这是因为，如果 n 是奇数，那么 x的n次方可以写作 x的n-1次方乘以 x，其中 n−1一定是偶数，所以在接下来的循环中 n 会变成 n−1 的一半，此时还需要额外乘上一个 x 来补偿。
4. x *= x
无论 n 是奇数还是偶数，都需要计算 x 的平方。这是因为 x 的n次方可以通过 x 的平方来更快地计算。所以这里让 x 自乘，实际上是为下一步的计算做准备。
5. n >>= 1
这是对 n 进行右移操作，相当于除以 2。这样做的目的是为了逐步减少 n 的值，直到 n 变为 0，这样就能逐渐逼近 x的n次方的计算。
多数元素
问题链接：多数元素
描述：给定一个大小为 n 的数组 nums。
要求：返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在多数元素。
说明：
- n==nums.length。
- 1≤n≤5∗104。
- −109≤nums[i]≤109。
示例：
- 示例 1：
输入：nums = [3,2,3] 输出：3
- 示例 2：
输入：nums = [2,2,1,1,1,2,2] 输出：2
代码：
class Solution:
def majorityElement(self, nums: List[int]) -> int:
numDict = dict()
for num in nums:
if num in numDict:
numDict[num] += 1
else:
numDict[num] = 1
max = float('-inf')
max_index = -1
for num in numDict:
if numDict[num] > max:
max = numDict[num]
max_index = num
return max_index
首先想到的是利用哈希表解决，通过遍历数组 nums,用哈希表统计每个元素 num 出现的次数后遍历一遍哈希表，找出元素个数最多的元素即可。
现在想想怎么用分治算法解决：
class Solution:
def majorityElement(self, nums: List[int]) -> int:
def get_mode(low, high):
if low == high:
return nums[low]
mid = low + (high - low) // 2
left_mod = get_mode(low, mid)
right_mod = get_mode(mid + 1, high)
if left_mod == right_mod:
return left_mod
left_mod_cnt, right_mod_cnt = 0, 0
for i in range(low, high + 1):
if nums[i] == left_mod:
left_mod_cnt += 1
if nums[i] == right_mod:
right_mod_cnt += 1
if left_mod_cnt > right_mod_cnt:
return left_mod
return right_mod
return get_mode(0, len(nums) - 1)
这是多数元素Leecode算法笔记给出的思路代码，如果一个子数组的众数是1，出现3次，另一个子数组的众数是2，出现3次，但是两个子数组加起来3出现了4次，在两个子数组各出现了2次，对于这种情况，它只是统计了左右众数各自的出现次数，最后也只会返回左右众数中的一个，这怎么就能符合实际情况呢？感觉有点问题
这个问题是由于众数和多数元素的概念不同导致的：
众数（Mode）
众数是指在一个数据集中出现次数最多的数值。众数可以有一个或多个，也可能不存在。具体来说：
- 定义：众数是在一组数据中出现频率最高的数值。
- 特点：数据集中可以有一个众数、多个众数或没有众数。
- 应用场景：统计学中用于描述数据分布的中心趋势之一。
多数元素（Majority Element）
多数元素是指在一个数组或序列中，出现次数超过数组长度一半的元素。具体来说：
- 定义：多数元素是在一个数组中出现次数超过数组长度一半的元素。
- 特点：如果存在多数元素，那么它是唯一的。
- 应用场景：计算机科学中用于解决某些特定问题，如在分布式系统中达成一致意见。
比较：
唯一性：
- 众数可以有多个（如果出现频率最高的数值不止一个）。
- 多数元素如果存在，则是唯一的。
频率要求：
- 众数只需是最频繁出现的数值，没有频率的具体要求。
- 多数元素必须出现次数超过数组长度的一半。
所以对于11122 33322序列，不存在所谓的多数元素，并且题目中也给出提示：
给定的数组总是存在多数元素
最大子数组和
题目链接：最大子数组和
描述：给定一个整数数组 nums。
要求：找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
说明：
- 子数组：指的是数组中的一个连续部分。
- 1≤nums.length≤105。
- −104≤nums[i]≤104。
示例：
- 示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4] 输出：6 解释：连续子数组 [4,-1,2,1] 的和最大，为 6。
- 示例 2：
输入：nums = [1] 输出：1
代码：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
size = len(nums)
dp = [0 for _ in range(size)]
dp[0] = nums[0]
for i in range(1, size):
if dp[i - 1] < 0:
dp[i] = nums[i]
else:
dp[i] = dp[i - 1] + nums[i]
return max(dp)
首先想到的是用动态规划解决，状态 dp[i] 代表以第 i 个数结尾的连续子数组的最大和。这时我们发现：
- 如果 dp[i−1]<0，则「第 i−1 个数结尾的连续子数组的最大和」+「第 i 个数的值」<「第 i 个数的值」，即：dp[i−1]+nums[i]<nums[i]。所以，此时 dp[i] 应取「第 i 个数的值」，即 dp[i]=nums[i]。
- 如果 dp[i−1]≥0，则「第 i−1 个数结尾的连续子数组的最大和」 +「第 i 个数的值」 >= 第 i 个数的值，即：dp[i−1]+nums[i]≥nums[i]。所以，此时 dp[i] 应取「第 i−1 个数结尾的连续子数组的最大和」+「 第 i 个数的值」，即 dp[i]=dp[i−1]+nums[i]。
归纳一下，状态转移方程为：
这样以此类推就可以返回正确的最大子数组和，现在我们尝试用这节教的分治算法来解决这个问题：
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
def max_sub_array(low, high):
if low == high:
return nums[low]
mid = low + (high - low) // 2
leftMax = max_sub_array(low, mid)
rightMax = max_sub_array(mid + 1, high)
total = 0
leftTotal = -inf
for i in range(mid, low - 1, -1):
total += nums[i]
leftTotal = max(leftTotal, total)
total = 0
rightTotal = -inf
for i in range(mid + 1, high + 1):
total += nums[i]
rightTotal = max(rightTotal, total)
return max(leftMax, rightMax, leftTotal + rightTotal)
return max_sub_array(0, len(nums) - 1)
这是Leetcode算法笔记的思路，它将数组 nums 根据中心位置分为左右两个子数组。则具有最大和的连续子数组可能存在以下 3 种情况：
- 具有最大和的连续子数组在左子数组中。
- 具有最大和的连续子数组在右子数组中。
- 具有最大和的连续子数组跨过中心位置，一部分在左子数组中，另一部分在右子树组中。
那么要求出具有最大和的连续子数组的最大和，则分别对上面 3 种情况求解即可。具体步骤如下：
- 将数组 nums 根据中心位置递归分为左右两个子数组，直到所有子数组长度为 1。
- 长度为 1 的子数组最大和肯定是数组中唯一的数，将其返回即可。
- 求出左子数组的最大和 leftMax。
- 求出右子树组的最大和 rightMax。
- 求出跨过中心位置，一部分在左子数组中，另一部分在右子树组的子数组最大和 leftTotal+rightTotal。
- 求出 3、4、5 中的最大值，即为当前数组的最大和，将其返回即可。
注意：这里在求解leftTotal+rightTotal时是由中心向两边扩张的，由此可以得出正确的结果。
由于篇幅限制，我们今天的学习之旅就到这里，我们下期再见！
标签：return,递归,nums,Leecode,Datawhale,算法,20%,数组 From： https://blog.csdn.net/MrBlackmzq/article/details/142363521