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