Python小白 Leetcode刷题历程 No.31-No.35 下一个排列、最长有效括号、搜索旋转排序数组、在排序数组中查找元素的第一个和最后一个位置、搜索插入位置
写在前面：
作为一个计算机院的大学生，总觉得仅仅在学校粗略的学习计算机专业课是不够的，尤其是假期大量的空档期，作为一个小白，实习也莫得路子，又不想白白耗费时间。于是选择了Leetcode这个平台来刷题库。编程我只学过基础的C语言，现在在自学Python，所以用Python3.8刷题库。现在我Python掌握的还不是很熟练，算法什么的也还没学，就先不考虑算法上的优化了，单纯以解题为目的，复杂程度什么的以后有时间再优化。计划顺序五个题写一篇日志，希望其他初学编程的人起到一些帮助，写算是对自己学习历程的一个见证了吧。
有一起刷LeetCode的可以关注我一下，我会一直发LeetCode题库Python3解法的，也可以一起探讨。
觉得有用的话可以点赞关注下哦，谢谢大家！
········································································································································································
题解框架：
1.题目，难度
2.题干,题目描述
3.题解代码（Python3（不是Python，是Python3））
4.或许有用的知识点（不一定有）
5.解题思路
6.优解代码及分析（当我发现有比我写的好很多的代码和思路我就会写在这里）
········································································································································································
No.31.下一个排列
难度：中等
题目描述：
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def nextPermutation(self, nums: List[int]) -> None:
flag=0
l=len(nums)
if l>=2:
for i in range(l-2,-1,-1):
if nums[i]<nums[i+1]:
flag=1
break
for j in range(l-1,i,-1):
if nums[j]>nums[i]:
nums[i],nums[j]=nums[j],nums[i]
nums[i+1:l]=nums[l-1:i:-1]
break
if flag==0:
nums.sort()
解题思路：
这个题用到的知识并不难，难就难在读题和思考写法。
这道题的题目每个字都能看懂，但第一遍连起来看却很难明白，其实这道题可以形象化的描述为：给定若干个数字，将其组合为一个整数。如何将这些数字重新排列，以得到下一个更大的整数？（“下一个更大的”即下一个数*指刚好比当前数大），这就很容易理解了。
之后是写法，我们想让一个数变大，只需要把低位的大数放到高位即可，为了使增加的幅度尽可能小尽可能小，我们应该从较低位开始寻找可以交换的数。设i<j,从左往右，当第i个数和第j刚好满足交换条件，此时一定有：第i个数后面的数递减，第j+1个数>第i个数>第j-1个数；故交换完第i个数后面的数还是递减。我们为了保证增加的幅度尽可能小，当我们增大了高位，需要使高位后面的数递增，所以我们再将交换后的i后面的数逆序即可，逆序用切片操作很容易实现。
No.32.最长有效括号
难度：困难
题目描述：
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s:
return 0
res=0
stack=[-1]
for i in range(len(s)):
if (s[i]=='('):
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
res=max(res,i-stack[-1])
return res
或许有用的知识点：
解决括号配对这类二元就近配对的问题，可以运用栈的思想。
这道题可以使用动态规划的方法。
解题思路：
运用栈的思想，先初始化栈stack=[−1]和结果res=0。遍历字符串，对每一个元素，若s[i]=="("，将当前位置索引加入stack，表示将当前左括号需要匹配，为不匹配索引；若s[i]==")"，出栈，stack.pop()，表示将对应左括号索引出栈，或者当栈中只有）时，将上一）索引出栈；若栈为空，表示之前的所有的（匹配成功，上一步出栈的是栈底的−1或者是前一个不匹配的），则更新栈底为当前))的索引，表示不匹配的位置；否则，说明和栈中的（匹配上了，此时更新最长序列res=max(res,i-stack[-1])，表示当前位置索引减去上一不匹配位置索引 和之前res中的较大值。
优解代码及分析：
优解代码（Python3.8）
class Solution:
def longestValidParentheses(self, s: str) -> int:
if not s:
return 0
l=len(s)
dp=[0]*l
res=0
for i in range(1,l):
if s[i]==')':
if s[i-1]=='(':
dp[i]=dp[i-2]+2
if s[i-1]==')' and i-dp[i-1]-1>=0 and s[i-dp[i-1]-1]=='(':
dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2
res=max(res,dp[i])
return res
分析：
动态规划的思想。
初始化dp=[0,...,0]，长度为n，dp[i]表示到i位置的最长有效括号的长度，显然，当s[i]s[i]为((时，dp[i]=0dp[i]=0
遍历字符串，遍历区间[1,n)，当s[i]==)时，若s[i-1]==(，说明这两个有效。则dp[i]=dp[i-2]+2；否则s[i-1]==)，此时找到上一匹配字符串的上一位i−dp[i−1]−1，若s[i-dp[i-1]-1]==(，说明s[i]可以和s[i-dp[i-1]-1]匹配，则dp[i]=dp[i-1]+dp[i-dp[i-1]-2]+2，表示当前位置的最长有效括号长度等于上一位有效括号的长度加上自身匹配的上一位的有效括号的长度加上2。
更新res，res=max(res,dp[i])，最后返回res。
该方法，时间复杂度：O(n)，空间复杂度：O(1)。
No.33.搜索旋转排序数组
难度：中等
题目描述：
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def search(self, nums: List[int], target: int) -> int:
def find_rotate_index(left,right): #一个用二分查找算法查找最小数(旋转点)的函数
if nums[left]<nums[right]:
return 0
while left <=right:
middle=(left+right)//2
if nums[middle]>nums[middle+1]:
return middle+1
else:
if nums[middle] >= nums[left]:
left=middle+1
else:
right=middle-1
def search(left,right): #一个用二分查找的基本函数
while left<=right:
middle=(left+right)//2
if nums[middle]==target:
return middle
else:
if nums[middle]<=target:
left=middle+1
else:
right=middle-1
return -1
n=len(nums)
if n==0:
return -1
if n==1:
return 0 if nums[0]==target else -1
rotate_index=find_rotate_index(0,n-1)
if nums[rotate_index]==target:
return rotate_index
if rotate_index==0:
return search(0,n-1)
if target<nums[0]:
return search(rotate_index,n-1)
return search(0,rotate_index)
或许有用的知识点：
看到了复杂度为O(logN)和有序数列，第一反应应该是使用「二分查找」来解决。
解题思路：
我们必须控制复杂度在O(logN)量级上，因此我们这道题不能采用遍历数组，只能对数组进行二分查找。我们可以先进行一次二分查找找出旋转点的位置（数列中最小数的索引），再判断要找的数再旋转点的左边还是右边，之后对该区域再进行一次二分查找找到目标值即可。
No.34.在排序数组中查找元素的第一个和最后一个位置
难度：中等
题目描述：
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def searchRange(self, nums: List[int], target: int) -> List[int]:
def search_min(left,right): #一个用二分查找的基本函数开始位置
if nums[left]==target:
return left
while left<right:
middle=(left+right)//2
if nums[middle]==target and nums[middle-1]<target:
return middle
else:
if nums[middle]>=target:
right=middle
else:
left=middle+1
if nums[right]==target:
return right
return -1
def search_max(left,right): #一个用二分查找的基本函数,查找结束位置
if nums[right]==target:
return right
while left<right:
middle=(left+right+1)//2
if nums[middle]==target and nums[middle+1]>target:
return middle
else:
if nums[middle]<=target:
left=middle
else:
right=middle-1
if nums[left]==target:
return left
return -1
l=len(nums)
if l==0 or (l==1 and nums[0]!=target) or (l==2 and nums[0]!=target and nums[1]!=target):
return [-1,-1]
if l==1 and nums[0]==target:
return [0,0]
if l==2:
if nums[0]==target and nums[1]==target:
return [0,1]
else:
return [0,0] if nums[0]==target else [1,1]
return [search_min(0,l-1),search_max(0,l-1)]
或许有用的知识点：
看到了复杂度为O(logN)和有序数列，第一反应应该是使用「二分查找」来解决。
解题思路：
这道题也是采用二分查找，只需要在基本的二分查找模板上加一些修改即可。首先定义search_min和search_max，search_min是通过二分查找找到开始位置，即满足nums[middle]==target and nums[middle-1]<target,而search_max是通过二分查找找到结束位置，即满足nums[middle]==target and nums[middle+1]>target。 之后调用这两个函数，并注意二分查找的边界值细节和特殊解即可。
No.35.搜索插入位置
难度：简单
题目描述：
在这里插入图片描述
题解代码（Python3.8）
class Solution:
def searchInsert(self, nums: List[int], target: int) -> int:
def search(left,right): #一个用二分查找的基本函数
if nums[left]>target or nums[right]<target:
return left if nums[left]>target else right+1
while left<=right:
middle=(left+right)//2
if nums[middle]==target or nums[middle-1]<target<nums[middle]:
return middle
else:
if nums[middle]<target:
left=middle+1
else:
right=middle-1
l=len(nums)
if l==0:
return 0
if l==1:
return 0 if nums[0]>=target else 1
if l==2:
if nums[1]<target:
return 2
else :
return 0 if nums[0]>=target else 1
return search(0,l-1)
或许有用的知识点：
看到了在有序数列中寻找目标值的索引位置，我们可以使用「二分查找」来降低复杂度。
解题思路：
这个题套用基本的二分查找的模板就行，定义一个二分查找函数，注意查找条件为nums[middle]==target or nums[middle-1]<target<nums[middle]，调用这个函数，并注意二分查找的边界值细节和特殊解即可。
网友评论