資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝設計
法律研究C++ 中移除區間
假設我們有一個排序的不相交區間的列表，每個區間 intervals[i] = [a, b] 表示一組數字 x，其中 a <= x < b。我們需要移除 intervals 中的任何區間與區間 toBeRemoved 之間的交集。最後，我們需要找到所有這些移除操作後排序的區間列表。因此，如果輸入類似於 - [[0,2], [3,4],[5,7]]，toBeRemoved := [1, 6]，則輸出將是 [[0, 2], [6,7]]。
為了解決這個問題，我們將遵循以下步驟 -
- 定義一個名為 manipulate2() 的方法，它將接收矩陣 a 和陣列 y
- x := 矩陣 a 的最後一行，然後從 a 中刪除最後一行
- z := x
- x[0] := y[1], z[1] := y[0]
- 如果 z[0] - z[1]，則將 z 插入到 a 中
- 如果 x[0] - x[1]，則將 x 插入到 a 中
- 主方法將接收矩陣 in 和陣列 t
- 定義一個矩陣 ans，並令 n := 矩陣 in 的行數
- 對於 i 從 0 到 n -
- 將 in[i] 插入到 ans 中
- a := a 的最後一行，b := t
- 如果 a[0] > b[0]，則交換 a 和 b
- 如果 a 和 b 相交，則呼叫 manipulate2(ans, t)
- 返回 ans
示例（C++）
讓我們看看以下實現，以便更好地理解 -
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<vector<auto> > v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << "[";
for(int j = 0; j <v[i].size(); j++){
cout << v[i][j] << ", ";
}
cout << "],";
}
cout << "]"<<endl;
}
class Solution {
public:
bool isIntersect(vector <int> a, vector <int> b){
return max(a[0], a[1]) >= min(b[0], b[1]);
}
void manipulate2(vector < vector <int> > &a, vector <int> y){
vector <int> x = a.back();
a.pop_back();
vector <int> z = x;
x[0] = y[1];
z[1] = y[0];
if(z[0] < z[1])a.push_back(z);
if(x[0] < x[1])a.push_back(x);
}
vector<vector<int>> removeInterval(vector<vector<int>>& in, vector<int>& t) {
vector < vector <int> > ans;
int n = in.size();
for(int i = 0; i < n; i++){
ans.push_back(in[i]);
vector <int> a;
vector <int> b;
a = ans.back();
b = t;
if(a[0]>b[0])swap(a, b);
if(isIntersect(a, b)){
manipulate2(ans, t);
}
}
return ans;
}
};
main(){
vector<int> v2 = {1,6};
vector<vector<int>> v1 = {{0,2},{3,4},{5,7}};
Solution ob;
print_vector(ob.removeInterval(v1, v2));
}輸入
[[0,2],[3,4],[5,7]] [1,6]
輸出
[[0, 1, ],[6, 7, ],]
更新於: 2020年4月30日
228 次檢視
廣告