终于考完试了,晚了一天参加打卡,代码随想录第一天的内容是了解一下数组的定义知识点,以及完成两道入门级别的题目:二分查找和移除元素
我们现在先来根据代码随想录当中的内容先看看数组的基本定义和要注意的知识点是什么:
#include<iostream>
using namespace std;
void print() {
int array[3][3] = {
{1,2,3},
{4,5,6}
};
cout << &array[0][0] << " " << &array[0][1] <<" " << &array[0][2] << endl;
cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;
}
int main() {
print();
return 0;
}
我们这个时候就会发现C++当中二维数组其实是连续的内存空间的,每个元素的地址都相差了四个字节
二分搜索法可以看carl大佬的bilibili视频
在leetcode的第704道题就是二分搜索法
首先我们在这里就是要明白,因为是左闭右闭区间,所以根据区间的合法性,我们是可以直接使用while(left<=right)来进行循环判断的,并且如果nums[middle]!=target,可以直接left=middle+1或者right=middle-1;? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size()-1;//在这里的左闭右闭
int middle=0;//定义middle用于定义left和right中间的值
while(left<=right){ //左闭右闭支持两端相等
middle=(left+right)/2;
if(nums[middle]==target){
return middle;
}else if(nums[middle]>target){
right=middle-1;
}else if(nums[middle]<target){
left=middle+1;
}
}
return -1;
}
};
因为是左闭右开,所以一开始的right的值就要取right=nums.size(),并且当nums[middle]>target的时候,right=middle而不是=middle-1
class Solution {
public:
int search(vector<int>& nums, int target) {
int left=0;
int right=nums.size();
int middle=0;
while(left<right){
middle=(left+right)/2;
if(nums[middle]==target){
return middle;
}else if(nums[middle]>target){
right=middle;
}else if(nums[middle]<target){
left=middle+1;
}
}
return -1;
}
};
使用双重for循环进行暴力解题:
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int length=nums.size();
for(int i=0;i<length;i++){
if(nums[i]==val){
for(int j=i+1;j<length;j++){
nums[j-1]=nums[j];
}
i--;
length--;
}
}
return length;
}
};
双重指针进行for循环,一下子就把我们前面说的那种暴力解法替代了
在这里我们需要先了解一下slow慢指针和fast快指针的作用,fast指针用来获取遍历原来数组当中的元素,slow慢指针用来给新数组赋值,不断更新新数组当中的元素
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int slow=0;
int fast=0;
for(fast=0;fast<nums.size();fast++){
if(nums[fast]!=val){
nums[slow]=nums[fast];
slow++;
}
}
return slow;
}
};