二维vector相关问题,C\C++交流,编程语言专区,鱼C论坛

DOLLAR. 发表于 2022-1-12 17:58:13

二维vector相关问题

在leetcode上刷题，最后自己在ide上试的时候发现写不来主函数....
/*以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals = .
*请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。*/

/*
*author:Ambert
*date:2022/01/12
*/

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
#include<numeric>
#include <algorithm>
using namespace std;

class Solution{
public:
vector<vector<int>> merge(vector<vector<int>>& intervals){
int n = intervals.size();
if(n==0||n==1) return intervals;
sort(intervals.begin(),intervals.end()); //使得数组内的数组有序
vector<vector<int>> merged;
for(int i=0;i<n;++i){
int L=intervals,R=intervals; //定义数组的最左指针和最右指针
if(!merged.size()||merged.back()<L) //前一个的最右元素小于后一个数组最左元素则不变
merged.push_back({L,R});
else
merged.back()=max(merged.back(),R); //否则，取最大的一个更新最右元素
}
return merged;
}
};

int main(){
vector<vector<int> > a = {{1,3},{2,6},{8,15},{10,18}};
Solution solution;
cout<<solution.merge(a)<<endl;
}

报错如下，请前辈指教

Stubborn 发表于 2022-1-13 11:46:32

本帖最后由 Stubborn 于 2022-1-13 12:07 编辑

输入：intervals = [,,,]
输出：[,,]
解释：区间和重叠, 将它们合并为

需要明确知道，我们在处理intervals ，会发生的情况，需要合并区间，或者合并不了区间，什么情况会发生，连续的任意两个区间【A, B】和【A`, B`】

第一覆盖的情况需要合并【1， 6】【2， 3】： A < A ` , B > B`
第二重叠的情况需要合并【1， 6】【2， 8】： A < A ` , B < B`
第三，不能合并【1， 6】【8， 10】： A < A ` , B < B` ，但是A` > B，导致区间发生了‘隔离’

综合上面的情况，可以分成2类
1类，A` > B ，不能合并
2类，A` < B ,可以合并，从B , B` 选择大的一个数字

# intervals前提是排序好得，根据区间的起始位置。
result = []
result.append(intervals)
FOR E IN intervals:
# 不能合并,把当前元素添加到结果集
if E > result[-1] :result.append(E)
#能合并,从B or B` 选择大的元素跟新到列表
else:result[-1] = max( result[-1],E)

人造人 发表于 2022-1-14 11:58:19

本帖最后由人造人于 2022-1-14 11:59 编辑

/*以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals = .
*请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。*/

/*
*author:Ambert
*date:2022/01/12
*/

#include <algorithm>
#include <iostream>
#include <numeric>
#include <stdio.h>
#include <stdlib.h>
#include <vector>

using namespace std;

class Solution {
public:
//vector<vector<int>> merge(vector<vector<int>> &intervals) {
const vector<vector<int>> merge(vector<vector<int>> &intervals) {
   int n = intervals.size();
   if(n == 0 || n == 1)
         return intervals;
   //sort(intervals.begin(), intervals.end()); //使得数组内的数组有序
   sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {return a < b;}); //使得数组内的数组有序
   vector<vector<int>> merged;
   for(int i = 0; i < n; ++i) {
         int L = intervals,
            R = intervals; //定义数组的最左指针和最右指针
         if(!merged.size() ||
            merged.back() < L) //前一个的最右元素小于后一个数组最左元素则不变
            merged.push_back({L, R});
         else
            merged.back() =
               max(merged.back(), R); //否则，取最大的一个更新最右元素
   }
   return merged;
}
};

ostream &operator<<(ostream &os, const vector<vector<int>> &rhs) {
for(const auto &i: rhs) {
   for(const auto &j: i) {
         os << j << " ";
   }
   os << endl;
}
return os;
}

int main() {
vector<vector<int>> a = {{1, 3}, {2, 6}, {8, 15}, {10, 18}};
Solution solution;
cout << solution.merge(a) << endl;
return 0;
}

DOLLAR. 发表于 2022-1-17 13:06:23

Stubborn 发表于 2022-1-13 11:46
需要明确知道，我们在处理intervals ，会发生的情况，需要合并区间，或者合并不了区间，什么情况会发生 ...

感谢，这两天没看帖子，我自己后来发现问题了：在主函数中不能直接cout数组

DOLLAR. 发表于 2022-1-17 13:07:12

我把改好的代码贴出来，有需要的朋友可以看看

#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
using namespace std;

class Solution{
public:
vector<vector<int>> mergeInterval(vector<vector<int>>& intervals){
int n = intervals.size();
if(n==0||n==1) return intervals;
sort(intervals.begin(),intervals.end()); //是数组内的数组有序
vector<vector<int>> merged;
for(int i=0;i<n;++i){
int L=intervals,R=intervals; //定义数组的最左指针位置及最右指针位置
if(!merged.size()||merged.back()<L) //前一个的最右元素小于后一个数组的最左元素则不变
merged.push_back({L,R});
else
merged.back()=max(merged.back(),R); //否则，取最大的一个元素更新最右指针
}
return merged;
}
};

int main(){
vector<vector<int>> a = {{1,3},{2,6},{8,15},{10,18}};
Solution solution;
vector<vector<int> > b = solution.mergeInterval(a);
for (decltype(b.size()) i = 0; i < b.size(); ++i) {
for (decltype(b.size()) j = 0; j < b.size(); ++j) {
cout << b << " ";
}
//cout << endl;
}
}

人造人 发表于 2022-1-17 13:14:39

DOLLAR. 发表于 2022-1-17 13:07
我把改好的代码贴出来，有需要的朋友可以看看

我感觉还是重载operator<<
直接这样输出比较好 cout << solution.merge(a) << endl;

人造人 发表于 2022-1-17 13:18:40

DOLLAR. 发表于 2022-1-17 13:07
我把改好的代码贴出来，有需要的朋友可以看看

这个 intervals 还是不要引用比较好，merge 这个函数不应该修改main函数中的那个变量a
虽然这样效率不高

//vector<vector<int>> merge(vector<vector<int>> &intervals) {
//const vector<vector<int>> merge(vector<vector<int>> &intervals) {
const vector<vector<int>> merge(vector<vector<int>> intervals) {
   int n = intervals.size();
   if(n == 0 || n == 1)
         return intervals;
   //sort(intervals.begin(), intervals.end()); //使得数组内的数组有序
   sort(intervals.begin(), intervals.end(), [](const vector<int> &a, const vector<int> &b) {return a < b;}); //使得数组内的数组有序
   vector<vector<int>> merged;
   for(int i = 0; i < n; ++i) {
         int L = intervals,
            R = intervals; //定义数组的最左指针和最右指针
         if(!merged.size() ||
            merged.back() < L) //前一个的最右元素小于后一个数组最左元素则不变
            merged.push_back({L, R});
         else
            merged.back() =
               max(merged.back(), R); //否则，取最大的一个更新最右元素
   }
   return merged;
}

页: [1]

鱼C论坛's Archiver

二维vector相关问题