C/C++每日一练(20230504)
目录
1. 将数据流变为多个不相交区间 🌟🌟🌟
2. 冒泡法排序大小 🌟
3. Pow(x, n) 🌟🌟
🌟 每日一练刷题专栏 🌟
Golang每日一练 专栏
Python每日一练 专栏
C/C++每日一练 专栏
Java每日一练 专栏
1. 将数据流变为多个不相交区间
给你一个由非负整数 a1, a2, ..., an 组成的数据流输入，请你将到目前为止看到的数字总结为不相交的区间列表。
实现 SummaryRanges 类：
SummaryRanges()使用一个空数据流初始化对象。void addNum(int val)向数据流中加入整数val。int[][] getIntervals()以不相交区间[starti, endi]的列表形式返回对数据流中整数的总结。
示例：
输入： ["SummaryRanges", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals", "addNum", "getIntervals"] [[], [1], [], [3], [], [7], [], [2], [], [6], []] 输出： [null, null, [[1, 1]], null, [[1, 1], [3, 3]], null, [[1, 1], [3, 3], [7, 7]], null, [[1, 3], [7, 7]], null, [[1, 3], [6, 7]]] 解释： SummaryRanges summaryRanges = new SummaryRanges(); summaryRanges.addNum(1); // arr = [1] summaryRanges.getIntervals(); // 返回 [[1, 1]] summaryRanges.addNum(3); // arr = [1, 3] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]] summaryRanges.addNum(7); // arr = [1, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]] summaryRanges.addNum(2); // arr = [1, 2, 3, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]] summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7] summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
提示：
0 <= val <= 10^4- 最多调用
addNum和getIntervals方法3 * 10^4次
进阶：如果存在大量合并，并且与数据流的大小相比，不相交区间的数量很小，该怎么办?
出处：
https://edu.csdn.net/practice/27007586
代码：
#include <bits/stdc++.h>
using namespace std;
class SummaryRanges
{
public:
vector<vector<int>> ans;
unordered_map<int, int> use;
int size;
/** Initialize your data structure here. */
SummaryRanges()
{
size = 0;
}
void addNum(int val)
{
if (use.count(val) != 0)
return;
use[val] = 1;
int i;
for (i = 0; i < size; i++)
if (val < ans[i][0])
break;
if (i == 0)
{
if (size == 0)
{
ans.insert(ans.begin(), {val, val});
size++;
}
else if (val + 1 == ans[i][0])
ans[0][0] = val;
else
{
ans.insert(ans.begin(), {val, val});
size++;
}
}
else if (i == size)
{
if (val - 1 == ans[i - 1][1])
ans[i - 1][1] = val;
else
{
ans.push_back({val, val});
size++;
}
}
else
{
if (val + 1 != ans[i][0] && val - 1 != ans[i - 1][1])
{
ans.insert(ans.begin() + i, {val, val});
size++;
}
else if (val + 1 == ans[i][0] && val - 1 == ans[i - 1][1])
{
ans[i - 1][1] = ans[i][1];
ans.erase(ans.begin() + i);
size--;
}
else if (val + 1 == ans[i][0])
{
ans[i][0] = val;
}
else
{
ans[i - 1][1] = val;
}
}
}
vector<vector<int>> getIntervals()
{
return ans;
}
};
/**
* Your SummaryRanges object will be instantiated and called as such:
* SummaryRanges* obj = new SummaryRanges();
* obj->addNum(val);
* vector<vector<int>> param_2 = obj->getIntervals();
*/
string Vector2dToString(vector<vector<int>> vec2d, string sep = ",")
{
stringstream ss;
ss << "[";
for (int i = 0; i < vec2d.size(); ++i) {
ss << "[";
copy(vec2d[i].begin(), vec2d[i].end(), ostream_iterator<int>(ss, sep.c_str()));
ss.seekp(-(int)sep.size(), ios_base::end);
ss << "]" << sep;
}
ss.seekp(-(int)sep.size(), ios_base::end);
ss << "]";
return ss.str();
}
int main()
{
SummaryRanges summaryRanges;
vector<vector<int>> res;
summaryRanges.addNum(1); // arr = [1]
res = summaryRanges.getIntervals(); // 返回 [[1, 1]]
cout << Vector2dToString(res, ", ") << endl;
summaryRanges.addNum(3); // arr = [1, 3]
res = summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3]]
cout << Vector2dToString(res, ", ") << endl;
summaryRanges.addNum(7); // arr = [1, 3, 7]
res = summaryRanges.getIntervals(); // 返回 [[1, 1], [3, 3], [7, 7]]
cout << Vector2dToString(res, ", ") << endl;
summaryRanges.addNum(2); // arr = [1, 2, 3, 7]
res = summaryRanges.getIntervals(); // 返回 [[1, 3], [7, 7]]
cout << Vector2dToString(res, ", ") << endl;
summaryRanges.addNum(6); // arr = [1, 2, 3, 6, 7]
res = summaryRanges.getIntervals(); // 返回 [[1, 3], [6, 7]]
cout << Vector2dToString(res, ", ") << endl;
return 0;
}输出：
[[1, 1]]
[[1, 1], [3, 3]]
[[1, 1], [3, 3], [7, 7]]
[[1, 3], [7, 7]]
[[1, 3], [6, 7]]
2. 冒泡法排序大小
4286 3185 2895 3550 2745 按从小到大排序
出处：
https://edu.csdn.net/practice/27007587
代码：
#include <stdio.h>
#define ARR_LEN 255
#define elemType int
void bubbleSort (elemType arr[], int len) {
elemType temp;
int i, j;
for (i=0; i<len-1; i++)
for (j=0; j<len-1-i; j++) {
if (arr[j] > arr[j+1]) {
temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
int main (void) {
elemType arr[ARR_LEN] = {4286,3185,2895,3550,2745};
int len = 5;
int i;
bubbleSort (arr, len);
for (i=0; i<len; i++)
printf ("%d\t", arr[i]);
putchar ('\n');
return 0;
}输出：
2745 2895 3185 3550 4286
3. Pow(x, n)
实现 pow(x, n)，即计算 x 的 n 次幂函数（即，xn）。
示例 1：
输入：x = 2.00000, n = 10 输出：1024.00000
示例 2：
输入：x = 2.10000, n = 3 输出：9.26100
示例 3：
输入：x = 2.00000, n = -2 输出：0.25000 解释：2-2 = 1/22 = 1/4 = 0.25
提示：
-100.0 < x < 100.0-2^31 <= n <= 2^31-1-10^4 <= x^n <= 10^4
以下程序实现了这一功能，请你填补空白处内容：
```c++
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
double myPow(double x, int n)
{
if (n == INT_MIN)
{
double t = dfs(x, -(n / 2));
return 1 / t * 1 / t;
}
else
{
___________________;
}
}
private:
double dfs(double x, int n)
{
if (n == 0)
{
return 1;
}
else if (n == 1)
{
return x;
}
else
{
double t = dfs(x, n / 2);
return (n % 2) ? (x * t * t) : (t * t);
}
}
};
```
出处：
https://edu.csdn.net/practice/27007588
代码：
#include <bits/stdc++.h>
using namespace std;
class Solution
{
public:
double myPow(double x, int n)
{
if (n == INT_MIN)
{
double t = dfs(x, -(n / 2));
return 1 / t * 1 / t;
}
else
{
return n < 0 ? 1 / dfs(x, -n) : dfs(x, n);
}
}
private:
double dfs(double x, int n)
{
if (n == 0)
{
return 1;
}
else if (n == 1)
{
return x;
}
else
{
double t = dfs(x, n / 2);
return (n % 2) ? (x * t * t) : (t * t);
}
}
};
int main (void) {
Solution s;
cout << s.myPow(2.0, 10) << endl;
cout << s.myPow(2.1, 3) << endl;
cout << s.myPow(2.0, -2) << endl;
return 0;
}输出：
1024
9.261
0.25
🌟 每日一练刷题专栏 🌟
✨ 持续，努力奋斗做强刷题搬运工！
👍 点赞，你的认可是我坚持的动力！
🌟 收藏，你的青睐是我努力的方向！
✎ 评论，你的意见是我进步的财富！
☸ 主页：https://hannyang.blog.csdn.net/
 | Golang每日一练 专栏 |
 | Python每日一练 专栏 |
 | C/C++每日一练 专栏 |
 | Java每日一练 专栏 |