免费自助网站百度一下你就知道原版
版本说明
当前版本号[20231118]。
| 版本 | 修改说明 |
|---|---|
| 20231118 | 初版 |
目录
文章目录
- 版本说明
- 目录
- 搜索插入位置
- 题目
- 解题思路
- 代码思路
- 参考代码
- 最大子序和
- 题目
- 解题思路
- 代码思路
- 参考代码
搜索插入位置
题目
给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
解题思路
- 初始化左右指针l和r，分别指向数组的第一个元素和最后一个元素。
- 当左指针小于右指针时，执行以下操作：
a. 计算中间位置mid。
b. 如果中间位置的元素小于目标值，将左指针移动到mid+1。
c. 否则，将右指针移动到mid。 - 当循环结束时，检查左指针所指的元素是否小于目标值。如果是，则返回左指针+1；否则，返回左指针。
代码思路
-
定义一个名为Solution的类。
-
在Solution类中定义一个名为searchInsert的方法，接收两个参数：nums和target。其中nums是有序数组，target是要查找的目标值。
# 定义一个名为searchInsert的方法，接收两个参数：nums和targetdef searchInsert(self, nums, target): -
初始化左右指针l和r，分别指向数组的第一个元素和最后一个元素。
# 初始化左右指针l和rl, r = int(0), len(nums) - 1 -
当左指针小于右指针时，执行循环。
-
计算中间位置mid。
# 计算中间位置midmid = int((l + r) / 2) -
如果中间位置的值小于目标值，则将左指针移动到中间位置的右侧；否则，将右指针移动到中间位置。
# 如果中间位置的值小于目标值，则将左指针移动到中间位置的右侧if nums[mid] < target:l = mid + 1# 否则，将右指针移动到中间位置else:r = mid -
循环结束后，如果左指针所指的值小于目标值，则返回左指针的右侧位置加1；否则，返回左指针所指的位置。
# 如果左指针所指的值小于目标值，则返回左指针的右侧位置加1if nums[l] < target:return l + 1# 否则，返回左指针所指的位置return l -
如果当前模块是主模块，则创建一个Solution类的实例s，并调用searchInsert方法，打印结果。
# 如果当前模块是主模块，则执行以下代码
if __name__ == '__main__':# 创建一个Solution类的实例ss = Solution()# 调用searchInsert方法，并打印结果print(s.searchInsert([1,3,5,6],5))
参考代码
这段代码是一个二分查找算法的实现，用于在一个有序数组中查找目标值应该插入的位置。
class Solution:def searchInsert(self, nums, target):l, r = int(0), len(nums) - 1while l < r:mid = int((l + r) / 2)if nums[mid] < target:l = mid + 1else:r = midif nums[l] < target:return l + 1return l
if __name__ == '__main__':s = Solution()print (s.searchInsert([1,3,5,6],5))
最大子序和
题目
给定一个整数数组 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 <= 3 * 104
-105 <= nums[i] <= 105
进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。
解题思路
- 初始化两个变量 maxEndingHere 和 maxSofFar，分别解题思路：
- 初始化两个变量 maxEndingHere 和 maxSofFar，分别表示以当前元素结尾的最大子数组和和全局最大子数组和。初始值都设为数组的第一个元素。
- 遍历数组中除第一个元素之外的其他元素。
- 对于每个元素，更新 maxEndingHere 的值。maxEndingHere 的更新规则是：取 maxEndingHere + nums[i] 和 nums[i] 中的较大值。这样可以保证 maxEndingHere 始终表示以当前元素结尾的最大子数组和。
- 同时更新 maxSofFar 的值。maxSofFar 的更新规则是：取 maxEndingHere 和 maxSofFar 中的较大值。这样可以保证 maxSofFar 始终表示全局最大子数组和。
- 遍历结束后，返回 maxSofFar 作为结果。
代码思路
-
定义一个名为Solution的类，继承自object。
-
在Solution类中定义一个名为maxSubArray的方法，接收一个参数nums。
# 定义一个名为maxSubArray的方法，接收一个参数numsdef maxSubArray(self, nums): -
初始化两个变量maxEndingHere和maxSofFar，分别赋值为nums的第一个元素。
# 初始化两个变量maxEndingHere和maxSofFar，分别赋值为nums的第一个元素maxEndingHere = maxSofFar = nums[0] -
遍历nums列表中从第二个元素开始的所有元素。
# 遍历nums列表中从第二个元素开始的所有元素for i in range(1, len(nums)): -
对于每个元素，更新maxEndingHere的值，取当前值与nums[i]之和与nums[i]中的较大值。
# 更新maxEndingHere的值，取当前值与nums[i]之和与nums[i]中的较大值maxEndingHere = max(maxEndingHere + nums[i], nums[i]) -
同时更新maxSofFar的值，取maxEndingHere与maxSofFar中的较大值。
# 更新maxSofFar的值，取maxEndingHere与maxSofFar中的较大值maxSofFar = max(maxEndingHere, maxSofFar) -
遍历结束后，返回maxSofFar的值，即为整个数组的最大子数组和。
-
创建一个Solution类的实例s。
-
调用s的maxSubArray方法，传入参数nums，并打印结果。
# 创建一个Solution类的实例s s = Solution() # 调用s的maxSubArray方法，传入参数nums，并打印结果 print(s.maxSubArray(nums = [-2,1,-3,4,-1,2,1,-5,4]))
参考代码
这段代码是一个求解最大子数组和的算法。它使用了动态规划的思想，通过遍历数组并不断更新当前最大子数组和（maxEndingHere）和全局最大子数组和（maxSofFar），最终得到整个数组的最大子数组和。
class Solution(object):def maxSubArray(self, nums):maxEndingHere = maxSofFar = nums[0]for i in range(1, len(nums)):maxEndingHere = max(maxEndingHere + nums[i], nums[i])maxSofFar = max(maxEndingHere, maxSofFar)return maxSofFar
# %%
s = Solution()
print(s.maxSubArray(nums = [-2,1,-3,4,-1,2,1,-5,4]))