当前在线人数9672
首页 - 分类讨论区 - 海外生活 - 待字闺中版 - 同主题阅读文章

此篇文章共收到打赏
0

  • 10
  • 20
  • 50
  • 100
您目前伪币余额:0
未名交友
[更多]
[更多]
f电面
[版面:待字闺中][首篇作者:jamespp] , 2014年08月01日02:14:40 ,2959次阅读,33次回复
来APP回复,赚取更多伪币 关注本站公众号:
[首页] [上页][下页][末页] [分页:1 2 ]
jamespp
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 1 ]

发信人: jamespp (rainyday), 信区: JobHunting
标  题: f电面
发信站: BBS 未名空间站 (Fri Aug  1 02:14:40 2014, 美东)

给定一些不相交的区间和一个新的区间,要求合并起来
但问题是不让用新的vector/stack,也就是说要用constant additional space

请教大家
估计是挂了
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
peking14
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 2 ]

发信人: peking14 (吐槽无力), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 02:16:13 2014, 美东)

merge interval?
【 在 jamespp (rainyday) 的大作中提到: 】
: 给定一些不相交的区间和一个新的区间,要求合并起来
: 但问题是不让用新的vector/stack,也就是说要用constant additional space
: 请教大家
: 估计是挂了



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 73.]

 
jamespp
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 3 ]

发信人: jamespp (rainyday), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 02:20:25 2014, 美东)

对啊,这题不用新的vector或者是list怎么搞?
【 在 peking14 (吐槽无力) 的大作中提到: 】
: merge interval?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
realshrek
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 4 ]

发信人: realshrek (shrek), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 02:39:49 2014, 美东)

老的排个序
新的挨个和老的比较
能merge就把老的删掉,更新新的interval
碰到不能merge,算法就可以结束


【 在 jamespp (rainyday) 的大作中提到: 】
: 给定一些不相交的区间和一个新的区间,要求合并起来
: 但问题是不让用新的vector/stack,也就是说要用constant additional space
: 请教大家
: 估计是挂了



--

※ 来源:·BBS 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
MaGongJia
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 5 ]

发信人: MaGongJia (code farmer one), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 02:48:49 2014, 美东)

不用排序应该就可以,一个个和老的比。如果有哪个老的完全包含新的就结束,如果新
的完全包含老的老的删除,剩下的情况就是最多有两个老的分别和新的的上下边界相交

排序还要nlogn呢

【 在 realshrek (shrek) 的大作中提到: 】
: 老的排个序
: 新的挨个和老的比较
: 能merge就把老的删掉,更新新的interval
: 碰到不能merge,算法就可以结束



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
realshrek
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 6 ]

发信人: realshrek (shrek), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 03:31:57 2014, 美东)

我觉得根本不用考虑那么多
就遍历一下,能合并就删老的
一遍就行了
因为老的彼此都是不想交的

【 在 MaGongJia (code farmer one) 的大作中提到: 】
: 不用排序应该就可以,一个个和老的比。如果有哪个老的完全包含新的就结束,如果新
: 的完全包含老的老的删除,剩下的情况就是最多有两个老的分别和新的的上下边界相交
: 排序还要nlogn呢



--

※ 来源:·BBS 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

 
MaGongJia
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 7 ]

发信人: MaGongJia (code farmer one), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 03:43:29 2014, 美东)

我就这个意思

【 在 realshrek (shrek) 的大作中提到: 】
: 我觉得根本不用考虑那么多
: 就遍历一下,能合并就删老的
: 一遍就行了
: 因为老的彼此都是不想交的



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
timeforce
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 8 ]

发信人: timeforce (timeforce), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 04:32:15 2014, 美东)

应该还有其他可能吧,比如新的区间落在两个老区间中间呢?还是说题目要求合并,所
以必然会有相交,而不用考虑这种情况
【 在 MaGongJia (code farmer one) 的大作中提到: 】
: 不用排序应该就可以,一个个和老的比。如果有哪个老的完全包含新的就结束,如果新
: 的完全包含老的老的删除,剩下的情况就是最多有两个老的分别和新的的上下边界相交
: 排序还要nlogn呢



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 216.]

 
MaGongJia
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 9 ]

发信人: MaGongJia (code farmer one), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 05:45:07 2014, 美东)

那就什么都不用干啊,下一个阿

【 在 timeforce (timeforce) 的大作中提到: 】
: 应该还有其他可能吧,比如新的区间落在两个老区间中间呢?还是说题目要求合并,所
: 以必然会有相交,而不用考虑这种情况



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 50.]

 
timeforce
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 10 ]

发信人: timeforce (timeforce), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 06:08:43 2014, 美东)

重新想了一下,这和leetcode上的insert intervals 做法应该一样吧,虽然那个原始
区间都排过序了
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 216.]

 
jamespp
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 11 ]

发信人: jamespp (rainyday), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 11:00:30 2014, 美东)

可是在c++中的vector或者是java中的List的iterator的时候,怎样能够删除又不引起
invalid iterator或者是concurrent modification exception呢?

能给个程序吗?我看到的解答都是创建新的vector或者是List

【 在 realshrek (shrek) 的大作中提到: 】
: 老的排个序
: 新的挨个和老的比较
: 能merge就把老的删掉,更新新的interval
: 碰到不能merge,算法就可以结束



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
UMDTA
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 12 ]

发信人: UMDTA (UMDTA), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 11:46:02 2014, 美东)

