【算法刷题之数组篇(1)】

目录

  • 1.leetcode-59. 螺旋矩阵 II
  • (题2.题3相当于二分变形)
  • 2.leetcode-33. 搜索旋转排序数组
  • 3.leetcode-81. 搜索旋转排序数组 II(与题目2对比理解)
  • (题4和题5都是排序+双指针)
  • 4.leetcode-15. 三数之和
  • 5.leetcode-18. 四数之和
  • 6.leetcode-80. 删除有序数组中的重复项 II
  • (通解方法)

1.leetcode-59. 螺旋矩阵 II

(1)题目描述
给你一个正整数 n ,生成一个包含 1 到 n2 所有元素,且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
在这里插入图片描述
(2)方法与思路(模拟)
1.首先明白螺旋矩阵的拐点是在哪里,并且在旋转一周后边界值会有哪些变化。
2.先定义四个变量,分别来表示这个正方形的上左下右的边界值。
3.走完一条边就要将这条边减去一。
4.终止条件就是数组元素所给值达到n*n。
(3)代码实现

class Solution {
public:vector<vector<int>> generateMatrix(int n) {int t = 0;      // topint b = n-1;    // bottomint l = 0;      // leftint r = n-1;    // rightvector<vector<int>> ans(n,vector<int>(n));int k=1;while(k<=n*n){for(int i=l;i<=r;++i,++k) ans[t][i] = k;++t;for(int i=t;i<=b;++i,++k) ans[i][r] = k;--r;for(int i=r;i>=l;--i,++k) ans[b][i] = k;--b;for(int i=b;i>=t;--i,++k) ans[i][l] = k;++l;}return ans;}
};

(题2.题3相当于二分变形)

2.leetcode-33. 搜索旋转排序数组

(1)题目描述
整数数组 nums 按升序排列,数组中的值 互不相同 。
在传递给函数之前,nums 在预先未知的某个下标 k(0 <= k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k+1], …, nums[n-1], nums[0], nums[1], …, nums[k-1]](下标 从 0 开始 计数)。例如, [0,1,2,4,5,6,7] 在下标 3 处经旋转后可能变为 [4,5,6,7,0,1,2] 。
给你 旋转后 的数组 nums 和一个整数 target ,如果 nums 中存在这个目标值 target ,则返回它的下标,否则返回 -1 。
你必须设计一个时间复杂度为 O(log n) 的算法解决此问题。
在这里插入图片描述
(2)方法及思路(二分查找)(虽然可以直接查找但是还是多练练吧,嘻嘻)
先上图
在这里插入图片描述
由此图可以看出分两种不同情况(在由mid第一次分开后)
1.target落在左(右)半部分有序部分中。
2.target还是落在错位的区间(即不有序),那就在while循环中进行再分。但是要更新左右的值
(如果左半部分不是有序,那右半部分必有序,反之也一样)
(3)代码实现

class Solution {
public:int search(vector<int>& nums, int target) {int n = (int)nums.size();if (!n) {return -1;}if (n == 1) {return nums[0] == target ? 0 : -1;}int l = 0, r = n - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) return mid;if (nums[0] <= nums[mid]) {if (nums[0] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[n - 1]) {l = mid + 1;} else {r = mid - 1;}}}return -1;}
};

3.leetcode-81. 搜索旋转排序数组 II(与题目2对比理解)

(1)其他条件与上题相同,唯有此题中数组是非降序。
在这里插入图片描述
(2)方法与思路(二分查找)
思路
1.对于数组中有重复元素的情况,二分查找时可能会有 a[l]=a[mid]=a[r],此时无法判断区间 [l,mid] 和区间 [mid+1,r] 哪个是有序的。

2.例如 nums=[3,1,2,3,3,3,3],target=2,首次二分时无法判断区间 [0,3][0,3][0,3] 和区间 [4,6][4,6][4,6] 哪个是有序的。

3.对于这种情况,我们只能将当前二分区间的左边界加一,右边界减一,然后在新区间上继续二分查找。
(3)代码实现

class Solution {
public:bool search(vector<int> &nums, int target) {int n = nums.size();if (n == 0) {return false;}if (n == 1) {return nums[0] == target;}int l = 0, r = n - 1;while (l <= r) {int mid = (l + r) / 2;if (nums[mid] == target) {return true;}if (nums[l] == nums[mid] && nums[mid] == nums[r]) {++l;--r;} else if (nums[l] <= nums[mid]) {if (nums[l] <= target && target < nums[mid]) {r = mid - 1;} else {l = mid + 1;}} else {if (nums[mid] < target && target <= nums[n - 1]) {l = mid + 1;} else {r = mid - 1;}}}return false;}
};

