代码编织梦想

Leetcode 977. 有序数组的平方

​题目描述:给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
 
题目链接:https://leetcode.cn/problems/squares-of-a-sorted-array/

解题思路:首先,最直观的解法就是平方后排序(这里可以复习一下排序算法)。 其次,双指针可以降低时间复杂度,使用双指针要明确指针代表的意思,该题是非递减顺序排序的整数数组,所以两个指针应分别指向数组起始位置和末尾,进而判断对应位置的数字平方大小。
 

1. 暴力解法

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

2. 双指针

  • 双指针定义:
    • left指针:指向数组起始位置。
    • right指针:指向数组结尾位置。
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        n = len(nums)
        left, right = 0, n - 1
        temp = n - 1
        ans = [-1] * n

        while left <= right:
            if nums[left] ** 2 > nums[right] ** 2:
                ans[temp] = nums[left] ** 2
                left += 1
            else:
                ans[temp] = nums[right] ** 2
                right -= 1
            temp -= 1
        return ans
  • 注意:双指针可降低时间复杂度,使用双指针要明确指针的含义。

 

Leetcode 209. 长度最小的子数组

题目描述:给定一个含有n个正整数的数组和一个正整数target。找出该数组中满足其和≥ target 的长度最小的连续子数组 [nums_l, nums_l+1, ..., nums_r-1, nums_r] ,并返回其长度。如果不存在符合条件的子数组,返回 0
 
题目链接:https://leetcode.cn/problems/minimum-size-subarray-sum/

解题思路:使用两个for循环的暴力解法在本题会超时,所以考虑双指针,题目中说要找出满足条件的连续数组,进而想到不断的调节子序列的起始位置和终止位置,从而得出要想结果的滑动窗口。使用滑动窗口要注意明确窗口内是什么如何移动窗口起始位置和结束位置
 
1. 滑动窗口

  • 窗口定义:满足其和 ≥ s 的长度最小的连续子数组
  • 窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。
  • 窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。
class Solution:
    def minSubArrayLen(self, target: int, nums: List[int]) -> int:
        n = len(nums)
        s = 0
        left = 0
        length = float("inf")

        for right in range(n):
            s += nums[right]
            while s >= target:
                length = min(length, right - left + 1)
                s -= nums[left]
                left += 1
        
        return 0 if length == float("inf") else length
  • 注意:滑动窗口的精妙之处在于根据当前子序列和大小的情况,不断调节子序列的起始位置。从而将O(n^2)暴力解法降为O(n)。
     

Leetcode 59. 螺旋矩阵II

题目描述:给你一个正整数n,生成一个包含 1n^2 所有元素,且元素按顺时针顺序螺旋排列的n x n正方形矩阵 matrix
 
题目链接:https://leetcode.cn/problems/spiral-matrix-ii/

  • 解题思路:本题是模拟题,按题目要求模拟即可。模拟过程中需要注意边界问题
    • 定义当前左右上下边界 l, r, t, b,初始值 num = 1,迭代终止值 tar = n * n
    • num <= tar 时,始终按照 从左到右 从上到下 从右到左 从下到上 填入顺序循环,每次填入后:执行 num += 1,得到下一个需要填入的数字;
    • 更新边界:例如从左到右填完后,上边界 t += 1,相当于上边界向内缩 1。
    • 使用num <= tar而不是l < r || t < b作为迭代条件,是为了解决当n为奇数时,矩阵中心数字无法在迭代过程中被填充的问题。

1. 模拟-设定边界(Leetcode Krahets大神解法)

class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        matrix = [[0] * n for _ in range(n)]
        left, right, top, bottom = 0, n - 1, 0, n - 1
        num, target = 1, n * n

        while num <= target:
            # left to right:
            for i in range(left, right + 1):
                matrix[top][i] = num
                num += 1
            top += 1

            # top to bottom:
            for i in range(top, bottom + 1):
                matrix[i][right] = num
                num += 1
            right -= 1

            # right to left:
            for i in range(right, left - 1, -1):
                matrix[bottom][i] = num
                num += 1
            bottom -= 1

            # bottom to top:
            for i in range(bottom, top - 1, -1):
                matrix[i][left] = num
                num += 1
            left += 1
        
        return matrix

 

