cpp刷题打卡记录30——轮转数组 螺旋矩阵 搜索二维矩阵II

轮转数组法一class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); while(k0){ vectorint nums1 nums; int tmp nums1[n-1]; for(int i 1; in; i){ nums[i] nums1[i-1]; } nums[0] tmp; k--; } } };超出时间限制。总体思想很简单就是每次循环时把变化前的数组记录下来然后第一个元素是最后一个元素其余都是把前一个元素赋值给当前元素。法二class Solution { public: void rotate(vectorint nums, int k) { int n nums.size(); k k % n; if(k 0){ return; } reverse(nums.begin(), nums.end()); reverse(nums.begin(), nums.begin()k); reverse(nums.begin()k, nums.end()); } };想法就是利用reverse如nums [1,2,3,4,5,6,7]k3那么先翻转整个数组[7,6,5,4,3,2,1]再翻转前k个[5,6,7,4,3,2,1]再翻转后面的[5,6,7,1,2,3,4]得到最终结果。但需要注意的是可能k 会大于数组的大小k如果等于数组的大小那就最终会刚好翻转一遍和原数组相同所以当k大于数组大小就没有必要翻转那么多次所以有k k%n的步骤。螺旋矩阵class Solution { public: vectorint spiralOrder(vectorvectorint matrix) { int m matrix.size(); int n matrix[0].size(); vectorint result(n*m, 0); int count 0; int n1 min(m, n)/2; int i 0, j 0, startx 0, starty 0; int offset 1; while(n1){ i startx; j starty; for(j ; jn-offset; j){ result[count] matrix[i][j]; count; } for(i; im-offset; i){ result[count] matrix[i][j]; count; } for(j; joffset; j--){ result[count] matrix[i][j]; count; } for(i; ioffset; i--){ result[count] matrix[i][j]; count; } startx; starty; offset; n1--; } if(min(n, m)%2 1){ if(m n){ for(jstarty; jn-offset; j){ result[count] matrix[startx][j]; count; } } else{ for(istartx; im-offset; i){ result[count] matrix[i][starty]; count; } } } return result; } };思路是一圈一圈的输出最后最中间那块再单独处理输出一下。需要注意的是一圈一圈的输出是要按照相同的规律去输出的如上代码就是左闭右开去输出的然后每次都从(0, 0)(1, 1)这样的位置开始进行输出。最后最中间需要单独处理的也分两种情况分为竖着的一列和横着的一行然后进行赋值输出。定义count变量是方便可以[ ]进行赋值不然要用push_back可能会影响时间。搜索二维矩阵IIclass Solution { public: bool searchMatrix(vectorvectorint matrix, int target) { int m matrix.size(); int n matrix[0].size(); int i 0; int j n-1; while(im j0){ if(target matrix[i][j]){ return true; } else if(target matrix[i][j]){ j--; } else{ i; } } return false; } };思路是从右上角开始当targetmatrix[i][j]时就往下进行移动去寻找当targetmatrix[i][j]时就往左进行移动去寻找如果是从左上角开始的话那么往下和往右都是逐渐变大的。