给定一个非负整数数组 nums ，你最初位于数组的 第一个下标 。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
判断你是否能够到达最后一个下标。

通过规范代码，可以使得相同思路卡进时间限制

即满足条件立马结束遍历

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        is_tra_from_fir=[False]*len(nums)
        is_tra_from_fir[0]=True
        for i in range(len(nums)):
            #flag=False
            for j in range(1,nums[i]+1):
                if i+j<len(nums):
                    is_tra_from_fir[i+j]=is_tra_from_fir[i+j] or is_tra_from_fir[i]
                if is_tra_from_fir[-1]==True:
                    return True 
        
        return is_tra_from_fir[-1]

image.png

• 标解

class Solution:
    def canJump(self, nums: List[int]) -> bool:
        n, rightmost = len(nums), 0
        for i in range(n):
            if i <= rightmost:
                rightmost = max(rightmost, i + nums[i])
                if rightmost >= n - 1:
                    return True
        return False

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/jump-game/solution/tiao-yue-you-xi-by-leetcode-solution/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

给你一个非负整数数组 nums ，你最初位于数组的第一个位置。
数组中的每个元素代表你在该位置可以跳跃的最大长度。
你的目标是使用最少的跳跃次数到达数组的最后一个位置。
假设你总是可以到达数组的最后一个位置。

class Solution:
    def jump(self, nums: List[int]) -> int:
        #init big list
        opt_list=[len(nums)]*len(nums)
        opt_list[0]=0
        for i in range(len(nums)):
            for j in range(1,nums[i]+1):
                if i+j <len(nums):
                    opt_list[i+j]=min(opt_list[i]+1,opt_list[i+j])
        return opt_list[-1]

image.png

给定两个由一些 闭区间 组成的列表，firstList 和 secondList ，其中 firstList[i] = [starti, endi] 而 secondList[j] = [startj, endj] 。每个区间列表都是成对 不相交 的，并且 已经排序 。
返回这 两个区间列表的交集 。
形式上，闭区间 [a, b]（其中 a <= b）表示实数 x 的集合，而 a <= x <= b 。
两个闭区间的 交集 是一组实数，要么为空集，要么为闭区间。例如，[1, 3] 和 [2, 4] 的交集为 [2, 3] 。

class Solution:
    def intervalIntersection(self, firstList: List[List[int]], secondList: List[List[int]]) -> 
List[List[int]]:
        handel_f,f_l,handel_s,s_l=0,len(firstList),0,len(secondList)
        ans=[]
        while handel_f<f_l and handel_s<s_l:
            if secondList[handel_s][0]<=firstList[handel_f][0]<=secondList[handel_s][1]:
                if firstList[handel_f][1]<=secondList[handel_s][1]:
                    ans.append(firstList[handel_f])
                    handel_f+=1
                else:
                    ans.append([firstList[handel_f][0],secondList[handel_s][1]])
                    handel_s+=1
            elif firstList[handel_f][0]<=secondList[handel_s][0]<=firstList[handel_f][1]:
                if secondList[handel_s][1]<=firstList[handel_f][1]:
                    ans.append(secondList[handel_s])
                    handel_s+=1
                else:
                    ans.append([secondList[handel_s][0],firstList[handel_f][1]])
                    handel_f+=1
                
            elif firstList[handel_f][1]<secondList[handel_s][0]:
                handel_f+=1
            elif secondList[handel_s][1]<firstList[handel_f][0]:
                handel_s+=1
        return ans

image.png

有时候一开始思路错了先别放弃，可能该思路中有可以保留的部分，又可以修正的部分

---

写代码过程中尤其是优化问题，即通过在遍历中优化答案

一定要注意初始化与动作顺序

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

class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        max_record,record=nums[0],nums[0]
        for i in nums[1:]:
            if record<0:
                record=0
            record+=i
            max_record=max(max_record,record)
        return max_record

image.png

纪念8月份的第一个击败100%用户

一个字符串如果没有 三个连续 相同字符，那么它就是一个 好字符串 。

给你一个字符串 s ，请你从 s 删除 最少 的字符，使它变成一个 好字符串 。
请你返回删除后的字符串。题目数据保证答案总是 唯一的 。

class Solution:
    def makeFancyString(self, s: str) -> str:
        cnt,mey=1,s[0]
        ans=s[0]
        for i in s[1:]:
            if i==mey:
                if cnt+1==3:
                    pass
                else:
                    ans+=i
                    cnt+=1
            else:
                cnt=1
                ans+=i
                mey=i
        return ans

image.png

关于252周赛的最后一题

第一自己的数据结构没有维护好，因为没有使用参数记忆，运行中修改了字典，使得逻辑乱了（对边修改边使用自己，其中对待不停修改key对应的值的操作尤为谨慎，便修改便用）

• 对代码与时间复杂度进行更高的要求，此时如果涉及排序问题，不考虑字典，因为字典的无序性

你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。
对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标 i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：
你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
在这条路线中，必须包含第 i 个障碍。
你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。
返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/find-the-longest-valid-obstacle-course-at-each-position
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。