LeetCode的C++ 11/Python3 题解及解释

会员服务 ·

LeetCode的C++ 11/Python3 题解及解释

2019 年 4 月 13 日 专知

【导读】本仓库包含LeetCode前710题的C++11和Python3 的题解与解释。

Github地址：

https://github.com/pezy/LeetCode

本仓库不仅包含题解，还有详细的解题思路，如：

084 题最大的矩阵

以及代码：

#include <vector>using std::vector;#include <stack>using std::stack;#include <algorithm>using std::max; using std::min;
class Solution {public:    int largestRectangleArea(vector<int> &height) {        int max_area = 0, i = 0, size = height.size();        for (stack<int> stk; i<size || !stk.empty(); )            if (stk.empty() || (i != size && height[stk.top()] <= height[i])) stk.push(i++);            else {                int tp = stk.top(); stk.pop();                max_area = max(max_area, height[tp] * (stk.empty() ? i : i-stk.top()-1));            }        return max_area;    }    int maximalRectangle(vector<vector<char> > &matrix) {        if (matrix.empty()) return 0;        int max_area = 0;        vector<int> height(matrix[0].size(), 0);        for (size_t i=0; i<matrix.size(); ++i) {            for (size_t j=0; j<matrix[0].size(); ++j)                if (matrix[i][j] == '0') height[j] = 0;                else ++height[j];            max_area = max(max_area, largestRectangleArea(height));        }        return max_area;    }};

#define CATCH_CONFIG_MAIN#include "../Catch/single_include/catch.hpp"#include "solution.h"
TEST_CASE("Maximal Rectangle", "[maximalRectangle]"){    Solution s;    SECTION( "common1" )    {        std::vector<std::vector<char>> matrix = {{'0', '1', '0', '0'},                                                 {'1', '1', '1', '0'},                                                 {'0', '1', '1', '0'},                                                 {'0', '0', '1', '0'},                                                 {'0', '1', '0', '0'}};        REQUIRE( s.maximalRectangle(matrix) == 4 );    }    SECTION( "common2" )    {        std::vector<std::vector<char>> matrix = {{'1', '1', '1', '1'},                                                 {'1', '0', '0', '1'},                                                 {'1', '1', '1', '1'},                                                 {'0', '0', '1', '0'},                                                 {'0', '1', '1', '1'}};        REQUIRE( s.maximalRectangle(matrix) == 4 );    }    SECTION( "common3" )    {        std::vector<std::vector<char>> matrix = {{'1', '1', '1', '1', '1'},                                                 {'1', '1', '1', '0', '1'},                                                 {'1', '1', '1', '0', '0'},                                                 {'1', '0', '0', '0', '0'},                                                 {'1', '0', '0', '0', '0'}};        REQUIRE( s.maximalRectangle(matrix) == 9 );    }    SECTION( "common4" )    {        std::vector<std::vector<char>> matrix = {{'0', '1', '0', '1', '0'},                                                 {'1', '1', '1', '1', '1'},                                                 {'0', '1', '1', '1', '0'},                                                 {'0', '1', '1', '1', '0'},                                                 {'1', '1', '1', '1', '1'},                                                 {'1', '1', '1', '1', '0'},                                                 {'0', '1', '0', '1', '0'},                                                 {'0', '0', '0', '0', '0'}};        REQUIRE( s.maximalRectangle(matrix) == 15 );    }