wy的leetcode刷题记录_Day89

声明

本文章的所有题目信息都来源于leetcode
如有侵权请联系我删掉!
时间：2024-3-18

前言

@TOC

303. 区域和检索 - 数组不可变

今天的每日一题是：
303. 区域和检索 - 数组不可变

题目介绍

给定一个整数数组 nums，处理以下类型的多个查询:

计算索引 left 和 right （包含 left 和 right）之间的 nums 元素的和，其中 left <= right

实现 NumArray 类：

NumArray(int[] nums) 使用数组 nums 初始化对象
int sumRange(int i, int j) 返回数组 nums 中索引 left 和 right 之间的元素的总和，包含
left 和 right 两点（也就是 nums[left] + nums[left + 1] + ... + nums[right] )

示例 1：
输入： ["NumArray", "sumRange", "sumRange", "sumRange"] [[[-2, 0, 3, -5,2, -1]], [0, 2], [2, 5], [0, 5]] 输出： [null, 1, -1, -3]
解释：
NumArray numArray = new NumArray([-2, 0, 3, -5, 2, -1]);
numArray.sumRange(0, 2); // return 1 ((-2) + 0 + 3)
numArray.sumRange(2, 5); // return -1 (3 + (-5) + 2 + (-1))
numArray.sumRange(0, 5); // return -3 ((-2) + 0 + 3 + (-5) + 2 + (-1))

思路

竟然被我一眼看出来了。。直接用前缀和，但这里题目要求的是左闭右闭区间，需要注意下即可。

代码

class NumArray {

private:
    vector<int> a;
public:
    NumArray(vector<int>& nums) {
        a.assign(nums.begin(),nums.end());
        int n=nums.size();
        for(int i=1;i<n;i++)
        {
            a[i]+=a[i-1];
        }
    }
    
    int sumRange(int left, int right) {
        if(left==0)
            return a[right];
        return a[right]-a[left-1];
    }
};

/**
 * Your NumArray object will be instantiated and called as such:
 * NumArray* obj = new NumArray(nums);
 * int param_1 = obj->sumRange(left,right);
 */

收获

无

230. 二叉搜索树中第K小的元素

题目介绍

给定一个二叉搜索树的根节点 root ，和一个整数 k ，请你设计一个算法查找其中第 k 个最小元素（从 1 开始计数）。

示例 1：
输入：root = [3,1,4,null,2], k = 1
输出：1
示例 2：
输入：root = [5,3,6,2,4,null,null,1], k = 3
输出：3

思路

这道题思路也是一想就出来了哈，最简单的：大家都知道二叉搜索树的中序遍历一定是升序序列，那么我就用中序遍历获得这个升序序列，然后直接返回第k个元素即可。这里使用了递归和递推两种方式。

代码

/**
 * 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 {
private:
    vector<int> a;
public:
    void dfs(TreeNode* node)
    {
        if(!node)   
            return ;
        dfs(node->left);
        a.emplace_back(node->val);
        dfs(node->right);
    }
    int kthSmallest(TreeNode* root, int k) {
        if(!root)
            return 0;
        dfs(root);
        int n=a.size();
        if(k>n)
            return 0;
        return a[k-1];
    }
};

/**
 * 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 kthSmallest(TreeNode* root, int k) {
        vector<int> a;
        stack<TreeNode*> stk;
        while(root!=nullptr||!stk.empty())
        {
            while(root!=nullptr)
            {
                stk.push(root);
                root=root->left;
            }
            root=stk.top();
            stk.pop();
            a.emplace_back(root->val);
            root=root->right;
        }
        return a[k-1];
    }
};

收获

无

199. 二叉树的右视图

题目介绍

给定一个二叉树的根节点 root，想象自己站在它的右侧，按照从顶部到底部的顺序，返回从右侧所能看到的节点值。

示例 1:

输入: [1,2,3,null,5,null,4]
输出: [1,3,4]
示例 2:
输入: [1,null,3]
输出: [1,3]
示例 3:
输入: []
输出: []

思路

也是一道比较简单的题，如图所知，我们只需要返回二叉树每一层的最右边的元素，那么我们使用层序遍历返回每层的最后的元素即可。

代码

/**
 * 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:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if(!root)
            return {};
        queue<TreeNode*> q;
        q.push(root);
        // ans.emplace_back(root->val);
        while(!q.empty())
        {
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode* node=q.front();
                q.pop();
                if(node->left) 
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
                if(i==n-1)
                    ans.emplace_back(node->val);
            }
        }

        return ans;
    }
};

收获

巩固层序遍历

114. 二叉树展开为链表

题目介绍

给你二叉树的根结点 root ，请你将它展开为一个单链表：

展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。
展开后的单链表应该与二叉树先序遍历顺序相同。

示例 1：
输入：root = [1,2,5,3,4,null,6]
输出：[1,null,2,null,3,null,4,null,5,null,6]
示例 2：
输入：root = []
输出：[]
示例 3：
输入：root = [0]
输出：[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:
    vector<int> rightSideView(TreeNode* root) {
        vector<int> ans;
        if(!root)
            return {};
        queue<TreeNode*> q;
        q.push(root);
        // ans.emplace_back(root->val);
        while(!q.empty())
        {
            int n=q.size();
            for(int i=0;i<n;i++)
            {
                TreeNode* node=q.front();
                q.pop();
                if(node->left) 
                    q.push(node->left);
                if(node->right)
                    q.push(node->right);
                if(i==n-1)
                    ans.emplace_back(node->val);
            }
        }

        return ans;
    }
};

收获

对树的结构有了新的认识，不仅可以常规的三种遍历，也可以自己定义从后开始遍历。

105. 从前序与中序遍历序列构造二叉树

题目介绍

给定两个整数数组 preorder 和 inorder ，其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。

示例 1:

输入: preorder = [3,9,20,15,7], inorder = [9,3,15,20,7]
输出:[3,9,20,null,null,15,7]
示例 2:
输入: preorder = [-1], inorder = [-1]
输出: [-1]

思路

前序遍历：中左右，中序遍历：左右中，所以我们可以根据前序遍历寻找到根节点，再根据根节点在中序序列中寻找到左子树和右子树再根据左子树的大小可以在前序序列中寻找到左子树和右子树的根节点，以此类推写个递归就可以了。

代码

/**
 * 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:
    unordered_map<int,int> index;
    TreeNode* build(vector<int> preorder,vector<int> inorder,int preLeft,int preRight,int inLeft,int inRight)
    {
        if(preLeft>preRight)
            return nullptr;
        
        int pre_root=preLeft;
        int in_root=index[preorder[pre_root]];//中序根的下标

        TreeNode* root=new TreeNode(preorder[pre_root]);
        int left_size=in_root-inLeft;
        root->left=build(preorder,inorder,preLeft+1,preLeft+left_size,inLeft,in_root-1);
        root->right=build(preorder,inorder,preLeft+left_size+1,preRight,in_root+1,inRight);
        return root;
    }
    TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) {
        int n=preorder.size();
        for(int i=0;i<n;i++)
        {
            index[inorder[i]]=i;
        }
        return build(preorder,inorder,0,n-1,0,n-1);
    }
};

收获

前序遍历和中序遍历