代码随想录算法训练营第一天 | 数组理论基础、704. 二分查找、27. 移除元素_业界新闻

发布时间:2024-07-29 11:01

阅读量:0

由于笔者没有系统学过c++，仅在一年多之前学程设的时候用过c语言，所以希望在算法训练营的这段时间也能够学习和熟悉一下c++语法，故blog中可能出现部分对于c++基本语法的学习记录。

数组理论基础

文章链接：代码随想录

数组的元素是不能删的，只能覆盖。

对于C++而言：

要注意vector 和 array的区别，vector的底层实现是array，严格来讲vector是容器，不是数组。

c++基本语法：

    cout << &array[0][0] << " " << &array[0][1] << " " << &array[0][2] << endl;     cout << &array[1][0] << " " << &array[1][1] << " " << &array[1][2] << endl;

cout 是标准输出流对象，用于向控制台输出信息。它属于std::ostream类，通常用于打印文本或其他数据到控制台。
<< 是插入运算符，用于将数据插入到cout流中。
endl 是预定义的操纵符，用于插入换行符并刷新流。这意味着它不仅会在输出后面添加一个新行，还会确保任何缓冲的数据立即被写入到控制台。
& 是取址运算符，它返回变量或数组元素的地址。
使用时要引入头文件 #include <iostream>

LeetCode 704.二分查找

题目链接：LeetCode 704. 二分查找

文章讲解：代码随想录
视频讲解：https://www.bilibili.com/video/BV1fA4y1o715

基本思路：

当题目前提是数组为有序数组，且数组中无重复元素，则考虑使用二分法。

要点：

确定区间规则，保持循环不变量，在while寻找中每一次边界的处理都要根据区间定义来操作。

左闭右闭：

在判断左右边界关系时，要考虑到最大合法区间，所以取 $left \leq right$ ；

在放缩区间时，我们已经判断不等于目标值，所以放缩闭区间下标时，要进行 $middle\pm 1$ 的操作。

class Solution { public:     int search(vector<int>& nums, int target) {         int left = 0;         int right = nums.size() - 1;         //增加if语句减少极端值运行次数         if (target < nums[0] || target > nums[right]){             return -1;         }         else{             while (left <= right){             // 防止溢出 等同于(left + right)/2                             int middle = left + ((right - left) / 2);             if (target < nums[middle]){                 right = middle - 1;             }             else if (target > nums[middle]){                 left = middle + 1;             }             else{                 return middle;             }         }         return -1;         }     } };

左闭右开：

注意初始取值时，；

在判断左右边界关系时，要考虑到最大合法区间，所以取；

在放缩区间时，对于左边界区间为闭，我们已经判断不等于目标值，要进行的操作；对于右边界为开，且不在下次循环的区间内，则直接取。

class Solution { public:     int search(vector<int>& nums, int target) {         int left = 0;         int right = nums.size();         //增加if语句减少极端值运行次数         if (target < nums[0] || target > nums[right-1]){             return -1;         }         else{             while (left < right){             // 防止溢出 等同于(left + right)/2                             int middle = left + ((right - left) / 2);             if (target < nums[middle]){                 right = middle;             }             else if (target > nums[middle]){                 left = middle + 1;             }             else{                 return middle;             }         }         return -1;         }     } };

基本语法知识

vector<int>& nums:

vector<int>: 这是C++标准模板库(STL)中的vector容器，专门用来存储整数(int)类型的数据。vector是一个动态数组，可以在运行时改变其大小。
&: 这是一个引用符号。在这里，它意味着函数接收一个对vector<int>的引用，而不是vector的一个副本。通过引用传递可以避免复制整个向量，从而提高效率。

使用时要导入头文件#include <iostream>

LeetCode 27.移除元素

题目链接：LeetCode 27. 移除元素

文章讲解：代码随想录
视频讲解：数组中移除元素并不容易！ | LeetCode：27. 移除元素_哔哩哔哩_bilibili

暴力解法

class Solution { public:     int removeElement(vector<int>& nums, int val) {         int size = nums.size();         for (int i=0; i<size; i++){             if (nums[i] == val){                 for (int j=i; j<size-1; j++){                     nums[j] = nums[j+1];                 }                 size--;                 i--;                 //下标i以后的数值都向前移动了一位，所以i也向前移动一位                 //就意味着把本位的移除之后，后一位前移，不处理i值则会有遗漏             }         }         return size;     } };

要注意每次下标i以后的数值都向前移动一位时，要对i值进行前移处理，防止搜查遗漏。

时间复杂度：O(n^2)
空间复杂度：O(1)

双指针法

双指针法： 通过一个快指针和慢指针在一个for循环下完成两个for循环的工作。

class Solution { public:     int removeElement(vector<int>& nums, int val) {         int slowIndex = 0;         for (int quickIndex = 0; quickIndex < nums.size(); quickIndex++){             if (nums[quickIndex] != val){                 nums[slowIndex] = nums[quickIndex];                 slowIndex++;             }         }         return slowIndex;     } };

注意，在for循环中，每次操作是先填值再给慢指针+1指向下一位置，所以在循环结束后慢指针本身便多加了一次1，返回数组大小时则不用再次+1。