C++数据结构与算法_线性表_数组_概念动态数组，刷题

第二章 线性表

2.1 数组

数组在内存中是连续存储的，下面使用C++实现一个动态数组vector.

2.1.1 C++实现动态数组vector

需求：实现动态数组，可以添加、删除、插入、是否为空、返回大小、下标访问等功能。

#include<iostream>#include<vector>usingnamespacestd;classVector{public:explicitVector(intsize=3)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_;}int&operator[](inti){returnm_point_[i];}constint&operator[](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(index>m_current_){return;}if(m_current_==m_total_){expand(m_total_*2);}// 移动元素 6 5 4inti=m_current_;for(;i>index;--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;}friendostream&operator<<(ostream&out,constVector&src);private:int*m_point_;intm_current_;// 指向数组中空位置索引intm_total_;};ostream&operator<<(ostream&out,constVector&src){for(inti=0;i<src.m_current_;++i){out<<src.m_point_[i]<<" ";}out<<endl;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(vector<char>&s){intbegin=0;intend=s.size()-1;while(begin<end){std::swap(s[begin++],s[end--]);}return;}voidtest(){std::vector<char>vecc{'a','b','c','d'};inverse(vecc);for(auto&v:vecc){cout<<v<<" ";}cout<<endl;}

总结swap用法，交换两个对象。

2.1.3 调整数组元素顺序，奇数在左边，偶数放右边 leetcode 905

https://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和q，p从前向后找奇数，q从后向前找偶数，p找到奇数就break;q找到偶数也break;然后交换两个数后，p++,q–.
判断奇数高效方法，*p & ob1 == 1，按位运算。

voidAdjustArr(vector<int>&vec){intleft=0;intright=vec.size()-1;while(left<right){while(left<right){// left 从前往后找奇数，找到就Break;if((vec[left]&0b1)==1)// 这里注意运算符优先级，== > & 所以要加括号{break;}// 否则没找到说明一直是偶数，left++++left;}// right 从后往前找偶数，找到就Break;while(left<right){if((vec[right]&0b1)==0){break;}// 否则没找到说明一直是奇数，right----right;}// left < right 说明有交换，直接交换if(left<right){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(vector<int>&nums,intval){intiSlow=0;for(intiFast=0;iFast<nums.size();++iFast){if(val!=nums[iFast]){nums[iSlow]=nums[iFast];++iSlow;}}returniSlow;}voidtest(){vector<int>vec{1,2,2,2,4,5,6};// 删除第3个元素for(intv:vec){cout<<v<<" ";}cout<<endl;// 调整顺序，奇偶数intcount=DeleteVal(vec,2);for(intv:vec){cout<<v<<" ";}}

2.1.5 删除有序数组中重复元素 leetcode 26

**题目要求：**对给定的非严格递增排序数组 nums 删除重复元素，在删除重复元素之后，每个元素只出现一次，并返回删除后的数组长度。
要求：上述操作必须通过原地修改数组的方法，使用 O(n) 的空间复杂度完成。
效果：将非严格递增的数组变化为严格递增的数组。
解题思路：数组从后向前覆盖方式去除重复元素。设置两个指针fast和slow，fast指针逐个遍历整个数组，slow指针指向新数组（新数组与原数组相同）的待插入位置的索引。每次都比较fast指针的前后两个元素，即vec[fast] != vec[fast - 1] 当两个元素不等时，就移动到slow指向位置。
对比：
这个题与上一道不同之处在于，当前元素和前一个元素比较，所以left和right都从1开始，当 right 和 right -1 不等时候，移动到left指向的位置；相等则直接right++。

intremoveChongfu(vector<int>&vec){intsize=vec.size();intleft=1,right=1;// 注意，这里所有的都是从1开始。while(right<size){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数组的最后)。
r
1 3 12 0 0
l

voidzeormove(vector<int>&nums){intslow=0;intfast=0;while(fast<nums.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

思路：开辟一个新数组用来保存排序后的结果，使用两个指针，分别指向求平方数组的前和后，前后两个指针是元素求平方后的最大值位置。找出最大值后，依次放入新开辟的数组中，从后往前存放。

vector<int>sortedSquares(vector<int>&nums){vector<int>result(nums.size());intindex=nums.size()-1;intleft=0;intright=nums.size()-1;std::function<int(int)>square=[](intx){returnx*x;};while(left<=right){if(square(nums[left])<square(nums[right])){result[index--]=square(nums[right]);right--;}else{result[index--]=square(nums[left]);left++;}}returnresult;}

核心逻辑：每次比较都找出最的元素，结果数组从后向前保存大的元素。

2.1.8 二分查找 704

leetcode 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(vector<int>&nums,inttarget){intleft=0;intright=nums.size()-1;while(left<=right){intmiddle=(left+right)/2;if(nums[middle]==target){returnmiddle;}elseif(nums[middle]<target){right=middle-1;}elseif(nums[middle]>target){left=middle+1;}}return-1;}

算法分析：时间复杂度，o(logn).