(题4和题5都是排序+双指针)

4.leetcode-15. 三数之和

(1)题目描述
给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
在这里插入图片描述
(2)方法与思路(排序+双指针)
1.对数组进行排序。
2.遍历排序后数组:
若 nums[i]>0:因为已经排序好,所以后面不可能有三个数加和等于 0,直接返回结果。
对于重复元素:跳过,避免出现重复解

3.令左指针 L=i+1,右指针 R=n−1,当 L<R时,执行循环:

4.当 nums[i]+nums[L]+nums[R]==0,执行循环,判断左界和右界是否和下一位置重复,去除重复解。并同时将 L,RL,RL,R 移到下一位置,寻找新的解
若和大于 0,说明 nums[R]太大,R 左移
若和小于 0,说明 nums[L] 太小,L 右移

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {int n=nums.size();sort(nums.begin(),nums.end());vector<vector<int>> ans;for(int first=0;first<n;++first){if(first>0&&nums[first-1]==nums[first]){continue;}int third=n-1;for(int second=first+1;second<n;second++){if(second>first+1&&nums[second-1]==nums[second]){continue;}while(second < third &&nums[first]+nums[second]+nums[third]>0){third--;}if(second==third){break;}if (nums[first]+nums[second] + nums[third] == 0) {ans.push_back({nums[first], nums[second], nums[third]});}}}return ans;}
};

5.leetcode-18. 四数之和

(1)题目简述
给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):
在这里插入图片描述
(2)方法及思路(排序+双指针)
1.首先要定义四个指针first=0, second=first+1, third=second+1, forth=n-1(这是四个指针的初始位置),后续过程还要进行循环。
2.其次是对于重复元素的处理(切记要放在循环当中,否则只能除掉一个重复,尤其是third)
3.接着是对于结果的排查,如果结果小于0,third右移,如果结果大于0,forth左移。
4.最后将找到的值插入新的数组中。

(3)代码实现

class Solution
{
public:vector<vector<int>> fourSum(vector<int>& num, int target){vector<vector<int>>  newnum;sort(num.begin(), num.end());int n = num.size();for (int first = 0; first < n; ++first){if (first > 0 && num[first] == num[first - 1])continue;for (int second = first + 1; second < n; ++second){if (second > first + 1 && num[second] == num[second - 1])continue;int third = second + 1;int forth = n - 1;long long target_c = (long long)target - num[first] - num[second];while (third < forth){if (target_c == num[third] + num[forth]) {newnum.push_back({ num[first], num[second], num[third], num[forth] });do {third++;} while (third < n && num[third] == num[third - 1]);}else if (target_c > num[third] + num[forth]){third++;}elseforth--;}}}return newnum;}
};

6.leetcode-80. 删除有序数组中的重复项 II

(1)题目描述
给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使得出现次数超过两次的元素只出现两次 ,返回删除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
在这里插入图片描述
(2)方法及思路(双指针)
1.首先定义slow和fast位于第三个位置
2.如果slow-2和fast的元素相同,fast++
3.如果slow-2和fast不同,将slow处的元素替换为fast处的元素,并且和fast一起往前移。
(3)代码实现

class Solution {
public:int removeDuplicates(vector<int>& nums) {int n = nums.size();if (n <= 2) {return n;}int slow = 2, fast = 2;while (fast < n) {if (nums[slow - 2] != nums[fast]) {nums[slow] = nums[fast];++slow;}++fast;}return slow;}
};

(通解方法)

为了让解法更具有一般性,我们将原问题的「保留 2 位」修改为「保留 k 位」。
由于是保留 k 个相同数字,对于前 k 个数字,我们可以直接保留
对于后面的任意数字,能够保留的前提是:与当前写入的位置前面的第 k 个元素进行比较,不相同则保留
举个例子🌰[1,1,1,1,1,1,2,2,2,2,2,2,3]
1.首先我们先让前 2 位直接保留,得到 1,1
2.对后面的每一位进行继续遍历,能够保留的前提是与当前位置的前面 k 个元素不同(答案中的第一个 1),因此我们会跳过剩余的 1,将第一个 2 追加,得到 1,1,2
3.继续这个过程,这时候是和答案中的第 2 个 1 进行对比,因此可以得到 1,1,2,2
4.这时候和答案中的第 1 个 2 比较,只有与其不同的元素能追加到答案,因此剩余的 2 被跳过,3 被追加到答案:1,1,2,2,3
代码实现

