📣 VIP通行证夏日特惠 限时立减$68
12
返回列表 发新帖
楼主: samson1215
跳转到指定楼层
上一主题 下一主题
收起左侧

🐶 VO 想不太出来的一道题 请教各位

🔗
daydream1 2021-10-13 09:59:27 | 只看该作者
全局:
The other way to look at this problem is to see it as a binary tree. The leaf node is a single restriction. Non-leaf nodes are operators such as AND/OR. However, I have no idea on how to solve it converting to binary tree.
回复

使用道具 举报

地里匿名用户
🔗
匿名用户-SSWHB  2021-10-15 06:09:15
可以将expression分解一下再用recursion得到答案吗~分解每个expression直到成为Restriction,然后求一下是否overlap~

本帖子中包含更多资源

您需要 登录 才可以下载或查看附件。没有帐号?注册账号

x
回复

使用道具 举报

🔗
pureklkl 2021-10-17 04:21:08 | 只看该作者
全局:
本帖最后由 pureklkl 于 2021-10-17 04:22 编辑

抛砖引玉:
首先求exp1,exp2有无重叠的部分其实就是求exp1 && exp2,把两个表达式放一起中间直接加个与,然后用开始evaluate expression tree
表达式的结果用map表示,key是变量名,value是list of interval。interval本身表示与,多个interval表示或,比如
(A>3)&&(A<6)表示成(3,6),
(A>3)||(A<6)表示成 [3,inf],[-inf,6]
然后计算与表达式就是经典的算interval intersect,或表达式就直接加进list,可选merge interval 化简。算与的时候检查一下是否重叠部分为空即可。
回复

使用道具 举报

🔗
zlqiszlq 2021-10-17 05:15:13 | 只看该作者
全局:
把表达式变化为expA and exp
回复

使用道具 举报

🔗
 楼主| samson1215 2021-10-17 14:15:59 | 只看该作者
全局:
pureklkl 发表于 2021-10-16 13:21
抛砖引玉:
首先求exp1,exp2有无重叠的部分其实就是求exp1 && exp2,把两个表达式放一起中间直接加个与, ...

思路很棒!感觉很接近了。请问如果是这样的表达式:
  1. (A > 1 && B < 1) OR (A < 1 && B > 1)
复制代码
那么map的内容长什么样呢?
回复

使用道具 举报

🔗
pureklkl 2021-10-21 04:01:14 | 只看该作者
全局:
samson1215 发表于 2021-10-17 14:15
思路很棒!感觉很接近了。请问如果是这样的表达式:那么map的内容长什么样呢?

哦,我没考虑变量之间的与或表达,只想了单变量区间的。
多变量因为相当于考虑多维问题,我考虑过kd tree但是那个只能读,不能增删改
我目前的思路:假设每个变量是一个维度,然后树的每层节点代表一维,指针代表对应的区间

你这个式子表示成

A:         [(1,inf), (inf,1)]
              |            |
B:       [(inf,1)]    [(1,inf)]
注意第一层的A是一个节点,两个区间分别对应B的两个节点。也就是A每多一个区间,就要多加一个B的节点,来表示A对应区间内B的有效范围。如过有C的话,B也同理。
两个树合并的时候,如果是或,只要把树里层数最高的节点接上就行。与会很复杂,要逐层merge。
这个复杂度会很高,因为最后一层的节点数是之前所有有效区间的累乘。

我感觉应该有专门的数据结构表示这种东西,我是不太清楚,有知道的求告知哈。

回复

使用道具 举报

🔗
yezhengli_mr9 2021-11-23 12:36:05 | 只看该作者
全局:
expr1 (expr2)应该默认化到比较简单了吧?比方不会出现
expr1: (foo = 'A') AND (foo != 'A')

类似情形
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号
隐私提醒:
  • ☑ 禁止发布广告,拉群,贴个人联系方式:找人请去🔗同学同事飞友,拉群请去🔗拉群结伴,广告请去🔗跳蚤市场,和 🔗租房广告|找室友
  • ☑ 论坛内容在发帖 30 分钟内可以编辑,过后则不能删帖。为防止被骚扰甚至人肉,不要公开留微信等联系方式,如有需求请以论坛私信方式发送。
  • ☑ 干货版块可免费使用 🔗超级匿名:面经(美国面经、中国面经、数科面经、PM面经),抖包袱(美国、中国)和录取汇报、定位选校版
  • ☑ 查阅全站 🔗各种匿名方法

本版积分规则

>
快速回复 返回顶部 返回列表