-
基础数据结构之——【顺序表】(上)
从今天开始更新数据结构的相关内容。（我更新博文的顺序一般是按照我当前的学习进度来安排，学到什么就更新什么（简单来说就是我的学习笔记），所以不会对一个专栏一下子更新到底，哈哈哈哈哈哈哈！！！😄）
本专栏以
力扣为落脚点，以实际题目为依据来进行相应知识点的讲解和应用，希望对你能有所帮助！废话不多说，我们直接开始！
🔥LC 2057 ----值相等的最小索引(简单)
题目链接：https://leetcode.cn/problems/smallest-index-with-equal-value/
题目简介：
给你一个下标从 0 开始的整数数组 nums ，返回 nums 中满足 i mod 10 == nums[i] 的最小下标 i ；如果不存在这样的下标，返回 -1 。
- x mod y 表示 x 除以 y 的 余数 。
这道题就很简单了，按照题目说的条件，直接线性枚举（可以理解为直接遍历）一遍，就可找出答案。
- 时间复杂度：O(n)
- 空间复杂度：O(1)
代码示例：
class Solution { public: int smallestEqual(vector<int>& nums) { //获取数组长度 int n=nums.size(); for(int i=0;i<n;i++){ if(i%10==nums[i]) return i; } return -1; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
可能会有人问，二分查找行不行，答案是不行！因为nums数组的元素之间并没有特定的联系（是无序的），不适合二分。
既然谈到了，那就简单说说什么是二分吧。
⭐️二分查找（Binary Search）：
是一种在有序数组中查找目标值的算法。它通过将目标值与数组的中间元素进行比较，从而确定目标值可能存在的位置。
下面是一个简单的函数模板：
int firstBadVersion(int *arr,int n) { //定义左右边界，这里我称left和right为游标，而不是指针！避免混淆 int left=-1,right=n; //定义中点 int mid=0; //进行二分 while(right-left>1){ //记录中点 mid=left+(right-left)/2; //满足条件时： if(arr[mid]满足条件){ //移动游标 right=mid; } //不满足条件时： else{ left=mid; } } return right; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
-
可能有人会问，游标为什么要取-1和n，不能取0和n-1吗？他们的中点不应该一样吗？
答：其实这是为了避免极端情况的发生，如果左右边界（即0和n-1）满足条件时，二分查找会出错，你可以想想为什么。
-
换位置时，一定是满足条件时换right吗？
答：不一定，这个得具体情况具体分析！
🔥LC 1464 ----数组中两元素的最大乘积（简单）
题目简介：
给你一个整数数组 nums，请你选择数组的两个不同下标 i 和 j，使 (nums[i]-1)*(nums[j]-1) 取得最大值。
请你计算并返回该式的最大值。代码示例：
class Solution { public: int maxProduct(vector<int>& nums) { //这里直接调用sort函数排序： sort(nums.begin(),nums.end()); //获取数组长度 int len=nums.size(); //返回结果 return (nums[len-1]-1)*(nums[len-2]-1); } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
这里我们用到了
sort函数，sort函数的时间复杂度通常为O(n log n)，所以我决定写一个O(n)的解法出来：class Solution { public: int maxProduct(vector<int>& nums) { int n=nums.size(); int max=0;//最大值 int maxIndex;//最大值索引 int sec=0;//次大值 int secIndex;//次大值索引 int i,j; //寻找最大值和其索引 for(i=0;i<n;i++){ if(nums[i]>max) { max=nums[i]; maxIndex=i; } } //寻找次大值和其索引 for(j=0;j<n;j++){ if(j!=maxIndex){ if(nums[j]>sec) { sec=nums[j]; secIndex=j; } } } int maxSum=(max-1)*(sec-1); return maxSum; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
既然用到了sort函数，那就来简单介绍一下：
⭐️sort函数：
是一种常见的排序算法，它能够将一个数组或容器中的元素按照指定的排序规则进行排列。
- 在C++语言中，sort函数在
< algorithm >头文件中。 - 基本形式：
sort(first,end,comp)
其中，first和last是表示待排序范围的迭代器，comp是一个可选的比较函数，用于指定排序规则。如果不提供comp参数，则默认按照升序排序。要想降序的话，第三个参数可以写成
greater，其中<>里面也可以写double，long，float等等() - 总的来说：
升序：sort(first,end,cmp)或者sort(first,end)
降序：sort(first,end,greater()）
🔥LC 485----最大连续 1 的个数（简单）
题目链接：https://leetcode.cn/problems/max-consecutive-ones/?envType=list&envId=7q99qCXM
题目简介：
给定一个二进制数组 nums ， 计算其中最大连续 1 的个数。
代码示例：
class Solution { public: int findMaxConsecutiveOnes(vector<int>& nums) { int n=nums.size(); //最长1的个数 int maxLenOne=0; //计数器：1出现的个数 int countOne=0; for(int i=0;i<n;i++){ if(nums[i]==1) countOne++;//计数器：遇1自增 else{ maxLenOne= (maxLenOne>countOne)?maxLenOne:countOne;//对长度赋值 countOne=0;//计数器归0 } } //边界值：可能最后一个数不是0，所以最后一段1的值没有被比较，在此比较一次，防止遗漏最优解 maxLenOne= (maxLenOne>countOne)?maxLenOne:countOne; return maxLenOne; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
🔥LC 27---- 移除元素（简单）
题目链接：https://leetcode.cn/problems/remove-element/?envType=list&envId=7q99qCXM
题目简介：
给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。
不要使用额外的数组空间，你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。代码示例：
class Solution { public: int removeElement(vector<int>& nums, int val) { // int n=0; for(int i=0;i<nums.size();i++){ if(nums[i]==val){ // n=i; nums.erase(nums.begin()+i); i=i-1; } } return nums.size(); } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
这里就是一个线性枚举，然后对当前值进行一个判断，如果等于目标值，就将其删除，用到了vector:erase()函数。
⭐️vector中删除元素的方法总结：
vector中删除元素大概有这么几种方法：
nums.pop_back(); //删除最后一个元素nums.clear(); //清空nums中的元素nums.erase(nums.begin()+i,nums.begin()+j); //删除nums中从第i+1个元素到第j+1个的所有元素，也就是索引[i,j]。写成nums.erase(nums.begin()+i)就是直接删除第i+1个元素（下标为i）
🔥LC 665----非递减数列（中等）
题目链接：https://leetcode.cn/problems/non-decreasing-array/?envType=list&envId=7q99qCXM
题目简介：
给你一个长度为 n 的整数数组 nums ，请你判断在 最多 改变 1 个元素的情况下，该数组能否变成一个非递减数列。
我们是这样定义一个非递减数列的： 对于数组中任意的 i (0 <= i <= n-2)，总满足 nums[i] <= nums[i + 1]。代码示例：
class Solution { public: bool checkPossibility(vector<int>& nums) { int n=nums.size(); if(n==1 || n==2) return true; int count=0; int count1=0; int count2=0; vector<int>num1(nums); vector<int>num2(nums); for(int i=1;i<n;i++){ if(nums[i]<nums[i-1]){ nums[i-1]=nums[i]; break; } } for(int i=1;i<n;i++){ if(num1[i]<num1[i-1]){ num1[i]=num1[i-1]; break; } } for(int i=1;i<n;i++){ if(num2[i]<num2[i-1]){ if(i+1<n){ num2[i]=num2[i+1]; break; } else num2[i]=num2[n-2]; } } for(int i=1;i<n;i++){ if(num1[i]<num1[i-1]) count1=1; if(nums[i]<nums[i-1]) count=1; if(num2[i]<num2[i-1]) count2=1; if(count==1 && count==1 && count2==1) return false; } return true; } };- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
这道题我用的是枚举的方法，暂时没啥更优化的方法，以后想到了会进行更新！
-
相关阅读:
Qt文件读写的天花板QFile和IODevice搭配第一集
5233: 【J1】【map】统计数字
多路分支选择结构—switch语句
搭建Spring的源码环境
微信小程序 -- 页面间通信
安装PLC1.9.1其它版本号Python3.6+PCL1.9.1+VS2017+gtkbundle_3.6.4版本
gdb and coredump分析
Unity 之 音频类型和编码格式介绍
Java设计模式-原型模式
centos如何安装最新版nodejs
- 原文地址：https://blog.csdn.net/weixin_73453526/article/details/133468654
