用自己的电脑做网站wordpress用户关注

用自己的电脑做网站,wordpress用户关注,商业授权什么意思,网站优惠券怎么做的文章目录普通数组理论基础1. 数组的基本概念1.1 基本术语1.2 数组的特点2. 数组的基本操作2.1 数组的遍历2.2 数组的修改3. 前缀和#xff08;Prefix Sum#xff09;3.1 前缀和的基本概念3.2 前缀和的构造3.3 区间和查询4. 矩阵#xff08;二维数组#xff09;操作4.1 矩阵…文章目录普通数组理论基础1. 数组的基本概念1.1 基本术语1.2 数组的特点2. 数组的基本操作2.1 数组的遍历2.2 数组的修改3. 前缀和Prefix Sum3.1 前缀和的基本概念3.2 前缀和的构造3.3 区间和查询4. 矩阵二维数组操作4.1 矩阵的基本概念4.2 矩阵的遍历4.3 螺旋矩阵模板1螺旋矩阵遍历模板2螺旋矩阵II生成4.4 矩阵的统计操作5. 数组操作的时间复杂度6. 何时使用数组技巧6.1 使用场景6.2 判断标准7. 数组操作的优缺点7.1 优点7.2 缺点8. 常见题型总结8.1 前缀和类8.2 矩阵类8.3 数组基本操作类9. 总结普通数组理论基础1. 数组的基本概念**数组Array**是一种线性数据结构由相同类型的元素按一定顺序排列而成通过索引访问元素。1.1 基本术语索引Index数组中元素的位置通常从0开始元素Element数组中存储的数据长度Length数组中元素的数量一维数组线性排列的数组二维数组矩阵按行和列排列的数组1.2 数组的特点连续内存数组元素在内存中连续存储随机访问通过索引可以在O(1)时间内访问任意元素固定大小数组大小在创建时确定C中vector是动态数组元素覆盖数组元素不能直接删除只能覆盖示例一维数组[1, 2, 3, 4, 5] 索引 0 1 2 3 4 二维数组矩阵 [1, 2, 3] [4, 5, 6] [7, 8, 9] 行索引0, 1, 2 列索引0, 1, 22. 数组的基本操作2.1 数组的遍历一维数组遍历// 方式1索引遍历for(inti0;inums.size();i){// 访问 nums[i]}// 方式2范围遍历for(intnum:nums){// 访问 num}二维数组遍历// 遍历二维数组for(inti0;imatrix.size();i){for(intj0;jmatrix[i].size();j){// 访问 matrix[i][j]}}2.2 数组的修改重要特性数组元素不能直接删除只能覆盖删除操作需要将后续元素前移示例// 删除索引为index的元素voidremoveElement(intarr[],intsize,intindex){if(index0||indexsize){return;// 索引无效}// 将后续元素前移for(intiindex;isize-1;i){arr[i]arr[i1];}size--;// 减少数组大小}3. 前缀和Prefix Sum3.1 前缀和的基本概念前缀和是数组中前i个元素的和用于快速计算区间和。定义prefix[i] arr[0] arr[1] ... arr[i]区间[a, b]的和 prefix[b] - prefix[a-1]a 0区间[0, b]的和 prefix[b]示例原数组[1, 2, 3, 4, 5] 前缀和[1, 3, 6, 10, 15] 计算区间[1, 3]的和 prefix[3] - prefix[0] 10 - 1 9 验证2 3 4 9 ✓3.2 前缀和的构造核心思路遍历数组累加元素将累加结果存入前缀和数组模板代码// 构造前缀和数组vectorintprefix(n);intpresum0;for(inti0;in;i){presumarr[i];prefix[i]presum;}3.3 区间和查询适用场景多次查询数组的区间和核心思路使用前缀和数组快速计算区间和时间复杂度O(1)查询O(n)预处理模板代码// LeetCode 58. 区间和#includeiostream#includevectorusingnamespacestd;intmain(){intn,a,b;cinn;vectorintvec(n);// 输入数组vectorintp(n);// 前缀和数组intpresum0;// 构造前缀和数组for(inti0;in;i){scanf(%d,vec[i]);presumvec[i];p[i]presum;}// 查询区间和while(~scanf(%d%d,a,b)){intsum;if(a0){sump[b];// 区间[0, b]的和}else{sump[b]-p[a-1];// 区间[a, b]的和}printf(%d\n,sum);}return0;}关键点前缀和数组p[i]表示前i1个元素的和区间和计算[a, b]的和 p[b] - p[a-1]边界处理当a0时直接使用p[b]时间复杂度预处理O(n)查询O(1)4. 矩阵二维数组操作4.1 矩阵的基本概念**矩阵Matrix**是二维数组由行和列组成。基本操作访问元素matrix[i][j]第i行第j列行数matrix.size()列数matrix[0].size()4.2 矩阵的遍历按行遍历for(inti0;imatrix.size();i){for(intj0;jmatrix[i].size();j){// 访问 matrix[i][j]}}按列遍历for(intj0;jmatrix[0].size();j){for(inti0;imatrix.size();i){// 访问 matrix[i][j]}}4.3 螺旋矩阵适用场景按螺旋顺序遍历或生成矩阵核心思路使用循环不变量每次操作的方法一致左闭右开按圈遍历从外圈到内圈处理边界单行或单列的特殊情况模板1螺旋矩阵遍历适用场景按螺旋顺序遍历矩阵并输出元素模板代码// LeetCode 54. 螺旋矩阵classSolution{public:vectorintspiralOrder(vectorvectorintmatrix){vectorintans;intmmatrix.size();intnmatrix[0].size();intstartx0,starty0;// 起始位置intoffset1;// 每圈的偏移量intloopmin(m,n)/2;// 循环圈数// 处理单行或单列if(m1){returnmatrix[0];}if(n1){for(intk0;km;k){ans.push_back(matrix[k][0]);}returnans;}// 按圈遍历左闭右开while(loop--){intistartx,jstarty;// 第一行从左到右for(;jn-offset;j){ans.push_back(matrix[i][j]);}// 最后一列从上到下for(;im-offset;i){ans.push_back(matrix[i][j]);}// 最后一行从右到左for(;jstarty;j--){ans.push_back(matrix[i][j]);}// 第一列从下到上for(;istartx;i--){ans.push_back(matrix[i][j]);}startx;starty;offset;}// 处理剩余的单行或单列if(min(m,n)%21){if(mn){// 剩余单行for(intjjstarty;jjn-offset1;jj){ans.push_back(matrix[startx][jj]);}}else{// 剩余单列for(intiistartx;iim-offset1;ii){ans.push_back(matrix[ii][starty]);}}}returnans;}};关键点循环不变量左闭右开四个方向右→下→左→上边界处理单行或单列的特殊情况时间复杂度O(m × n)空间复杂度O(1)模板2螺旋矩阵II生成适用场景生成一个n×n的螺旋矩阵模板代码// LeetCode 59. 螺旋矩阵IIclassSolution{public:vectorvectorintgenerateMatrix(intn){vectorvectorintvec(n,vectorint(n));intstartx0,starty0;// 起始位置intoffset1;// 每圈的偏移量intcount1;// 填充的数字intcirn/2;// 循环圈数intmidn/2;// 中间位置// 按圈填充左闭右开while(cir--){intistartx,jstarty;// 第一行从左到右for(;jn-offset;j){vec[i][j]count;}// 最后一列从上到下for(;in-offset;i){vec[i][j]count;}// 最后一行从右到左for(;jstartx;j--){vec[i][j]count;}// 第一列从下到上for(;istarty;i--){vec[i][j]count;}startx;starty;offset;}// 处理中间元素n为奇数时if(n%2){vec[mid][mid]count;}returnvec;}};关键点循环不变量左闭右开四个方向填充右→下→左→上中间元素n为奇数时需要单独处理时间复杂度O(n²)空间复杂度O(n²)4.4 矩阵的统计操作适用场景统计矩阵的行和、列和等模板代码// 统计矩阵的行和与列和vectorinthorizontal(n,0);// 每行的和vectorintvertical(m,0);// 每列的和// 统计行和for(inti0;in;i){for(intj0;jm;j){horizontal[i]matrix[i][j];}}// 统计列和for(intj0;jm;j){for(inti0;in;i){vertical[j]matrix[i][j];}}5. 数组操作的时间复杂度操作时间复杂度空间复杂度说明访问元素O(1)O(1)通过索引直接访问遍历数组O(n)O(1)需要访问所有元素查找元素O(n)O(1)线性查找插入元素O(n)O(1)需要移动后续元素删除元素O(n)O(1)需要移动后续元素前缀和构造O(n)O(n)需要额外空间存储前缀和区间和查询O(1)O(1)使用前缀和数组矩阵遍历O(m × n)O(1)m为行数n为列数螺旋矩阵O(m × n)O(1)需要遍历所有元素注意数组的随机访问是O(1)插入和删除操作需要移动元素时间复杂度为O(n)前缀和可以优化区间和查询到O(1)6. 何时使用数组技巧6.1 使用场景区间和问题多次查询数组的区间和使用前缀和优化查询效率矩阵遍历问题螺旋矩阵遍历矩阵的按行、按列遍历矩阵的统计操作数组基本操作数组的遍历数组元素的修改数组的查找二维数组问题矩阵的生成矩阵的旋转、转置矩阵的统计和计算6.2 判断标准当遇到以下情况时考虑使用数组技巧需要多次查询区间和 → 使用前缀和需要按特殊顺序遍历矩阵 → 使用螺旋矩阵技巧需要统计矩阵的行和、列和 → 使用矩阵统计需要快速访问元素 → 利用数组的随机访问特性示例// 问题多次查询数组的区间和// 暴力解法每次查询O(n)for(intia;ib;i){sumarr[i];}// 前缀和解法预处理O(n)查询O(1)vectorintprefix(n);// 构造前缀和数组for(inti0;in;i){prefix[i](i0?arr[i]:prefix[i-1]arr[i]);}// 查询区间和intsumprefix[b]-(a0?prefix[a-1]:0);7. 数组操作的优缺点7.1 优点随机访问通过索引可以在O(1)时间内访问任意元素内存连续数组元素在内存中连续存储访问效率高实现简单数组操作逻辑清晰易于实现前缀和优化可以将区间和查询优化到O(1)7.2 缺点固定大小数组大小在创建时确定C中vector是动态数组插入删除慢插入和删除操作需要移动元素时间复杂度为O(n)空间限制需要连续的内存空间无法直接删除数组元素不能直接删除只能覆盖8. 常见题型总结8.1 前缀和类区间和查询使用前缀和数组快速计算区间和时间复杂度预处理O(n)查询O(1)子数组和问题结合前缀和和哈希表可以解决子数组和等于k的问题8.2 矩阵类螺旋矩阵按螺旋顺序遍历或生成矩阵使用循环不变量左闭右开矩阵统计统计矩阵的行和、列和矩阵的旋转、转置矩阵遍历按行遍历、按列遍历对角线遍历等特殊遍历方式8.3 数组基本操作类数组遍历一维数组遍历二维数组遍历数组修改元素的覆盖元素的移动9. 总结普通数组是基础的数据结构掌握数组的基本操作和常用技巧对于解决算法问题至关重要。核心要点数组特性连续内存、随机访问、元素覆盖前缀和用于优化区间和查询预处理O(n)查询O(1)矩阵操作螺旋矩阵、矩阵统计、矩阵遍历时间复杂度访问O(1)遍历O(n)插入删除O(n)空间复杂度通常为O(1)或O(n)使用建议区间和问题优先考虑前缀和矩阵遍历问题考虑螺旋矩阵技巧注意数组的边界条件利用数组的随机访问特性合理使用循环不变量常见题型总结前缀和类区间和查询、子数组和问题矩阵类螺旋矩阵、矩阵统计、矩阵遍历数组基本操作数组遍历、数组修改