不收费的企业查询网站,软件开发交易平台,怎么在门户网站上发布,哪里有网页设计文章目录 1. 485 最大连续1的个数2. 495 提莫攻击3. 414 第三大的数4. 628 三个数的最大乘积5. 645 错误的集合6. 697 数组的度7. 448 找到所有数组中消失的数字9. 41 缺失的第一个正数10. 274 H指数11. 453 最小操作次数使得数组元素相等12. 665 非递减数列13. 283 移动零14. … 文章目录 1. 485 最大连续1的个数2. 495 提莫攻击3. 414 第三大的数4. 628 三个数的最大乘积5. 645 错误的集合6. 697 数组的度7. 448 找到所有数组中消失的数字9. 41 缺失的第一个正数10. 274 H指数11. 453 最小操作次数使得数组元素相等12. 665 非递减数列13. 283 移动零14. 118 杨辉三角15. 119 杨辉三角II16. 661 图片平滑器17. 598 范围求和 II18. 419 甲板上的战舰19. 189 轮转数组20. 396 旋转函数21. 54 螺旋矩阵22. 59 螺旋矩阵II23. 498 对角线遍历24. 566 重塑矩阵25. 73 矩阵置零26.289 生命游戏27. 303 区域和检索--数组不可变28. 304 二维区域和检索-矩阵不可变29. 238 除自身以外数组的乘积 数组的遍历 485、495、414、628 统计数组中的元素 645、697、448、442、41、274
数组的改变、移动 453、665、283
二维数组及滚动数组 118、119、661、598、419
数组的旋转 189、396
特定顺序遍历二维数组 54、59、498
二维数组变换 566、48、73、289
前缀和数组 303、304、238
1. 485 最大连续1的个数 解法很简单的一次遍历
为了得到数组中最大的连续1的个数使用cnt记录当前连续1的个数使用max记录最大连续的1。当遇到1时候cnt1当碰到的不是1时需要比较cnt和max之间的值判断是否更新max值并且将cnt置为0。
最后要注意的是当循环遍历结束之后还需要比较一次cnt和max。因为数组的最后一位数有可能是1且最长连续1的子数组可能出现在数组的末尾。
代码
//
// Created by 高森森 on 2022/9/19.
//#ifndef LEETCODE_SOLUTION_1_H
#define LEETCODE_SOLUTION_1_H
#includebits/stdc.h
using namespace std;class solution_1 {
public:
int findMaxConsecutiveOnes(vectorint nums) {
int cnt0;
int max0;
for(int i0;inums.size();i){
if(nums[i]1){
cnt;
}
else{
if(cntmax){
maxcnt;
}
cnt0;
}
}
if(cntmax){
maxcnt;
}
return max;
}
};#endif //LEETCODE_SOLUTION_1_H
时间复杂度Onn是数组的长度
空间复杂度O1
2. 495 提莫攻击 解法简单的模拟题遍历一遍数组每次保存上一次结束的时间lastans用于累积加和。当last小于当前的时间时说明不会冲突ansansduration;当last当前的时间时说明时间有重叠ans当前结束时间-上一个结束时间
代码
class Solution {
public: int findPoisonedDuration(vectorint timeSeries, int duration) {int last-1;int ans0;for(int i0;itimeSeries.size();i){if(lasttimeSeries[i]){lasttimeSeries[i]duration-1;ansduration;}else{anstimeSeries[i]duration-1-last;lasttimeSeries[i]duration-1;}}return ans;}
};3. 414 第三大的数 解法采用有序数组的形式遍历数组有一个有序的集合维护数组中的前三大的数。遍历每一个数将其插入有序集合因为set有序集合是自动排序的自动按照从小到大的顺序排序如果有序集合的大小超过3。那么就删除最小的元素相当于维护一个容量为3的队列。遍历结束后如果有序集合的大小是3最小值就是第三大的数字如果有序集合没有3个那么就返回有序集合中最大值。
代码
class solution_3 {
public:int thirdMax(vectorint nums) {setintmaxsize;for(int i0;inums.size();i){maxsize.insert(nums[i]);if(maxsize.size()3){maxsize.erase(maxsize.begin());}}return maxsize.size()3?*maxsize.begin():*maxsize.rbegin();}
};
时间复杂度On其中n是数组nums的长度。因为有序集合大小至多为3插入和删除的时间复杂度可以看作O1
空间复杂度O1
4. 628 三个数的最大乘积 解法首先分析以下情况数组中数组的个数大于等于3。1.如果数组全部为非负数数那么最大值为最大的三个如果数组中全部为负数那么最大值也为最大的三个。如果数组中既有正数又有负数最大值可能是最小的两个负数*最大的正数也有可能是最大的三个正数。需要取两者最大值。
代码
class solution_4 {
public:int maximumProduct(vectorint nums) {sort(nums.begin(),nums.end());int result0;int nnums.size();if(*(nums.end()-1)0*nums.begin()0){resultnums[n-1]*nums[n-2]*nums[n-3];}else if(*nums.begin()0*(nums.end()-1)0){resultnums[n-1]*nums[n-2]*nums[n-3];}else{int anums[0]*nums[1]*nums[n-1];int bnums[n-1]*nums[n-2]*nums[n-3];resultab?a:b;}return result;}
};时间复杂度Onlogn为排序的复杂度
空间复杂度Onlogn为排序的空间
5. 645 错误的集合 解法因为包含1-n个数字并且每个数字只能出现1遍所以可以遍历nums数组将其存入集合set中如果set中的key已经存在说明数字重复。同时set默认升序排序遍历1-n检查1-n数字是否在set中存在若不存在则缺少的数字找到。
代码
class solution_5 {
public:vectorint findErrorNums(vectorint nums) {int nnums.size();int r1,r2;setintt;for(int i0;inums.size();i){if(t.count(nums[i])0){t.insert(nums[i]);}else{r1nums[i];}}for(int i1;in;i){if(t.count(i)0){r2i;break;}}return {r1,r2};}
};时间复杂度On
空间复杂度:On
解法2数组异或
数组的异或求解
6. 697 数组的度 解法
题目可以分成两个部分求解首先求得原数组的度然后求得与原数组有相同的度的最短子数组。 求原数组的度就是求各个元素出现的次数可以用map计数map中的key是元素value是该元素出现的次数。因此字典中所有的value的最大值就是数组的度degree。 求得最大度之后如果求与度相同的最短子数组 分析上面的示例1[1,2,2,3,1]最短子数组为[2,2]。因为最短子数组中必须包括度的所有元素所以最短的子数组的大小与度的元素的最早和最迟的出现位置有关。因此度最大的数字有1和2. 包含2的最短子数组为[2,2]包含1的最短子数组为[1,2,2,3,1]。所以最短子数组为包含度最大元素的最短子数组大小的最小值。 示例2[1,2,2,3,1,4,2]度为3元素为2。包含2的最短子数组为[2,2,3,1,4,2]。 因此可以得到规律包含某个元素的最短子数组的长度为该数字最后一次出现的位置索引-第一次出现的位置索引1。 代码 class solution_6 {
public:int findShortestSubArray(vectorint nums) {unordered_mapint,intleft,right,counter;int degree0;for(int i0;inums.size();i){if(left.count(nums[i])0){left.insert(make_pair(nums[i],i));}right[nums[i]]i;counter[nums[i]];degreemax(degree,counter[nums[i]]);}int resINT_MAX;//得到最大的度for(auto itcounter.begin();it!counter.end();it){if(it-seconddegree){resmin(right[it-first]-left[it-first]1,res);}}return res;}
}; 时间复杂度ON 空间复杂度ON
7. 448 找到所有数组中消失的数字 解法
方法一遍历vector数组将所有的数字都保存在set中因为set的自动重复的功能得到的是所有的数字。
遍历1-n,如果数字在set中不存在则输出。
class solution_7 {
public:vectorint findDisappearedNumbers(vectorint nums) {setintp;int nnums.size();for(int i0;in;i){p.insert(nums[i]);}vectorintres;for(int i1;in;i){if(p.count(i)0){res.push_back(i);}}return res;}
};
时间复杂度On
空间复杂度O(n)
方法二官方解法 就地修改
我们可以用一个哈希表记录数组nums 中的数字由于数字范围均在 [1,n] 中记录数字后我们再利用哈希表检查 [1,n] 中的每一个数是否出现从而找到缺失的数字。
由于数字范围均在 [1,n] 中我们也可以用一个长度为 n 的数组来代替哈希表。这一做法的空间复杂度是 O(n) 的。我们的目标是优化空间复杂度到 O(1)。
注意到 nums 的长度恰好也为 n能否让 nums 充当哈希表呢
由于nums 的数字范围均在[1,n] 中我们可以利用这一范围之外的数字来表达「是否存在」的含义。
具体来说遍历 nums每遇到一个数 x就让 nums[x−1] 增加 n。由于 nums 中所有数均在[1,n] 中增加以后这些数必然大于 n。最后我们遍历 nums若 nums[i] 未大于 n就说明没有遇到过数 i1。这样我们就找到了缺失的数字。
注意当我们遍历到某个位置时其中的数可能已经被增加过因此需要对 n 取模来还原出它本来的值。
class Solution {
public:vectorint findDisappearedNumbers(vectorint nums) {int n nums.size();for (auto num : nums) {int x (num - 1) % n;nums[x] n;}vectorint ret;for (int i 0; i n; i) {if (nums[i] n) {ret.push_back(i 1);}}return ret;}
};时间复杂度On
空间复杂度O1
9. 41 缺失的第一个正数 解法当然暴力解法也能够解决问题但是不满足在时间复杂度为On。
我们还可以把每个元素存放到对应的位置比如1存放到数组的第一个位置3存放到数组的第3个位置如果是非正数或者大于数组的长度的值我们不做处理最后在遍历一遍数组如果位置不正确说明这个位置没有这个数我们就直接返回。 代码 int firstMissingPositive(vectorint nums) {
int index0;
while(indexnums.size()){
int tmpnums[index];
if(tmp0||tmpnums.size()) {
index;
}
else{
if(tmpnums[tmp-1]){
index;
continue;
}
int cntnums[tmp-1];
nums[tmp-1]nums[index];
nums[index]cnt;}
}
for(int i0;inums.size();i){
if(nums[i]!i1){
return i1;
}
}
return nums.size()1;
}时间复杂度On
空间复杂度O1
10. 274 H指数 解法一排序
首先我们可以将初始的}H 指数 h 设为 0然后将引用次数排序并且对排序后的数组从大到小遍历。
根据H 指数的定义如果当前H 指数为 h 并且在遍历过程中找到当前值citations[i]h则说明我们找到了一篇被引用了至少 h1 次的论文所以将现有的 h 值加 1。继续遍历直到 h 无法继续增大。最后返回 h 作为最终答案。
class solution_9 {
public:int hIndex(vectorint citations) {sort(citations.begin(),citations.end());int ncitations.size()-1;int h0;while(n0citations[n]h){h;n--;}return h;}
};
时间复杂度OnlogN
空间复杂度: Olog n排序的空间复杂度
解法二计数排序
根据上述解法我们发现最终的时间复杂度与排序算法的时间复杂度有关所以我们可以使用计数排序算法新建并维护一个数组 counter 用来记录当前引用次数的论文有几篇。
根据定义我们可以发现 H 指数不可能大于总的论文发表数所以对于引用次数超过论文发表数的情况我们可以将其按照总的论文发表数来计算即可。这样我们可以限制参与排序的数的大小为 [0,n]其中 n 为总的论文发表数使得计数排序的时间复杂度降低到 O(n)。
最后我们可以从后向前遍历数组 counter对于每个 0≤i≤n在数组 counter 中得到大于或等于当前引用次数 i 的总论文数。当我们找到一个 H 指数时跳出循环并返回结果。
注意官方给出的counter是使用vector数组的形式声明vectorcounter(n1)
但是我在实现的时候使用的是int counter[n1],所以必须注意此时需要将counter数组初始化。
class Solution {
public:int hIndex(vectorint citations) {int n citations.size(), tot 0;int counter[n1];fill(counter,countern1,0);for (int i 0; i n; i) {if (citations[i] n) {counter[n];} else {counter[citations[i]];}}for (int i n; i 1; i--) {tot counter[i];if (tot i) {return i;}}return 0;}
};
时间复杂度On其中 n 为数组citations 的长度。需要遍历数组
空间复杂度On其中 nn 为数组citations 的长度。需要创建长度为n1 的数组counter。
11. 453 最小操作次数使得数组元素相等 解法这题找对思路很重要一开始以为是动态规划类型得题结果发现找不到状态转换方程。原来是一项逆向思维题。总体分两步骤求最小值求和 重点因为题目只要求操作操作的次数使得n-1个数字加1的操作其实等同于是得1个数字减一。 最后要求所有的数字都相同的最少操作那么就让其余所有的数字向最小的那个数字看齐也就是通过减一操作使得所有数字变成最小数的过程。 一个数字变成最小数字的操作nums[i]-min。对所有的数字进行计算nums[i]-1,并且求和 代码
class solution_10 {
public:int minMoves(vectorint nums) {int minINT_MAX;//找到最小值for(int i0;inums.size();i){if (nums[i]min){minnums[i];}}//每个值和最小值之间的差别int res0;for(int i0;inums.size();i){resnums[i]-min;}return res;}
};时间复杂度On
空间复杂度: O1
12. 665 非递减数列 解法思路一开始以为只要判断下降序列的次数如果超过1就返回false否则返回true。提交发现有问题在[3,4,2,3]这个例子上面出错了此时下降序列只有1但是返回false。因此想到了下降序列的两个点可能还和之前的点和之后的点构成的序列有关系。
如【3423】的例子i4时出现nums[i]nums[i1],如果将4修改为2那么[3,2,2,3]仍然不符合非递减。
所以此时要将nums[i]改为nums[i1]明显是有条件的必须nums[i-1]nums[i1]
如果将2修改为4序列[3,4,4,2]仍然不满足条件因为此时42
所以此时要将nums[i1]改为nums[i]明显是有条件的必须nums[i]nums[i2]
那么如果以上两种条件不满足的话一定返回的false。即当i-10且i2nums.size()-1的时候
num[i-1]nums[i1]nums[i]nums[i2]一定无法满足条件因为满足了一边就无法满足另一半边了。
代码
class solution_11 {
public:bool checkPossibility(vectorint nums) {int count0;for(int i0;inums.size()-1;i){if(nums[i]nums[i1]){count;}if(count1){return false;}if((i0nums[i-1]nums[i1])(i1nums.size()-1nums[i]nums[i2])){return false;}}return true;}
};
时间复杂度On
空间复杂度O1
13. 283 移动零 解法双指针
设置一个left指针和一个right指针left指针和right指针left和right的都赋值为0。left指针指向第一个为0的位置right表示left后面第一个不为0的数字的位置。因此right指针为快指针只需要判断rightnums.size为终止条件。因此当数字中不为0时right和left同时移动当找到第一个为0的left指针位置时候此时right指针也指向left指针。此时需要找到第一个不为0的位置也就是right指针位置。如果找到不为0的位置那么将left和right位置的数转换。
举例:
12 3 0 1 0 2
left2 right3 -swap(nums[2],nums[3]) 12 3 1 0 0 2
left 3 right4
left3 right5 swap(nums[3],nums[5]) 12 3 1 2 0 0
right6 退出循环
代码
class Solution_12 {
public:void moveZeroes(vectorint nums) {if(nums.size()1){return;}int left0,right0;while(rightnums.size()){if(nums[left]0){while(rightnums.size()nums[right]0){right;}if(rightnums.size())swap(nums[left],nums[right]);}left;right;}for(int n:nums){coutn ;}}void swap(int a,int b){int tmpa;ab;btmp;}
};时间复杂度On
空间复杂度O1
14. 118 杨辉三角 解法杨辉三角除了第一行外每一行的第一个数以及最后一个数都为1其他的为上一行的该位置以及下一个位置之和。因此可以进行双重循环 r e s u l t [ j ] [ i ] r e s u l t [ j − 1 ] [ i − 1 ] r e s u l t [ j ] [ i ] ∣ ∣ r e s u l t [ j ] [ i ] 0 第一个或者最后一个数字 result[j][i]result[j-1][i-1]result[j][i] || result[j][i]0 第一个或者最后一个数字 result[j][i]result[j−1][i−1]result[j][i]∣∣result[j][i]0第一个或者最后一个数字 注意vector中需要使用resize定义vector数组的大小否则不能进行随机访问 代码
class Solution {
public:vectorvectorint generate(int numRows) {vectorvectorintresult(numRows);result[0].push_back(1);for(int j1;jnumRows;j){result[j].resize(j1);for(int i0;ij;i){if(i0||ij){result[j][i]1;}else{result[j][i]result[j-1][i]result[j-1][i-1];}}}return result;}
};时间复杂度On^2
空间复杂度O1
15. 119 杨辉三角II 解法可以像118题目一样从1已知列举到目标行但是空间复杂度就高了。而根据杨辉三角的更新规律可以使用动态规划的思想只在这一行进行改变。
假设结果集合为res[rowIndex1],除了第一个和最后一个数字为1外其余位置的更新等于前一行的此位置和前一个位置之和所以状态转移方程为 r e s [ j ] r e s [ j ] r e s [ j − 1 ] res[j]res[j]res[j-1] res[j]res[j]res[j−1] (j0且j!最后一位)
初始化时res[0]1
若rowIndex3
举例说明
初始{1}
第1位为1{11}
第2位为1{111}
根据状态转移方程更新第1位置res[1]res[1]res[0]112 {1,2,1}
第3位为1{1211}
根据状态转移方程跟新第2和第1位置注意从后往前更新否则覆盖答案。
更新第2位置{1231}
更新第1位置{1331}
因此更新的位置是除了第一个位置和最后一个位置的其他位置
代码
class solution_14 {
public:vectorint getRow(int rowIndex) {vectorintresult(rowIndex1);result[0]1;for(int i1;irowIndex;i){result[i]1;for(int ji-1;j0;j--){result[j]result[j]result[j-1];}}return result;}
};时间复杂度On^2
空间复杂度O1
16. 661 图片平滑器 解法
对于矩阵中的每一个单元格只要找到9个包括它自身在内的紧邻的格子里的数组将其相加取平困即可。然后取得的结果向下取整保存在和矩阵相同的二维数组中即可。
假设一个矩阵的节点为x,y则以它为中心的9个节点为
(x-1,y-1)(x-1,y)(x-1,y1)(x,y-1)(x,y)(x,y1)(x1,y-1)(x1,y)(x1,y1)
同时需要判断这九个节点是否都在这个矩阵的范围内如果是则count技术加1这九个节点的和都相加保存导result二维数组中。
代码
class solution_15 {vectorvectorint imageSmoother(vectorvectorint img) {int ximg.size();int yimg[0].size();vectorvectorintresult(x,vectorint(y,0));int count;for(int i0;ix;i){for(int j0;jy;j){count0;for(int nxi-1;nxi1;nx){for(int nyj-1;nyj1;ny){if(nx0nxxny0nyy){result[i][j]img[nx][ny];count;}}}result[i][j]result[i][j]/count;}}return result;}
};17. 598 范围求和 II 解法
首先想到的是最常规的解法将ops范围内的数加1但是这种解法需要三重循环时间复杂度为On^3在数据大的时候超时。
正确的解法为注意到题目中0xai,0ybi,已知包含00点所以每次操作都是在以00点为起点的矩形内数字加1。 那么最大整数的个数就是这些矩形中的长宽都最小的矩形大小。即找到最小的长宽即可。
代码
class solution_16 {
public://常规解法 超时int maxCount(int m, int n, vectorvectorint ops) {vectorvectorint result(m, vectorint(n, 0));for (int i 0; i ops.size(); i) {int nx ops[i][0];int ny ops[i][1];for (int m 0; m nx; m) {for (int n 0; n ny; n) {result[m][n] result[m][n]1;}}}int max 0;int count 0;for (int i 0; i m; i)for (int j 0; j n; j) {if (result[i][j] max) {count;}if (result[i][j] max) {max result[i][j];count 1;}}return count;}//正确解法 数学解法int maxCount2(int m, int n, vectorvectorint ops) {int minxm;int minyn;for(int i0;iops.size();i){int xops[i][0];int yops[i][1];minxmin(minx,x);minymin(miny,y);}return minx*miny;}
};时间复杂度O(k)其中 k是数组ops 的长度。
空间复杂度O(1)
18. 419 甲板上的战舰 解法这题首先是理解题目的意思题目的意思其实是这个战舰可以是连续的竖着一列X也可以是连续横着的一行X有连续X组成的战舰之间必须有分割。例如 在上述的例子中共有两个战舰因为竖着的两个战舰之间无间隔所以只能算一个战舰。
遍历计算战舰的方法有两种可以遍历矩阵将以X为起点的战舰位置都设置为空位即X开始同行和同列的X都设置为空位。统计仍存在的X的个数就是战舰个数。
这里用第二种方法实现不需要改变原有的矩阵就是计算每个战舰队列的战舰头的位置即可。因为战舰之间必须有水平或者垂直的间隔。如果一个战舰的左侧和上方都是空位或者围墙那么战舰的个数加1。统计符合条件的顶点数就是所有战舰的个数了。
即 b o r a d [ i ] [ j ] ′ X ′ borad[i][j]X borad[i][j]′X′ b o r a d [ i ] [ j − 1 ] ′ . ′ borad[i][j-1]. borad[i][j−1]′.′ b o r a d [ i − 1 ] [ j ] ′ . ′ borad[i-1][j]. borad[i−1][j]′.′
满足此条件即为一条战舰。
代码
class solution_17 {
public:int countBattleships(vectorvectorchar board) {int rowboard.size();int col board[0].size();int cnt0;for(int i0;irow;i){for(int j0;jcol;j){if(board[i][j]X){if(i0board[i-1][j]X){continue;}if(j0board[i][j-1]X){continue;}cnt;}}}return cnt;}
};时间复杂度O(m×n)其中 m 是矩阵的行数n 是矩阵的列数我们只需要遍历一遍矩阵中每个位置即可。
空间复杂度O(1)
19. 189 轮转数组 解法最开始解法使用就地移位的方式n数组的长度那么每次都将前n-1个数字后移然后将最后一个放到第一个位置。即按照题目的要去每次翻转一次。但是这种方式在37个案例的时候超时。
解法二就地翻转。题目的意思就是将后k个数组移动到前k个上。
以例1为例[1,2,3,4,5,6,7]
首先可以将整个数组翻转[7,6,5,4,3,2,1]
然后将前k个数字翻转[5,6,7,4,3,2,1]
再将后n-k个数字翻转[5,6,7,1,2,3,4]
class solution_18 {
public://打算向后移动位数的方法 超时void rotate2(vectorint nums, int k) {int temp;int nnums.size()-1;while(k){tempnums[n];for(int in-1;i0;i--){nums[i1]nums[i];}nums[0]temp;k--;}
// for(int num:nums){
// coutnum ;
// }}//前后翻转 可用void rotate(vectorint nums, int k) {int nnums.size()-1;kk%nums.size();reverse(nums,0,n);reverse(nums,0,k-1);reverse(nums,k,n);}void reverse(vectorintnums,int start,int end){while(startend){int tempnums[end];nums[end]nums[start];nums[start]temp;start1;end-1;}}
};时间复杂度O(n)其中 n 为数组的长度。每个元素被翻转两次一共 n 个元素因此总时间复杂度为 O(2n)O(n)。
空间复杂度O(1)
20. 396 旋转函数 解法利用类似等差数列解法采用动态规划的思想求解。
动态规划的状态方程 F k F ( k − 1 ) s u m − n ∗ n u m s [ n − k ] FkF(k-1)sum-n*nums[n-k] FkF(k−1)sum−n∗nums[n−k]
如何得到
假设 F ( 0 ) 0 ∗ a [ 0 ] 1 ∗ a [ 1 ] 2 ∗ a [ 2 ] . . . ( n − 1 ) ∗ a [ n − 1 ] F(0)0*a[0]1*a[1]2*a[2]...(n-1)*a[n-1] F(0)0∗a[0]1∗a[1]2∗a[2]...(n−1)∗a[n−1] F ( 1 ) 0 ∗ a [ n − 1 ] 1 ∗ a [ 0 ] 2 ∗ a [ 1 ] . . . ( n − 1 ) ∗ a [ n − 2 ] F(1)0*a[n-1]1*a[0]2*a[1]...(n-1)*a[n-2] F(1)0∗a[n−1]1∗a[0]2∗a[1]...(n−1)∗a[n−2] F ( 2 ) 0 ∗ a [ n − 2 ] 1 ∗ a [ n − 1 ] 2 ∗ a [ 0 ] . . . ( n − 1 ) ∗ a [ n − 2 ] F(2)0*a[n-2]1*a[n-1]2*a[0]...(n-1)*a[n-2] F(2)0∗a[n−2]1∗a[n−1]2∗a[0]...(n−1)∗a[n−2]
观察到F(0)、F(1)、F(2)的变化类似于等差数列的求和当F0的所有位置都加上一个a[i]
会得到 F ( 0 ) ′ 1 ∗ a [ 0 ] 2 ∗ a [ 1 ] 3 ∗ a [ 2 ] . . . ( n − 1 ) ∗ a [ n − 2 ] n ∗ a [ n − 1 ] F(0)1*a[0]2*a[1]3*a[2]...(n-1)*a[n-2]n*a[n-1] F(0)′1∗a[0]2∗a[1]3∗a[2]...(n−1)∗a[n−2]n∗a[n−1] F ( 1 ) − F ( 0 ) ‘ 0 ∗ a [ n − 1 ] − n ∗ a [ n − 1 ] 即 F ( 1 ) F ( 0 ) ′ − n ∗ a [ n − 1 ] F(1)-F(0)^‘0*a[n-1]-n*a[n-1] 即F(1)F(0)-n*a[n-1] F(1)−F(0)‘0∗a[n−1]−n∗a[n−1]即F(1)F(0)′−n∗a[n−1]
同理得到 F ( 2 ) − F ( 1 ) ‘ 0 ∗ a [ n − 2 ] − n ∗ a [ n − 2 ] 即 F ( 2 ) F ( 1 ) ′ − n ∗ a [ n − 2 ] F(2)-F(1)^‘0*a[n-2]-n*a[n-2] 即F(2)F(1)-n*a[n-2] F(2)−F(1)‘0∗a[n−2]−n∗a[n−2]即F(2)F(1)′−n∗a[n−2]
所以假设$sumnums[0]nums[1]…nums[n-1] $ 所以 F ( k ) ‘ F ( k − 1 ) s u m 所以F(k)^‘F(k-1)sum 所以F(k)‘F(k−1)sum
所以状态转移方程为 F k F ( k − 1 ) s u m − n ∗ n u m s [ n − k ] FkF(k-1)sum-n*nums[n-k] FkF(k−1)sum−n∗nums[n−k]
每次求得Fk之后取最大值即可因为题目保证让测试案例不超过32位即没有超过int的范围。直接使用int即可。
class solution_19 {
public:int maxRotateFunction(vectorint nums) {int f00;int sum0;int nnums.size();for(int i0;in;i){f0i*nums[i];sumnums[i];}int mf0;for(int i1;in;i){f0f0sum-n*nums[n-i];mmax(m,f0);}return m;}
};
时间复杂度O(n)其中 n是数组 }nums 的长度。计算 Sum 和第一个 f 消耗 O(n) 时间后续迭代n−1 次 f 消耗 O(n)时间。
空间复杂度O(1)。仅使用常数空间。
21. 54 螺旋矩阵 解法因为观察到顺时针方向是按照右、下、左、上的顺序执行的因此可以用递归的方式按照此顺序遍历矩阵只有在遍历位置超出矩阵长度范围或者此节点已经访问过才会改变下一个方向。
因此设置direction数组表示右、下、左、上四个方向。status表示此次取到的direction的方向索引可例2可以看到当5遍历到1时发现已经访问呢因此会转向右方向因此可以用取余的方式遇到阻碍需要转向。
需要注意dfs递归的终点是当result的结果等于矩阵的大小说明已经遍历结束可以返回。
代码
const int direction[4][2]{{0,1},{1,0},{0,-1},{-1,0}};
class solution_20 {
public:vectorint spiralOrder(vectorvectorint matrix) {vectorintresult;vectorvectorintflag(matrix.size(),vectorint(matrix[0].size(),0));int status0;dfs(matrix,flag,result,0,0,status);for(int num:result){coutnum ;}return result;}void dfs(vectorvectorintmatrix,vectorvectorintflag,vectorint result,int i,int j,int status){flag[i][j]1;result.push_back(matrix[i][j]);if(result.size()matrix.size()*matrix[0].size()){return ;}int nextIidirection[status][0];int nextJjdirection[status][1];if(nextI0||nextImatrix.size()||nextJ0||nextJmatrix[0].size()||flag[nextI][nextJ]1){status(status1)%4;}dfs(matrix,flag,result,idirection[status][0],jdirection[status][1],status);}
};
时间复杂度O(mn)其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
空间复杂度O(mn)。需要创建一个大小为 m×n 的矩阵 visited 记录每个位置是否被访问过。 22. 59 螺旋矩阵II 解法可以采用和54相似的思路按照右下左上的顺序将1-n^2的数字依次填充到矩阵中用一个二维数组matrix保存最后结果初始化全为0如果碰到越界或者该位置数字已经不为0就转变方向继续递归。直到所有的元素都已经在矩阵中了即cntn*n了返回。
const int direction[4][2]{{0,1},{1,0},{0,-1},{-1,0}};
class solution_21 {
public:vectorvectorint generateMatrix(int n) {vectorvectorintmatrix(n,vectorint(n,0));int cnt0;int status0;dfs(matrix,n,cnt,0,0,status);for(int i0;in;i){for(int j0;jn;j){coutmatrix[i][j] ;}coutendl;}}void dfs(vectorvectorintmatrix,int n,int cnt,int i,int j,int status){cnt;matrix[i][j]cnt;if(cntn*n){return;}int nextIidirection[status][0];int nextJjdirection[status][1];if(nextI0||nextImatrix.size()||nextJ0||nextJmatrix[0].size()||matrix[nextI][nextJ]!0){status(status1)%4;}dfs(matrix,n,cnt,idirection[status][0],jdirection[status][1],status);}
};
时间复杂度O(mn)其中 m 和 n 分别是输入矩阵的行数和列数。矩阵中的每个元素都要被访问一次。
空间复杂度O(mn)。需要创建一个大小为 m×n 的矩阵 visited 记录每个位置是否被访问过。 23. 498 对角线遍历 解法简单模拟遍历可以看到按照对角线遍历的规律若从左下角到右上角则x-1,y1;
若从右上角到左下角则x1,y-1;
flag0,表示从左下到右上flag1表示右下到左上。
访问对角线需要转方向的时候若左下到右上越界则转变方向向右x不变y1,此时需要注意当位于3这个点时候若转向向右则为03点不正确应为12点因此若y1mat[0].size的话y不变x1。
同理当从右上到左下时候位于7的点x1mat.size时候x不变y1 代码
class solution_22 {
public:vectorintresult;vectorint findDiagonalOrder(vectorvectorint mat) {int x,y,nx,ny;int flag0;x0;y0;int rowmat.size();int colmat[0].size();while(result.size()!mat.size()*mat[0].size()){result.push_back(mat[x][y]);nxxdirection[flag][0];nyydirection[flag][1];if(nxrow||nx0||nycol||ny0){if(flag0){//如果flag0是向右移动但是同时注意若移动到最右边即y1m应该向下移动nxy1mat[0].size()?x:x1;nyy1mat[0].size()?y1:y;}else{//如果flag1是向下移动但是同时注意若移动到最下边即x1m应该向右移动nxx1mat.size()?x1:x;nyx1mat.size()?y:y1;}flag(flag1)%2;}xnx;yny;}return result;}};时间复杂度On*m
空间复杂度O1
24. 566 重塑矩阵 解法
对于一个行数为 m列数为 n行列下标都从 0 开始编号的二维数组将其中的每个元素 (i,j) 映射到整数域内并且它们按照行优先的顺序一一对应着 [0,mn) 中的每一个整数。形象化地来说我们把这个二维数组变成了一个一维数组。
映射为 ( i , j ) − i ∗ n j (i,j)-i*nj (i,j)−i∗nj
同样的可以将一个整数x映射到矩阵的下标
ix/n, jx%n
所以此题需要两步骤
将二位数组nums映射成一维数组将一维数组映射回r行c列的二维数组
代码
class solution_23 {
public:vectorvectorint matrixReshape(vectorvectorint mat, int r, int c) {vectorvectorintresult(r,vectorint(c,0));int rowmat.size();int colmat[0].size();if((row*col)!(r*c)){return mat;}for(int i0;irow*col;i){result[i/c][i%c]mat[i/col][i%col];}return result;}
};
时间复杂度O(rc)。这里的时间复杂度是在重塑矩阵成功的前提下的时间复杂度否则当 mn rc 时C 语言中返回的是原数组的一份拷贝本质上需要的时间复杂度为 O(mn)而其余语言可以直接返回原数组的对象需要的时间复杂度仅为 O(1)。
空间复杂度O(1)。这里的空间复杂度不包含返回的重塑矩阵需要的空间
25. 73 矩阵置零 解法简单标记循环遍历矩阵将矩阵为0的位置的行和列记录下来放入set集合中去重然后
再次遍历矩阵若这个位置的行或者列在set集合中那么就将这个位置置为1。
代码
class solution_24 {
public:void setZeroes(vectorvectorint matrix) {setintrow;setintcol;for(int i0;imatrix.size();i)for(int j0;jmatrix[0].size();j){if(matrix[i][j]0) {row.insert(i);col.insert(j);}}for(int i0;imatrix.size();i)for(int j0;jmatrix[0].size();j){if(row.count(i)1||col.count(j)1){matrix[i][j]0;}}}
};时间复杂度O(mn)其中 m是矩阵的行数n 是矩阵的列数。我们至多只需要遍历该矩阵两次。
空间复杂度O(mn)其中 m 是矩阵的行数n 是矩阵的列数。我们需要分别记录每一行或每一列是否有零出现。
26.289 生命游戏 解法
注意到不能根据每个细胞位置的八个方向的活细胞或者死细胞数字更新数组这样无法做到题目中的同步更新。因为下一状态是根据当前状态生成的如果更新后后面的位置的细胞状态可能收到最新更新的细胞状态的影响。因此我的解法是遍历这个board数组对于每个位置的八个方向的活细胞数字进行统计然后将原来数组中需要翻转数字的位置索引记录下来。
如果是活细胞并且活细胞的数目2或者3,那么该活细胞要变成死细胞所以该位置需要翻转记录结果。
如果是死细胞并且活细胞的数组3死细胞变为活细胞也需要翻转
对于如果是活细胞并且周围活细胞数组2或者2仍然是活细胞不需要翻转即不需要记录。
最后遍历一次board将索引的位置进行翻转。
class solution_25 {
public:int direction[8][2]{{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{1,1},{-1,1},{1,-1}};void gameOfLife(vectorvectorint board) {vectorpairint,intresult;int count0;int x,y,nx,ny;for(int i0;iboard.size();i){for(int j0;jboard[0].size();j){count0;xi;yj;for(int k0;k8;k){nxidirection[k][0];nyjdirection[k][1];if(nx0nxboard.size()ny0nyboard[0].size()){if(board[nx][ny]){count;}}}if(board[x][y]1){if(count2||count3){result.push_back(make_pair(x,y));}}if(board[x][y]0count3){result.push_back(make_pair(x,y));}}}//遍历修改for(int i0;iboard.size();i){for(int j0;jboard[0].size();j){if(find(result.begin(),result.end(), make_pair(i,j))!result.end()){if(board[i][j]0){board[i][j]1;}else{board[i][j]0;}coutboard[i][j];}}}}
};时间复杂度Omn
空间复杂度Omn
27. 303 区域和检索–数组不可变 解法一暴力解法
从left到right进行求和操作
class NumArray {
public:vectorintn;NumArray(vectorint nums) {this-n.assign(nums.begin(),nums.end());}int sumRange(int left, int right) {int sum0;for(int ileft;iright;i){sumn[i];}return sum;}
};时间复杂度On^2
空间复杂度On
解法二预处理得到前缀和。sumsRange(left,right)其实可以用nums[0,right]的和-nums[0,left-1]。
所以只需要记录到每个位置的前缀和即可但是left-1有可能越界如果将sums数组的大小定位nums.size()1。
sums[i1]nums[i]sums[i]; 所以sums[i]表示的是从nums[0i-1]的所有的数字和
即sumsRange[left,right]sums[right1]-sums[left]
代码
class NumArray {
public:vectorintsums;NumArray(vectorint nums) {sums.resize(nums.size()1);for(int i0;inums.size();i){sums[i1]sums[i]nums[i];}}int sumRange(int left, int right) {return sums[right1]-sums[left];}
};/*** Your NumArray object will be instantiated and called as such:* NumArray* obj new NumArray(nums);* int param_1 obj-sumRange(left,right);*/时间复杂度初始化 O(n)每次检索 O(1)其中 n 是数组 nums 的长度。初始化需要遍历数组 nums 计算前缀和时间复杂度是 O(n)。每次检索只需要得到两个下标处的前缀和然后计算差值时间复杂度是 O(1)。
空间复杂度O(n)其中 n是数组 nums 的长度。需要创建一个长度为n1 的前缀和数组。
28. 304 二维区域和检索-矩阵不可变 解法二维数组前缀和关于二维数组前缀和的算法见
二维数组前缀和
代码
class NumMatrix {
public: vectorvectorintsums;NumMatrix(vectorvectorint matrix) {int rowmatrix.size();int colmatrix[0].size();sums.resize(row1,vectorint(col1,0));//预处理for(int i1;irow;i)for(int j1;jcol;j){sums[i][j]sums[i-1][j]sums[i][j-1]-sums[i-1][j-1]matrix[i-1][j-1];}}int sumRegion(int row1, int col1, int row2, int col2) {row11;col11;row21;col21;return sums[row2][col2]-sums[row1-1][col2]-sums[row2][col1-1]sums[row1-1][col1-1];}
};时间复杂度初始化 O(mn)每次检索O(1)其中 m 和 n 分别是矩阵matrix 的行数和列数。 初始化需要遍历矩阵 matrix 计算二维前缀和时间复杂度是O(mn)。 每次检索的时间复杂度是 O(1)。
空间复杂度O(mn)其中 m 和 n 分别是矩阵 matrix 的行数和列数。需要创建一个m1 行 n1 列的二维前缀和数组 sums。
29. 238 除自身以外数组的乘积 解法注意题目要求不能使用除法如果要求一个nums中除nums[i]之外的其余各元素的乘积。
一种方法是所有乘积除以nums[i]因为题目要求不能使用除法所以这种方法不行。
因此可以换一种方式nums[i]的左侧的数字乘积乘以nums[i]右侧的数字乘积。
通过预处理的方式得到两个数组分别表示索引i位置左侧的乘积和右侧的乘积。
初始化两个空数组 L 和 R。对于给定索引 iL[i] 代表的是 i 左侧所有数字的乘积R[i] 代表的是 i 右侧所有 数字的乘积。 用两个循环来填充 L 和 R 数组的值。对于数组 LL[0] 应该是 1因为第一个元素的左边没有元素。对于其他元素L[i] L[i-1] * nums[i-1]。 同理对于数组 RR[nums.size()-1] 应为 1。length 指的是输入数组的大小。
其他元素R[i] R[i1] * nums[i1]。 当 R 和 L 数组填充完成我们只需要在输入数组上迭代且索引 i 处的值为L[i] * R[i]。
代码
class solution_28 {
public:vectorint productExceptSelf(vectorint nums) {vectorintresult(nums.size());vectorintleft(nums.size(),0);vectorintright(nums.size(),0);left[0]1;//left[i]表示索引i左侧所有元素乘积for(int i1;inums.size();i){left[i]left[i-1]*nums[i-1];}right[nums.size()-1]1;//right[i]表示索引i右侧所有元素乘积for(int inums.size()-2;i0;i--){right[i]right[i1]*nums[i1];}for(int i0;inums.size();i){result[i]left[i]*right[i];}return result;}
};
时间复杂度O(N)其中 N 指的是数组 nums 的大小。预处理 L 和 R 数组以及最后的遍历计算都是 O(N) 的时间复杂度。
空间复杂度O(N)其中 N指的是数组 nums 的大小。使用了 L 和 R 数组去构造答案L 和 R 数组的长度为数组 nums 的大小。
