刷题笔记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采取的是完全不同的用例组织和运行方式…...

通过Wrangler CLI在worker中创建数据库和表
官方使用文档:Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后,会在本地和远程创建数据库: npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库: 现在,您的Cloudfla…...

dedecms 织梦自定义表单留言增加ajax验证码功能
增加ajax功能模块,用户不点击提交按钮,只要输入框失去焦点,就会提前提示验证码是否正确。 一,模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

微信小程序云开发平台MySQL的连接方式
注:微信小程序云开发平台指的是腾讯云开发 先给结论:微信小程序云开发平台的MySQL,无法通过获取数据库连接信息的方式进行连接,连接只能通过云开发的SDK连接,具体要参考官方文档: 为什么? 因为…...
Unit 1 深度强化学习简介
Deep RL Course ——Unit 1 Introduction 从理论和实践层面深入学习深度强化学习。学会使用知名的深度强化学习库,例如 Stable Baselines3、RL Baselines3 Zoo、Sample Factory 和 CleanRL。在独特的环境中训练智能体,比如 SnowballFight、Huggy the Do…...

多模态大语言模型arxiv论文略读(108)
CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文标题:CROME: Cross-Modal Adapters for Efficient Multimodal LLM ➡️ 论文作者:Sayna Ebrahimi, Sercan O. Arik, Tejas Nama, Tomas Pfister ➡️ 研究机构: Google Cloud AI Re…...
浅谈不同二分算法的查找情况
二分算法原理比较简单,但是实际的算法模板却有很多,这一切都源于二分查找问题中的复杂情况和二分算法的边界处理,以下是博主对一些二分算法查找的情况分析。 需要说明的是,以下二分算法都是基于有序序列为升序有序的情况…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)
参考官方文档:https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java(供 Kotlin 使用) 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

10-Oracle 23 ai Vector Search 概述和参数
一、Oracle AI Vector Search 概述 企业和个人都在尝试各种AI,使用客户端或是内部自己搭建集成大模型的终端,加速与大型语言模型(LLM)的结合,同时使用检索增强生成(Retrieval Augmented Generation &#…...

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

打手机检测算法AI智能分析网关V4守护公共/工业/医疗等多场景安全应用
一、方案背景 在现代生产与生活场景中,如工厂高危作业区、医院手术室、公共场景等,人员违规打手机的行为潜藏着巨大风险。传统依靠人工巡查的监管方式,存在效率低、覆盖面不足、判断主观性强等问题,难以满足对人员打手机行为精…...