目录第二章 线性表2.1 数组2.1.1 C实现动态数组vector2.1.2 数组中字符串逆序 leetcode 3442.1.3 调整数组元素顺序奇数在左边偶数放右边 leetcode 9052.1.4 删除数组中值为val的元素 leetcode 272.1.5 删除有序数组中重复元素 leetcode 262.1.6 移动0 leetcode 2832.1.7 有序数组的平方 9772.1.8 二分查找 704本文记录数据结构与算法的线性结构—数组并刷题作为练习。第二章 线性表2.1 数组数组在内存中是连续存储的下面使用C实现一个动态数组vector.2.1.1 C实现动态数组vector需求实现动态数组可以添加、删除、插入、是否为空、返回大小、下标访问等功能。#includeiostream#includevectorusingnamespacestd;classVector{public:explicitVector(intsize3)noexcept:m_point_(newint[size]),m_current_(0),m_total_(size){}virtual~Vector()noexcept{cout析构函数执行endl;if(m_point_!nullptr){delete[]m_point_;}}public:// push_back()voidpush_back(intvalue)noexcept{// 判断已经满了if(m_current_m_total_){expand(m_total_*2);}m_point_[m_current_]value;return;}intsize()constnoexcept{returnm_current_;}intoperator[](inti){returnm_point_[i];}constintoperator[](inti)const{returnm_point_[i];}// pop_back()voidpop_back(){if(empty()){return;}m_current_--;return;}boolempty()const{returnm_current_0;}intfront()constnoexcept{if(empty()){return-1;}returnm_point_[0];}voidinsert(intindex,intvalue)noexcept{if(empty()){return;}if(indexm_current_){return;}if(m_current_m_total_){expand(m_total_*2);}// 移动元素 6 5 4intim_current_;for(;iindex;--i){m_point_[i]m_point_[i-1];}m_point_[i]value;m_current_;return;}private:voidexpand(intsize)noexcept{Vectorvec(20);memcpy(vec.m_point_,this-m_point_,this-m_current_*sizeof(int));delete[]m_point_;m_point_vec.m_point_;vec.m_point_nullptr;m_total_*2;return;}friendostreamoperator(ostreamout,constVectorsrc);private:int*m_point_;intm_current_;// 指向数组中空位置索引intm_total_;};ostreamoperator(ostreamout,constVectorsrc){for(inti0;isrc.m_current_;i){outsrc.m_point_[i] ;}outendl;returnout;}2.1.2 数组中字符串逆序 leetcode 344对应题目Leetcode344: https://leetcode.cn/problems/reverse-string/编写一个函数其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。不要给另外的数组分配额外的空间你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。示例 1输入s [“h”,“e”,“l”,“l”,“o”]输出[“o”,“l”,“l”,“e”,“h”]示例 2输入s [“H”,“a”,“n”,“n”,“a”,“h”]输出[“h”,“a”,“n”,“n”,“a”,“H”]**解题思路**两个指针一个指向开始一个指向末尾元素然后使用std::swap(s[begin],s[end–]);当begin end时交换完毕。// 思想两个指针一个指向开始一个指向结束位置然后进行交换。// 当p ! q 时就后移动voidreverseString(vectorchars){intbegin0;intends.size()-1;while(beginend){std::swap(s[begin],s[end--]);}return;}voidtest(){std::vectorcharvecc{a,b,c,d};inverse(vecc);for(autov:vecc){coutv ;}coutendl;}总结swap用法交换两个对象。2.1.3 调整数组元素顺序奇数在左边偶数放右边 leetcode 905https://leetcode.cn/problems/sort-array-by-parity/description/示例 1输入nums [3,1,2,4]输出[2,4,3,1]解释[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。示例 2输入nums [0]输出[0]解题思路双指针方法两个指针p和qp从前向后找奇数q从后向前找偶数p找到奇数就break;q找到偶数也break;然后交换两个数后p,q–.判断奇数高效方法*p ob1 1按位运算。voidAdjustArr(vectorintvec){intleft0;intrightvec.size()-1;while(leftright){while(leftright){// left 从前往后找奇数找到就Break;if((vec[left]0b1)1)// 这里注意运算符优先级 所以要加括号{break;}// 否则没找到说明一直是偶数leftleft;}// right 从后往前找偶数找到就Break;while(leftright){if((vec[right]0b1)0){break;}// 否则没找到说明一直是奇数right----right;}// left right 说明有交换直接交换if(leftright){std::swap(vec[left],vec[right]);left;--right;}}}需要注意的是使用 按位与方式判断奇数偶数时需要注意运算符顺序。(vec[right] 0b1) 0 加括号。2.1.4 删除数组中值为val的元素 leetcode 27题目要求原地删除数组nums中元素等于val的元素并返回数组中非val的元素数量。**解题思路双指针思想。**本质上将数组中非val值从后向前覆盖。使用快慢指针fast和slow快指针fast逐个元素向后移动当快指针指向元素值不等于val时就更新操作 nums[slow] nums[fast]; 该操作本质就是将符合条件的元素不等于val移动到slow指向的数组索引位置只不过slow对应的数组就是原数组最后得到的slow值就是取出val后数组的末尾位置。最后slow会多加一次所以slow返回的就是数组的大小。在这里插入代码片intDeleteVal(vectorintnums,intval){intiSlow0;for(intiFast0;iFastnums.size();iFast){if(val!nums[iFast]){nums[iSlow]nums[iFast];iSlow;}}returniSlow;}voidtest(){vectorintvec{1,2,2,2,4,5,6};// 删除第3个元素for(intv:vec){coutv ;}coutendl;// 调整顺序奇偶数intcountDeleteVal(vec,2);for(intv:vec){coutv ;}}2.1.5 删除有序数组中重复元素 leetcode 26**题目要求**对给定的非严格递增排序数组 nums 删除重复元素在删除重复元素之后每个元素只出现一次并返回删除后的数组长度。要求上述操作必须通过原地修改数组的方法使用 O(n) 的空间复杂度完成。效果将非严格递增的数组变化为严格递增的数组。解题思路数组从后向前覆盖方式去除重复元素。设置两个指针fast和slowfast指针逐个遍历整个数组slow指针指向新数组新数组与原数组相同的待插入位置的索引。每次都比较fast指针的前后两个元素即vec[fast] ! vec[fast - 1] 当两个元素不等时就移动到slow指向位置。对比这个题与上一道不同之处在于当前元素和前一个元素比较所以left和right都从1开始当 right 和 right -1 不等时候移动到left指向的位置相等则直接right。intremoveChongfu(vectorintvec){intsizevec.size();intleft1,right1;// 注意这里所有的都是从1开始。while(rightsize){if(vec[right]!vec[right-1]){vec[left]vec[right];}right;}returnleft;}2.1.6 移动0 leetcode 283题目要求给定一个数组 nums编写一个函数将所有 0 移动到数组的末尾同时保持非零元素的相对顺序。请注意必须在不复制数组的情况下原地对数组进行操作。示例 1:输入: nums [0,1,0,3,12]输出: [1,3,12,0,0]示例 2:输入: nums [0]输出: [0]分析这道题还是考察双指针与去除重复元素(slow 和 fast 从1开始)和去除指定元素思路相同左右指针从0开始。slow指向新数组的待插入的位置fast指向当前要处理的元素。初始时两个指针都指向0位置之后fast每次向后1当fast不等于0时将fast位置与slow位置交换交换之后进行slow(如果slow之后指向的是0元素则再次与fast交换时就将0交换到了非0数组的最后)。r1 3 12 0 0lvoidzeormove(vectorintnums){intslow0;intfast0;while(fastnums.size()){if(nums[fast]!0){swap(nums[slow],nums[fast]);slow;}fast;}}2.1.7 有序数组的平方 977对一个非递减序列排序的整数数组Nums, 返回每个数的平方组成的新数组新数组也是非递减顺序。示例 1输入nums [-4,-1,0,3,10]输出[0,1,9,16,100]解释平方后数组变为 [16,1,0,9,100]排序后数组变为 [0,1,9,16,100]示例 2输入nums [-7,-3,2,3,11]输出[4,9,9,49,121]解题思路如果一个序列是非递减情况这个序列平方后最大值一定在两端分三种情况举例情况1序列有正负数平方后最大值分别在最前和最后两边-5 -3 -1 0 1 2 3 , 平方后25 9 1 0 1 4 9情况2序列中只有负数平方后最大值在左边。-5 -3 -2 -1 0 , 平方后25 9 4 1 0情况3序列中只有正数平方后最大值在右边。1 3 5 7 ,平方后最大值在右边。1 9 25 49思路开辟一个新数组用来保存排序后的结果使用两个指针分别指向求平方数组的前和后前后两个指针是元素求平方后的最大值位置。找出最大值后依次放入新开辟的数组中从后往前存放。vectorintsortedSquares(vectorintnums){vectorintresult(nums.size());intindexnums.size()-1;intleft0;intrightnums.size()-1;std::functionint(int)square[](intx){returnx*x;};while(leftright){if(square(nums[left])square(nums[right])){result[index--]square(nums[right]);right--;}else{result[index--]square(nums[left]);left;}}returnresult;}核心逻辑每次比较都找出最的元素结果数组从后向前保存大的元素。2.1.8 二分查找 704leetcode 704,二分查找题目描述如下给定一个 n 个元素有序的升序整型数组 nums 和一个目标值 target 写一个函数搜索 nums 中的 target如果 target 存在返回下标否则返回 -1。要求必须时间复杂度为O(logn)。示例 1:输入: nums [-1,0,3,5,9,12], target 9输出: 4解释: 9 出现在 nums 中并且下标为 4示例 2:输入: nums [-1,0,3,5,9,12], target 2输出: -1解释: 2 不存在 nums 中因此返回 -1解题思路如果是有序数组在对其进行查找某个元素时就使用二分法。每次循环时先计算middle (left right) / 2; 如果相等就直接返回下标如果不等根据查找的数组比arr[middle]大小来判断从midlle左边查找还是右边查找。intsearch(vectorintnums,inttarget){intleft0;intrightnums.size()-1;while(leftright){intmiddle(leftright)/2;if(nums[middle]target){returnmiddle;}elseif(nums[middle]target){rightmiddle-1;}elseif(nums[middle]target){leftmiddle1;}}return-1;}算法分析时间复杂度o(logn).