LeetCode 题目-28/35/53 (python实现)

作为要准备踏入码农行业的人来说，要准备校招，怎么能不去刷刷LeetCode呢？
28. 实现strStr()

• 题目要求：
  给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回 -1。

• 示例：

输入: haystack = \"hello\", needle = \"ll\"
输出: 2

输入: haystack = \"aaaaa\", needle = \"bba\"
输出: -1

• 分析：
  不断刷新头尾位置进行与needle比较，结束的标志是起始位置+needle长度>haystack.

class Solution:
    def strStr(self, haystack, needle):
        if needle not in haystack:
            return -1
        Nelenth= len(needle)
        Halengh =len(haystack)
        sta = 0
        i =0
        while sta+Nelenth<=Halengh:
            if haystack[sta:sta+Nelenth] == needle:
                i =i+1
                return sta
            sta = sta +1

1. 搜索插入位置

• 题目要求：
  给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。你可以假设数组中无重复元素

• 示例：

输入: [1,3,5,6], 5
输出: 2

输入: [1,3,5,6], 2
输出: 1

输入: [1,3,5,6], 7
输出: 4

输入: [1,3,5,6], 0
输出: 0

• 分析：
  方法一： 折半查找.

class Solution:
    def SearchInsert(self,nums,target):
        star =0
        end=len(nums)
        while star<end:
            mid =star+(end-star)//2
            if nums[mid]>target:
                end =mid
            elif nums[mid]<target:
                star =mid+1
            else:
                return mid
        return star

方法二：利用python内置函数

class Solution:
    def searchInsert(self, nums, target):
        if target in nums:
            return nums.index(target)
        else:
            nums.append(target)
            nums.sort()
            return nums.index(target)

1. 最大子序和

• 题目要求：
  给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

• 示例：

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

• 分析：
  方法一：暴力求解

class Solution:
    def maxsubarrt(self,nums):
        max_nums = nums[0]
        for i in range(0,len(nums)):
            sum =0
            for j in range(i,len(nums)):
                sum = sum +nums[j]
                if (sum>max_nums):
                    max_nums=sum
        return max_nums

方法二：扫描法

class Solution:
    def maxSubArray(self, nums):
        sum = 0
        max_num = nums[0]
        for num in nums:
            sum = sum+num
            if sum>max_num:
                max_num=sum
            if sum<0:
                sum = 0
        return max_num