当前位置: 首页 > news >正文

刷题笔记2 | 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结

977.有序数组的平方

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

输入:nums = [-4,-1,0,3,10]
输出:[0,1,9,16,100]
解释:平方后,数组变为 [16,1,0,9,100]
排序后,数组变为 [0,1,9,16,100]

输入:nums = [-7,-3,2,3,11]
输出:[4,9,9,49,121]

 解法1:当然是暴力咯

C++版本:注意冒泡排序过不了,用快排吧

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {for(int i = 0; i<nums.size();i++){nums[i] = nums[i]*nums[i];}// return maoPaoSort(nums);sort(nums.begin(),nums.end());return nums;}// vector<int> maoPaoSort(vector<int>& nums) { //冒泡排序  //     for(int i = 0; i<nums.size();i++){//         for(int j = i; j<nums.size(); j++){//             if(nums[i]>nums[j]){//                 int temp = 0;//                 temp = nums[i];//                 nums[i] = nums[j];//                 nums[j] = temp;//             }//         }//     }//     return nums;// }};

Python版本:

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:nums = [i**2 for i in nums]nums.sort()return nums

解法2:双指针法

 

数组其实是有序的, 那么数组平方的最大值就在数组的两端,不是最左边就是最右边,不可能是中间。此时可以考虑双指针法了,i指向起始位置,j指向终止位置。比较平方后的大小,存入到result中。

C++版本:

class Solution {
public:vector<int> sortedSquares(vector<int>& nums) {vector<int> result;for(int i = 0, j = nums.size()-1; i <= j;){if (nums[i]*nums[i] < nums[j]*nums[j]){result.push_back(nums[j]*nums[j]);j--;}else{result.push_back(nums[i]*nums[i]);i++;}}reverse(result.begin(),result.end());   // 反转return result;}
};

Python版本:

class Solution:def sortedSquares(self, nums: List[int]) -> List[int]:result = []i = 0j = len(nums)-1while(i<=j):if(nums[i]**2<nums[j]**2):result.append(nums[j]**2)j -= 1else:result.append(nums[i]**2)i += 1result.reverse()return result

209.长度最小的子数组 

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

输入:target = 7, nums = [2,3,1,2,4,3]
输出:2
解释:子数组 [4,3]是该条件下的长度最小的子数组。

解法一:暴力解决,两层for循环,不断更新子数组的长度,写了半天,超时了。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int result = INT32_MAX;for(int i = 0; i<nums.size(); i++){int subArrLength = 1;int currentNum = nums[i];// cout << nums[i] << endl;if(currentNum>=target){return 1;}else{for(int j = i + 1; j<nums.size();){subArrLength++;currentNum = currentNum + nums[j];// cout << nums[j] << endl;if (currentNum<target){j++;}else{result = result<subArrLength ? result : subArrLength;// cout <<"subArrLength"<<subArrLength <<endl;break;}}}}return result == INT32_MAX ? 0 : result;}
};

解法二:滑动窗口

 

在本题中实现滑动窗口,主要确定如下三点:

  • 窗口内是什么?
  • 如何移动窗口的起始位置?
  • 如何移动窗口的结束位置?

窗口就是 满足其和 ≥ s 的长度最小的 连续 子数组。

窗口的起始位置如何移动:如果当前窗口的值大于s了,窗口就要向前移动了(也就是该缩小了)。窗口的结束位置如何移动:窗口的结束位置就是遍历数组的指针,也就是for循环里的索引。

  • 滑动窗口:本质是满足了单调性,即左右指针只会往一个方向走且不会回头。收缩的本质即去掉不再需要的元素。也就是做题我们可以先固定移动右指针,判断条件是否可以收缩左指针算范围。大家可以好好理解一下。
  • 加入滑动窗口中有负数怎么办?
    如果有负数的话感觉也不能用滑动窗口了,因为有负数的话无论你收缩还是扩张窗口,你里面的值的总和都可能增加或减少,就不像之前收缩一定变小,扩张一定变大,一切就变得不可控了。如果要 cover 所有的情况,那每次 left 都要缩到 right,那就退化为暴力了哈哈。
  • 在滑动窗口类型题目里有没有去DEBUG的什么小技巧呢?
    一般是怀疑哪里有问题就打印哪里  像今天的滑动窗口  就可以把窗口首尾的下标变化过程打印出来  能很清楚的看到窗口是怎样移动的
  • 双指针和滑动窗口有什么区别,感觉双指针也是不断缩小的窗口。这道题,我想用两头取值的双指针,结果错了?
    因为两头指针走完相当于最多只把整个数组遍历一遍,会漏掉很多情况。滑动窗口实际上是双层遍历的优化版本,而双指针其实只有一层遍历,只不过是从头尾开始遍历的。
    滑动窗口的原理是右边先开始走,然后直到窗口内值的总和大于target,此时就开始缩圈,缩圈是为了找到最小值,只要此时总和还大于target,我就一直缩小,缩小到小于target为止在这过程中不断更新最小的长度值,然后右边继续走,如此反复,直到右边碰到边界。这样就保证了可以考虑到最小的情况

其实本题就是利用双指针来实现滑动窗口的收缩与扩张,实质还是双指针的解题思想。

C++版本:

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int result = INT32_MAX;int i = 0;int currentNum = 0;int subArrLength = 0;for(int j = 0; j<nums.size(); j++){currentNum += nums[j];while(currentNum >= target){  // 如多当前累加值大于目标值subArrLength = j - i + 1; //滑动窗口的长度result = result<subArrLength?result:subArrLength;currentNum -= nums[i++];   //收缩窗口}}return result == INT32_MAX ? 0 : result;}
};

Python版本:

class Solution:def minSubArrayLen(self, target: int, nums: List[int]) -> int:result = float("inf")currentNum = 0i = 0subArrLength = 0for j in range(len(nums)):currentNum += nums[j]while(currentNum >= target):subArrLength = j - i + 1result = min(subArrLength,result)currentNum -= nums[i]i += 1return 0 if result == float("inf") else result

59.螺旋矩阵II

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

 

示例:

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

纯纯一个模拟题。

class Solution {
public:vector<vector<int>> generateMatrix(int n) {vector<vector<int>> res(n, vector<int>(n, 0)); // 使用vector定义一个二维数组int startx = 0, starty = 0; // 定义每循环一个圈的起始位置int loop = n / 2; // 每个圈循环几次,例如n为奇数3,那么loop = 1 只是循环一圈,矩阵中间的值需要单独处理int mid = n / 2; // 矩阵中间的位置,例如:n为3, 中间的位置就是(1,1),n为5,中间位置为(2, 2)int count = 1; // 用来给矩阵中每一个空格赋值int offset = 1; // 需要控制每一条边遍历的长度,每次循环右边界收缩一位int i,j;while (loop --) {i = startx;j = starty;// 下面开始的四个for就是模拟转了一圈// 模拟填充上行从左到右(左闭右开)for (j = starty; j < n - offset; j++) {res[startx][j] = count++;}// 模拟填充右列从上到下(左闭右开)for (i = startx; i < n - offset; i++) {res[i][j] = count++;}// 模拟填充下行从右到左(左闭右开)for (; j > starty; j--) {res[i][j] = count++;}// 模拟填充左列从下到上(左闭右开)for (; i > startx; i--) {res[i][j] = count++;}// 第二圈开始的时候,起始位置要各自加1, 例如:第一圈起始位置是(0, 0),第二圈起始位置是(1, 1)startx++;starty++;// offset 控制每一圈里每一条边遍历的长度offset += 1;}// 如果n为奇数的话,需要单独给矩阵最中间的位置赋值if (n % 2) {res[mid][mid] = count;}return res;}
};

代码直接抄 再看看学习下吧 之后再写。

总结:

再多看看滑动窗口和螺旋矩阵这个题吧

相关文章:

刷题笔记2 | 977.有序数组的平方 ,209.长度最小的子数组 ,59.螺旋矩阵II ,总结

977.有序数组的平方 给你一个按 非递减顺序 排序的整数数组 nums&#xff0c;返回 每个数字的平方 组成的新数组&#xff0c;要求也按 非递减顺序 排序。 输入&#xff1a;nums [-4,-1,0,3,10] 输出&#xff1a;[0,1,9,16,100] 解释&#xff1a;平方后&#xff0c;数组变为 […...

python 支付宝营销活动现金红包开发接入流程-含接口调用加签

1 创建网页/移动应用 2 配置接口加签方式 涉及到金额的需要上传证书&#xff0c;在上传页面有教程&#xff0c; 在支付宝开放平台秘钥工具中生成CSR证书&#xff0c;会自动保存应用公钥和私钥到电脑上&#xff0c;调用支付宝接口需要应用私钥进行加签 上传完CSR证书后会有三个…...

Python操作Windows

用python进行windows端UI自动化的库有很多&#xff0c;比如pywinauto等&#xff0c;本文介绍一个使用autoit3来实现的 pyautoit 库pyautoit 是一个用python写的基于AutoItX3.dll的接口库&#xff0c;用来进行windows窗口的一系列操作&#xff0c;也支持鼠标键盘的操作。安装pip…...

Aptos SDK交互笔记(一)

背景 之前我们已经了解TS的一些语法&#xff0c;接下来可以实战训练下&#xff0c;这系列的文章就会介绍如何通过Aptos官网提供的TypeScript SDK与Aptos进行交互&#xff0c;这篇文章主要讲的就是如何使用提供API在aptos区块链上转帐。 官网示例 官网提供了交互的例子&#…...

汽车 12V 和 24V 电池输入保护推荐

简介汽车电池电源线路在运行系统时容易出现瞬变。所需的典型保护包括过压、过载、反极性和跨接启动。在汽车 的生命周期中&#xff0c;交流发电机可能会被更换为非OEM 部件。售后市场上的交流发电机可能具有不同的负载突降&#xff08;LOAD DUMP&#xff09;保护或没有负载突降…...

龙蜥LoongArch架构研发全揭秘,龙芯开辟龙腾计划技术合作新范式

编者按&#xff1a;在开源新基建加快建设的背景下&#xff0c;越来越多的企业选择加入龙蜥社区&#xff0c;当前社区生态合作伙伴已突破 300 家。于是&#xff0c;龙蜥社区能为加入的企业提供哪些支持成为越多伙伴们更加关注的话题。本文将以龙蜥社区和龙芯中科联合研发龙蜥 Lo…...

剑指 Offer 16. 数值的整数次方

摘要 剑指 Offer 16. 数值的整数次方 本题的方法被称为快速幂算法&#xff0c;有递归和迭代两个版本。这篇题解会从递归版本的开始讲起&#xff0c;再逐步引出迭代的版本。当指数n为负数时&#xff0c;我们可以计算 x^(-n)再取倒数得到结果&#xff0c;因此我们只需要考虑n为…...

在苹果电脑 mac 上安装原神(playCover)

该方法只能在 M1、M2 mac 上安装原神 目录前言一、首先下载安装 playCover1. playCover 下载2. playCover 安装安装出现问题解决方法二、下载安装原神1.安装包下载2.安装原神三、登录、键盘映射及版本更新等问题登录键盘映射版本更新前言 最近买了新的mac&#xff0c;作者本人…...

数据结构考研习题精选

&#xff11; A假设比较&#xff54;次&#xff0c;由于换或不换&#xff0c;则必然有&#xff12;&#xff3e;&#xff54;种可能。又设有&#xff4e;个关键字&#xff0c;&#xff4e;&#xff01;排列组合&#xff0c;则必然有&#xff12;&#xff3e;&#xff54;&…...

linux常用命令介绍 04 篇——uniq命令使用介绍(Linux重复数据的统计处理)

linux常用命令介绍 04 篇——uniq命令使用介绍&#xff08;Linux重复数据的统计处理&#xff09;1. uniq 使用语法2. sort 简单效果3. uniq 使用例子3.1 不加任何选项3.1.1 不用 sort 效果3.1.2 uniq 结合 sort 一起使用3.2 使用选项例子3.2.1 去重打印&#xff08;或打印不重复…...

网站打不开数据库错误等常见问题解决方法

1、“主机开设成功&#xff01;”上传数据后显示此内容&#xff0c;是因为西部数码默认放置的index.htm内容&#xff0c;需要核实wwwroot目录里面是否有自己的程序文件&#xff0c;可以删除index.htm。 2、恭喜&#xff0c;lanmp安装成功&#xff01;这个页面是wdcp的默认页面&…...

爬虫实战进阶版【1】——某眼专业版实时票房接口破解

某眼专业版-实时票房接口破解 某眼票房接口:https://piaofang.maoyan.com/dashboard-ajax 前言 当我们想根据某眼的接口获取票房信息的时候,发现它的接口处的参数是加密的,如下图: 红色框框的参数都是动态变化的,且signKey明显是加密的一个参数。对于这种加密的参数,我们需要…...

大话数据结构-普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal)

5 最小生成树 构造连通网的最小代价生成树称为最小生成树&#xff0c;即Minimum Cost Spanning Tree&#xff0c;最小生成树通常是基于无向网/有向网构造的。 找连通网的最小生成树&#xff0c;经典的有两种算法&#xff0c;普里姆算法和克鲁斯卡尔算法。 5.1 普里姆&#xff…...

UNet-肝脏肿瘤图像语义分割

目录 一. 语义分割 二. 数据集 三. 数据增强 图像数据处理步骤 CT图像增强方法 &#xff1a;windowing方法 直方图均衡化 获取掩膜图像深度 在肿瘤CT图中提取肿瘤 保存肿瘤数据 四. 数据加载 数据批处理 ​编辑​编辑 数据集加载 五. UNet神经网络模型搭建 单张图片…...

三周爆赚千万 电竞选手在无聊猿游戏赢麻了

如何用3个星期赚到1千万&#xff1f;普通人做梦都不敢想的事&#xff0c;电竞职业选手Mongraal却用几把游戏轻易完成&#xff0c;赚钱地点是蓝筹NFT项目Bored Ape Yacht Club&#xff08;BAYC无聊猿&#xff09;出品的新游戏Dookey Dash。 这款游戏类似《神庙逃亡》&#xff0…...

BERT学习

非精读BERT-b站有讲解视频&#xff08;跟着李沐学AI&#xff09; &#xff08;大佬好厉害&#xff0c;讲的比直接看论文容易懂得多&#xff09; 写在前面 在计算MLM预训练任务的损失函数的时候&#xff0c;参与计算的Tokens有哪些&#xff1f;是全部的15%的词汇还是15%词汇中真…...

大话数据结构-图的深度优先遍历和广度优先遍历

4 图的遍历 图的遍历分为深度优先遍历和广度优先遍历两种。 4.1 深度优先遍历 深度优先遍历&#xff08;Depth First Search&#xff09;&#xff0c;也称为深度优先搜索&#xff0c;简称DFS&#xff0c;深度优先遍历&#xff0c;是指从某一个顶点开始&#xff0c;按照一定的规…...

c语言指针怎么理解 第一部分

不理解指针&#xff0c;是因为有人教错了你。 有人告诉你&#xff0c;指针是“指向”某某某的&#xff0c;那就是误导你&#xff0c;给你挖了个坑。初学者小心不要误读这“指向”二字。 第一&#xff0c;“指针”通常用于保存一个地址&#xff0c;这个地址的数据类型在定义指…...

计算机网络安全基础知识2:http超文本传输协议,请求request消息的get和post,响应response消息的格式,响应状态码

计算机网络安全基础知识&#xff1a; 2022找工作是学历、能力和运气的超强结合体&#xff0c;遇到寒冬&#xff0c;大厂不招人&#xff0c;可能很多算法学生都得去找开发&#xff0c;测开 测开的话&#xff0c;你就得学数据库&#xff0c;sql&#xff0c;oracle&#xff0c;尤…...

Pytest自动化框架~权威教程03-原有TestSuite的执行方法

前言TestSuite一直是unittest的灵活与精髓之处, 在繁多的测试用例中, 可以任意挑选和组合各种用例集, 比如smoke用例集, level1用例集, webtest用例集, bug回归用例集等等, 当然这些TestSuite需要我们提前定义好, 并把用例加载进去.Pytest采取的是完全不同的用例组织和运行方式…...

云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?

大家好&#xff0c;欢迎来到《云原生核心技术》系列的第七篇&#xff01; 在上一篇&#xff0c;我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在&#xff0c;我们就像一个拥有了一块崭新数字土地的农场主&#xff0c;是时…...

利用ngx_stream_return_module构建简易 TCP/UDP 响应网关

一、模块概述 ngx_stream_return_module 提供了一个极简的指令&#xff1a; return <value>;在收到客户端连接后&#xff0c;立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量&#xff08;如 $time_iso8601、$remote_addr 等&#xff09;&a…...

shell脚本--常见案例

1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件&#xff1a; 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

UE5 学习系列(三)创建和移动物体

这篇博客是该系列的第三篇&#xff0c;是在之前两篇博客的基础上展开&#xff0c;主要介绍如何在操作界面中创建和拖动物体&#xff0c;这篇博客跟随的视频链接如下&#xff1a; B 站视频&#xff1a;s03-创建和移动物体 如果你不打算开之前的博客并且对UE5 比较熟的话按照以…...

【Redis技术进阶之路】「原理分析系列开篇」分析客户端和服务端网络诵信交互实现(服务端执行命令请求的过程 - 初始化服务器)

服务端执行命令请求的过程 【专栏简介】【技术大纲】【专栏目标】【目标人群】1. Redis爱好者与社区成员2. 后端开发和系统架构师3. 计算机专业的本科生及研究生 初始化服务器1. 初始化服务器状态结构初始化RedisServer变量 2. 加载相关系统配置和用户配置参数定制化配置参数案…...

【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分

一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计&#xff0c;提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合&#xff1a;各模块职责清晰&#xff0c;便于独立开发…...

全面解析各类VPN技术:GRE、IPsec、L2TP、SSL与MPLS VPN对比

目录 引言 VPN技术概述 GRE VPN 3.1 GRE封装结构 3.2 GRE的应用场景 GRE over IPsec 4.1 GRE over IPsec封装结构 4.2 为什么使用GRE over IPsec&#xff1f; IPsec VPN 5.1 IPsec传输模式&#xff08;Transport Mode&#xff09; 5.2 IPsec隧道模式&#xff08;Tunne…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...