潍坊哪里能找到做网站的,毕业设计做网站论文,合肥制作网站的公司简介,飞数石家庄网站建设从今天开始更新数据结构的相关内容。#xff08;我更新博文的顺序一般是按照我当前的学习进度来安排#xff0c;学到什么就更新什么#xff08;简单来说就是我的学习笔记#xff09;#xff0c;所以不会对一个专栏一下子更新到底#xff0c;哈哈哈哈哈哈哈#xff01;我更新博文的顺序一般是按照我当前的学习进度来安排学到什么就更新什么简单来说就是我的学习笔记所以不会对一个专栏一下子更新到底哈哈哈哈哈哈哈 本专栏以力扣为落脚点以实际题目为依据来进行相应知识点的讲解和应用希望对你能有所帮助
废话不多说我们直接开始 文章目录 :fire:LC 2057 ----值相等的最小索引(简单):star:二分查找Binary Search :fire:LC 1464 ----数组中两元素的最大乘积简单:star:sort函数 :fire:LC 485----最大连续 1 的个数简单:fire:LC 27---- 移除元素简单:star:vector中删除元素的方法总结 :fire:LC 665----非递减数列中等 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(vectorint nums) {//获取数组长度int nnums.size();for(int i0;in;i){if(i%10nums[i]) return i;}return -1;}
};可能会有人问二分查找行不行答案是不行因为nums数组的元素之间并没有特定的联系是无序的不适合二分。
既然谈到了那就简单说说什么是二分吧。
⭐️二分查找Binary Search
是一种在有序数组中查找目标值的算法。它通过将目标值与数组的中间元素进行比较从而确定目标值可能存在的位置。
下面是一个简单的函数模板
int firstBadVersion(int *arr,int n) {//定义左右边界这里我称left和right为游标而不是指针避免混淆
int left-1,rightn;//定义中点
int mid0;//进行二分
while(right-left1){//记录中点
midleft(right-left)/2;//满足条件时
if(arr[mid]满足条件){//移动游标
rightmid;
}
//不满足条件时
else{
leftmid;
}
}
return right;
}可能有人会问游标为什么要取-1和n不能取0和n-1吗他们的中点不应该一样吗 答其实这是为了避免极端情况的发生如果左右边界即0和n-1满足条件时二分查找会出错你可以想想为什么。 换位置时一定是满足条件时换right吗 答不一定这个得具体情况具体分析 LC 1464 ----数组中两元素的最大乘积简单
题目链接https://leetcode.cn/problems/maximum-product-of-two-elements-in-an-array/?envTypelistenvId7q99qCXM
题目简介 给你一个整数数组 nums请你选择数组的两个不同下标 i 和 j使 (nums[i]-1)*(nums[j]-1) 取得最大值。 请你计算并返回该式的最大值。 代码示例
class Solution {
public:int maxProduct(vectorint nums) {//这里直接调用sort函数排序sort(nums.begin(),nums.end());//获取数组长度int lennums.size();//返回结果return (nums[len-1]-1)*(nums[len-2]-1);}
};这里我们用到了sort函数sort函数的时间复杂度通常为O(n log n)所以我决定写一个O(n)的解法出来
class Solution {
public:int maxProduct(vectorint nums) {int nnums.size();int max0;//最大值int maxIndex;//最大值索引int sec0;//次大值int secIndex;//次大值索引int i,j;//寻找最大值和其索引for(i0;in;i){if(nums[i]max) {maxnums[i];maxIndexi;}}//寻找次大值和其索引for(j0;jn;j){if(j!maxIndex){if(nums[j]sec) { secnums[j]; secIndexj; }}}int maxSum(max-1)*(sec-1);return maxSum;}
};既然用到了sort函数那就来简单介绍一下
⭐️sort函数
是一种常见的排序算法它能够将一个数组或容器中的元素按照指定的排序规则进行排列。
在C语言中sort函数在 algorithm 头文件中。基本形式sort(first,end,comp) 其中first和last是表示待排序范围的迭代器comp是一个可选的比较函数用于指定排序规则。如果不提供comp参数则默认按照升序排序。要想降序的话第三个参数可以写成greaterint()其中里面也可以写doublelongfloat等等 总的来说 升序sort(first,end,cmp)或者sort(first,end) 降序sort(first,end,greaterint() LC 485----最大连续 1 的个数简单
题目链接https://leetcode.cn/problems/max-consecutive-ones/?envTypelistenvId7q99qCXM
题目简介 给定一个二进制数组 nums 计算其中最大连续 1 的个数。 代码示例
class Solution {
public:int findMaxConsecutiveOnes(vectorint nums) {int nnums.size();//最长1的个数int maxLenOne0;//计数器1出现的个数int countOne0;for(int i0;in;i){if(nums[i]1) countOne;//计数器遇1自增else{ maxLenOne (maxLenOnecountOne)?maxLenOne:countOne;//对长度赋值countOne0;//计数器归0}}//边界值可能最后一个数不是0所以最后一段1的值没有被比较在此比较一次防止遗漏最优解maxLenOne (maxLenOnecountOne)?maxLenOne:countOne;return maxLenOne;}
}; LC 27---- 移除元素简单
题目链接https://leetcode.cn/problems/remove-element/?envTypelistenvId7q99qCXM
题目简介 给你一个数组 nums 和一个值 val你需要 原地 移除所有数值等于 val 的元素并返回移除后数组的新长度。 不要使用额外的数组空间你必须仅使用 O(1) 额外空间并 原地 修改输入数组。 元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。 代码示例
class Solution {
public:int removeElement(vectorint nums, int val) {// int n0;for(int i0;inums.size();i){if(nums[i]val){// ni;nums.erase(nums.begin()i);ii-1;}}return nums.size();}
};
这里就是一个线性枚举然后对当前值进行一个判断如果等于目标值就将其删除用到了vector:erase()函数。
⭐️vector中删除元素的方法总结
vector中删除元素大概有这么几种方法
nums.pop_back(); //删除最后一个元素nums.clear(); //清空nums中的元素nums.erase(nums.begin()i,nums.begin()j); //删除nums中从第i1个元素到第j1个的所有元素也就是索引[i,j]。写成nums.erase(nums.begin()i)就是直接删除第i1个元素下标为i LC 665----非递减数列中等
题目链接https://leetcode.cn/problems/non-decreasing-array/?envTypelistenvId7q99qCXM
题目简介 给你一个长度为 n 的整数数组 nums 请你判断在 最多 改变 1 个元素的情况下该数组能否变成一个非递减数列。 我们是这样定义一个非递减数列的 对于数组中任意的 i (0 i n-2)总满足 nums[i] nums[i 1]。 代码示例
class Solution {
public:bool checkPossibility(vectorint nums) {int nnums.size();if(n1 || n2) return true;int count0;int count10;int count20;vectorintnum1(nums);vectorintnum2(nums);for(int i1;in;i){if(nums[i]nums[i-1]){ nums[i-1]nums[i]; break; } }for(int i1;in;i){if(num1[i]num1[i-1]){num1[i]num1[i-1]; break;} }for(int i1;in;i){if(num2[i]num2[i-1]){if(i1n){num2[i]num2[i1]; break; } else num2[i]num2[n-2]; } } for(int i1;in;i){if(num1[i]num1[i-1]) count11;if(nums[i]nums[i-1]) count1;if(num2[i]num2[i-1]) count21;if(count1 count1 count21) return false;} return true;}
};
这道题我用的是枚举的方法暂时没啥更优化的方法以后想到了会进行更新
