l**h
发帖数: 893 | 1 看之前的面试题:
3 sorted linked lists, find the min(|x-y|, |x-z|, |y-z|) |
s*****m
发帖数: 8094 | 2 这么出题会让人抓狂的。
【在 l**h 的大作中提到】
: 看之前的面试题:
: 3 sorted linked lists, find the min(|x-y|, |x-z|, |y-z|)
|
p*****2
发帖数: 21240 | 3 这题去年讨论过。当时我太弱，没有参与。印象中是DP搞的。这次要参与了。 |
l**h
发帖数: 893 | 4 感觉没有思路啊
【在 p*****2 的大作中提到】
: 这题去年讨论过。当时我太弱，没有参与。印象中是DP搞的。这次要参与了。
|
A**u
发帖数: 2458 | |
c********t
发帖数: 5706 | 6 呵呵，这道题记忆犹新。不给提示了。加油！
【在 l**h 的大作中提到】
: 感觉没有思路啊
|
h***i
发帖数: 1970 | 7 小的往前移，可以么？
【在 c********t 的大作中提到】
: 呵呵，这道题记忆犹新。不给提示了。加油！
|
p****e
发帖数: 3548 | 8 没测试过，任意数量的list
bool listcompr(ListNode * a, ListNode * b){
if(a == NULL) return true;
if(b == NULL) return false;
return a->valval;
}
int MinDiff(vector &a){
sort(a.begin(), a.end(), listcompr);
int s = 0;
while(s
if(s >= a.size() - 1) return -1;
int mindiff = INT_MAX;
while(mindiff > 0){
if(a[s+1]->val - a[s]->val < mindiff)
mindiff = a[s+1]->val - a[s]->val;
a[s] = a[s]->next;
if(a[s] == NULL){
++s;
if(s == a.size() - 1)
break;
continue;
}
for(int i=s; i
if(a[i]->val>a[i+1]->val)
swap(a[i], a[i+1]);
else
break;
}
return mindiff;
} |
c********t
发帖数: 5706 | 9 数组不一样长怎么定义min dist?
【在 p****e 的大作中提到】
: 没测试过，任意数量的list
: bool listcompr(ListNode * a, ListNode * b){
: if(a == NULL) return true;
: if(b == NULL) return false;
: return a->valval;
: }
: int MinDiff(vector &a){
: sort(a.begin(), a.end(), listcompr);
: int s = 0;
: while(s
|
b*****a
发帖数: 7 | |
|
|
p****e
发帖数: 3548 | 11 vector只是存下x,y,z的head，跟list的长度无关
【在 c********t 的大作中提到】
: 数组不一样长怎么定义min dist?
|
j*****y
发帖数: 1071 | 12 二爷能详细的翻译一下题目的意思吗？ thanks.
【在 p*****2 的大作中提到】
: 这题去年讨论过。当时我太弱，没有参与。印象中是DP搞的。这次要参与了。
|
p*****2
发帖数: 21240 | 13
就是三个链表各取一个，使得满足那个条件最小
【在 j*****y 的大作中提到】
: 二爷能详细的翻译一下题目的意思吗？ thanks.
|
j*****y
发帖数: 1071 | 14 是求 min(min(|x-y|, |y-z|, |x-z|)) 吗
【在 p*****2 的大作中提到】
:
: 就是三个链表各取一个，使得满足那个条件最小
|
p*****2
发帖数: 21240 | 15
你一说我才注意，我记得以前是求min(|x-y|+|y-z|+|z-x|)呀。
【在 j*****y 的大作中提到】
: 是求 min(min(|x-y|, |y-z|, |x-z|)) 吗
|
j*****y
发帖数: 1071 | 16 要是你这样的话也算清楚了。 thanks.
【在 p*****2 的大作中提到】
:
: 你一说我才注意，我记得以前是求min(|x-y|+|y-z|+|z-x|)呀。
|
p****e
发帖数: 3548 | 17 这样的话貌似解法也是差不多
【在 p*****2 的大作中提到】
:
: 你一说我才注意，我记得以前是求min(|x-y|+|y-z|+|z-x|)呀。
|
G****A
发帖数: 4160 | 18 是这个意思么?
Objective:
Minimize: min(|x-y|, |x-z|, |y-z|)
Constraints:
x is in List1
y is in List2
z is in List3
【在 p*****2 的大作中提到】
:
: 你一说我才注意，我记得以前是求min(|x-y|+|y-z|+|z-x|)呀。
|
h***i
发帖数: 1970 | 19 解法是什么，没仔细读code，直觉上感觉小的那个list往前移就行。
【在 p****e 的大作中提到】
: 这样的话貌似解法也是差不多
|
p****e
发帖数: 3548 | 20 就是那样
【在 h***i 的大作中提到】
: 解法是什么，没仔细读code，直觉上感觉小的那个list往前移就行。
|
|
|
j*****y
发帖数: 1071 | 21 应该是 max(min(|x-y|, |x-z|, |y-z|)) 才有点意思
如果是 min(min) 的话就太简单了， 只需两两比较每两个list就行了
【在 G****A 的大作中提到】
: 是这个意思么?
: Objective:
: Minimize: min(|x-y|, |x-z|, |y-z|)
: Constraints:
: x is in List1
: y is in List2
: z is in List3
|
l***i
发帖数: 1309 | 22 Imagine if you have only one list, then the pair achieving min has to be
adjacent in the sorted list.
Now you have 3 sorted list, one way to reduce it would be merge the 3 lists
and then compare adjacent elements (you need to remember from which list the
element is). Clearly this works. On a second thought you can do an implicit
merge, which is the way suggested in an earlier post, by keeping throwing
away the min in the three lists. |
s*********l
发帖数: 103 | 23
记得原题是求min(max(|x-y|, |x-z|, |y-z|))
http://spellscroll.com/spellscrolls/question/MK1I7QsMhb4/
每次替换triplet最小的那个
Python code:
http://git.io/XFcLoQ
【在 l**h 的大作中提到】
: 看之前的面试题:
: 3 sorted linked lists, find the min(|x-y|, |x-z|, |y-z|)
|
