leetcode每日一题43

2024-01-08 23:46:21

116. 填充每个节点的下一个右侧节点指针

层序遍历嘛

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* next;

    Node() : val(0), left(NULL), right(NULL), next(NULL) {}

    Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}

    Node(int _val, Node* _left, Node* _right, Node* _next)
        : val(_val), left(_left), right(_right), next(_next) {}
};
*/

class Solution {
public:
    Node* levelOder(Node* root)
    {
        queue<Node*> que;
        if(root==NULL)
        {
            return root;
        }
        que.push(root);
        while(!que.empty())
        {
            int size = que.size();
            for(int i=0;i<size;i++)
            {
                Node* node = que.front();
                que.pop();
                if(i<size-1)
                    node->next=que.front();
                if(node->left) que.push(node->left);
                if(node->right) que.push(node->right);
            }
        }
        return root;
    }
    Node* connect(Node* root) {
        return levelOder(root);
    }
};

120. 三角形最小路径和

其实就是DP啦

  1. 确定dp数组(dp table)以及下标的含义
    dp[i][j]就是三角形的第i行第j列的最小路径和
  2. 确定递推公式
    不在三角形的腰上时,路径和由上一行的两个路径和中选更小的
    dp[i][j]=min(dp[i-1][j-1], dp[i-1][j]) + c[i][j]
    c[i][j]为三角形第i行第j列的值
    三角形的两个腰上的值是只能由上一行的腰上的值决定
    dp[i][0]=c[i][0]+dp[i-1][0]
    dp[i][i]=c[i][i]+dp[i-1][i-1]
  3. dp数组如何初始化
    三角形的两个腰上的值是只能由上一行的腰上的值决定
    dp[0][0]=c[0][0]
  4. 确定遍历顺序
    从上到小从左到右
  5. 举例推导dp数组
class Solution {
public:
    int minimumTotal(vector<vector<int>>& triangle) {
        int size = triangle.size();
        vector<vector<int>> dp(size, vector<int>(size));
        dp[0][0]=triangle[0][0];
        for(int i=1;i<size;i++)
        {
            dp[i][0] = triangle[i][0] + dp[i-1][0];
            for(int j=1;j<i;j++)
            {
                dp[i][j]=min(dp[i-1][j-1], dp[i-1][j]) + triangle[i][j];
            }
            dp[i][i] = triangle[i][i]+dp[i-1][i-1];
        }
        int min = dp[size-1][0];
        for(int i =1;i<size;i++)
        {
            if(min>dp[size-1][i])
                min = dp[size-1][i];
        }
        return min;
    }
};

128. 最长连续序列

直接用sort()的话是O(nlogn)
题目要求O(n)
所以我们使用一个哈希表对于数据进行快速的查找
当前数字nums[i]是序列的第一个数据的条件是找不到nums[i]-1
找到第一个数据后,递增,找下一个数据在不在哈希表里,若在,当前序列长度++

class Solution {
public:
    int longestConsecutive(vector<int>& nums) {
        int res_len = 0;
        unordered_set<int> num_set(nums.begin(), nums.end());  
        int cur_len;
        for(int i=0;i<nums.size();i++)
        {
            int cur = nums[i];
            if(!num_set.count(cur-1)){
                cur_len = 1;
                while(num_set.count(++cur))
                    cur_len++;
                res_len = max(res_len,cur_len);
            }
        }
        return res_len;
    }
};

为什么代码里for里套了while还是O(n)呢

如果所有数字都是连续的,那么只有第一个数字会去走while,其他数字无法通过if判断,那么每个数字都只处理一次。如果所有数字都是不连续的,每个数字都去走while,但是while只会处理这个数字,相当于还是每个数字只处理一次。不是说for里面套了while就一定是平方级别的复杂度,关键在于看数组中每个元素的处理次数。

就酱

129. 求根节点到叶节点数字之和

深度搜索,前序遍历
从根节点开始,遍历每个节点,如果遇到叶子节点,则获得该路径的数字。如果当前节点不是叶子节点,则计算其子节点对应的数字,然后对子节点递归遍历,获得该节点对应的所有路径的数字之和。

  1. 参数及返回值
    因为要用到当前路径到达父节点组成的值,所以参数不仅要当前节点,也需要父节点组成的值presum
    返回值是当前节点到叶节点的数字之和,整型
  2. 终止条件
    当前节点为根节点的时候,返回当前值
    if(root->left==nullptr&&root->right==nullptr)
    return sum;
    因为左右节点是空的时候已经判断了,那么整个树的root节点是空的时候,返回0
    if(root==nullptr)
    return 0;
  3. 单层逻辑
    首先计算当前节点对应的数字int sum=preSum*10+root->val;
    然后深度遍历,获得左右节点的值之和
int leftSum=0;
int rightSum=0;
if(root->left)
    leftSum=preOrder(root->left,sum);
if(root->right)
    rightSum=preOrder(root->right,sum);

最后将左右节点对应的路径的数字之和再求和,就是当前节点所在的所有路径的数字之和

/**
 * 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 preOrder(TreeNode* root, int preSum)
    {
        if(root==nullptr)
            return 0;
        int sum=preSum*10+root->val;
        if(root->left==nullptr&&root->right==nullptr)
            return sum;
        int leftSum=0;
        int rightSum=0;
        if(root->left)
            leftSum=preOrder(root->left,sum);
        if(root->right)
            rightSum=preOrder(root->right,sum);
        return leftSum+rightSum;
    }
    int sumNumbers(TreeNode* root) {
        return preOrder(root,0);
    }
};

文章来源:https://blog.csdn.net/weixin_40530554/article/details/135466965
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。