数组(使用C++实现) - 李小基的个人站

🤔一些问题

C++中数组无法用变量定义大小, 如何像Java那样用变量控制数组大小

1 2	`int size = 5; // 数组大小 int* arr = new int[size]; // 动态分配一个大小为size的int类型数组`

应该如何遍历一个未知大小的数组呢?

C++中数组没有求大小的内置函数, 数组大小的求法: sizeof(arr) / sizeof(arr[0])

int arr[] = {1, 2, 3, 4, 5};
int size = sizeof(arr) / sizeof(arr[0]);

for (int i = 0; i < size; i++) {
    // 访问数组元素 arr[i]
    // 进行相应的操作
}

有没有类似Java中的ArrayList那样的可以方便插入,删除,获取length的线性表

在C++中，<vector>是一个标准库头文件，用于包含与向量容器相关的功能和类。向量是一种动态数组，可以在运行时调整大小，并提供了许多方便的操作和函数。

以下是一些<vector>头文件中常用的功能和用法：
创建向量

#include <vector>

std::vector<int> vec; // 创建一个空的整数向量
std::vector<double> vec2(5); // 创建一个包含5个元素的双精度浮点数向量
std::vector<std::string> vec3 = {"apple", "banana", "orange"}; // 创建并初始化一个字符串向量

添加和访问元素：

vec.push_back(10); // 在向量末尾添加元素
vec.push_back(20);

int firstElement = vec[0]; // 访问向量中的第一个元素
int lastElement = vec.back(); // 访问向量中的最后一个元素

获取向量的大小和遍历元素：

int size = vec.size(); // 获取向量的大小
for (int i = 0; i < vec.size(); i++) {
    std::cout << vec[i] << " "; // 遍历向量中的元素
}
for (int element : vec) {
    std::cout << element << " "; // 使用范围-based for 循环遍历向量中的元素
}

插入和删除元素：

1
2
3

vec.insert(vec.begin() + 2, 30); // 在指定位置插入元素
vec.erase(vec.begin() + 1); // 删除指定位置的元素
vec.clear(); // 清空向量中的所有元素

其他常用操作：

bool isEmpty = vec.empty(); // 检查向量是否为空
vec.resize(10); // 调整向量的大小为10
vec.pop_back(); // 删除向量中的最后一个元素
vec.sort(); // 对向量进行排序（需要包含<algorithm>头文件）

💪力扣刷题

704. 二分查找

力扣传送门

循环条件使用begin<=end比较方便, 3个分支一定会进入一个, 只要没找到,begin或者end至少有一个发生变化

class Solution {
public:
    int search(vector<int>& nums, int target) {
        // 使用闭区间[begin,end]缩小查找范围
        int begin=0, end=nums.size()-1;
        int mid;
        while(begin<=end){
            mid = (begin+end)/2;
            if(nums[mid]==target)       // 先比较mid位置
                return mid;             // 比较成功直接返回
            else if(target>nums[mid])   // 如果在左边
                begin = mid+1;
            else                        // 如果在右边
                end = mid-1;
        }
        // 没找到
        return -1;
    }
};

27. 移除元素

力扣传送门

Alt text

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        // 快慢指针, 快指针指向旧数组, 慢指针指向新数组, 旧数组的数据给新数组的对应位置赋值
        int slow=0, fast=0, len = nums.size();
        while(fast<len){
            if(nums[fast]==val)
                fast++;
            else{
                nums[slow] = nums[fast];
                slow++;
                fast++;
            }
        }
        return slow;
    }
};

977. 有序数组的平方

力扣传送门

从两边到中间, 数字的平方依次减小

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

209. 长度最小的子数组

力扣传送门

记录最小值, 那么就需要预先赋值一个最大值, C++中的整型最大值为INT32_MAX,INT32_MAX是一个预定义的常量，不需要引入任何库来使用它。它是在标准的C++头文件<limits.h>或<cstdint>中定义的。只要包含其中一个头文件，就可以直接使用INT32_MAX常量，无需额外的库。以下是一个示例代码：

#include <iostream>
#include <cstdint>

int main() {
    int32_t maxInt = INT32_MAX;
    std::cout << "最大整数值：" << maxInt << std::endl;

    return 0;
}

使用滑动窗口, 两个窗口闭区间内判断是否符合要求, 循环条件为窗口末端指针j遍历整个数组, 如果符合要求就通过移动窗口前端的指针i来逐步缩小窗口, 看看能缩小到什么程度, 如果缩小导致窗口内数字的和小于target, 那么就移动窗口后端指针j, 如果j==nums.size()-1但是和小于target, 那么要终止循环

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int rs = INT32_MAX;
        // 两个窗口指针
        int i=0,j=0,len=nums.size(),num=nums[0];
        while(j<len){
            if(j==len-1 && num<target)  // 已经到了最后一个数字但是不能继续后移j
                break;
            if(j!=len-1 && num<target){ // 没有到达最后一个数字, 且需要后移j
                j++;
                num+=nums[j];
            }
            else{                       // num>=target, 后移i
                rs = min(rs,j-i+1);
                num-=nums[i];
                i++;
            }
        }
        return rs==INT32_MAX ? 0 : rs;  // 如果没找到符合要求的窗口那么返回0
    }
};

59. 螺旋矩阵 II

力扣传送门

方法很多, 主要考察对代码的掌控能力
思路一: 可以再写一个方法用于控制方向, 坐标(i,j)顺时针运动, 转变关系为(0,+1)->(+1,0)->(0,-1)->(-1,0), 循环条件使用一个计数的变量, 当他等于n²的时候就是终点
思路二: 用圈数控制循环, 每一圈的四个方向都写一遍, 其中如果n为基数, 最中间那个位置不太容易赋值, 放在最后判断n为奇数的时候赋值

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> rs(n,vector<int>(n,0));
        int k=1,loop=1,end_loop=n/2;
        while(loop<=end_loop){
            int from=loop-1,end=n-loop;
            for(int i=from,j=i;j<end;j++){
                rs[i][j] = k;
                k++;    
            }
            for(int i=from,j=end;i<end;i++){
                rs[i][j] = k;
                k++;
            }
            for(int i=end,j=end;j>from;j--){
                rs[i][j] = k;
                k++;
            }
            for(int i=end,j=from;i>from;i--){
                rs[i][j] = k;
                k++;
            }
            loop++;
        }
        if(n%2!=0){
            rs[n/2][n/2] = k;
        }
        return rs;
    }
};

技术笔记

#算法 #数据结构 #C++ #力扣刷题 #Java转C++

数组(使用C++实现)

http://example.com/数组/

作者

李小基

许可协议

骡儿往上瞧, 马儿向下看上一篇

链表(使用C++实现) 下一篇