代码随想录算法训练营day2|977.有序数组的平方、209.长度最小的子数组、59.螺旋矩阵II



第一章  数组part02 

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

 977.有序数组的平方 

题目建议: 本题关键在于理解双指针思想 

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

文章讲解:代码随想录

视频讲解: 双指针法经典题目 | LeetCode:977.有序数组的平方_哔哩哔哩_bilibili

 209.长度最小的子数组

题目建议: 本题关键在于理解滑动窗口,这个滑动窗口看文字讲解 还挺难理解的,建议大家先看视频讲解。  拓展题目可以先不做。 

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

文章讲解:代码随想录

视频讲解:拿下滑动窗口! | LeetCode 209 长度最小的子数组_哔哩哔哩_bilibili

 59.螺旋矩阵II

题目建议:  本题关键还是在转圈的逻辑,在二分搜索中提到的区间定义,在这里又用上了。 

题目链接:力扣(LeetCode)官网 - 全球极客挚爱的技术成长平台

文章讲解:代码随想录

视频讲解:一入循环深似海 | LeetCode:59.螺旋矩阵II_哔哩哔哩_bilibili

 总结 

文章链接:代码随想录


        最直观的方法就是遍历数组并平方,然后对新数组排序,排序如果使用冒泡的话,输入规模最大1e4,在O(n^2)下就是1e8,估计会超时的,试了一下确实超时了。O(nlogn)的排序算法下1e6可以试一下。

1.C++标准库中的<vector>中包含了一个内置的sort函数,用于对vector容器中的元素进行排序。sort函数使用的是快速排序(Quicksort)算法,具有时间复杂度为O(nlogn)。

2.C++标准库中的sort函数使用的是一种混合了快速排序(Quicksort)和插入排序(Insertion Sort)的排序算法,具体是使用的是Introsort算法。

Introsort算法在排序的过程中,首先使用快速排序来快速地进行划分,当快速排序的递归深度超过一定限制时,为了避免快速排序的最坏情况时间复杂度O(n^2)的发生,转而使用插入排序,这样可以保证时间复杂度不会超过O(nlogn)。

c++代码示例如下O(n+nlogn)

vector<int>sortedSquares(vector<int>& nums) {for (int i = 0; i < nums.size(); i++) {nums[i] *= nums[i];}sort(nums.begin(), nums.end(), less<int>());return nums;
}

        双指针法

可以发现数组负数部分平方后从大到小,正数部分平方后从小到大。如图

数组最大的数满足max{左端,右端},使用双指针,i指向左起始位置,j指向右起始位置。定义一个和数组同样大小的新数组ret,k指向ret数组右起始位置。

每次比较左右起始位置值大小,并把较大值添加至ret数组尾。更新较大值指针、ret数组右起始位置k。

动画如图

c++代码示例如下O(n)

vector<int>sortedSquares(vector<int>& nums) {int k = nums.size() - 1;vector<int>ret(nums.size(), 0);for (int i = 0, j = nums.size() - 1; i <= j;) {if (nums[i] * nums[i] >= nums[j] * nums[j]) {ret[k--] = nums[i] * nums[i];i++;}else {ret[k--] = nums[j] * nums[j];j--;}}return ret;
}

        直观的暴力方法就是遍历数组,定义len为一个大数,每次以i为起始求满足情况的最短连续子序列,记录长度并与len做判断,若小于则更新len。最后输出结果,若len没有更新则表示没有满足情况的子序列,返回0。

c++代码示例如下O(n^2)

int minSubArrayLen(int target, vector<int>& nums) {int lmin = INT32_MAX;int sum = 0;for (int i = 0; i < nums.size(); i++) {sum = 0;for (int j = i; j < nums.size(); j++) {sum += nums[j];if (sum >= target) {int len = j - i + 1;lmin = len < lmin ? len : lmin;}}}return lmin == INT32_MAX ? 0 : lmin;
}

超时了

        在暴力解法中,一个for循环指向子序列头,嵌套一个for循环指向子序列尾,用两个循环完成了不断搜索区间的过程。在实际运行中,假设存在多个连续子序列,第一次找的子序列1后,在第二次找子序列2的时候,更新头指针也就是外循环,然后回溯尾指针也就是内循环。实际上下次寻找子序列的时候,上一次尾指针可以复用,子序列1由头尾指针确定的区间和大于等于target,可以证明若仅更新头指针,复用尾指针所得区间和是符合题意的。这个更新是精髓。

        也就是双指针法了,由于这种解法更像是一个窗口的滑动,故命名为滑动窗口。虽然我觉得跟毛毛虫一样

