代码随想录刷题 | Day1

发布时间:2023年12月30日

今日学习目标

一、基础

  • 数组

  • array类

  • 模板类vector

数组是存放在连续内存空间上的相同类型数据的集合。

数组可以方便的通过下标索引的方式获取到下标下对应的数据。

算法通关数组

需要两点注意的是

  • 数组下标都是从0开始的。

  • 数组内存空间的地址是连续的

而且大家如果使用C++的话,要注意vector 和 array的区别,vector的底层实现是array,严格来讲vector是容器,不是数组。

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

  • array 和vector容器有什么区别?

array容器和vector容器是C++ STL库中的两种容器,它们的区别如下:

  1. 大小不同

array容器是一个固定大小的数组,创建时需要指定大小,不能动态调整大小。而vector容器是一个动态数组,可以动态调整大小。

  1. 内存分配方式不同

array容器的内存是静态分配的,即在编译时就分配好了内存。而vector容器的内存是动态分配的,即在运行时根据需要动态分配内存。

  1. 访问方式不同

array容器支持随机访问,可以通过下标快速访问元素。而vector容器也支持随机访问,但是由于内存分配方式的不同,vector容器的访问速度可能会慢一些。

  1. 初始化方式不同

array容器可以使用初始化列表来初始化,也可以使用默认构造函数创建一个空的array容器。而vector容器只能使用默认构造函数创建一个空的vector容器,需要使用push_back()等方法来添加元素。

  1. 适用场景不同

由于array容器是固定大小的,适合存储大小已知且不会改变的数据。而vector容器适合存储大小未知或者可能会改变的数据。

下面是使用C++实现array和vector的示例代码:

array的实现

#include <iostream>
#include <array>
using namespace std;
 
int main() {
    array<int, 3> myArray = {1, 2, 3}; // 创建一个大小为3的int类型的Array
    // 遍历Array中的元素
    for (int i = 0; i < myArray.size(); ++i) {
        cout << myArray[i] << " ";
    }
    cout<<endl;
    return 0;
}

vector的实现:

#include <iostream>
#include <vector>
using?namespace?std;
int?main() {
? ?vector<int>?myVector;?// 创建一个int类型的空的vector容器

? ?// 在vector中插入元素
? ?myVector.push_back(1);
? ?myVector.push_back(2);
? ?myVector.push_back(3);

? ?// 遍历vector中的元素
? ?for?(int?i?=?0;?i?<?myVector.size();?++i) {
? ? ? ?cout?<<?myVector[i]?<<?" ";
? }
? ?cout?<<?endl;
? ?return?0;
}

二、算法

?1.?704. 二分查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0, high = nums.size()-1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                return mid;
            } else if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
};

2. 27. 移除元素

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

3. 977. 有序数组的平方?

class Solution {
public:
    vector<int> sortedSquares(vector<int>& nums) {
        int k = nums.size() - 1;
        vector<int> result(nums.size(), 0);
        for (int i = 0, j = nums.size() - 1; i <= j;) {
            if (nums[i] * nums[i] < nums[j] * nums[j]) {
                result[k--] = nums[j] * nums[j];
                j--;
            } else {
                result[k--] = nums[i] * nums[i];
                i++;
            }
        }
        return result;
    }
};

4.?209.长度最小的子数组

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑动窗口数值之和
        int i = 0; // 滑动窗口起始位置
        int subLength = 0; // 滑动窗口的长度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意这里使用while,每次更新 i(起始位置),并不断比较子序列是否符合条件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的长度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 这里体现出滑动窗口的精髓之处,不断变更i(子序列的起始位置)
            }
        }
        // 如果result没有被赋值的话,就返回0,说明没有符合条件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};

5.?59.螺旋矩阵II

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> res(n, vector<int>(n, 0));
        int k = 1;
        int right = n - 1, left = 0, up = 0, down = n - 1;
        while (k <= n * n) {
            for (int i = left; i <= right; i++)
                res[up][i] = k++;
            up++;
            for (int i = up; i <= down; i++)
                res[i][right] = k++;
            right--;
            for (int i = right; i >= left; i--)
                res[down][i] = k++;
            down--;
            for (int i = down; i >= up; i--)
                res[i][left] = k++;
            left++;
        }
        return res;
    }
};

6.?283. 移动零

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int i = 0;
        for (int j = 0; j < nums.size(); j++) {
            if (nums[j] != 0) {
                swap(nums[i], nums[j]);
                i++;
            }
        }
    }
};

7.?26. 删除有序数组中的重复项

力扣LeetCode第26题 删除有序数组中的重复项

8.?80. 删除有序数组中的重复项 II?

力扣LeetCode第80题 删除有序数组中的重复项 II

文章来源:https://blog.csdn.net/weixin_42823298/article/details/135304337
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。