cpp刷题打卡记录29——矩阵置零 旋转图像 除了自身以外数组的乘积

矩阵置零class Solution { public: void setZeroes(vectorvectorint matrix) { int n matrix.size(); int m matrix[0].size(); vectorbool rowZero(n, false); vectorbool culZero(m, false); for(int i 0; in; i){ for(int j 0; jm; j){ if(matrix[i][j] 0){ rowZero[i] true; culZero[j] true; } } } for(int i 0; in; i){ for(int j 0; jm; j){ if(rowZero[i] || culZero[j]){ matrix[i][j] 0; } } } } };属于暴力解法时间复杂度为O(mn)空间复杂度为O(m n)。旋转图像法一class Solution { public: void rotate(vectorvectorint matrix) { vectorvectorint result; int n matrix.size(); for(int j 0; jn; j){ vectorint curMrow; for(int i n-1; i0; i--){ curMrow.push_back(matrix[i][j]); } result.push_back(curMrow); } matrix result; } };时间复杂度为O()空间复杂度为O()。其实并没有达到题目要求题目要求是要原地算法。我还是创建了额外的vector来进行存旋转后的矩阵所以思路想法比较简单。法二class Solution { public: void rotate(vectorvectorint matrix) { int n matrix.size(); for(int i 0; in/2; i){ for(int j 0; jn; j){ swap(matrix[i][j], matrix[n-i-1][j]); } } for(int i 0; in; i){ for(int j 0; ji; j){ swap(matrix[i][j], matrix[j][i]); } } } };很巧妙的思路是通过翻转来做到顺时针旋转90°的。先按照中心横线进行水平翻转再按照主对角线进行翻转。如果是逆时针旋转90°就先水平翻转再副对角线进行翻转。除了自身以外数组的乘积法一class Solution { public: vectorint productExceptSelf(vectorint nums) { vectorint result; for(int i 0; inums.size(); i){ int tmp 1; for(int j 0; jnums.size(); j){ if(j ! i){ tmp tmp*nums[j]; } } result.push_back(tmp); } return result; } };超出时间限制。法二class Solution { public: vectorint productExceptSelf(vectorint nums) { int n nums.size(); vectorint result(n, 0); vectorint left(n, 0); vectorint right(n, 0); left[0] 1; right[n-1] 1; for(int i 1; in; i){ left[i] nums[i-1]*left[i-1]; } for(int i n-2; i0; i--){ right[i] right[i1]*nums[i1]; } for(int i 0; in; i){ result[i] left[i]*right[i]; } return result; } };这个思路是定义了一个左数组和一个右数组然后对应的除了自身以外数组的乘积就是该位置的左边和右边乘积。这个左数组和右数组的赋值有点像前缀和的感觉。left[0]和right[n-1]设置为1是因为left[0]没有左边的数right[n-1]也没有右边的数。