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

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

题单介绍：

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

题单介绍：

题目：124. 二叉树中的最大路径和 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

题目：128. 最长连续序列 - 力扣（Leetcode）

题目的接口：

解题思路：

代码：

过过过过啦！！！！

写在最后：

题目：124. 二叉树中的最大路径和 - 力扣（Leetcode）

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

题目的接口：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int maxPathSum(TreeNode* root) {

    }
};

解题思路：

这道题的思路并不算难，可以说不算是一道合格的困难题，

直接用搜索去做就行，

题目的核心思路是：

1. 寻找最大路径和

2. 根据题意，当我们走到一个节点上之后，最大的路径和是：左节点 + 当前节点 + 右节点的和

3. 左节点的值等于左节点本身的值 + 他自己的左节点的值，右节点思路相同

4. 所以当前节点需要返回给上一个节点的值就是自己本身的值 + max(左节点，右节点)

5. 当然，如果出现路径和<0的情况就可以置空重新计算了。

那么代码如下：

代码：

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    //最大路径和
    int sumMax = INT_MIN; 
    int maxPathSum(TreeNode* root) {
        calSum(root);
        return sumMax;
    }
private:
    int calSum(TreeNode* root) {
        if(root == nullptr) return 0;

        //接收左右节点的最大值
        int left = max(calSum(root->left), 0);
        int right = max(calSum(root->right), 0);

        //计算当前的最大路径和
        int MaxSum = root->val + left + right;

        //更新最大路径和
        sumMax = max(sumMax, MaxSum);

        //返回的值是给前面的接收节点最大值接收的
        return root->val + max(left, right);
    }
};

过过过过啦！！！！

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

题目：128. 最长连续序列 - 力扣（Leetcode）

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

题目的接口：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {

    }
};

解题思路：

这道题我一开始在想直接sort

但是他要求要O（N），我又想要用哈希来做，

但是有点不知道咋用，

主要思路如下：

遍历整个哈希，如果遇到一个没有与上一个数联结的数，就求出序列长度并更新长度，

没有与上一个数联结的数：比如说：遍历到数字2，如果没有1，这个就是没有与上一个数联结的数

代码如下：

这里补充一点：

count这个接口，是如果找到这个数就返回1，否则返回0

代码：

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        unordered_set<int> st;
        for(auto e : nums) st.insert(e);
        int ans = 0;
        for(auto k : st) {
            if(!st.count(k - 1)) {
                int y = k;
                while(st.count(y + 1)) y++;
                ans = max(ans, y - k + 1);
            }
        }
        return ans;
    }
};