刷题笔记2-977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,数组总结

发布时间:2024年01月13日

刷题2-977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,数组总结

有序数组三个方法,长度最小的子数组两个方法,螺旋矩阵纯写(模拟行为)



1.有序数组的平方

题目链接
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 :
输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]

暴力破解

直接理解,先一个一个平方,再排序

#暴力破解
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i]*=nums[i]
        j=sorted(nums)  # nums.sort()不要变量接收-永久排序,sorted()需要-临时排序
        return j

暴力+列表推导

列表(list)推导:将循环和条件语句的功能结合到一行代码中
基础语法:

	[expression for item in iterable]
class Solution:
   def sortedSquares(self, nums: List[int]) -> List[int]:
       return sorted(i**2 for i in nums)

双指针

数组有序,平方之后的最大值在必定在数组两头。
比较两头大小,放入新列表。

  • float(‘inf’) 表示正无穷大
    双指针法
#双指针法
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l=0
        r=i=len(nums)-1
        result=len(nums)*[float('inf')] #长度*空间大小
        while l<=r:
            if nums[l]**2<nums[r]**2:
                result[i]=nums[r]**2
                r-=1
            else:
                result[i]=nums[l]**2
                l+=1
            i-=1
        return result
        

总结

使用三种方法解题,复习了双指针法


2.长度最小的子数组

题目链接
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl+1, …, numsr-1, numsr] ,并返回其长度。如果不存在符合条件的子数组,返回 0 。
示例 :
输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3] 是该条件下的长度最小的子数组。

暴力破解

目的:找到>=target的最小长度
本方法在leetcode超时

#暴力破解
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        lenth=len(nums)
        minlen=float('inf')
        for i in range(lenth):
            sum=0
            for j in range(i,lenth):
                sum+=nums[j]
                if sum>=target:
                    minlen=min(minlen,j-i+1)
                    break
        if minlen!=float('inf'):
            return minlen
        else:
            return 0

滑动窗口

  • 调节窗口开始(左)和结束位置(右)
  • 原理:小于右扩,大于左缩
    小扩大缩
#滑动窗口(双指针)
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        left=right=0
        minlen=float('inf')
        sum=0
        for right in range(len(nums)):#找第一个>=target
            sum+=nums[right]
            while sum>=target:
                minlen=min(minlen,right-left+1)
                sum-=nums[left] #减掉窗口最左侧
                left+=1
        if minlen!=float('inf'):
            return minlen
        else:
            return 0  

总结

滑动先画图,多了缩小,小了扩大,一直更新minlen


3.螺旋矩阵II

题目链接
给你一个正整数 n n n ,生成一个包含 1 到 n 2 n^2 n2 所有元素,且元素按顺时针顺序螺旋排列的 n ? n n*n n?n正方形矩阵 matrix 。
示例:
示例
输入:n = 3
输出:[[1,2,3],[8,9,4],[7,6,5]]

  • 怎么画这个正方形
  • 是左闭右开,还是左闭右闭
  • 要不要填充中心点nums[i][i](看奇偶)
#左闭右开
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        nums=[[0]*n for _ in range(n)] #生成n*n的0列表
        x=y=0
        count=1
        loop=mid=n//2
        for bias in range(1,loop+1): #循环圈数
            for j in range(y,n-bias): #i控制行,j控制列;左到右
                nums[x][j]=count
                count+=1
            for i in range(x,n-bias):#上到下
                nums[i][n-bias]=count
                count+=1
            for j in range(n-bias,y,-1):#右到左
                nums[n-bias][j]=count
                count+=1
            for i in range(n-bias,x,-1):#下到上
                nums[i][y]=count
                count+=1
            x+=1
            y+=1
        if n%2!=0: #n为奇数进行中心填充
            nums[mid][mid]=count
        return nums

总结

没具体算法,靠观察,画个图,不然太容易乱了


4.数组总结

借个图
总结

文章来源:https://blog.csdn.net/qq_46657538/article/details/135551684
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。