2024.8.31 Python，合并区间，用sort通过列表第一个元素给列表排序，三数之和，跳跃游戏

1.合并区间

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回 一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间 。
示例 1：
输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].
示例 2：
输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

class Solution:
    def merge(self, intervals: List[List[int]]) -> List[List[int]]:
        if intervals==[]:
            return intervals
        intervals.sort(key=lambda x: x[0])	#第二次报错
        res=[intervals[0]]
        for i in range(1,len(intervals)):
            changed=False
            for j in range(0,len(res)):
                if res[j][0]<=intervals[i][0]<=res[j][1] or \
                        res[j][0]<=intervals[i][1]<=res[j][1] or \
                        intervals[i][0]<=res[j][0]<=intervals[i][1] or \
                        intervals[i][0]<=res[j][1]<=intervals[i][1]:
                    res[j][0]=min(res[j][0],intervals[i][0])
                    res[j][1]=max(res[j][1],intervals[i][1])
                    changed=True
            if changed==False:
                res.append(intervals[i])			#第一次出错
        return res

上面是我的代码，中间报错了一次，第一次报错是因为我把res.append(intervals[i])那里写成了+=。你永远记住加等这个操作是在本层加元素进去才这样用的，如果要层套层一定是append，第二次出错是因为，测试用例里出现了这样的一个
输入：[[2,3],[4,5],[6,7],[8,9],[1,10]]
我的输出是：[[1,10],[1,10],[1,10],[1,10]]
造成这样的原因是，前面四个都没有找到合适的好兄弟来给他缩进去，导致最后一个救赎他们的进来了以后每一个都救赎了一遍，但是本身他们应该是一体的，也就是说，如果1,10早早来的话，就没这么多事了，所以我就不知道该怎么办了，一看答案，发现答案里有一个先排序的操作：intervals.sort(key=lambda x: x[0])，这个操作的含义是按照第一个元素先给所有的列表排序，现在我才懂了，列表的最后一个控制到底有没有连接，列表的第一个控制先后顺序，所以在这个操作中必须得先排序。最后我的代码过了，但是我的代码用时太久了，用了4秒才做完，所以这对整体而言是不合适的。

intervals.sort(key=lambda x: x[0])
#等效于
def get_first_element(x):
    return x[0]
# 使用自定义函数进行排序
intervals.sort(key=get_first_element)

lambda就相当于一个弱定义，在一些一行定义中使用，这个让我来做我可能做不到，但是可以学习一下
方法二：

class Solution:
	def merge(self,intervals:List[List[int]])->List[List[int]]:
		intervals.sort(key=lambda x:x[0])
		merged=[]
		for interval in intervals:
			if not merged or merged[-1][1]<interval[0]:
				merged.append(interval)
			else:
				merged[-1][1]=max(merged[-1][1],interval[1])
	
		return merged		

也就是说排序以后，可能性就已经排除了很多了，我的方法是和项目中每一个进行比较，如果有那就融合，因为我想的是给的排序是乱的，那么就没法确定谁先谁后，我当时心想，要是这玩意是有顺序的那就好了，但是我没想到的事，真的可以先排序再进行操作，对列表进行排序还是头一次见。

2.sort和sorted

一句话，sort是方法，作用于对象，sorted是函数，输出得有东西接住

# 使用 sort()
numbers = [3, 1, 4, 1, 5, 9]
numbers.sort()
print(numbers)  # 输出: [1, 1, 3, 4, 5, 9]

# 使用 sorted()
numbers = [3, 1, 4, 1, 5, 9]
sorted_numbers = sorted(numbers)
print(sorted_numbers)  # 输出: [1, 1, 3, 4, 5, 9]
print(numbers)         # 原列表未改变，输出: [3, 1, 4, 1, 5, 9]

3.三数之和

这个题在8.31的文章中写过，这个题的大概要求就是，在列表的一堆数字里找出三个数字，然后让他等于0，当时我的想法是通过组合combine来找出所有的三连的选项，然后计算每一组的答案，如果等于0，那就输出，但是这样的效率我不知道高不高，然后我昨天看这个双指针的答案的时候就有点不屑一顾，我心想这玩意能有啥说法，但是让chat写这个题的答案，也是这样的处理，说明这个方法就是最佳解法，所以我现在就来尝试一下

#以下代码是错误的
class Solution:
    def threeSum(self,nums:List[int])->List[List[int]]:
        n=len(nums)
        nums.sort()
        res=[]

        for first in range(n):
            if first>0 and nums[first]==nums[first-1]:
                continue
            target=-nums[first]
            
            for second in range(first+1,n):
                third=n-1			#注意这里			
                if second>first+1 and nums[second]==nums[second-1]:
                    continue
                while second<third and nums[second]+nums[third]!=target: #注意这里，不是错了，在我的代码中是对的，但是如果把third=n-1提出去这里就不对了，就得改成>target
                    third-=1
                if second==third:
                    continue		#注意这里
                if nums[second]+nums[third]==target:
                    res.append([nums[first],nums[second],nums[third]])
        return res