总结

  1. 双指针是很好的降低时间复杂度的方法,使用双指针要明确指针定义。
  2. 滑动窗口也是双指针的一种类型,所以也能够降低时间复杂度。使用滑动窗口要明确窗口内是什么,如何移动窗口起始位置和结束位置。
  3. 模拟题需要注意边界问题。

 
参考链接:
代码随想录-有序数组的平方
代码随想录-长度最小的子数组
代码随想录-螺旋矩阵II
Leetcode题解-Krahets大神模拟设定边界法

版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/qq_37972695/article/details/128660326

代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵ii_chauncey1995的博客-爱代码爱编程

代码随想录算法训练营第二天|977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II 一. 继续数组相关算法练习977.有序数组的平方暴力解法双指针解法 209.长度最小的子数组暴力解法(此方法

代码随想录算法训练营第二天| 977. 有序数组的平方、209. 长度最小的子数组、59. 螺旋矩阵 ii_mxg_zzu的博客-爱代码爱编程

代码随想录算法训练营第二天| 977. 有序数组的平方、209. 长度最小的子数组、59. 螺旋矩阵 II 977. 有序数组的平方209. 长度最小的子数组59. 螺旋矩阵 II 977. 有序数组的平方

随想录算法训练营第二天|977.有序数组、209.长度最小的子数组、59.螺旋矩阵ii_西久的博客-爱代码爱编程

977.有序数组的平方 题目描述 :给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1: 输入:nums = [-4,-1,0,3,10] 输出:

代码随想录算法训练营第二天 | 977. 有序数组的平方、209. 长度最小的子数组、59.螺旋矩阵ii_lei00764的博客-爱代码爱编程

目录 知识点 有序数组的平方 最小长度的子数组 螺旋矩阵II (难) 知识点 有关vector的使用,在前一天里有详细介绍 这里主要补充关于用vector定义二维数组的方法 我们可以使用 vector<T> v(n, val) 来初始化一个vector对象,这里的T可以是任意类型,包括vector本身 所以,我们就可以

代码随想录算法训练营第一天 | 977. 有序数组的平方、209. 长度最小的子数组、59. 螺旋矩阵 ii_小刘很ok的博客-爱代码爱编程

977.有序数组的平方 题目链接: 977.有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1: 输入:nums = [-

代码随想录算法训练营第二天| 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵ii_小葱抹抹酱的博客-爱代码爱编程

代码随想录算法训练营第二天 977.有序数组的平方209.长度最小的子数组59.螺旋矩阵II 977.有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,

代码随想录算法训练营第二天| 977.有序数组的平方,209长度最小的子数组,59螺旋矩阵||_牧野如烟的博客-爱代码爱编程

977.有序数组的平方 题目链接:977.有序数组的平方 记录:看到题目的第一眼想法:     一看到题,可以,直接平方就可以了。平方后的没有升序了怎么办?弄个排序。    如果是按照上面说的平方后排序这样的思路,得到的时间复杂度是O(nlogn)的时间。因为遍历一遍并把平方后的数据赋到新数组,用时O(n),然后排序,排序效果最好的是快排O(nlo

代码随想录算法训练营第二天|977.有序数组的平方、209.长度最小的子数组、59.螺旋矩阵_陌璃算的博客-爱代码爱编程

题目链接:977. 有序数组的平方 - 力扣(LeetCode) 👉🏻 第一次自己做题的思路,时间复杂度较大,仅仅记录,读者可以直接跳过此部分? 思路: 本题中因为我们是返回每个数字的平方组成的以递增顺序排序的

代码随想录算法训练营第二天 | 977.有序数组的平方、209.长度最小的子数组、59.螺旋矩阵ii-爱代码爱编程

今天依旧是数组知识的训练,加油💪 977.有序数组的平方 题目:给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 示例 1: 输入:nums = [

代码随想录算法训练营第二天| 977.有序数组的平方, 209.长度最小的子数组, 59.螺旋矩阵ii-爱代码爱编程

代码随想录算法训练营第二天| 977.有序数组的平方, 209.长度最小的子数组, 59.螺旋矩阵II 题目链接: 977.有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的

代码随想录算法训练营第二天| 977. 有序数组的平方、209.长度最小的子数组、59.螺旋矩阵ii 。-爱代码爱编程

977. 有序数组的平方 题目链接 给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。  暴力解法: class Solution { public int[] sortedSquares(int[] nums) { for(int i=0;i<

代码随想录算法训练营第二天| 977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵ii-爱代码爱编程

977.有序数组的平方 1.暴力 这个时间复杂度是 O(n + nlogn), 可以说是O(nlogn)的时间复杂度,但为了和下面双指针法算法时间复杂度有鲜明对比,我记为 O(n + nlog n) 2.双指针 此时的时间复杂度为O(n),相对于暴力排序的解法O(n + nlog n)还是提升不少的。 这里还是说一下,大家不必太在意leetcod

代码随想录算法训练营第二天|977.有序数组的平方 209.长度最小的子数组 59.螺旋矩阵ii-爱代码爱编程

有序数组的平方 题目链接: 特点: 细节: 语言知识: 题解: 长度最小的子数组 题目链接: 细节/手法: 语言知识: 题解: 螺旋矩阵II 特点/解法概述: 细节/手法: 语言知识: 题解: 有序数组的平方 题目链接: 有效数组的平方 特点: 最大值在两边 可以用双指针,逐步由两边向中间合拢, 就得到

代码随想录算法训练营第二天| 977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵 ii-爱代码爱编程

代码随想录算法训练营第二天| 977. 有序数组的平方 209. 长度最小的子数组 59. 螺旋矩阵 II LeetCode977. 有序数组的平方自己实现题解总结 LeetCode209. 长度最小的子数组自

代码随想录算法训练营第二天| 977. 有序数组的平方、209. 长度最小的子数组、59. 螺旋矩阵 ii-爱代码爱编程

977. 有序数组的平方 思路:可以采用暴力解法和双指针解法 暴力解法:先将数组中每个元素平方,然后再对数组中的元素排序。双指针解法:由该数组中的元素按非递减排列的原则可以知道平方后最大的元素存在于数组的两端,从左端到中间是从大到小的顺序,而从右端到中间也是从大到小的顺序。此时可以考虑双指针法,i指向起始位置,j指向终止位置,从两端的最大值开始进行比较

边双连通分量-爱代码爱编程

如果还未学习强连通分量,建议先学习强连通分量的tarjan算法强连通分量(tarjan算法) 1,定义 相对于在单向图的强连通分量,双连通分量是在无向图中,无向图有一个特点,可以以任何一个点为根节点建dfs树 割边(桥):删去一条边,会增加图中的强连通分量(即可以使原来连通的部分变成两半(不连通)) 割点 :同理割边,不过是删边 如果删去一条边,

阿拉伯数转中文与英文[找到规律,抽象问题,转换成代码]-爱代码爱编程

阿拉伯数转中文与英文 前言一、阿拉伯数字转换1、阿拉伯数字转中文a、案例b、解决方案 2、阿拉伯数转英文a、案例b、解决方案 总结参考文献 前言 如果思考算法的解法方案是一种模拟,那么这一般不

leetcode(string)基础10道汇总-爱代码爱编程

LeetCode(String)基础10道汇总 1.LeetCode(String) 1108. Defanging an IP Address破坏 IP 地址 2.LeetCode(String) 2011.

5.10回溯法--圆排列问题--排列树-爱代码爱编程

 圆排列问题描述  给定n个大小不相等的圆,要将这n个大小不相等的圆排进一个矩形框中,且要求个个圆都与矩形框的最底边相切。要找出最小长度的圆排列。 问题分析  排列排列,解空间是一个排列树。 设开始时,a[n]储存n个圆的半径,相应的排列树就由a[1:n]的所有排列构成了。 初始的时候,数组a是n个圆的半径,这是输入原始数据 我们要计算每一

p1057 [noip2008 普及组] 传球游戏-爱代码爱编程

[NOIP2008 普及组] 传球游戏 题目描述 上体育课的时候,小蛮的老师经常带着同学们一起做游戏。这次,老师带着同学们一起做传球游戏。 游戏规则是这样的: