刷题笔记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,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。 输入:nums [-4,-1,0,3,10] 输出:[0,1,9,16,100] 解释:平方后,数组变为 […...

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

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

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

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

龙蜥LoongArch架构研发全揭秘,龙芯开辟龙腾计划技术合作新范式
编者按:在开源新基建加快建设的背景下,越来越多的企业选择加入龙蜥社区,当前社区生态合作伙伴已突破 300 家。于是,龙蜥社区能为加入的企业提供哪些支持成为越多伙伴们更加关注的话题。本文将以龙蜥社区和龙芯中科联合研发龙蜥 Lo…...

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

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

数据结构考研习题精选
1 A假设比较t次,由于换或不换,则必然有2^t种可能。又设有n个关键字,n!排列组合,则必然有2^t&…...

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

网站打不开数据库错误等常见问题解决方法
1、“主机开设成功!”上传数据后显示此内容,是因为西部数码默认放置的index.htm内容,需要核实wwwroot目录里面是否有自己的程序文件,可以删除index.htm。 2、恭喜,lanmp安装成功!这个页面是wdcp的默认页面&…...

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

大话数据结构-普里姆算法(Prim)和克鲁斯卡尔算法(Kruskal)
5 最小生成树 构造连通网的最小代价生成树称为最小生成树,即Minimum Cost Spanning Tree,最小生成树通常是基于无向网/有向网构造的。 找连通网的最小生成树,经典的有两种算法,普里姆算法和克鲁斯卡尔算法。 5.1 普里姆ÿ…...

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

三周爆赚千万 电竞选手在无聊猿游戏赢麻了
如何用3个星期赚到1千万?普通人做梦都不敢想的事,电竞职业选手Mongraal却用几把游戏轻易完成,赚钱地点是蓝筹NFT项目Bored Ape Yacht Club(BAYC无聊猿)出品的新游戏Dookey Dash。 这款游戏类似《神庙逃亡》࿰…...

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

大话数据结构-图的深度优先遍历和广度优先遍历
4 图的遍历 图的遍历分为深度优先遍历和广度优先遍历两种。 4.1 深度优先遍历 深度优先遍历(Depth First Search),也称为深度优先搜索,简称DFS,深度优先遍历,是指从某一个顶点开始,按照一定的规…...

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

计算机网络安全基础知识2:http超文本传输协议,请求request消息的get和post,响应response消息的格式,响应状态码
计算机网络安全基础知识: 2022找工作是学历、能力和运气的超强结合体,遇到寒冬,大厂不招人,可能很多算法学生都得去找开发,测开 测开的话,你就得学数据库,sql,oracle,尤…...

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

web自动化 基于python+Selenium+PHP+Ftp实现的轻量级web自动化测试框架
1、 开发环境 win7 64 PyCharm 4.0.5 setuptools-29.0.1.zip 下载地址:setuptools-29.0.1.zip_免费高速下载|百度网盘-分享无限制 官方下载地址:setuptools PyPI python 3.3.2 mysql-connector-python-2.1.4-py3.3-win64 下载地址:mysq…...

【MyBatis】源码学习 05 - 关于 xml 文件解析的分析
文章目录前言参考目录学习笔记1、章节目录概览2、14.3:SqlSourceBuilder 类与 StaticSqlSource 类3、14.4.2:ResultMapResolver 类3.1、测试代码说明3.2、结果集 userMap 解析流程3.3、结果集 getGirl 解析流程3.4、鉴别器 discriminator 解析流程4、14.…...

代码随想录算法训练营第二天| 977. 有序数组的平方、209. 长度最小子数组、59.螺旋矩阵II
977 有序数组的平方题目链接:977 有序数组的平方介绍给你一个按 非递减顺序 排序的整数数组 nums,返回 每个数字的平方 组成的新数组,要求也按 非递减顺序 排序。思路看到题目的第一反应,首先负数的平方跟正数的平方是相同的&…...

Ethercat系列(10)用QT实现SOEM主站
首先将SOEM编译成静态Lib库可以参考前面的博文(83条消息) VS2017下编译SOEM(Simle Open EtherCAT Master)_soem vs_CoderIsArt的博客-CSDN博客make_libsoem_lib.bat "C:\Program Files (x86)\Microsoft Visual Studio\2017\Community\VC\Auxiliary\Build" x86用QT创建…...

论文投稿指南——中文核心期刊推荐(科学、科学研究)
【前言】 🚀 想发论文怎么办?手把手教你论文如何投稿!那么,首先要搞懂投稿目标——论文期刊 🎄 在期刊论文的分布中,存在一种普遍现象:即对于某一特定的学科或专业来说,少数期刊所含…...

jQuery属性操作prop()、attr()和data()
jQuery 提供了一些属性操作的方法,主要包括 prop()、attr() 和 data() 等。通过这些方法,能够实现不同的需求。下面我们分别进行详细讲解。 1.prop() 方法 prop0 方法用来设置或获取元素固有属性值。元素固有属性是指元素本身自带的属性,如 …...

git的使用
1.git的四个区域: 2.常规git命令 git status 查看working directory哪些文件被更改了git add .把更改add到staging area,缓存的地方。改一个地方可以就先暂存一下,最后确认是哪些改动后再一起commit,以免不必要的版本。 在暂存区域ÿ…...

webpack生产环境配置
3 webpack生产环境配置 由于笔记文档没有按照之前的md格式书写,所以排版上代码上存在问题😢😢😢😢 09 提取css成单独文件 使用下载插件 npm i mini-css-extract-plugin0.9.0 -D webpack配置此时a,b提取成单独文件,并且…...

linux下安装jenkins
1.初始化Jenkins安装环境 系统版本:Red Hat Enterprise Linux 8.7 将脚本文件jenkins_install_env.sh 、 jenkins_install.sh和apache-maven-3.6.2-bin.tar.gz、jdk-8u251-linux-x64.tar.gz都上传到/usr/local/src目录下执行jenkins_install_env.sh脚本初始化Jenki…...

IGKBoard(imx6ull)-I2C接口编程之SHT20温湿度采样
文章目录1- 使能开发板I2C通信接口2- SHT20硬件连接3- 编码实现SHT20温湿度采样思路(1)查看sht20从设备地址(i2cdetect)(2)获取数据大体流程【1】软复位【2】触发测量与通讯时序(3)返…...