评价：
其实是个三指针问题了，但是这个题巧就巧在他可以使用sort来降低工作量，我上面的代码是学习这个题的代码思路自己写的，但是我写的过程可以通过大部分的测试，但是我的代码和纯枚举已经没什么太大区别了，所以要优化这个代码还是有说法的
代码逻辑如下：
1.排序，sort()方法，非常的合适
2.first用来遍历所有，在这里的判断非常的好，是我没想到的东西，他的逻辑是当first超过0以后，如果当前值和上一个值一样的话，那就直接continue，跳过这次循环
3.target等于-nums[first]这样就去找另外两个就好了。
4.进入遍历second的循环，这里因为列表已经是排序过了，所以在这里我不如second从左往右走，third从右往左走，等到这两个相遇的时候停下来，继续下一个first的循环，这样的好处是，你如果两个for循环从头到尾遍历，可以，当然可以，那你排序的意义是什么，既然排序了，那我两头效率快一倍。
5.while循环我写的其实还更符合直觉一些我写的是当这两个加起来不等于target的时候不停，当然，右边一定要在右边也是必须的，你third没必要到左边去遍历了，second已经走过了。
6.如果这两个重了，那就进行下一次循环
然后超时了，我昨天的代码只能过70%的量，今天的代码已经过了90%，最后还是超时了，那就需要优化代码

class Solution:
    def threeSum(self,nums:List[int])->List[List[int]]:
        n=len(nums)
        nums.sort()
        res=[]

        for first in range(n):
            if first>0 and nums[first]==nums[first-1]:
                continue
            target=-nums[first]
            third=n-1 #注意这里1
            for second in range(first+1,n):
                
                if second>first+1 and nums[second]==nums[second-1]:
                    continue
                while second<third and nums[second]+nums[third]>target:  #注意这里2
                    third-=1
                if second==third:
                    break   	#注意这里3
                if nums[second]+nums[third]==target:
                    res.append([nums[first],nums[second],nums[third]])
        return res

优化的部分：
1.我的third在second的里面，我保证每个second都有权利去找一次最大，所以保证了正确，但是你想，因为排序以后，他们都是递进式的，在固定了second的时候，缩小third，会出现从大于target到小于target的过程，而这个过程second也可以配合增加，这个时候你没必要把third从头再遍历一遍，所以就这个时候固定third，增加second是可以的，这里如果没看懂欢迎来评论区讨论
2.这个2，我中间报错了，我把third=n-1提出去以后，还用不等于判断while，然后就漏了一种可能性，那就是third没有找到相等的情况然后加起来已经比target小了，然后second增加了，third没有机会去往回走了，那就错过了，具体的测试用例是[-1,-1,0,1]，所以要保证加起来大于target，就能避免这种情况，要不然就是third=n-1放循环里面，再跑一次得了
3.我当时写的是continue，但是你想，再continue的话，second和third在之后的循环中，他们的和都会比target大，也就是进入了垃圾循环，所以之后的循环就没有意义了，所以我还不如直接退出这一层循环，该改first了。
这个题确实有点难想，在实际操作的时候也有很多问题，这个测试用例写的非常的好，非常的合适。

4.跳跃游戏

给定一个长度为 n 的 0 索引整数数组 nums。初始位置为 nums[0]。
每个元素 nums[i] 表示从索引 i 向前跳转的最大长度。换句话说，如果你在 nums[i] 处，你可以跳转到任意 nums[i + j] 处:
0 <= j <= nums[i]
i + j < n
返回到达 nums[n - 1] 的最小跳跃次数。生成的测试用例可以到达 nums[n - 1]。
下面是我写的版本

#错的
class Solution:
    def jump(self, nums: List[int]) -> int:
        n=len(nums)
        if n==1:
            return 0
        index=0
        step=0
        if nums[0]>=n:
            return 1
        while index<n-1:
            max_step=nums[index] 
            tmp_index=0
            tmp=[]
            while tmp_index<max_step:
                if index+tmp_index+1< n: #假设max_step是2那么tmp_index就可以取0,1
                    tmp.append(nums[index+tmp_index+1])  #+1是为了模拟跳数，因为没有0跳
                tmp_index+=1
            #此时的tmp已经好了，接下来要找tmp的最大值和最大下标
            max_value, max_index=self.find_max_with_index(tmp)
            step+=1
            index+=max_index+1
        return step



    def find_max_with_index(self,lst):
     # 假设最大值的索引为0
        max_value = max(lst)
        for i in range(len(lst)-1,-1,-1):
            if lst[i]==max_value:
                max_index=i
                break

        return max_value, max_index

下面是chatGPT根据我写的代码的修改版

class Solution:
    def jump(self, nums: List[int]) -> int:
        n = len(nums)
        if n == 1:
            return 0
        
        index = 0
        step = 0
        
        while index < n - 1:
            max_step = nums[index]
            if index + max_step >= n - 1:  # 如果当前可以直接跳到最后位置
                return step + 1
            
            # 找出从当前 index 开始，能够跳跃到的最远位置
            max_reach = 0
            next_index = index
            
            for i in range(1, max_step + 1):
                if index + i < n and index + i + nums[index + i] > max_reach:
                    max_reach = index + i + nums[index + i]
                    next_index = index + i
            
            index = next_index
            step += 1
        
        return step

更好的版本：贪心算法

class Solution:
    def jump(self, nums: List[int]) -> int:
        
        if len(nums)==1:
            return 0

        start,cnt=0,0
        
        while start<len(nums)-1:
            step=nums[start]
            if step+start>=len(nums)-1:#如果能直接跳到最后一位
                return cnt+1
           
            #默认从第一位开始跳
            next_index=start+1
            max_address=nums[next_index]+next_index
          
            #选择能达到的最大索引的作为跳点
            for i in range(start+2,start+step+1):
                if i+nums[i]>=max_address:
                    next_index=i
                    max_address=i+nums[i]
            
            start=next_index
            cnt+=1
        return cnt+1

我将在明天的文章中详细品鉴每一种代码