下面以题目中的示例来演示滑动窗口的起始位置是怎么移动的。s=7,数组{2,3,1,2,4,3}来看一下查找的过程。

c++代码示例如下O(n)

int minSubArrayLen(int target, vector<int>& nums) {int lmin = INT32_MAX;int sum = 0, i = 0, len = 0;for (int j = 0; j < nums.size(); j++) {sum += nums[j];while (sum >= target) {len = j - i + 1;lmin = len < lmin ? len : lmin;sum -= nums[i++];}}return lmin == INT32_MAX ? 0 : lmin;
}

        简单的模拟题。解法可以分为二类,如图

左边写法在边长为奇数时需要单独补中心,右边写法则通用

由上,右,下,左的模拟行为里的区间定义决定。

c++代码示例如下

vector<vector<int>> generateMatrix(int n){vector<vector<int>> res(n, vector<int>(n, 0));int startx = 0, starty = 0;int loop = n / 2;int cnt = 1;int offset = 1;int i, j;while (loop--) {i = startx;j = starty;for (j = starty; j < n - offset; j++) res[i][j] = cnt++;for (i = startx; i < n - offset; i++) res[i][j] = cnt++;for (; j > starty; j--) res[i][j] = cnt++;for (; i > startx; i --) res[i][j] = cnt++;startx++; starty++;offset += 1;}if (n % 2) res[n / 2][n / 2] = cnt;return res;
}

——未完待续

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://xiahunao.cn/news/2659842.html

如若内容造成侵权/违法违规/事实不符,请联系瞎胡闹网进行投诉反馈,一经查实,立即删除!

相关文章

w7数据库基础之mysql函数

系统函数 1.version() --mysql版本 2.user() --当前登录的数据库用户名system_user() 3.database() --当前使用的数据库名。schema() 4.datadir --数据库路径 5.version_compile_os 操作系统版本&#xff0c;like 后面可以使用%%进行模糊查询。 6.hostname 当前机器…

出现频率高达70%软件测试面试题及答案!——看完面试官:是你面试我还是我面试你啊!

【纯干货&#xff01;&#xff01;&#xff01;】花费了整整3天&#xff0c;整理出来的全网最实用软件测试面试大全&#xff0c;一共30道题目答案的纯干货&#xff0c;希望大家多多支持&#xff0c;建议 点赞&#xff01;&#xff01;收藏&#xff01;&#xff01;长文警告&…

QuestMobile:网易有道词典、美团、知乎等一同入榜2023年“00后喜爱APP”

近期&#xff0c;国内第三方数据机构QuestMobile发布《2023中国互联网核心趋势年度报告》&#xff0c;网易有道词典荣获“2023中国互联网APP TOP50赛道用户规模NO.1”及“00后用户喜爱App”两项殊荣。 据悉&#xff0c;QuestMobile年度“行业用户规模”奖项是以2022年10月-2023…

代码随想录-刷题第三十九天

动态规划理论基础 动态规划的题目由重叠子问题构成&#xff0c;每一个状态一定是由上一个状态推导出来的。这一点就区分于贪心&#xff0c;贪心没有状态推导&#xff0c;而是从局部直接选最优的。 动态规划五步曲 确定dp数组&#xff08;dp table&#xff09;以及下标的含义…

MySQL按月分片

一、按照月分片 使用场景为按照自然月来分片,每个自然月为一个分片,但是一年有12个月,是不是要有12个数据节点才行呢?并不是。例如我现在只有三个分片数据库,这样就可以1月在第一个数据分片中,2月在第二个数据分片中,3月在第三个数据分片中,当来到4月的时候,就会重新开…

w4操作系统之windows上创建隐藏用户

隐藏用户–在windows上创建隐藏用户 1.首先查看现有哪些用户。&#xff08;通过net user 命令&#xff09; 2.然后创建隐藏用户&#xff08;net user client$ 123 /add&#xff09; 此时出现报错信息。原因是登录用户没权限。需要用管理员的权限 3.用管理员身份运行cmd&am…

【数据结构】C语言实现单链表的基本操作

单链表基本操作的实现 导言一、查找操作1.1 按位查找1.1.1 按位查找的C语言实现1.1.2 按位查找的时间复杂度 1.2 按值查找1.2.1 按值查找的C语言实现1.2.2 按值查找的时间复杂度 二、插入操作2.1 后插操作2.2 前插操作 三、删除操作结语 导言 大家好&#xff0c;很高兴又和大家…

