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

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 ); }

-END-

专 · 知

专知,专业可信的人工智能知识分发,让认知协作更快更好!欢迎登录www.zhuanzhi.ai,注册登录专知,获取更多AI知识资料!

欢迎微信扫一扫加入专知人工智能知识星球群,获取最新AI专业干货知识教程视频资料和与专家交流咨询!

请加专知小助手微信(扫一扫如下二维码添加),加入专知人工智能主题群,咨询技术商务合作~

专知《深度学习:算法到实战》课程全部完成!530+位同学在学习,现在报名,限时优惠!网易云课堂人工智能畅销榜首位!

点击“阅读原文”,了解报名专知《深度学习:算法到实战》课程

登录查看更多
点赞 0
Top