CSDN每日一题学习训练——Python版（搜索插入位置、最大子序和）

版本说明

当前版本号[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

解题思路

1. 初始化左右指针l和r，分别指向数组的第一个元素和最后一个元素。
2. 当左指针小于右指针时，执行以下操作：
   a. 计算中间位置mid。
   b. 如果中间位置的元素小于目标值，将左指针移动到mid+1。
   c. 否则，将右指针移动到mid。
3. 当循环结束时，检查左指针所指的元素是否小于目标值。如果是，则返回左指针+1；否则，返回左指针。

代码思路

1. 定义一个名为Solution的类。

2. 在Solution类中定义一个名为searchInsert的方法，接收两个参数：nums和target。其中nums是有序数组，target是要查找的目标值。

       # 定义一个名为searchInsert的方法，接收两个参数：nums和target
       def searchInsert(self, nums, target):
   1
   2

3. 初始化左右指针l和r，分别指向数组的第一个元素和最后一个元素。

    # 初始化左右指针l和r
           l, r = int(0), len(nums) - 1
   1
   2

4. 当左指针小于右指针时，执行循环。

5. 计算中间位置mid。

     # 计算中间位置mid
               mid = int((l + r) / 2)
   1
   2

6. 如果中间位置的值小于目标值，则将左指针移动到中间位置的右侧；否则，将右指针移动到中间位置。

    # 如果中间位置的值小于目标值，则将左指针移动到中间位置的右侧
               if nums[mid] < target:
                   l = mid + 1
               # 否则，将右指针移动到中间位置
               else:
                   r = mid
   1
   2
   3
   4
   5
   6

7. 循环结束后，如果左指针所指的值小于目标值，则返回左指针的右侧位置加1；否则，返回左指针所指的位置。

     # 如果左指针所指的值小于目标值，则返回左指针的右侧位置加1
           if nums[l] < target:
               return l + 1
           # 否则，返回左指针所指的位置
           return l
   1
   2
   3
   4
   5

8. 如果当前模块是主模块，则创建一个Solution类的实例s，并调用searchInsert方法，打印结果。

# 如果当前模块是主模块，则执行以下代码
if __name__ == '__main__':
    # 创建一个Solution类的实例s
    s = Solution()
    # 调用searchInsert方法，并打印结果
    print(s.searchInsert([1,3,5,6],5))
1
2
3
4
5
6

参考代码

这段代码是一个二分查找算法的实现，用于在一个有序数组中查找目标值应该插入的位置。

class Solution:
    def searchInsert(self, nums, target):
        l, r = int(0), len(nums) - 1
        while l < r:
            mid = int((l + r) / 2)
            if nums[mid] < target:
                l = mid + 1
            else:
                r = mid
        if nums[l] < target:
            return l + 1
        return l 
if __name__ == '__main__':
    s = Solution()
    print (s.searchInsert([1,3,5,6],5))    
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

最大子序和

题目

给定一个整数数组 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) 的解法，尝试使用更为精妙的 分治法 求解。

解题思路

1. 初始化两个变量 maxEndingHere 和 maxSofFar，分别解题思路：
2. 初始化两个变量 maxEndingHere 和 maxSofFar，分别表示以当前元素结尾的最大子数组和和全局最大子数组和。初始值都设为数组的第一个元素。
3. 遍历数组中除第一个元素之外的其他元素。
4. 对于每个元素，更新 maxEndingHere 的值。maxEndingHere 的更新规则是：取 maxEndingHere + nums[i] 和 nums[i] 中的较大值。这样可以保证 maxEndingHere 始终表示以当前元素结尾的最大子数组和。
5. 同时更新 maxSofFar 的值。maxSofFar 的更新规则是：取 maxEndingHere 和 maxSofFar 中的较大值。这样可以保证 maxSofFar 始终表示全局最大子数组和。
6. 遍历结束后，返回 maxSofFar 作为结果。

代码思路

1. 定义一个名为Solution的类，继承自object。

2. 在Solution类中定义一个名为maxSubArray的方法，接收一个参数nums。

       # 定义一个名为maxSubArray的方法，接收一个参数nums
       def maxSubArray(self, nums):
   1
   2

3. 初始化两个变量maxEndingHere和maxSofFar，分别赋值为nums的第一个元素。

     # 初始化两个变量maxEndingHere和maxSofFar，分别赋值为nums的第一个元素
           maxEndingHere = maxSofFar = nums[0]
   1
   2

4. 遍历nums列表中从第二个元素开始的所有元素。

     # 遍历nums列表中从第二个元素开始的所有元素
           for i in range(1, len(nums)):
   1
   2

5. 对于每个元素，更新maxEndingHere的值，取当前值与nums[i]之和与nums[i]中的较大值。

    # 更新maxEndingHere的值，取当前值与nums[i]之和与nums[i]中的较大值
               maxEndingHere = max(maxEndingHere + nums[i], nums[i])
   1
   2

6. 同时更新maxSofFar的值，取maxEndingHere与maxSofFar中的较大值。

   # 更新maxSofFar的值，取maxEndingHere与maxSofFar中的较大值
               maxSofFar = max(maxEndingHere, maxSofFar)
   1
   2

7. 遍历结束后，返回maxSofFar的值，即为整个数组的最大子数组和。

8. 创建一个Solution类的实例s。

9. 调用s的maxSubArray方法，传入参数nums，并打印结果。

   # 创建一个Solution类的实例s
   s = Solution()
   # 调用s的maxSubArray方法，传入参数nums，并打印结果
   print(s.maxSubArray(nums = [-2,1,-3,4,-1,2,1,-5,4]))
   1
   2
   3
   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]))
1
2
3
4
5
6
7
8
9
10