代码随想录二刷 | 二叉树 | 最大二叉树

代码随想录二刷 &#xff5c; 二叉树 &#xff5c; 最大二叉树 题目描述解题思路代码实现 题目描述 654.最大二叉树 给定一个不重复的整数数组 nums 。 最大二叉树可以用下面的算法从 nums 递归地构建: 创建一个根节点&#xff0c;其值为 nums 中的最大值。递归地在最大值 左…

SpringSecurity6 | 默认用户生成(上)

✅作者简介:大家好,我是Leo,热爱Java后端开发者,一个想要与大家共同进步的男人😉😉 🍎个人主页:Leo的博客 💞当前专栏: Java从入门到精通 ✨特色专栏: MySQL学习 🥭本文内容:SpringSecurity6 | 默认用户生成(上) 📚个人知识库: [Leo知识库]https://gaozim…

基于STM8S103F3P6的超声波测距仪设计

大三的时候给大四学长做的毕业设计题目 文章目录 1 绪论1.1 设计背景1.2 设计的主要任务 2 超声波测距基本理论及总体架构2.1 基本知识2.1.1 超声波特性2.1.2 超声波传感器2.1.3 超声波测距原理 2.2 总体架构2.2.1 设计原则2.2.2 总体方案介绍 2.3 主要器件选择与介绍2.3.1 主控…

网盘项目话术(0.5w字精选)

功能结构图 数据库设计总结 该项目主要就是对文件的操作&#xff0c;file表&#xff0c;file_share表。 file表主要字段&#xff1a;id&#xff0c;用户id&#xff0c;父级目录id&#xff0c;文件的地址&#xff0c;文件的封面图片地址&#xff0c;创建和修改时间。 file_sha…

react 之 美团案例

1.案例展示 2.环境搭建 克隆项目到本地&#xff08;内置了基础静态组件和模版&#xff09; git clone http://git.itcast.cn/heimaqianduan/redux-meituan.git 安装所有依赖 npm i 启动mock服务&#xff08;内置了json-server&#xff09; npm run serve 启动前端服务 npm…

Translation翻译插件

Translation插件是为IntelliJ IDEA开发的&#xff0c;因此只能在IntelliJ IDEA中使用。但是&#xff0c;如果你需要在其他软件中进行翻译&#xff0c;可以考虑使用其他的翻译工具或服务。例如&#xff0c;一些在线翻译网站&#xff08;如Google翻译、百度翻译等&#xff09;提供…

VScode——下载、安装、配置C/C++环境(windows)

一.快速下载 还在因为vscode官方下载慢而头疼嘛&#xff0c;按这个步骤来直接起飞兄弟萌 首先进入vscode官方网站然后选择对应版本下载然后进入浏览器下载页面复制下载链接粘贴到地址栏 将地址中的/stable前换成vscode.cdn.azure.cn 即可实现超速下载 下面是一个国内镜像的下…

mysql原理--MySQL基于规则的优化

设计 MySQL 的大叔依据一些规则&#xff0c;竭尽全力的把一些很糟糕的语句转换成某种可以比较高效执行的形式&#xff0c;这个过程也可以被称作 查询重写 &#xff08;就是人家觉得你写的语句不好&#xff0c;自己再重写一遍&#xff09;。 1.条件化简 我们编写的查询语句的搜…

vue虚拟列表展示

效果图 <template><!-- 总体高度区域 --><divref"listWrap"class"m-container"scroll"scrollListener"><div:style"handleContainerHeight()"><!-- 可视区域 --><divclass"m-area":style&…

打地鼠游戏来了

主要利用js鼠标点击事件和window.setInterval&#xff08;&#xff09;回调函数来进行实现的. 源码获取方式&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1eW9qvX3zFH9qlH82-I4yOA 提取码&#xff1a;1233

中间件系列 - Redis入门到实战(原理篇)

前言 学习视频&#xff1a; 黑马程序员Redis入门到实战教程&#xff0c;深度透析redis底层原理redis分布式锁企业解决方案黑马点评实战项目 中间件系列 - Redis入门到实战 本内容仅用于个人学习笔记&#xff0c;如有侵扰&#xff0c;联系删除 学习目标 Redis数据结构Redis网…

Matlab:非线性规划

1、语法&#xff1a; xfmincon(fun,x0,A,b) xfmincon(fun,x0,A,b,Aeq,beq) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon) xfmincon(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options) xfmincon(problem) [x,fval]fmincon(___) [x,fval,exitflag,…