977.有序数组的平方、209.长度最小的子数组、 59.螺旋矩阵II

简介: 1. **997. 有序数组的平方**:给定非递减顺序的整数数组,返回每个数字平方后的新数组,要求结果仍为非递减顺序。提供了两种解法——使用`sort()`函数和双指针法,后者利用原数组有序特性优化时间复杂度。 2. **209. 长度最小的子数组**:寻找和大于等于目标值的最短连续子数组长度。采用滑动窗口(毛毛虫比喻)方法,在O(n)时间内完成任务,通过动态调整窗口大小实现高效求解。 3. **59. 螺旋矩阵 II**:生成一个按顺时针螺旋排列的n×n矩阵。通过模拟填充过程,依次向右、下、左、上四个方向扩展边界,直至填满整个矩阵。

题目:997.有序数组的平方

997.有序数组的平方——力扣

给你一个按 非递减顺序 排序的整数数组 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]

提示:

1 <= nums.length <= 104

-104 <= nums[i] <= 104

nums 已按 非递减顺序 排序

思考历程与知识点:  

题目的意思很简单,就是把每个数的平方,按从小到大的顺序排个序,再输出出来。

第一想法是先每个数平方一遍,用sort()函数排序一步到位。但是这道题用sort时间复杂度很高,主要考查的是对双指针的理解,所以两种方法都做一遍吧。

为什么选用双指针做法:因为原来的数组是有序的,并且可以有负数,所以平方之后最大值要么在最左边,要么在最右边,在左右两端放两个指针,依次比较排序,就可以得到排好的数组啦

题解:

1、用 sort() 一步到位法:

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        vector<int> res;
        for(int i : nums)  
        res.push_back(i * i);
        sort(res.begin(),res.end());
        return res;
    }
};
2、双指针法
class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
      vector<int> res;
      int l = 0, r = nums.size()-1;
      while(r >= l){
          if(nums[l] * nums[l] >= nums[r] * nums[r]) {
              res.push_back(nums[l]*nums[l]);
              l++;
          }
          else {
               res.push_back(nums[r]*nums[r]);
               r--;
          }
      }
      reverse(res.begin(),res.end());
      return res;
    }
};

其他语言版本:

java:
class Solution {
    public int[] sortedSquares(int[] nums) {
        int right = nums.length - 1;
        int left = 0;
        int[] result = new int[nums.length];
        int index = result.length - 1;
        while (left <= right) {
            if (nums[left] * nums[left] > nums[right] * nums[right]) {
                // 正数的相对位置是不变的, 需要调整的是负数平方后的相对位置
                result[index--] = nums[left] * nums[left];
                ++left;
            } else {
                result[index--] = nums[right] * nums[right];
                --right;
            }
        }
        return result;
    }
}
python:
class Solution:
    def sortedSquares(self, nums: List[int]) -> List[int]:
        l, r, i = 0, len(nums)-1, len(nums)-1
        res = [float('inf')] * len(nums) # 需要提前定义列表,存放结果
        while l <= r:
            if nums[l] ** 2 < nums[r] ** 2: # 左右边界进行对比,找出最大值
                res[i] = nums[r] ** 2
                r -= 1 # 右指针往左移动
            else:
                res[i] = nums[l] ** 2
                l += 1 # 左指针往右移动
            i -= 1 # 存放结果的指针需要往前平移一位
        return res

题目:209. 长度最小的子数组

Leetcode原题链接:力扣

给定一个含有 n 个正整数的数组和一个正整数 target 。

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

示例 1:

输入:target = 7, nums = [2,3,1,2,4,3]

输出:2

解释:子数组  

[4,3]

是该条件下的长度最小的子数组。

示例 2:

输入:target = 4, nums = [1,4,4]

输出:1

示例 3:

输入:target = 11, nums = [1,1,1,1,1,1,1,1]

输出:0

提示:

1 <= target <= 109

1 <= nums.length <= 105

1 <= nums[i] <= 105

思考历程与知识点:  

题目最后一句的进阶,相当于是提示有O(n)的解法,也有O(n log(n))的解法。

但是,O(n)复杂度是小的那个,进阶反而要设计一个复杂度更大的,一般都应该反着来的,复杂度越小越好啊。所以题目是想引导我们思考别的解题方式。

那就先想想O(n)。第一反应,前缀和。想了想,确实就是O(n)的解法。

至于O(n log(n)),其实是滑动窗口,就像一只毛毛虫,从这个长长的数组上爬过去,身子下面的数字和如果小了,那其他位置不动,就头往前探探,多加几个数字,如果大了,那尾巴就收回来一点,少加几个数字。根据这个原则,毛毛虫爬完一趟,就知道最短的区间长度是多少了。(奇妙の比喻hhh)

题解:

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int l = 0, r = 0,sum = nums[0];
        int len = INT_MAX;
        while( 1) {
            if(sum < s && r+1 < nums.size()) {
                r++;
                sum=sum + nums[r];
            }
            else if(sum >= s)
            {
                if(len > r - l + 1)len = r - l + 1;
                sum=sum - nums[l++];
            }
            else{
                break;
            }
        }
        if(len == INT_MAX)len = 0;
        return len;
    }
};

其他语言版本:

java:
class Solution {
 
    // 滑动窗口
    public int minSubArrayLen(int s, int[] nums) {
        int left = 0;
        int sum = 0;
        int result = Integer.MAX_VALUE;
        for (int right = 0; right < nums.length; right++) {
            sum += nums[right];
            while (sum >= s) {
                result = Math.min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == Integer.MAX_VALUE ? 0 : result;
    }
}
 python:
class Solution:
    def minSubArrayLen(self, s: int, nums: List[int]) -> int:
        l = len(nums)
        left = 0
        right = 0
        min_len = float('inf')
        cur_sum = 0 #当前的累加值
       
        while right < l:
            cur_sum += nums[right]
           
            while cur_sum >= s: # 当前累加值大于目标值
                min_len = min(min_len, right - left + 1)
                cur_sum -= nums[left]
                left += 1
           
            right += 1
       
        return min_len if min_len != float('inf') else 0

题目:59.螺旋矩阵 II

Leetcode原题链接:59. 螺旋矩阵 II

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

示例 1:

输入:n = 3

输出:[[1,2,3],[8,9,4],[7,6,5]]

示例 2:

输入:n = 1

输出:[[1]]

提示:

1 <= n <= 20

思考历程与知识点:  

看起来是个模拟题,一圈一圈的模拟。那就按数字顺序,从左上角1开始一圈圈遍历。

比较复杂,可以看下官方的动画图解:59.螺旋矩阵II题解——力扣

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int row = 0, col = 0;
        for(int i = 1; i <= n * n;){
            //先向右,行不变,列+1
            while(col < n && ans[row][col] == 0 && i <= n * n){
                ans[row][col++] = i++;
            }
            row++;
            col--;
            //向下,列不变,行+1
            while(row < n && ans[row][col] == 0 && i <= n * n){
                ans[row++][col] = i++;
            }
            row--;
            col--;
            //向左,行不变,列-1
            while(col >= 0 && ans[row][col] == 0 && i <= n * n){
                ans[row][col--] = i++;
            }
            row--;
            col++;
            //向上,列不变,行-1
            while(row >= 0 && ans[row][col] == 0 && i <= n * n){
                ans[row--][col] = i++;
            }
            row++;
            col++;
        }
        return ans;
    }
};

其他语言版本:

java:
class Solution {
    public int[][] generateMatrix(int n) {
        int loop = 0;  // 控制循环次数
        int[][] res = new int[n][n];
        int start = 0;  // 每次循环的开始点(start, start)
        int count = 1;  // 定义填充数字
        int i, j;
 
        while (loop++ < n / 2) { // 判断边界后,loop从1开始
            // 模拟上侧从左到右
            for (j = start; j < n - loop; j++) {
                res[start][j] = count++;
            }
 
            // 模拟右侧从上到下
            for (i = start; i < n - loop; i++) {
                res[i][j] = count++;
            }
 
            // 模拟下侧从右到左
            for (; j >= loop; j--) {
                res[i][j] = count++;
            }
 
            // 模拟左侧从下到上
            for (; i >= loop; i--) {
                res[i][j] = count++;
            }
            start++;
        }
 
        if (n % 2 == 1) {
            res[start][start] = count;
        }
 
        return res;
    }
}
python:
class Solution:
    def generateMatrix(self, n: int) -> List[List[int]]:
        nums = [[0] * n for _ in range(n)]
        startx, starty = 0, 0               # 起始点
        loop, mid = n // 2, n // 2          # 迭代次数、n为奇数时,矩阵的中心点
        count = 1                           # 计数
 
        for offset in range(1, loop + 1) :      # 每循环一层偏移量加1,偏移量从1开始
            for i in range(starty, n - offset) :    # 从左至右,左闭右开
                nums[startx][i] = count
                count += 1
            for i in range(startx, n - offset) :    # 从上至下
                nums[i][n - offset] = count
                count += 1
            for i in range(n - offset, starty, -1) : # 从右至左
                nums[n - offset][i] = count
                count += 1
            for i in range(n - offset, startx, -1) : # 从下至上
                nums[i][starty] = count
                count += 1                
            startx += 1         # 更新起始点
            starty += 1
 
        if n % 2 != 0 :   # n为奇数时,填充中心点
            nums[mid][mid] = count  
        return nums

                       

相关文章
|
存储 人工智能 监控
|
数据采集
以“股票代码实时抓取股票信息”为例的爬虫案例
爬虫—根据股票代码实时抓取股票信息
1020 0
HTML网页制作——制作一个属于自己的网页
HTML网页制作——制作一个属于自己的网页
406 0
HTML网页制作——制作一个属于自己的网页
|
XML 网络协议 Unix
每个系统管理员都应该知道的 6 个 Linux 网络命令
作为系统管理员,我们每天都会跟各种各样的Linux命令打交道,其中网络相关的命令涉及的十分频繁,本文笔者就给大家分享一下Linux中6个常用的网络命令,强烈建议全部看完,我相信大多数你都是用过的。
421 0
每个系统管理员都应该知道的 6 个 Linux 网络命令
|
Devops jenkins 持续交付
打造云上代码交付链,CodePipeline实践分享
在2017在线技术峰会——首届阿里巴巴研发效能嘉年华上,来自阿里云飞天研发部的工程师莫源分享了《打造云上代码交付链,CodePipeline实践分享》。他在云计算和云平台、持续集成流程、DevOps的基础上,详细分享了Alibaba Cloud CodePipeline优于Jenkins的性能和实践。
15605 0
|
8天前
|
Linux Go 开发工具
手机上跑 DeepSeek 智能体:开源安卓客户端 DSH Go 安装与使用指南
DSH Go 是一款开源安卓客户端,将 DeepSeek Harness 智能体引擎装进手机:免 Root、免 Termux,一键安装即用;支持本机运行(内置 Ubuntu+Node.js)或远程接管电脑会话;具备插话打断、过程折叠、屏幕操控、端到端加密分享等特色功能,真正实现智能体“口袋化”。
9775 25
|
8天前
|
弹性计算 人工智能 API
Codex超详细入门指南(下载·安装·登录·上手,全版本覆盖,2026最新版)
建议收藏本教程,2026 全年各版本更新随时回来查阅。如果你在搭建过程中遇到任何问题,欢迎结合 阿里云工单系统 提交技术支持请求,或在 阿里云开发者社区 搜索 Codex 相关话题交流。 祝你编码愉快,效率翻倍!
2756 14