这个怎么样?
/*
merege interals
*/
void mergeIntervals(vector<Pair> &vp, Pair np){
    int size = (int)vp.size();
    if(size == 0) {
        vp.push_back(np);
        return;
    }
   
    for(vector<Pair>::iterator it = vp.begin(); it != vp.end();){
        if(np.first > it->second || np.second < it->first){
            it++;
        }
        else if(np.first > it->first && np.second < it->second){
            return;
        }
        else if(np.first <=  it->first && np.second >= it->second){
            vp.erase(it);
        }
        else{
            np.first = np.first < it->first ? np.first : it->first;
            np.second = np.second > it->second? np.second : it->second;
            vp.erase(it);
        }
    }
   
    vp.push_back(np);
}
【 在 jamespp (rainyday) 的大作中提到: 】
: 可是在c++中的vector或者是java中的List的iterator的时候,怎样能够删除又不引起
: invalid iterator或者是concurrent modification exception呢?
: 能给个程序吗?我看到的解答都是创建新的vector或者是List



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 12.]

 
lolhaha
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 13 ]

发信人: lolhaha (长期骑驴,一直找马), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 12:22:56 2014, 美东)

你可以连续调用
list.remove(cur)
相当于把list中cur,cur+1,cur+2..删除
然后list.insert(cur,**)
就是插在当前位置
【 在 jamespp (rainyday) 的大作中提到: 】
: 可是在c++中的vector或者是java中的List的iterator的时候,怎样能够删除又不引起
: invalid iterator或者是concurrent modification exception呢?
: 能给个程序吗?我看到的解答都是创建新的vector或者是List



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 142.]

 
jobhunter123
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 14 ]

发信人: jobhunter123 (jobhunting), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 12:43:37 2014, 美东)

排序然后binary search
--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 71.]

 
lolhaha
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 15 ]

发信人: lolhaha (长期骑驴,一直找马), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 12:49:37 2014, 美东)

结果不需要顺序的话
你为什么要排序
【 在 jobhunter123 (jobhunting) 的大作中提到: 】
: 排序然后binary search



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 142.]

 
jamespp
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 16 ]

发信人: jamespp (rainyday), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 13:09:03 2014, 美东)

这里的vector.erase非常耗时吧?
我改了之后没有能够在leetcode上通过测试
【 在 UMDTA (UMDTA) 的大作中提到: 】
: 这个怎么样?
: /*
:  merege interals
:  */
: void mergeIntervals(vector<Pair> &vp, Pair np){
:     int size = (int)vp.size();
:     if(size == 0) {
:         vp.push_back(np);
:         return;
:     }
: ...................



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
UMDTA
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 17 ]

发信人: UMDTA (UMDTA), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 13:14:41 2014, 美东)

为什么耗时?
你怎么该的?
【 在 jamespp (rainyday) 的大作中提到: 】
: 这里的vector.erase非常耗时吧?
: 我改了之后没有能够在leetcode上通过测试



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 12.]

 
jamespp
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 18 ]

发信人: jamespp (rainyday), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 13:19:21 2014, 美东)

vector<Interval> insert(vector<Interval> &intervals, Interval newInterval) {
    int size = (int) intervals.size();
    if (size == 0) {
        intervals.push_back(newInterval);
        return intervals;
    }

    for (vector<Interval>::iterator it = intervals.begin(); it != intervals.
end();) {
        if (newInterval.start > it->end || newInterval.end < it->start) {
            it++;
        } else if (newInterval.start > it->start && newInterval.end < it->
end) {
            return intervals;
        } else if (newInterval.start <= it->start && newInterval.end >= it->
end) {
            it = intervals.erase(it);
        } else {
            newInterval.start = newInterval.start < it->start ? newInterval.
start : it->start;
            newInterval.end = newInterval.end > it->end ? newInterval.end :
it->end;
            it = intervals.erase(it);
        }
    }
    intervals.push_back(newInterval);
    return intervals;
}
【 在 UMDTA (UMDTA) 的大作中提到: 】
: 为什么耗时?
: 你怎么该的?



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
jamespp
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 19 ]

发信人: jamespp (rainyday), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 13:20:27 2014, 美东)

能否给个代码?我还自认为比较熟java,但发现硬是没有搞出来

【 在 lolhaha (长期骑驴,一直找马) 的大作中提到: 】
: 你可以连续调用
: list.remove(cur)
: 相当于把list中cur,cur+1,cur+2..删除
: 然后list.insert(cur,**)
: 就是插在当前位置



--
※ 来源:·WWW 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 76.]

 
realshrek
进入未名形象秀
我的博客
[回复] [回信给作者] [本篇全文] [本讨论区] [修改] [删除] [转寄] [转贴] [收藏] [举报] [ 20 ]

发信人: realshrek (shrek), 信区: JobHunting
标  题: Re: f电面
发信站: BBS 未名空间站 (Fri Aug  1 13:31:23 2014, 美东)

不能先记下index,然后最后统一删除么?
啊,晕,这就相当于新建了List……
那从List<interval>的后面向前用index扫描呢?
碰到合并的就删除,这个没问题吧?

【 在 jamespp (rainyday) 的大作中提到: 】
: 可是在c++中的vector或者是java中的List的iterator的时候,怎样能够删除又不引起
: invalid iterator或者是concurrent modification exception呢?
: 能给个程序吗?我看到的解答都是创建新的vector或者是List



--

※ 修改:·realshrek 于 Aug  1 13:34:49 2014 修改本文·[FROM: 98.]
※ 来源:·BBS 未名空间站 网址:mitbbs.com 移动:在应用商店搜索未名空间·[FROM: 98.]

[首页] [上页][下页][末页] [分页:1 2 ]
[快速返回] [ 进入待字闺中讨论区] [返回顶部]
回复文章
标题:
内 容:

未名交友
将您的链接放在这儿

友情链接


 

Site Map - Contact Us - Terms and Conditions - Privacy Policy

版权所有,未名空间(mitbbs.com),since 1996