Python小白 Leetcode刷题历程 No.31-No.35 下一个排列、最长有效括号、搜索旋转排序数组、在排序数组中查找元素的第一个和最后一个位置、搜索插入位置(有题干 有代码 有思路)

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],调用这个函数,并注意二分查找的边界值细节和特殊解即可。

©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 214,904评论 6 497
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 91,581评论 3 389
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 160,527评论 0 350
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 57,463评论 1 288
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 66,546评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 50,572评论 1 293
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,582评论 3 414
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,330评论 0 270
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,776评论 1 307
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,087评论 2 330
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,257评论 1 344
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,923评论 5 338
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,571评论 3 322
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,192评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,436评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,145评论 2 366
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,127评论 2 352

推荐阅读更多精彩内容