代码随想录学习Day 2

977.有序数组的平方

题目链接

讲解链接

题目要求对有序数组进行平方，返回的数组依然保持有序

暴力解法：将数组中每个元素直接平方后进行排序，时间复杂度为O(nlogn)

class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            nums[i] *= nums[i]
        nums = sorted(nums)
        return nums

双指针法：

数组本身是有序的，但由于其中存在负数，所以在平方之后不再有序。但由此可知，平方后数组的最大值一定在数组的左右两端，不可能出现在中间，所以可以考虑使用双指针法，使用两个指针指向数组的两端。同时定义一个和nums相同大小的数组，用来存储排序后的数据。两个指针从两端向中间遍历整个数组，将满足条件的元素以由大到小的顺序放入新数组的末尾，如下图所示： 

双指针解法代码如下： 

​class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l, r, k = 0, len(nums) - 1, len(nums) - 1  # l，r指向左右两端，k指向新数组尾端
        result = [float('inf')] * len(nums)  # 定义新列表存储结果，[float('inf')]意为无穷大
        while l <= r:  # 若取l<r则会导致l==r时的一个元素丢失
            if nums[l] ** 2 > nums[r] ** 2:
                result[k] = nums[l] ** 2
                l += 1
            else:
                result[k] = nums[r] ** 2
                r -= 1
            k -= 1  # 每次循环后需要让k向前移一位
        return result
 
​

209.长度最小的子数组

题目链接

讲解链接

暴力解法为设置两个for循环，然后不断的寻找符合条件的子序列，时间复杂度为O(n^2)，在力扣上会超时 。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        sum, result = 0, float('inf')  # result初值为无穷大，方便后续判断
        for i in range(len(nums)):  # i代表区间的起始位置
            sum = 0  # 每轮循环前将sum置为0
            for j in range(i, len(nums)):  # j代表区间的终止位置
                sum += nums[j]
                if sum >= target:  # 若子序列和>=目标
                    length = j - i + 1  # j-i+1为子序列长度
                    # length比之前的结果更小时才进行赋值
                    result = length if length < result else result  
                    break
        return result if result != float('inf') else 0  # 若result未被赋值则说明无子序列返回0

 此时考虑滑动窗口法

滑动窗口的意思就是不断调节子序列的初始位置和末尾位置，从而得到题目需要的结果。并且相较于暴力方法，滑动窗口只需要采用一个for循环来表示窗口的终止位置（若表示起始位置则与暴力法没有区别）。滑动窗口也是双指针法的一种。

重点：窗口中的内容是什么？如何确定窗口的起始位置和终止位置？ 

①窗口内是满足sum>=target的最短子序列。

②窗口的终止位置就是for循环的索引，起始位置则是如果当前窗口中的sum>target，那么窗口就需要向前移动，将窗口变小，移除窗口中的第一个值。

class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        i, sum, result = 0, 0, float('inf')
        for j in range(i, len(nums)):
            sum += nums[j]
            while sum >= target:  # 采用while的原因是窗口的起始点可能需要连续前移
                length = j - i + 1  # 子序列长度
                result = min(length, result)  # 取最小值
                sum -= nums[i]  # 窗口前移，删去起始点的值
                i += 1  # 起始点前移一位
        return result if result != float('inf') else 0

滑动窗口的精妙之处在于根据当前子序列和大小的情况，不断调节子序列的起始位置。从而将时间复杂度降为O(n)。 虽然是for循环中嵌套了while循环，但是每个元素只进行了移入和移出两次操作，所以共进行了2n次操作，时间复杂度为O(n)。

59.螺旋矩阵Ⅱ

题目链接

解题步骤：

①定义当前左右上下边界 left，right，top，buttom，初始值 num = 1，迭代终止值 tar = n * n；

②当 num <= tar 时，始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环，每次填入后执行 num += 1，得到下一个需要填入的数字；

③更新边界：例如从左到右填完后，上边界 t += 1，相当于上边界向内缩1;

④使用num <= tar而不是left < right || top < buttom作为迭代条件，是为了解决当n为奇数时，矩阵中心数字无法在迭代过程中被填充的问题。

本题代码如下：

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        martix = [[0] * n for _ in range(n)]  # 初始化一个n*n的全零二维矩阵
        left, right, top, buttom = 0, n - 1, 0, n - 1  # 定义上下左右的值，作为边界
        num, tar = 1, n * n  # num初始值为1，tar的值为n^2
        while num <= tar:  # 当n的值大于tar时终止循环
            for i in range(left, right + 1):  # 从左到右，right要+1，否则最右边一格填充不到
                martix[top][i] = num  # 给横坐标为top，纵坐标为i的区域填上数字，因为在这个过程中top的值是不变的，并且在下一次进行从左到右的循环过程中，填充的位置和top是相关的，例如第一次循环填充的是第0行，结束后top+1，那么下次填充的就变成了第1行，所以横坐标要设为top
                num += 1  # 每填充一格矩阵就给num+1
            top += 1  # 从左到右的循环完成后，第一行填充完毕，下次填充的就是从上到下，并且是从第二行开始的，所以需要给top值+1
            for i in range(top, buttom + 1):  # 从上到下，buttom同样要加1，否则最下面一格填充不到
                martix[i][right] = num  # 给横坐标为i，纵坐标为right的区域填上数字，纵坐标为right的理由同上，下次进行从上到下的循环时会向左缩进一列，所以纵坐标取righht
                num += 1  # 每填一格num+1
            right -= 1  # 理由同上
            for i in range(right, left - 1, -1):  # 从右到左，left的值记得-1，否则最左边一个填充不到，步长设置为-1，意为反向循环
                martix[buttom][i] = num  # 给横坐标为buttom，纵坐标为i的区域填上数字，因为在从右到左的过程中buttom的值是不变的，所以将其作为横坐标。在下次循环中，由于最下面一行已经填充完毕，所以要给buttom-1
                num += 1
            buttom -= 1  # 理由同上
            for i in range(buttom, top - 1, -1):  #从下到上，top值要-1
                martix[i][left] = num  # 给横坐标为i，纵坐标为left的区域填上数字，因为在从下到上的过程中横坐标是变化的，而纵坐标始终为left，而在从下到上填充完毕之后，下一次会向右移动一列，所以要给left的值+1
                num += 1
            left += 1
        return martix  # 返回结果