首页   注册   登录
 ofooo 最近的时间轴更新

ofooo

V2EX 第 295755 号会员,加入于 2018-03-02 00:16:50 +08:00
今日活跃度排名 11432
中年程序员, 是否需要一套正装?
问与答  •  ofooo  •  15 天前  •  最后回复来自 Infinite2K
12
如何才能做到沉迷编程?
程序员  •  ofooo  •  44 天前  •  最后回复来自 ericgui
65
ofooo 最近回复了
点赞, 周一试用一下
如果有这样的方案,商家会都做成这样,无良商家也会
,然后消费者发现这个方案不值得信赖

over
22 天前
回复了 tenstone 创建的主题 程序员 你通常使用什么写作工具?
typora 加 hexo 部署
34 天前
回复了 328174749 创建的主题 程序员 工作三年,有点迷茫
推荐找一个算法的视频课看了,把 leetcode 刷一两百道,把复杂度什么的搞清楚

因为应用方面你没有偏好,所以推荐先练基本功

等基本功好了,再应用方向上挑一个,例如前端,后端,大数据,人工智能等等,然后面向方向深入
@wutiantong 这个图的解法挺巧妙的, 这样的算法复杂度大概是什么量级的呢?
```python3
class Test:
def get_groups(self, items, reject_pairs):
"""
生成由 items 组成的 N 个组, 保证每个组里的元素不互相排斥, 且 N 最小
:param items: [item1, item2, item3, ...] 要成组的全部元素
:param reject_pairs: {(item1, item3), (item2, item9) } 二元组集合, 每个二元组表示一个排斥条件
:return: [ [item1], [item2, item3], [...] ] 二维数组
"""
self.sub_groups = {} # {排序的 item 元组: 最佳成组二维数组} 保存临时结果, 减小计算量
groups = self._get_groups(items, reject_pairs)

return groups

def _get_groups(self, items, reject_pairs):
if len(items) == 1:
return [[items[0]]]
sort_types = tuple(sorted(items))
if sort_types in self.sub_groups:
return self.sub_groups[sort_types]
best_groups = None
for t1 in items:
now_group = [t1] # 可以和 t1 成组的元素组成的组
others = [] # 不能和 t1 成组的元素组成的组
for t2 in items:
if t1 == t2:
continue
for tt in now_group:
if self.is_cross(tt, t2, reject_pairs):
others.append(t2)
break
else:
now_group.append(t2)
if len(others) == 0:
best_groups = [now_group]
self.sub_groups[sort_types] = best_groups
return best_groups
else:
groups = self._get_groups(others, reject_pairs) + [now_group]
if best_groups is None or len(best_groups) > len(groups):
best_groups = groups
self.sub_groups[sort_types] = best_groups
return best_groups

def is_cross(self, t1, t2, cross_pairs):
if (t1, t2) in cross_pairs:
return True
if (t2, t1) in cross_pairs:
return True
return False

```
我上面说的计算过程的代码...如果有问题大家多指出, 谢谢
@wanwenx 我要写个小工具其中需要解决这个问题, 没想到真的是个算法题啊.....

我的解法是
先循环每个元素 a, 把全部元素分成 2 组, A 组=包含元素 a 的最多的元素, B 组是其他元素
然后其他元素递归调用这个函数, 这样就获得的以 a 元素为核心的组, 找到数量最少的成组, 返回

然后加了一个临时变量, 保存每一组计算过的元素和最佳成组, 减少计算量

不知道这样算不算解出来了.....
45 天前
回复了 ofooo 创建的主题 程序员 如何才能做到沉迷编程?
今天已经编程 3 个小时, 刚才又走神看了会龙空.....
关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   967 人在线   最高记录 5043   ·     Select Language
创意工作者们的社区
World is powered by solitude
VERSION: 3.9.8.3 · 15ms · UTC 22:24 · PVG 06:24 · LAX 14:24 · JFK 17:24
♥ Do have faith in what you're doing.