class Solution {
public:int work(vector<int>& nums, int k) {int len = 0;for(auto num : nums)if(len < k || nums[len-k] != num)nums[len++] = num;return len;}int removeDuplicates(vector<int>& nums) {return work(nums, 2);}
};

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

ByteV“智农”平台--数字乡村可视化

“智农”平台基于自主可控的数字孪生技术、物联网技术、大数据技术&#xff0c;构建全流程的新型农业一体化管理平台&#xff0c;围绕产运销管理全流程&#xff0c;实现生产->存储->包装->运输->销售的全链条管理。融合农业数据管理、农业数据预警显示、多维数据综…

回归预测 | MATLAB实现IPSO-SVM改进粒子群优化算法优化支持向量机多输入单输出回归预测(多指标,多图)

回归预测 | MATLAB实现IPSO-SVM改进粒子群优化算法优化支持向量机多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xff09; 目录 回归预测 | MATLAB实现IPSO-SVM改进粒子群优化算法优化支持向量机多输入单输出回归预测&#xff08;多指标&#xff0c;多图&#xf…

Java智慧工地系统源码(微服务+Java+Springcloud+Vue+MySQL)

智慧工地系统是依托物联网、互联网、AI、可视化建立的大数据管理平台&#xff0c;是一种全新的管理模式&#xff0c;能够实现劳务管理、安全施工、绿色施工的智能化和互联网化。围绕施工现场管理的人、机、料、法、环五大维度&#xff0c;以及施工过程管理的进度、质量、安全三…

WPF国际化的实现方法(WpfExtensions.Xaml)

https://blog.csdn.net/eyupaopao/article/details/120090431 resx资源文件实现 resx资源文件&#xff0c;实现的过程比第一种复杂&#xff0c;但resx文件本身编辑比较简单&#xff0c;维护起来比较方便。需要用到的框架&#xff1a;WpfExtensions.Xaml 为每种语言添加.resx资…

Nginx的介绍

本资料转载于传智教育-解锁你的IT职业薪未来&#xff0c;仅用于学习和讨论&#xff0c;如有侵权请联系 视频地址&#xff1a;04-Nginx的优点_哔哩哔哩_bilibili 资源文档&#xff1a;链接&#xff1a;https://pan.baidu.com/s/1RlFl92FdxRUqc858JSxPSQ 提取码&#xff1a;12…

Postman接口自动化测试实例

一.实例背景 在实际业务中&#xff0c;经常会出现让用户输入用户密码进行验证的场景。而为了安全&#xff0c;一般都会先请求后台服务器获取一个随机数做为盐值&#xff0c;然后将盐值和用户输入的密码通过前端的加密算法生成加密后串传给后台服务器&#xff0c;后台服务器接到…

每个.NET开发都应掌握的C#委托事件知识点

上篇文章讲述了C#接口的知识点&#xff0c;本文将介绍C#委托事件知识点。C#作为.NET开发的核心语言之一&#xff0c;提供了丰富的特性来支持面向对象编程和事件驱动的模型。其中&#xff0c;委托和事件是C#中不可或缺的关键概念&#xff0c;每个.NET开发者都应该深入理解它们的…

常用字符串匹配算法

一、BF匹配 BF算法中的BF是Brute Force的缩写&#xff0c;中文叫作暴力匹配算法&#xff0c;也叫朴素匹配算法。 BF算法的时间复杂度很高&#xff0c;是O(nm)&#xff0c;但在实际的开发中&#xff0c;它却是一个比较常用的字符串匹配算法。 第一&#xff0c;实际的软件开发中…

JVM——配置常用参数,GC调优策略

文章目录 JVM 配置常用参数Java内存区域常见配置参数概览堆参数回收器参数项目中常用配置常用组合 常用 GC 调优策略GC 调优原则GC 调优目的GC 调优策略 JVM 配置常用参数 Java内存区域常见配置参数概览堆参数&#xff1b;回收器参数&#xff1b;项目中常用配置&#xff1b;常…

【nodejs】用Node.js实现简单的壁纸网站爬虫

