台州市网站制作,wordpress 粘贴,同源大厦 网站建设,企业网站建设杭州公司版本说明
当前版本号[20231118]。
版本修改说明20231118初版
目录 文章目录 版本说明目录搜索插入位置题目解题思路代码思路参考代码 最大子序和题目解题思路代码思路参考代码 搜索插入位置
题目
给定一个排序数组和一个目标值#xff0c;在数组中找到目标值#xff0c;…版本说明
当前版本号[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. 如果中间位置的元素小于目标值将左指针移动到mid1。 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]))
