- LeetCode 977.有序数组的平方
- LeetCode 209.长度最小的子数组
- LeetCode 59.螺旋矩阵II
977.有序数组的平方
给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。
示例 1:
1 | 输入:nums = [-4,-1,0,3,10] |
示例 2:
1 | 输入:nums = [-7,-3,2,3,11] |
思路
由于数组有序,负数平方之后可能成为最大数,所以平方后的最大值一定在数组的两端。
方法一:从中间向两边:找到正负分界点,然后分别向左向右遍历比较大小。
- 平方的特点是会把负数变成正数,所以一个负数和一个正数平方后的大小要根据绝对值来比较。
方法二:从两边向中间:
- 从两边向中间搜索数字是从大到小的,所以需要提前申请好数组空间,然后从后向前写入。
python代码
找到正负分界点,然后左右遍历比较
1 | class Solution: |
从两边到中间,双指针
1 | class Solution: |
209.长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 target ,找出该数组中满足其和 ≥ target 的长度最小的连续子数组,并返回其长度。如果不存在符合条件的子数组,返回 0。
示例 1:
1 | 输入:target = 7, nums = [2,3,1,2,4,3] |
示例 2:
1 | 输入:target = 11, nums = [1,1,1,1,1,1,1,1] |
思路
暴力解法
- 连续子数组的长度大小从0至length依次遍历,当和>=target,返回连续子数组大小
双指针(可变滑动窗口)
- 窗口的值< target,增大窗口
- 窗口的值>= target,缩小窗口
python代码
暴力解法 - 超时
1 | class Solution: |
双指针(可变滑动窗口)
1 | class Solution: |
59.螺旋矩阵II
给你一个正整数 n ,生成一个包含 1 到 n^2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
示例 1:
1 | 输入:n = 3 |
示例 2:
1 | 输入:n = 1 |
思路
循环填充
- 过程:填充上行,从左到右;填充右列,从上到下;填充下行,从右到左;填充左列,从下到上。
- 每条边的填充都要坚持循环一致的原则,左闭右开或者左开右闭。
python代码
1 | class Solution: |
赏
感觉不错 支持一下
本文作者:
三水
最后更新: 2022年11月22日 20:22:21
本文链接: https://sanshui.findn.cn/post/931914af.html
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可,转载请注明出处!
最后更新: 2022年11月22日 20:22:21
本文链接: https://sanshui.findn.cn/post/931914af.html
版权声明: 本作品采用 CC BY-NC-SA 4.0 许可协议进行许可,转载请注明出处!