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,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)
- 最大子序和
-
题目要求:
给定一个整数数组 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