小工具知识网

当前位置: 首页 > 行业知识 > 算法打卡Day02

行业知识

算法打卡Day02

2026-11-20 02:11:43 来源:互联网转载

今���任务:

1)977.有序数组的平方

2)209.长度最小的子数组

3)59.螺旋矩阵II

977.有序数组的平方

题目链接:977. 有序数组的平方 - 力扣(LeetCode)

给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。

示例 1:

输入:nums = [-4,-1,0,3,10]

输出:[0,1,9,16,100]

解释:平方后,数组变为 [16,1,0,9,100]

排序后,数组变为 [0,1,9,16,100]

示例 2:

输入:nums = [-7,-3,2,3,11]

输出:[4,9,9,49,121]

文章讲解:代码随想录 (programmercarl.com)

视频讲解:双指针法经典题目 | LeetCode:977.有序数组的平方哔哩哔哩bilibili

思路:

1)重新创建一个列表l,

2)采用双指针从两边向中间遍历,比较指针位置的平方大小,大的放入新列表l的末尾,并且相应的指针向中间移动

3)直到两个指针重叠,则退出循环

def sortedSquares(nums: list[int]) -> list[int]:    k = len(nums) - 1    left, right = 0, k    l = list(range(k+1))    while left  int:    i = 0  # 起始指针    result = len(nums) + 1  # 存储符合要求的最小长度,先给一个比最大长度大的数    while i  int:    i, j = 0, 0  # 定义起始指针和终止指针    result = len(nums) + 1  # 存储符合要求的最小长度,先给一个比最大长度大的数    num = 0  # 区间累加和    while j = target:            subLength = j - i + 1            result = min(result, subLength)            num -= nums[i]            i += 1        j += 1    return 0 if result == len(nums) + 1 else result

感想:

暴力法遍历数组,移动初始指针,并循环计算当前初始指针下最小的长度,这里时间复杂度为O(n^2)

而滑动窗口只用一次循环,遍历数组,移动终止指针与开始指针,这样时间复杂度降为O(n)

59.螺旋矩阵II

题目链接:59. 螺旋矩阵 II - 力扣(LeetCode)

给定一个正整数 n,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的正方形矩阵。

示例1:

输入: 3

输出: [ [ 1, 2, 3 ],

       [ 8, 9, 4 ],

       [ 7, 6, 5 ] ]

       

示例2:

输入: 1

输出: [[1]]

文章讲解:代码随想录 (programmercarl.com)

视频讲解:

一入循环深似海 | LeetCode:59.螺旋矩阵II哔哩哔哩bilibili

思路:

我们可以按螺旋的方向,向矩阵里填充数据,先填最上的横边,再填入最右的竖边,在填入最下面横边,最后填入最左的竖边。

这题最麻烦的地方在于四个顶点的处理,为了统一,我们可以将范围定义为左闭右开。以最外层为例,即每条边填入n-1个数

1)定义上下左右四条边界,从外向里循环的层数(=n//2) 

   ①如果n为奇数,最后中心还有一个数[n//2][n//2],直接将最后的数给它

   ②如果n为偶数,则循环n//2层

2)从外向里循环,按顺时针顺序将1~n^2填进矩阵中

3)每进入下一层时,上下左右边界要相应的向里进1

 

def generateMatrix2(n: int) -> list[list[int]]:    matrix = [[0] * n for _ in range(n)]  # 定义一个n*n的矩阵    left, right, top, bottom = 0, n - 1, 0, n - 1  # 定义上下左右边界    loop = n // 2  # 需要走的圈数    count = 1    for l in range(loop):  # l从0开始        # 第一条边的循环(左上-->右上)        for col in range(left, right):            matrix[top][col] = count            count += 1        # 第二条边的循环(右上-->右下)        for row in range(top, bottom):            matrix [row] [right] = count            count += 1        # 第三条边的循环(右下--> 左下)        for col in range(right,left,-1):            matrix[bottom][col] = count            count += 1        # 第四条边的循环(左下--> 左上)        for row in range(bottom,top,-1):            matrix [row][left] = count            count += 1        left += 1        right -= 1        top += 1        bottom -= 1    if n%2 != 0:        matrix[loop][loop] = count    return matrix

感想:

这一题在上面思路下,代码中对于一些细节也有很多处理方式,需要格外小心。在我写的第一版代码中,没有定义上下左右边界,而是找出n、l与边界之间的关系,用n和l表示,稍不注意就会弄错,所以在测试容易出现索引溢出,后来按如上方法,代码便清晰不少。

上一篇:如何重启电脑安装系统?

下一篇:sf服务器怎么?