数组定义
数组是一种数据结构，用于存储一系列相同类型的元素。在大多数编程语言中，数组中的每个元素都有一个索引，通常从0开始。
数组的特点
- 固定大小：一旦定义，数组的大小通常是固定的，不能动态增减。
- 相同数据类型：数组中的所有元素应具有相同的数据类型。
- 元素索引：数组中的元素可以通过索引快速访问。
数组的应用
数组可以用于存储数据列表，如用户输入的数据、文件中的数据行等。常见的应用场景包括：
- 数据收集
- 排序和搜索操作
- 实现其他数据结构，如堆栈和队列
在C++中，你可以这样定义一个数组：
#include <iostream>
using namespace std;
int main() {
int myArray[5] = {10, 20, 30, 40, 50};
return 0;
}
随机访问数据元素
你可以通过索引来随机访问数组中的任何元素。索引通常从0开始。例如，访问上面数组的第三个元素：
cout << "第三个元素: " << myArray[2] << endl;
多维数组
二维是个矩阵（数表），以此类推。
数组基本操作
首先访问元素：
正因为数组的连续存储，所以索引其实就是内存地址的偏移量，首个元素的地址偏移量为0，因此用数组来随机访问元素也非常的高效，直接索引即可，时间复杂度为O(1).
举个例子，把这几个操作都实现一遍（Cpp）
首先，我们需要一个基础数组来展示这些操作：
#include <iostream>
using namespace std;
int main() {
int myArray[10] = {10, 20, 30, 40, 50, 60, 70, 80, 90, 100};
return 0;
}
查找元素
int target = 50;
bool found = false;
for (int i = 0; i < 10; i++) {
if (myArray[i] == target) {
cout << "元素 " << target << " 在数组的位置: " << i << endl;
found = true;
break;
}
}
if (!found) {
cout << "元素 " << target << " 不在数组中" << endl;
}
修改元素
myArray[4] = 55; // 将数组第五个元素修改为 55
cout << "修改后的第五个元素: " << myArray[4] << endl;
插入元素
方法1：
/* 在数组的索引 index 处插入元素 num */
void insert(int *nums, int size, int num, int index) {
// 把索引 index 以及之后的所有元素向后移动一位
for (int i = size - 1; i > index; i--) {
nums[i] = nums[i - 1];
}
// 将 num 赋给 index 处的元素
nums[index] = num;
}
- 但是由于数组空间是固定的，如果插入会导致尾部元素的丢失。以此动态数组很好地解决了这个问题。简单介绍一下vector容器，它属于标准模板库（STL）的一部分。vector可以被视为一个能够存储任意类型数据的动态数组。与普通数组相比，vector的大小可以动态改变，可以随机访问元素，还可以在内部自动处理内存分配和释放。当添加的元素超过当前分配的容量时，vector会自动重新分配更大的内存空间来存储更多的元素。
- cpp中一般使用vector容器进行动态删除插入修改更加方便.
#include <vector>
vector<int> myVector = {10, 20, 30, 40, 50};
myVector.insert(myVector.begin() + 3, 35); // 在索引3的位置插入35
删除元素
方法1：
/* 删除索引 index 处的元素 */
void remove(int *nums, int size, int index) {
// 把索引 index 之后的所有元素向前移动一位
for (int i = index; i < size - 1; i++) {
nums[i] = nums[i + 1];
}
}
方法2：
myVector.erase(myVector.begin() + 4); // 删除索引4的元素
基础知识就介绍到这里，都非常简单。
开始今天的Leetcode之旅~：
【1】 66.加1
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int len = digits.size();
for (int i = len - 1; i >= 0; i--) {
// 当前位置加一
digits[i]++;
// 检查是否需要进位
if (digits[i] < 10) {
// 如果不需要进位，直接返回
return digits;
}
// 如果需要进位，设置当前位为0，并在下一轮循环增加上一位
digits[i] = 0;
}
// 如果所有的位都处理完了还有进位，说明是类似999+1这种情况
vector<int> ans(len + 1);
ans[0] = 1; // 进位后第一位为1，其余位默认为0
return ans;
}
};
- 整体思路非常简单，就直接在原数组上进行修改，从后往前遍历，就顺着题目的思路，首先最后一位加一，然后判断是否需要进位，不需要就直接返回了。需要进位它最高是0，你就直接赋0就行了，就继续循环往前，到第一位的时候，如果需要进位，你就使用vector容器给数组前面加一位1就行了。
【2】0724. 寻找数组的中心下标
这道题看完直接给我笑😀~太简单了，直接从左往右减判断是否相等。
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int totalSum = 0;
for (int num : nums) {
totalSum += num;
}
int leftSum = 0;
for (int i = 0; i < nums.size(); ++i) {
// 右侧和可以由总和减去左侧和再减去当前元素得到
if (leftSum == totalSum - leftSum - nums[i]) {
return i;
}
leftSum += nums[i];
}
return -1;
}
};
- 分两步：
- step1:计算总和：首先通过一个循环计算数组nums的总和totalSum。
检查中心下标：接着，我们再次遍历数组，这次计算左侧和leftSum。 - step2:对于每个元素，我们检查左侧和是否等于总和减去左侧和再减去当前元素的值（即右侧和）。如果相等，当前下标就是中心下标。
【3】0189. 轮转数组
用cpp的反转函数reserve其实很容易实现，但是不用这个函数怎么实现呢，我的思路是：开辟一个动态数组，首先一个循环记录k之后的放在vector中，再一个循环记录k之前的，依次下标索引放入vector中。
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n=nums.size();
vector<int> res(n);
k = k%n;//取长的的模，防止出界
int flag=0;//原数组从前往后的索引
for(int i=k;i<n;i++){
res[i] = nums[flag++];
}
for(int j=0;j<k;j++){
res[j]=nums[flag++];
}
nums = res;
return;
}
};
perfect!!!代码很简单了，相信大家都能看懂。
【4】0048. 旋转图像
这道题有个投机的方法，你观察这个不就是矩阵先转置再反转行吗，so：
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
void rotate(vector<vector<int>>& matrix) {
int n = matrix.size();
// 转置
for (int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
swap(matrix[i][j], matrix[j][i]);
}
}
// 反转行
for (int i = 0; i < n; i++) {
reverse(matrix[i].begin(), matrix[i].end());
}
}
};
【5】0054. 螺旋矩阵
思路就是，层层递进，逆时针访问完当前边界，然后更新边界位置，缩小范围，进入下一层。这里解释一下代码里的push_back是vector里面的一个成员函数，他的作用是向动态数组的末尾添加元素。遵循上->右->下->左的操作顺序就行。
另外vector还有很多好用的成员函数：
size()：返回向量中元素的个数。 empty()：检查向量是否为空，如果为空则返回 true，否则返回 false。
clear()：清空向量中的所有元素。 resize()：改变向量的大小，可以增加或减少元素的数量。
reserve()：预留存储空间，但不改变向量的大小。 push_back()：向向量末尾添加一个元素。
pop_back()：删除向量末尾的元素。 insert()：在指定位置插入一个或多个元素。
erase()：删除指定位置或指定范围内的元素。 begin()：返回一个指向向量第一个元素的迭代器。
end()：返回一个指向向量最后一个元素之后位置的迭代器。 front()：返回向量第一个元素的引用。
back()：返回向量最后一个元素的引用。 at()：返回指定位置的元素的引用，带有边界检查。
operator[]：返回指定位置的元素的引用，不带边界检查。
class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
if (matrix.empty()) return {};
int rows = matrix.size(), cols = matrix[0].size();//获取矩阵的行数和列数
vector<int> spiral;//生成最后的答案矩阵
int top = 0, bottom = rows - 1, left = 0, right = cols - 1;//定义四个边界
while (top <= bottom && left <= right) {//定义顶部边界小于底部边界，左侧边界小于右侧边界时
// 从左到右遍历顶部行
for (int i = left; i <= right; ++i) {
spiral.push_back(matrix[top][i]);
}
++top;
// 从上到下遍历右侧列
for (int i = top; i <= bottom; ++i) {
spiral.push_back(matrix[i][right]);
}
--right;
if (top <= bottom) {
// 从右到左遍历底部行
for (int i = right; i >= left; --i) {
spiral.push_back(matrix[bottom][i]);
}
--bottom;
}
if (left <= right) {
// 从下到上遍历左侧列
for (int i = bottom; i >= top; --i) {
spiral.push_back(matrix[i][left]);
}
++left;
}
}
return spiral;
}
};
【6】498.对角线遍历
这个题其实和上一道题差不多，上一个四个方向，这道题两个方向，一个向上一个向下，那么我们就来个变量记录方向就行。
其次对角线个数为m+n-1
然后就开始遍历，每次遍历完改变方向。
class Solution {
public:
vector<int> findDiagonalOrder(vector<vector<int>>& mat) {
if (mat.empty() || mat[0].empty()) return {};
int m = mat.size(), n = mat[0].size();//获取行和列数
vector<int> result;//存放结果
/*上面的先列好*/
bool up = true; // 标记当前遍历方向
for (int sum = 0; sum < m + n - 1; ++sum) {//对角线数为m+n-1
if (up) {
// 对角线向上遍历
for (int i = min(sum, m - 1); i >= 0 && sum - i < n; --i) {
result.push_back(mat[i][sum - i]);
}
} else {
// 对角线向下遍历
for (int i = max(0, sum - n + 1); i < m && sum - i >= 0; ++i) {
result.push_back(mat[i][sum - i]);
}
}
up = !up; // 每次遍历方向切换
}
return result;
}
};
今天就敲到这，太累了今天，线代今天的任务还没做完好焦虑。
参考：
[1] 【教程地址 】[电子网站]
[2]Hello 算法教程
感谢：DataWhale社区
