1.20 LeetCode总结（基本算法）_模拟类

编程总结

每每刷完一道题后，其思想和精妙之处没有地方记录，本篇博客用以记录刷题过程中的遇到的算法和技巧

1599. 经营摩天轮的最大利润

intmaxi(intx,inty){returnx>y?x:y;}intminOperationsMaxProfit(int*customers,intcustomersSize,intboardingCost,intrunningCost){if(boardingCost*4<=runningCost){return-1;}intcur=0;// 当前时间等待人数（登轮前）intprofit=0;//（当前总利润）intmax=0;//（最大利润持续更新）intans=0;//（返回的最大转动次数）//有人来的时间段先根据已有时间线按部就班进行转动for(inti=0;i<customersSize;i++){cur+=customers[i];if(cur>=4){// 大于等于四个就四个一批处理profit+=4*boardingCost-runningCost;cur=cur-4;}else{// 小于4则清空人数profit+=cur*boardingCost-runningCost;cur=0;}if(profit>max){ans=i+1;// 本次操作下来看利润能否增长，是则更新答案}max=maxi(profit,max);}//没有人来了以后，处理剩下等待的人intc=0;//记录转动次数while(cur>=4)//四个一批处理获取最大利润{profit+=4*boardingCost-runningCost;cur=cur-4;c++;if(profit>max)//更新结果ans=customersSize+c;max=maxi(profit,max);//更新最大利润}if(cur<4&&cur>0&&cur*boardingCost>runningCost)// 处理落单的1-3人，前提是能使利润正增长{profit+=cur*boardingCost-runningCost;cur=0;if(profit>max)ans=customersSize+c+1;max=maxi(profit,max);}if(ans==0)//没有使利润>0的情况，返回-1return-1;returnans;}

885. 螺旋矩阵 III

在 rows x cols 的网格上，你从单元格 (rStart, cStart) 面朝东面开始。网格的西北角位于第一行第一列，网格的东南角位于最后一行最后一列。
你需要以顺时针按螺旋状行走，访问此网格中的每个位置。每当移动到网格的边界之外时，需要继续在网格之外行走（但稍后可能会返回到网格边界）。
最终，我们到过网格的所有 rows x cols 个空间。
按照访问顺序返回表示网格位置的坐标列表。

提示：
1 <= rows, cols <= 100
0 <= rStart < rows
0 <= cStart < cols

int**spiralMatrixIII(introws,intcols,intrStart,intcStart,int*returnSize,int**returnColumnSizes){inttotal=rows*cols;// 分配结果空间int**ans=(int**)malloc(sizeof(int*)*total);*returnColumnSizes=(int*)malloc(sizeof(int)*total);*returnSize=total;for(intk=0;k<total;k++){ans[k]=(int*)malloc(sizeof(int)*2);(*returnColumnSizes)[k]=2;}intx=rStart;// 当前行坐标inty=cStart;// 当前列坐标intidx=0;// 结果数组写入下标// 先存入起点ans[idx][0]=x;ans[idx][1]=y;idx++;// r = 当前圈层每一条边需要走的步数，等价你代码的圈层半径rintr=1;while(idx<total){// ========== 第一段：向东 右走 r 步 (dy=+1) ==========for(intstep=0;step<r&&idx<total;step++){y=y+1;// 判断当前坐标在网格内才存入答案if(x>=0&&x<rows&&y>=0&&y<cols){ans[idx][0]=x;ans[idx][1]=y;idx++;}}// ========== 第二段：向南 下走 r 步 (dx=+1) ==========for(intstep=0;step<r&&idx<total;step++){x=x+1;if(x>=0&&x<rows&&y>=0&&y<cols){ans[idx][0]=x;ans[idx][1]=y;idx++;}}// 走完右、下两条边，圈层扩大，步数+1r++;// ========== 第三段：向西 左走 r 步 (dy=-1) ==========for(intstep=0;step<r&&idx<total;step++){y=y-1;if(x>=0&&x<rows&&y>=0&&y<cols){ans[idx][0]=x;ans[idx][1]=y;idx++;}}// ========== 第四段：向北 上走 r 步 (dx=-1) ==========for(intstep=0;step<r&&idx<total;step++){x=x-1;if(x>=0&&x<rows&&y>=0&&y<cols){ans[idx][0]=x;ans[idx][1]=y;idx++;}}// 走完左、上两条边，圈层再扩大，步数+1r++;}returnans;}