首页 > 代码库 > LeetCode--Combination Sum

LeetCode--Combination Sum

由于需要就地保存清零信息,所以把信息保存在第一行和第一列

 1 class Solution { 2 public: 3     void setZeroes(vector<vector<int> > &matrix) { 4         const int ROW = matrix.size(); 5         if (ROW == 0) 6             return; 7         const int COL = matrix[0].size(); 8         if (COL == 0) 9             return;10         11         // we store the 0 information in12         // the 1st row and 1st col13         bool R00 = false;14         for(int i = 0; i < COL; ++i)15             if (matrix[0][i] == 0)16             {17                 R00 = true;18                 break;19             }20         bool C00 = false;21         for(int i = 0; i < ROW; ++i)22             if (matrix[i][0] == 0)23             {24                 C00 = true;25                 break;26             }27         28         // now traverse the remaining parts of29         // the matrix and store 0 into the 30         // first row31         for(int i = 1; i < ROW; ++i)32             for(int j = 1; j < COL; ++j)33                 if (matrix[i][j] == 0)34                 {35                     matrix[i][0] = 0;36                     matrix[0][j] = 0;37                 }38                 39         // use the first row/col information to40         // fill zeros41         for(int i = 1; i < ROW; ++i)42             if (matrix[i][0] == 0)43                 for(int j = 1; j < COL; ++j)44                     matrix[i][j] = 0;45         46         for(int i = 1; i < COL; ++i)47             if (matrix[0][i] == 0)48                 for(int j = 1; j < ROW; ++j)49                     matrix[j][i] = 0;50         51         // Finally check the 1st row/col52         if (R00)53             fill(begin(matrix[0]), end(matrix[0]), 0);54         if (C00)55             for(int i = 0; i < ROW; ++i)56                 matrix[i][0] = 0;57         58         return;59     }60 };

 

LeetCode--Combination Sum