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
