169. 多数元素
难度：简单题
题目描述
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 [n/2] 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3] 输出: 3
示例 2:
输入: [2,2,1,1,1,2,2] 输出: 2
- 解题思路
- 确定切分的终止条件
直到所有的子问题都是长度为 1 的数组，停止切分。 - 准备数据，将大问题切分为小问题
递归地将原数组二分为左区间与右区间，直到最终的数组只剩下一个元素，将其返回 - 处理子问题得到子结果，并合并
- 长度为 1 的子数组中唯一的数显然是众数，直接返回即可。
- 如果它们的众数相同，那么显然这一段区间的众数是它们相同的值。
- 如果他们的众数不同，比较两个众数在整个区间内出现的次数来决定该区间的众数
class Solution: def majorityElement(self, nums) -> int: # 使用递归进行解析 # 切分的终止条件 if not nums: return None if len(nums)==1: return nums[0] # # 【准备数据，并将大问题拆分为小问题】 left = self.majorityElement(nums[:len(nums)//2]) right = self.majorityElement(nums[len(nums)//2:]) # 【处理子问题，得到子结果】 # 【对子结果进行合并 得到最终结果】 if left == right: return left if nums.count(left) > nums.count(right): return left else: return right
53.最大子序列和
难度：简单
题目描述
给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
示例:
示例 1：
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
示例 2：
输入：nums = [1]
输出：1
示例 3：
输入：nums = [0]
输出：0
示例 4：
输入：nums = [-1]
输出：-1
示例 5：
输入：nums = [-100000]
输出：-100000
提示:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
- 解题思路
- 确定切分的终止条件
直到所有的子问题都是长度为 1 的数组，停止切分。 - 准备数据，将大问题切分为小问题
递归地将原数组二分为左区间与右区间，直到最终的数组只剩下一个元素，将其返回 - 处理子问题得到子结果，并合并
- 将数组切分为左右区间
- 对与左区间：从右到左计算左边的最大子序和
- 对与右区间：从左到右计算右边的最大子序和
- 由于左右区间计算累加和的方向不一致，因此，左右区间直接合并相加之后就是整个区间的和
- 最终返回左区间的元素、右区间的元素、以及整个区间(相对子问题)和的最大值
class Solution: def maxSubArray(self, nums) -> int: # 确立分割条件 n = len(nums) if n ==1: return nums[0] # 分割问题 left = self.maxSubArray(nums[:len(nums)//2]) rigth = self.maxSubArray(nums[len(nums)//2:]) # 处理小的问题得到结果 # 从右到左计算左边的最大子序和 max_l = nums[len(nums)//2-1] temp = 0 for i in range(len(nums)//2-1,-1,-1): temp += nums[i] max_l = max(temp,max_l) # 从左到右计算右边的最大子序和 max_r = nums[len(nums)//2] temp=0 for i in range(len(nums)//2,len(nums)): temp += nums[i] max_r = max(temp,max_r) # 【对子结果进行合并 得到最终结果】 # 返回三个中的最大值 return max(left,rigth,max_r+max_l)
50. 实现 pow()
难度：中等
题目： 实现 pow(x, n) ，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10
输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3
输出：9.26100
示例 3：
输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0
-231 <= n <= 231-1
-104 <= xn <= 104"""
解题思路
- 确定切分的终止条件
对n不断除以2，并更新n，直到为0，终止切分 - 准备数据，将大问题切分为小问题
对n不断除以2，更新 - 处理子问题得到子结果，并合并
x与自身相乘更新x- 如果
n%2 ==1
- 将
p乘以x之后赋值给p(初始值为1)，返回p
- 最终返回p
class Solution: def myPow(self, x: float, n: int) -> float: # 处理n为负值的情况 if n < 0 : x = 1/x n = -n if n ==0: # 确定不断切分的终止条件 return 1 # 准备数据，并将大问题拆分为小的问题 if n%2 ==1: # 处理小问题，得到子结果 p = x * self.myPow(x,n-1) # 对子结果进行合并 得到最终结果 return p return self.myPow(x*x,n/2) # 2*2 1 # #
