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]
示例 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
