C/C++每日一练(20230515) 区间和的个数、BST最近公共祖先、最接近元素-Toy模板网

这篇具有很好参考价值的文章主要介绍了C/C++每日一练(20230515) 区间和的个数、BST最近公共祖先、最接近元素。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

C/C++每日一练(20230515) 区间和的个数、BST最近公共祖先、最接近元素

1. 区间和的个数 🌟🌟🌟

2. 二叉搜索树的最近公共祖先 🌟

3. 找最接近元素 🌟🌟

🌟 每日一练刷题专栏 🌟

Golang每日一练专栏

Python每日一练专栏

C/C++每日一练专栏

Java每日一练专栏

1. 区间和的个数

给你一个整数数组 nums 以及两个整数 lower 和 upper 。求数组中，值位于范围 [lower, upper] （包含 lower 和 upper）之内的 区间和的个数 。

区间和 S(i, j) 表示在 nums 中，位置从 i 到 j 的元素之和，包含 i 和 j (i ≤ j)。

示例 1：

输入：nums = [-2,5,-1], lower = -2, upper = 2
输出：3
解释：存在三个区间：[0,0]、[2,2] 和 [0,2] ，对应的区间和分别是：-2 、-1 、2 。

示例 2：

输入：nums = [0], lower = 0, upper = 0
输出：1

提示：

1 <= nums.length <= 10^5
-2^31 <= nums[i] <= 2^31 - 1
-10^5 <= lower <= upper <= 10^5
题目数据保证答案是一个 32 位 的整数

出处：

https://edu.csdn.net/practice/27859951

代码：

#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
    int countRangeSum(vector<int> &nums, int lower, int upper)
    {
        int n = nums.size();
        long presum = 0;
        multiset<long> S;
        S.insert(0);
        int ret = 0;
        for (int i = 0; i < n; i++)
        {
            presum += nums[i];
            ret += distance(S.lower_bound(presum - upper), S.upper_bound(presum - lower));
            S.insert(presum);
        }
        return ret;
    }
};

int main()
{
	Solution s;
	vector<int> nums = {-2, 5, -1};
	int lower = -2, upper = 2;
	cout << s.countRangeSum(nums, lower, upper) << endl;
	nums = {0};
	lower = 0; upper = 0;
	cout << s.countRangeSum(nums, lower, upper) << endl;
	return 0;	
}

输出：

3
1

2. 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

C/C++每日一练(20230515) 区间和的个数、BST最近公共祖先、最接近元素

示例 1:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。

示例 2:

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

说明:

所有节点的值都是唯一的。
p、q 为不同节点且均存在于给定的二叉搜索树中。

出处：

https://edu.csdn.net/practice/27859952

代码：

#define null INT_MIN
#include <bits/stdc++.h>
using namespace std;
struct TreeNode
{
    int val;
    TreeNode *left;
    TreeNode *right;
    TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution
{
public:
    TreeNode *lowestCommonAncestor(TreeNode *root, TreeNode *p, TreeNode *q)
    {
        if (root == NULL)
            return NULL;
        if ((root->val > q->val) && (root->val > p->val))
            return lowestCommonAncestor(root->left, p, q);
        else if ((root->val < q->val) && (root->val < p->val))
            return lowestCommonAncestor(root->right, p, q);
        return root;
    }
};

TreeNode* buildTree(vector<int>& nums)
{
    TreeNode *root = new TreeNode(nums[0]);
    queue<TreeNode*> q;
    q.push(root);
    int i = 1;
    while(!q.empty() && i < nums.size())
    {
        TreeNode *cur = q.front();
        q.pop();
        if(nums[i] != null)
        {
            cur->left = new TreeNode(nums[i]);
            q.push(cur->left);
        }
        i++;
        if(i < nums.size() && nums[i] != null)
        {
            cur->right = new TreeNode(nums[i]);
            q.push(cur->right);
        }
        i++;
    }
    return root;
}

int main()
{
	Solution s;
	vector<int> nums = {6,2,8,0,4,7,9,null,null,3,5};
	TreeNode *root = buildTree(nums);
	TreeNode *p = new TreeNode(2);
	TreeNode *q = new TreeNode(8);
	cout << s.lowestCommonAncestor(root, p, q)->val << endl;
	q = new TreeNode(4);
	cout << s.lowestCommonAncestor(root, p, q)->val << endl;
	
	return 0;	
}

输出：

6
2

3. 找最接近元素

目标值与数组所有元素去比对，找出最接近的元素，输出下标。

举例如下：一个数组{915,941,960,976,992,1015,1034,1050,1073,1089,1115,1131,1150,1166,1182,1208,1227};目标值假设是1000，最接近元素为992，下标为4

以下程序实现了这一功能，请你填补空白处内容：

```c++
#include <stdio.h>
int main()
{
int min = (1 << 31) - 1;
int idx = 0;
int arr[] = {915, 941, 960, 976, 992, 1015, 1034, 1050, 1073, 1089, 1115, 1131, 1150, 1166, 1182, 1208, 1227};
int n = 1000;
for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
{
int diff = arr[i] - n;
if (diff < 0)
diff = -diff;
_________________;
}
printf("最接近的是%d 下标是%d", arr[idx], idx);
return 0;
}
```

出处：

https://edu.csdn.net/practice/27859953

代码：

#include <stdio.h>
int main()
{
    int min = (1 << 31) - 1;
    int idx = 0;
    int arr[] = {915, 941, 960, 976, 992, 1015, 1034, 1050, 1073, 1089, 1115, 1131, 1150, 1166, 1182, 1208, 1227};
    int n = 1000;
    for (int i = 0; i < sizeof(arr) / sizeof(int); i++)
    {
        int diff = arr[i] - n;
        if (diff < 0)
            diff = -diff;
        if (diff < min)
        {
            min = diff;
            idx = i;
        }
    }
    printf("最接近的是%d 下标是%d", arr[idx], idx);
    return 0;
}

输出：

最接近的是992 下标是4