泰州网站设计公司,软件开发项目管理书籍,怎么做才能发布网站,房产网站cms注#xff1a;本文学习借鉴于《代码随想录》
一.介绍数组
数组是储存在连续内存空间中的相同类型数据的集合
数组名的理解#xff1a; 数组名就是数组⾸元素(第⼀个元素)的地址是对的#xff0c;但是有两个例外#xff1a; sizeof(数组名)#xff0c;sizeof中单独放数…注本文学习借鉴于《代码随想录》
一.介绍数组
数组是储存在连续内存空间中的相同类型数据的集合
数组名的理解 数组名就是数组⾸元素(第⼀个元素)的地址是对的但是有两个例外 sizeof(数组名)sizeof中单独放数组名这⾥的数组名表⽰整个数组计算的是整个数组的⼤⼩ 单位是字节 数组名这⾥的数组名表⽰整个数组取出的是整个数组的地址整个数组的地址和数组⾸元素 的地址是有区别的 除此之外任何地⽅使⽤数组名数组名都表⽰⾸元素的地址 数组中的元素不能删除只能覆盖。 二.数组解题法 下面我们介绍数组解决问题的几大方法。 1.二分查找
适用类型对于数组中在范围查找元素的位置求解平方根以及插入元素等。
使用前提二分查找使用前一定要观察元素是否已排好位置
二分查找主要有以下两种写法
1.1.左闭右闭[left,right]
该写法注意点本文不再进行基础实现讲解可以翻看我的之前文章有实现过程 1.while (left right) 要使⽤ 因为 left right 是有意义的所以使⽤ 2.if (nums[middle] target) right 要赋值为 middle - 1 因为当前这个 nums[middle] ⼀定不是 target 那么接下来要查找的左区间结束下标位置就是 middle - 1 对于leedcode这题力扣LeetCode官网 - 全球极客挚爱的技术成长平台
就是典型的第一类写法
下面是我对于该题的C语言解法代码
int search(int* nums, int numsSize, int target)
{int left0;int rightnumsSize-1;while(leftright){int mid(leftright)/2;if(nums[mid]target){leftmid1;}else if(nums[mid]target){rightmid-1;}else{return mid;}}return -1;
} 时间复杂度 O(log n) 空间复杂度 O(1) 1.2.左闭右开[left,right)
注意点 1.while (left right) 这⾥使⽤ , 因为 left right 在区间 [left, right) 是没有意义的 2.if (nums[middle] target) right 更新为 middle 因为当前 nums[middle] 不等于 target 去左区间继续寻找⽽寻找区间是左闭右开区间所以right 更新为 middle 即下⼀个查询区间不会去⽐较 nums[middle]。 还是刚才那题现在我们用第二种方法实现它 int search(int* nums, int numsSize, int target)
{int left0;int rightnumsSize;//注意right现在是被赋值为numsSizewhile(leftright){int mid(leftright)/2;if(nums[mid]target){leftmid1;}else if(nums[mid]target){rightmid;//由于用边界为空所以rightmid而不是rightmid-1}else{return mid;}}return -1;
} 补充如果你想问有没有左开右闭的二分查找我想说的是有当使用的意义不大所以作者这里就不讲了。 下面是推荐的练习题 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 69.x 的平⽅根 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 367.有效的完全平⽅数 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 (35.搜索插⼊位置) 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 (34.在排序数组中查找元素的第⼀个和最后⼀个位置) 这些题可能对你有点难请加油我相信你一定可以的。 2.双指针法重点 解释双指针法是定义两个有关联的变量可能是指针也可能是整数通过他们实现对数组的操作使得高效快捷。 具体的我们来在题目中去感受吧 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 对于leedcod这题大家第一反应可能就是暴力出手疯狂遍历数组一个for循环不行那我两个再不行再加但是现在来看看大佬们的思路让你直呼666…… 双指针法就是这题的良方妙药下面我带着大家用双指针来实现它 由于是数组我们定义两个整型变量即slow和fast表示快慢指针 快指针寻找新数组的元素 新数组就是不含有⽬标元素的数组 慢指针指向更新新数组下标的位置 看代码 int removeElement(int* nums, int numsSize, int val)
{//双指针法int src0;int dest0;while(srcnumsSize){if(nums[src]!val){nums[dest]nums[src];}else{src;}}return dest;
} 是不是大呼学到了。 关于双指针的使用场景大家需要多做题自己把握这样慢慢可能就能感受的啥题目是考察双指针了。 来再带着大家看一题 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 对于这题我们就直接开始双指针吧 这题比较特殊它是有序的又是问平方只需要比较负数的平方与整数平方关系即可大家想想如果我们定义两个指针一个指向头一个指向尾是不是就可以最快的进行排好序。 看代码实现 /*** Note: The returned array must be malloced, assume caller calls free().*/
int* sortedSquares(int* nums, int numsSize, int* returnSize)
{*returnSize numsSize;int* arr(int*)malloc(numsSize*sizeof(int));int n0;int mnumsSize-1;int cnumsSize-1;while(nm){int inums[n]*nums[n];int jnums[m]*nums[m];if(ij){arr[c--]i;n;}else//ji{arr[c--]j;m--;}}return arr;
} 双指针⻛骚起来也是⽆敌转自程序员Carl 下面给大家推荐几道好题不用说谢了这种好东西一定要拿出来共享当时快把我写吐了 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 刷完绝对对于双指针有一定的使用感觉了。 3.滑动窗口 如果大家深入了解过数组就一定听过数组恶魔---滑动窗口 对于滑动窗口连leedcode上都是中等题起步 下面我们就一题进行了解 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 滑动窗⼝ 就是不断的调节⼦序列的起始位置和终⽌位置从⽽得出我们要想的结果 我们应该可以看出如果我们纯暴力来解决这题就是两个for循环但是如果用滑动窗口一个for循环即可下面来看看实现过程 ⾸先要思考 如果⽤⼀个 for 循环那么应该表示滑动窗⼝的起始位置还是终⽌位置。 如果只⽤⼀个for 循环来表示 滑动窗⼝的起始位置那么如何遍历剩下的终⽌位置 此时难免再次陷⼊ 暴⼒解法的怪圈。 所以只⽤⼀个for 循环那么这个循环的索引⼀定是表示滑动窗⼝的终⽌位置。 在本题中实现滑动窗⼝主要确定如下三点 窗⼝内是什么 如何移动窗⼝的起始位置 如何移动窗⼝的结束位置 窗⼝就是 满⾜其和 ≥ s 的⻓度最⼩的 连续 ⼦数组。 窗⼝的起始位置如何移动如果当前窗⼝的值⼤于 s 了窗⼝就要向前移动了也就是该缩⼩了。 窗⼝的结束位置如何移动窗⼝的结束位置就是遍历数组的指针也就是 for 循环⾥的索引. 看代码实现过程 int minSubArrayLen(int target, int* nums, int numsSize)
{int size0;int resultINT_MAX;int left0;int sum0;for(int right0;rightnumsSize;right){sumnums[right];while(sumtarget){sizeright-left1;resultresultsize?result:size;sum-nums[left];}}return resultINT_MAX?0:result;
} 时间复杂度直接从ON*N)降到了O(N),可见这种方法的强大。 推荐大家去B站看代码随想录视频可能理解更加深入。 下面给大家推荐题目吧 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 力扣LeetCode官网 - 全球极客挚爱的技术成长平台 这两题是真的难啊加油 最后给小编点赞呗kiss
