代码随想录打卡 Day 1
1.二分法
leetcode编号:704.二分查找
【题目描述】
在一个有序无重复有元素的数组nums中，寻找一个元素target，如果找到乐就返回对应的下标，如果没有找到就返回-1。
【题目分析】
二分法的前提是数组为有序数组，题目中同时强调无重复元素。两者都是使用二分法的前提条件。
二分法需要注意的主要就是区间的定义。区间的定义就是不变量--在while循环中，每一次的边界处理的定义来操作，即所谓的”循环不变量“规则。
常见的二分法写法一般有左闭右闭的区间 $[left,right]$和左闭右开的区间$[left,right)$。在编写代码时，必须时刻按照区间定义来实现函数。
下面以左闭右闭区间来实现该算法:
int binarySearch(vector<int>& nums, int target) {
int left=0, right=nums.size()-1;
while(left<=right){ //由于区间是左右闭区间，所以边界条件为left<=right
int mid = left + (right-left)/2;
if(nums[mid]<target){ //target在左半区间的处理
left = mid+1;
}
else if (nums[mid]>target){ //target在右半区间的处理
right = mid-1;
}
else {
return mid;
}
}
//未找到目标值
return -1;
}
2.移除元素
leetcode编号:27.移除元素
【题目描述】
原地移除数组中所有等于val的元素，要求不能使用额外的辅助空间，即空间复杂度为$O(1)$.
返回移除后的新数组的size
【题目分析】
暴力解法
不难想出，本体的一个暴力解法是使用两个for循环，第一个for循环循环数组元素，第二个for循环更新数组，其时间复杂度为$O(n^2)$。暴力解的代码如下:
int removeElement(vector<int>& nums,int val){
int size=nums.size()
for (int i= 0; i < size;i++){
if(nums[i] == val){ //发现val值的元素，将数组元素集体向前移动一位
for (int j = i+1;j<size;j++){
nums[j-1] = nums[j];
}
i--; //找到元素后下标i以后的数值都向前移动一位
size--; //数组的长度-1
}
}
return size;
}
快慢指针法
但是，快慢指针法通过一个快指针和一个慢指针在一个for循环内完成两个for循环的工作。其中两个指针相对有序。
int removeElement(vector<int>& nums, int val) { //双指针法移除数组元素
int Slow = 0;
for(int Fast = 0; Fast < nums.size(); Fast++){
if(val != nums[Fast]){ //Fast未指向值为val的元素时，Slow与Fast同时向后移动
//Fast指向值为val的元素时，Fast向后移动，Slow不动
nums[Slow] = nums[Fast]; //略去val元素
Slow++;
}
}
return Slow; //Slow表示元素个数
}
3.长度最小的子数组
leetcode题号:209.长度最小的子数组
【题目描述】
在一个正整数数组nums中找到最小长度的连续子数组，使子数组元素之和大于或等于s.返回满足条件的连续子数组的最小长度，如果没有找到则返回0.
【题目分析】
暴力解法
暴力解法同样是使用两个for循环，不断寻找符合条件的子数组，时间复杂度为$O(n^2)$
滑动窗口法
数组操作中另一个重要方法是滑动窗口法，所谓的滑动窗口，就是不断调节子数组的起始和终止位置，从而得到我们想要的答案。实现滑动窗口，主要确定:
-
窗口内的元素是什么？ —在本问中，窗口内的元素就是数值和大于等于
s的长度最小的连续子数组 -
如何移动窗口的起始位置？ —在本问中，当当前窗口内元素总和大于等于
s时，窗口向前移动 -
如何移动窗口的终止位置？—在本问中。窗口结束位置就是
for循环遍历数组的指针。本题使用滑动窗口法的CPP代码如下，通过该方法，不断调节子数组的起始位置，从而将时间复杂度将为$O(n^2)$:
int findShortestSubArray2(vector<int>& nums, int k) { // 滑动窗口 时间复杂度为O(N) int result = INT32_MAX; int sum =0; int subLength = 0; for (int i=0, j=0; j<nums.size(); j++){ sum += nums[j]; while( sum >= k){ subLength = j-i+1; result = min(result, subLength); sum -= nums[i++]; } } return result == INT32_MAX ? 0 : result; }
4.有序数组的平方
leetcode题号:977:有序数组的平方
【题目描述】
给你一个按 非递减顺序排序的整数数组 nums，返回 每个数字的平方组成的新数组，要求也按非递减顺序 排序。
【题目分析】
同样，一个简单的想法是先将nums数组自平方，然后使用快速排序将nums数组进行排序，时间复杂度为$O(nlogn)$。
本题也可以使用双指针法进行操作，利用双指针将nums元素按照元素绝对值重新排序，然后对nums每个元素平方处理。由于给出的nums数组是非递减顺序排序的整数数组，这就给按绝对值重新排序带来了一定便利性。
vector<int> sortedSquare(vector<int>& nums) {
vector<int> ans(nums.size());//ans为返回的数组
int i=0;
int j=nums.size()-1; //i与j为两个指针
int k=nums.size()-1;
while (i<j)
{
if(abs(nums[i])<abs(nums[j])){
ans[k--]=nums[j];
j--;
}
else{
ans[k--]=nums[i];
i++;
}
}
for (int i = 0; i < nums.size(); i++)
{
ans[i]=ans[i]*ans[i];
}
return ans;
}
不难看出，该解法时间复杂度为$O(n)$,空间复杂度为$O(n)$.
5.区间和
【题目描述】
给定一个整数数组 Array，请计算该数组在每个指定区间内元素的总和。
【题目分析】
最直观的想法便是使用循环将所有区间的和都累加一边，该解法的时间复杂度为$O(m*n)$,其中$n$为数组长度,$m$为查询次数.如果查询次数非常大,时间复杂度也会非常大.
接下来,引入了前缀和这一想法,其思想史重复利用计算过的子数组之和,从而降低区间查询所需要的累加次数,在设计计算区间的问题时非常有用.通过创建辅助数组$p[n]$,就可以将区间和从循环转换为简单的数组元素相减.同时需要注意的是,使用前缀和时,需要注意下标.如$[2,5]$的元素和为 $p[5]-p[1]$.
利用前缀和,本题的时间复杂度为$O(n)$,空间复杂度为$O(n)$
int main(){
int n;
int a,b;
cin>>n;
vector<int> arr(n);
for (int i = 0; i < n; i++)
{
cin>>arr[i];
}
vector<int> preSum(n);
preSum[0]=arr[0];
for (int i = 1; i < n; i++){
preSum[i]=preSum[i-1]+arr[i];
}
while(cin >> a >> b){
int sum;
if (a==0)
{
sum=preSum[b];
}
else
{
sum=preSum[b]-preSum[a-1];
}
cout<<sum<<endl;
}
}
总结
对于以数组为基础数据结构的算法题,常见的技巧有:
- 边界条件:对于数组遍历时,必须坚持“循环不变量”的原则,按照统一的规则进行循环
- 双指针法:其常见场景包括查找成对元素,移除重复元素,合并有序数等,包括同向双指针法和异向双指针法.
- 滑动窗口:其方法主要用于连续子数组或者字串问题,通过一定规则动态调整窗口的大小与位置,在使用过程中,必须明白窗口元素以及何时调整窗口.
- 前缀和法:利用辅助数组,可以通过相减快速得到子数组的和,对于频繁查找子数组和的场景很有必要.