s*******m
发帖数: 228 | 1 makefriend，
n个人，每个人都要在其他（n-1)个人中交f个不同的朋友，问所有人都能交且只能交f
个朋友吗（少一个，多一个，都不行）？
比如，makeFriends（n,f）
makeFriends(2,1)=true;
makeFriends(3,1)=false;
makeFriends(3,2)=true;
makeFriends(4,1)=true;
makeFriends(4,2)=true;
因为1,2；1,3；2,4；3,4。 这样，每个人就都是2个朋友了
| g****o
发帖数: 547 | | s*******m
发帖数: 228 | 3 不是吧。
每个人只能且必须交f个朋友。
比如，makeFriends（n,f）
makeFriends(2,1)=true;
makeFriends(3,1)=false;
makeFriends(3,2)=true;
makeFriends(4,1)=true;
makeFriends(4,2)=true;
因为1,2；1,3；2,4；3,4。 这样，每个人就都是2个朋友了
【在 g****o 的大作中提到】
: 啥意思？ n*f必须偶数？
| g****o
发帖数: 547 | 4 我觉得n*f是偶数，并且f
否则就是false啊
有反例么？
【在 s*******m 的大作中提到】
: 不是吧。
: 每个人只能且必须交f个朋友。
: 比如，makeFriends（n,f）
: makeFriends(2,1)=true;
: makeFriends(3,1)=false;
: makeFriends(3,2)=true;
: makeFriends(4,1)=true;
: makeFriends(4,2)=true;
: 因为1,2；1,3；2,4；3,4。 这样，每个人就都是2个朋友了
:
| n******n
发帖数: 12088 | 5 题意不清。交朋友有排斥关系吗？
f
【在 s*******m 的大作中提到】
: makefriend，
: n个人，每个人都要在其他（n-1)个人中交f个不同的朋友，问所有人都能交且只能交f
: 个朋友吗（少一个，多一个，都不行）？
: 比如，makeFriends（n,f）
: makeFriends(2,1)=true;
: makeFriends(3,1)=false;
: makeFriends(3,2)=true;
: makeFriends(4,1)=true;
: makeFriends(4,2)=true;
: 因为1,2；1,3；2,4；3,4。 这样，每个人就都是2个朋友了
| s*******m
发帖数: 228 | 6 举不出反例。
但肯定不能这么做吧，这是一个小时的面试呢。。。
【在 g****o 的大作中提到】
: 我觉得n*f是偶数，并且f: 否则就是false啊
: 有反例么？
| s*******m
发帖数: 228 | 7 什么是排斥关系。
【在 n******n 的大作中提到】
: 题意不清。交朋友有排斥关系吗？
:
: f
| Y**G
发帖数: 1089 | 8 如果f是偶数，那就比较容易。把所有的人排成一个圆圈，每个人朋友就是他左边的f/2
个人，右边的f/2个人。
如果f是奇数，则按照上面的方法，可以得到每个人有f-1个朋友的解。然后假设n是偶
数，把所有的人分成男女，男女间隔的排成一个圆圈，按照f-1的思路先每个人有f-1个
朋友。然后每个人必须在不认识的人中找一个异性朋友，问题就解了。
如果f和n都是奇数，则无解。应为n*f/2必须是整数。因为总共的朋友有n*f/2对。
f
【在 s*******m 的大作中提到】
: makefriend，
: n个人，每个人都要在其他（n-1)个人中交f个不同的朋友，问所有人都能交且只能交f
: 个朋友吗（少一个，多一个，都不行）？
: 比如，makeFriends（n,f）
: makeFriends(2,1)=true;
: makeFriends(3,1)=false;
: makeFriends(3,2)=true;
: makeFriends(4,1)=true;
: makeFriends(4,2)=true;
: 因为1,2；1,3；2,4；3,4。 这样，每个人就都是2个朋友了
| k****r
发帖数: 807 | 9 the total degrees of all vertexes in undirected graph should be even number,
so f*n is even is a necessary condition. | s*******m
发帖数: 228 | 10 fn是偶数确实个必要条件，
如果follow up是请输出一个解，应该用什么算法呢
number,
【在 k****r 的大作中提到】
: the total degrees of all vertexes in undirected graph should be even number,
: so f*n is even is a necessary condition.
| | | n******n
发帖数: 12088 | 11 七楼不是给了算法？
【在 s*******m 的大作中提到】
: fn是偶数确实个必要条件，
: 如果follow up是请输出一个解，应该用什么算法呢
:
: number,
| s*******m
发帖数: 228 | 12 没有啊。
下午用bfs试了试
没做出来。
我想输出一个解。
【在 n******n 的大作中提到】
: 七楼不是给了算法？
| w*****d
发帖数: 105 | 13 只要f
证明：
把每个人看成顶点，好友关系看成边，那么题目要求每个顶点连f条边，那么总共的边
数为：
E = n * f / 2
显然E要是一个整数才行，即nf是偶数。
生成一个例子的算法，可以用greedy：遍历所有顶点，只要边数没达到f，就增加边，
另一头连后面没达到要求的顶点。naive实现为O(f*n^2)复杂度，个人认为可以优化的O
(f*n)。 | s*******m
发帖数: 228 | 14 关于，生成一个例子的算法
比如1,2,3,4四个人， f=2
用greedy的话，找不到解:
第一步 1和2，1和3
第二部 2和3
然后就结束了，4没有朋友。
但其实是有解的，
1和2,1和3,2和4,3和4；
的O
【在 w*****d 的大作中提到】
: 只要f: 证明：
: 把每个人看成顶点，好友关系看成边，那么题目要求每个顶点连f条边，那么总共的边
: 数为：
: E = n * f / 2
: 显然E要是一个整数才行，即nf是偶数。
: 生成一个例子的算法，可以用greedy：遍历所有顶点，只要边数没达到f，就增加边，
: 另一头连后面没达到要求的顶点。naive实现为O(f*n^2)复杂度，个人认为可以优化的O
: (f*n)。
| g*********r
发帖数: 4 | 15 如果要找解法的话可不可以这样：
判断 nf 是不是偶数
base cases:（1） 每人只有一个朋友， 两两配对
（2）每人有两个朋友，围成一个圈
如果>2个朋友，
以base（2）为起始状态，选择一个node为起点，第一次iteration跳过一个邻居连接两
个node，直到不能再添加edge（没有一个node有超过3个edge）
第二次iteration 跳过两个邻居
。。。
直到每个node有f个outgoing edge | s*******m
发帖数: 228 | 16 试了下您的做法，比如n=8, f=4.
没做出来。
第二次iteration， 还剩编号7,8 两个节点，没法达到4个朋友。
贴了一张图。
【在 g*********r 的大作中提到】
: 如果要找解法的话可不可以这样：
: 判断 nf 是不是偶数
: base cases:（1） 每人只有一个朋友， 两两配对
: （2）每人有两个朋友，围成一个圈
: 如果>2个朋友，
: 以base（2）为起始状态，选择一个node为起点，第一次iteration跳过一个邻居连接两
: 个node，直到不能再添加edge（没有一个node有超过3个edge）
: 第二次iteration 跳过两个邻居
: 。。。
: 直到每个node有f个outgoing edge
| a*******o
发帖数: 15 | 17 9楼正解啊，因为有联通图的degree是偶数啊，也就是X=N*F, X为偶数就可以啊~~突然
发现最近上上课还是有收获的啊 | s*******m
发帖数: 228 | 18 现在问题是如何找到一个解。
就是如何构造一个k-regular graph
【在 a*******o 的大作中提到】
: 9楼正解啊，因为有联通图的degree是偶数啊，也就是X=N*F, X为偶数就可以啊~~突然
: 发现最近上上课还是有收获的啊
| h*****y
发帖数: 298 | 19 数学题吧, n 个节点, 每个节点 n-1个neighbor恒成立。然后剪连接, 直到受影响的节
点覆盖一遍全部。
n为奇数的时候每次减掉两根连接, 因为剪掉一根的话会影响两个节点的度, n奇数不满
足, 减两根覆盖 2* n, 满足。
n为偶数每两个节点间减掉一根, 恒满足。
所以 if n is odd f(n, n + 1 - 2k) = true
always true if n is even.
不知道对不对 | s*****y
发帖数: 14 | |
|
