【LeetCode】HOT 100（14）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【LeetCode】HOT 100（14）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题单介绍：

精选 100 道力扣（LeetCode）上最热门的题目，适合初识算法与数据结构的新手和想要在短时间内高效提升的人，熟练掌握这 100 道题，你就已经具备了在代码世界通行的基本能力。

题单介绍：

题目：85. 最大矩形 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

题目：96. 不同的二叉搜索树 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

写在最后：

题目：85. 最大矩形 - 力扣（Leetcode）

【LeetCode】HOT 100（14）,LeetCode HOT 100,leetcode,算法,c++

题目的接口：

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {

    }
};

解题思路：

我不知道他们是怎么想出这道题的解法的，

是在是太强了，反正我是想不出来。

主要思路如下：

按行读取这个数组，

如果读到的格子的数是1，高度就+1，如果是0，高度就变成0，

每行读取按照这个规则，就能得到一个存放高度的数组，

把求高度的最大矩形面积的代码带入：（建议先学会这道题）

84. 柱状图中最大的矩形 - 力扣（Leetcode）

然后求出每更新一行的最大矩形即可

代码如下：

代码：

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.empty()) return 0;
        int ans = 0; 
        vector<int> line(matrix[0].size() + 2, 0);
        for(int i = 0; i < matrix.size(); i++) {
            for(int j = 0; j < matrix[0].size(); j++) {
                line[j + 1] = (matrix[i][j] == '0') ? 0 : line[j + 1] + 1;
            }
            ans = max(ans, largestRectangleArea(line));
        }
        return ans;
    }
private: //带入求最大矩形的代码
    int largestRectangleArea(vector<int>& heights) {
        vector<int> st;
        int ans = 0;
        for(int i = 0; i < heights.size(); i++) {
            while(!st.empty() && heights[st.back()] > heights[i]) {
                int high = st.back();
                st.pop_back();
                int left = st.back() + 1;
                int right = i - 1;
                ans = max(ans, (right - left + 1) * heights[high]);
            }
            st.push_back(i);
        }
        return ans;
    }
};

过过过过啦！！！！

【LeetCode】HOT 100（14）,LeetCode HOT 100,leetcode,算法,c++

题目：96. 不同的二叉搜索树 - 力扣（Leetcode）

【LeetCode】HOT 100（14）,LeetCode HOT 100,leetcode,算法,c++

题目的接口：

class Solution {
public:
    int numTrees(int n) {

    }
};

解题思路：

这道题我一开始是想着搜索然后计数来求的，

但是复杂的不允许，

只能用动态规划去做，

我画了图观察了规律，但是还是不太明白下面这个状态表达式是怎么求出来的，

dp[i] += dp[以j为头结点左子树节点数量] * dp[以j为头结点右子树节点数量]

我觉得我得系统的学习一下动态规划了，不然每次遇到动态规划就痛苦面具。

代码如下：

代码：

class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n + 1);
        dp[0] = 1;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] += dp[j - 1] * dp[i - j]; 
            }
        }
        return dp[n];
    }
};