1. 简介 在这个博客中&#xff0c;我们将学习如何使用Node.js编写一个简单的爬虫来从壁纸网站获取图片并将其下载到本地。我们将使用Axios和Cheerio库来处理HTTP请求和HTML解析。 2. 设置项目 首先&#xff0c;确保你已经安装了Node.js环境。然后&#xff0c;我们将创建一个…

cuOSD(CUDA On-Screen Display Library)库的学习

目录 前言1. cuOSD1.1 Description1.2 Getting started1.3 For Python Interface1.4 Demo1.5 Performance Table 2. cuOSD案例2.1 环境配置2.2 simple案例2.3 segment案例2.4 segment2案例2.5 polyline案例2.6 comp案例2.7 perf案例 3. cuOSD浅析3.1 simple_draw函数 4. 补充知…

小程序中display:flex和v-show,v-show不生效,uni-app

小程序中display:flex和v-show&#xff0c;v-show不生效、、 解决方案&#xff1a; display&#xff1a;flex样式的优先级高于了v-show &#xff0c;v-show其实就是display&#xff1a;none&#xff0c;display&#xff1a;flex优先级高于display&#xff1a;none。 使用 :s…

【系统工具】开源服务器监控工具WGCLOUD初体验

经常看到服务器上传下载流量一直在跑&#xff0c;也不知道是啥软件在偷偷联网~~~官网地址&#xff1a;www.wgstart.com&#xff0c;个人使用是免费的。 WGCLOUD官网介绍 "WGCLOUD支持主机各种指标监测&#xff08;cpu使用率&#xff0c;cpu温度&#xff0c;内存使用率&am…

了解生成对抗网络 (GAN)

一、介绍 Yann LeCun将其描述为“过去10年来机器学习中最有趣的想法”。当然&#xff0c;来自深度学习领域如此杰出的研究人员的赞美总是对我们谈论的主题的一个很好的广告&#xff01;事实上&#xff0c;生成对抗网络&#xff08;简称GAN&#xff09;自2014年由Ian J. Goodfel…

K8s学习笔记1

一、课程介绍&#xff1a; 1、背景&#xff1a; 1&#xff09;从基础设备主机化向容器化转换。 2&#xff09;从人肉式运维工作模式向自动化运维模式转换。 3&#xff09;从自动化运维体系向全体系智能化运维模式转换。 2、课程目标人群: 1&#xff09;掌握Linux操作系统基…

【数据分享】2006-2021年我国城市级别的节约用水相关指标(免费获取\20多项指标)

《中国城市建设统计年鉴》中细致地统计了我国城市市政公用设施建设与发展情况&#xff0c;在之前的文章中&#xff0c;我们分享过基于2006-2021年《中国城市建设统计年鉴》整理的2006—2021年我国城市级别的市政设施水平相关指标、2006-2021年我国城市级别的各类建设用地面积数…

ES:一次分片设计问题导致的故障

### 现象&#xff1a; 1. 单节点CPU持续高 2.写入骤降 3.线程池队列积压&#xff0c;但没有reject 4.使用方没有记录日志 ### 排查 1.ES监控 只能看到相应的结果指标&#xff0c;无法反应出原因。 2.ES日志&#xff1a;大量日志打印相关异常&#xff08;routate等调用栈&a…

【仿写tomcat】六、解析xml文件配置端口、线程池核心参数

线程池改造 上一篇文章中我们用了Excutors创建了线程&#xff0c;这里我们将它改造成包含所有线程池核心参数的形式。 package com.tomcatServer.http;import java.util.concurrent.*;/*** 线程池跑龙套** author ez4sterben* date 2023/08/05*/ public class ThreadPool {pr…

微服务-Ribbon(负载均衡)

负载均衡的面对多个相同的服务的时候&#xff0c;我们选择一定的策略去选择一个服务进行 负载均衡流程 Ribbon结构组成 负载均衡策略 RoundRobinRule&#xff1a;简单的轮询服务列表来选择服务器AvailabilityFilteringRule 对两种情况服务器进行忽略&#xff1a; 1.在默认情…

Elasticsearch 处理地理信息

1、GeoHash ​ GeoHash是一种地理坐标编码系统&#xff0c;可以将地理位置按照一定的规则转换为字符串&#xff0c;以方便对地理位置信息建立空间索引。首先要明确的是&#xff0c;GeoHash代表的不是一个点而是一个区域。GeoHash具有两个显著的特点&#xff1a;一是通过改变 G…