GIS与Climate

V1

2022/09/23阅读:7主题:默认主题

算法60天:Day 2-数组与双指针

代码随想录(截图自参考【1】)
代码随想录(截图自参考【1】)

本系列是代码随想录算法训练营的学习笔记之day2,主要记录一下刷题的过程,以及核心知识点和一些值的记录的问题。

代码随想录的资源都是免费的,具体可以看参考链接【1】。

今日知识点

数组理论基础:

  • 存放相同类型数据;
  • 在内存上是连续的(二维数组视语言而定);
  • 数组元素不能删除,只能覆盖;

今日题目

  1. 有序数组的平方(977)

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

链接:https://leetcode.cn/problems/squares-of-a-sorted-array/

解题思路

  • 原题目说非递减顺序,所以排序后的数组最大值应该是从原数组的两端得到的(负值平方后也许是最大值);
  • 输出的结果要求是非递减顺序,所以可以用双指针法,一直比较原始数组两端的数据平方后的大小,把大的放在输出结果的最后(所以这里要预先构造好相应的数组用来存放数据);
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l,r,k = 0, len(nums)-1,len(nums)-1
        re = [0]*(k+1)
        while l<=r:
            ls,rs = nums[l]**2,nums[r]**2
            if ls>rs:
                re[k]=ls
                k -= 1
                l += 1
            else:
                re[k]=rs
                k -= 1
                r -= 1
        return re 
  1. 长度最小的子数组(209)

给定一个含有 n 个正整数的数组和一个正整数 target 。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr],并返回其长度。如果不存在符合条件的子数组,返回 0 。

链接:https://leetcode.cn/problems/minimum-size-subarray-sum/

解题思路

  • 注意题目说的,数组都是正整数,target也是正整数;
  • 找出满足条件的连续子数组,因为是连续数组,所以用双指针法(头尾);
  • 返回的是新数组的长度,不是新数组!
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        l,r = 0, len(nums)-1
        index = 0
        sum_ = 0
        res = float('inf')

        while l<=r:
            sum_ += nums[l]
            while sum_>= target:
                res = min(res,l-index+1)
                sum_ = sum_ - nums[index]
                index += 1
            l +=1

        return 0 if index==0 else res

  • 这里的双指针指的是最小子数组的首尾两个指针;
  • 满足条件的可能有很多个子串,我们要找到长度最小的那个,所以在内层的while循环中要记录下当前的子串长度(l-index+1),并且与上一个满足条件的长度进行(res)对比;
  • 返回的时候要注意,需要考虑到没有满足条件的情况(返回0);
  1. 螺旋矩阵(59)

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

链接:https://leetcode.cn/problems/spiral-matrix-ii/

解题思路

  • 正整数n,生成n**2个元素,注意预先构造矩阵;
  • 元素是顺时针排序。
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        re = [[0]*n for _ in range(n)]
        stx,sty = 0,0
        loop = n//2
        count = 1

        for offset in range(1,loop+1):
            for i in range(sty,n-offset):
                re[stx][i] = count
                count += 1
            for i in range(stx,n-offset):
                re[i][n-offset] = count
                count +=1
            for i in range(n-offset,sty,-1):
                re[n-offset][i] = count
                count += 1
            for i in range(n-offset,stx, -1):
                re[i][sty] = count
                count += 1
            stx += 1
            sty += 1
        if n%2==1:
            re[n//2][n//2]=n**2
        return re

  • 要理解螺旋是通过什么变量来控制的(stx,sty和offset);
  • offset要从1开始,且能取到n的一半(非常重要)!
  • 如果n是奇数,要注意给最中间的元素进行赋值。

补充知识点

  1. 下换线_的作用是什么?

占位。

今日思考

  1. 对于区间的遍历时,用for还是while更好?

对于python,个人感觉用for更好,因为可以用range,如果用while,记得要在最后+1。

  1. 二分查找的时候区间的划分其本质是什么?

遍历到所有元素,做到查无遗漏。(再次牢记!)

  1. 螺旋矩阵为什么要设置offset?

这样子可以保存每次在遍历下标的时候四条边是一样的长度,且边界值更好确定。

参考

【1】代码随想录:https://programmercarl.com/

分类:

后端

标签:

数据结构与算法

作者介绍

GIS与Climate
V1

公众号:GIS与Climate,欢迎关注