技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> MySQL --> 《百姓网公开笔试题:查询条件的子集判断》的一份 PHP 答卷

《百姓网公开笔试题:查询条件的子集判断》的一份 PHP 答卷

浏览:2729次  出处信息

    原题见 百姓网公开笔试题:查询条件的子集判断

    我的答卷在 http://soulogic.com/subset_test/subset_test.tar.gz

    演示地址为 http://soulogic.com/subset_test/


    碰到这道题时才意识到自己的见识浅薄,非等到这种题出来才能明白,高等数学对于程序员而言是多么重要。其中最难最关键的部分是在留言里看到了 qmigh 的解释才搞定的。

    这道题分三部分:把查询语句转成数组结构,然后把层级混乱的条件最终分解成 以 OR 关联的 AND 合集(也就是 qmigh 所解释的),以及按规则来读取并判断两个数组。在我的代码里,Class TreeStore 负责前两步,Class SetCheck 负责后一步。

    由于我完全说不出任何术语,只能把数组的转换过程列一下了。

    原始语句

    a = 1 AND (b = 1 OR (c = 1 AND (e > 1 OR f = 1)))

    第一步,循环用正则,从最里面的括号开始,分解出每一级。这样每一级里面都没括号了

    Array

    (

        [1] => e > 1 OR f = 1

        [2] => c = 1 AND _1

        [3] => b = 1 OR _2

        [4] => a = 1 AND _3

    )

    按照 AND OR 的优先级进一步分解

    Array

    (

        [AND] => Array

            (

                [0] => a = 1

                [1] => Array

                    (

                        [OR] => Array

                            (

                                [0] => b = 1

                                [1] => Array

                                    (

                                        [AND] => Array

                                            (

                                                [0] => c = 1

                                                [1] => Array

                                                    (

                                                        [OR] => Array

                                                            (

                                                                [0] => e > 1

                                                                [1] => f = 1

                                                            )

                                                    )

                                            )

                                    )

                            )

                    )

            )

    )

    将上述数组最终分解成 OR 下的一堆 AND

    Array

    (

        [OR] => Array

            (

                [0] => Array

                    (

                        [AND] => Array

                            (

                                [0] => a = 1

                                [1] => b = 1

                            )

                    )

                [1] => Array

                    (

                        [AND] => Array

                            (

                                [0] => a = 1

                                [1] => c = 1

                                [2] => e > 1

                            )

                    )

                [2] => Array

                    (

                        [AND] => Array

                            (

                                [0] => a = 1

                                [1] => c = 1

                                [2] => f = 1

                            )

                    )

            )

    )

    其实就是按 qmigh 说的,做一下转换,把最开始的表达式转换为

    (a = 1 AND b = 1) OR (a = 1 AND c = 1 AND e > 1) OR (a = 1 AND c = 1 AND f = 1)

    如果只有一个表达式,可以理解为只有一个元素的 AND

    如果

    (a > 3) AND (b < 4)

    可以用数组表示为

    array(

        [0] => a > 3

        [1] => b < 4

    )

    那么

    a > 3

    可以用数组表示为

    array(

        [0] => a > 3

    )

    OR 也同理

    用来判断时的数组样子,也就是 Class TreeStore 的最终输出

    Array

    (

        [0] => Array

            (

                [a] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [b] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

            )

        [1] => Array

            (

                [a] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [c] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [e] => Array

                    (

                        [>] => 1

                    )

            )

        [2] => Array

            (

                [a] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [c] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

                [f] => Array

                    (

                        [=] => Array

                            (

                                [1] => 1

                            )

                    )

            )

    )

    至于判断,应该不算难,按照上面的数组挨个字段判断就可以了。以及判断父集合是否有子集合没有的字段,如果有,那肯定不是子集关系了。

    写完之后一直没把握到底做的对不对,要是有类似 ACID 2 或者 Man or boy test 那样的东西就好了。如果能有人告诉我有什么复杂条件是我的代码判断不了的,实在感激不尽(当然,用 10MB 长的条件语句搞溢出不算……)

    看了看 其他人的答案,“从离散数学到编译原理”,这标题总结得不错,核心也就是这两个问题吧。我用正则来把“编译”那部分绕过去了,但从执行效率上讲是很蠢的。

    看来大家都知道画蛇添足的故事,所以都只做了满足要求(“为了简单起见,只需要实现最简单的AND, OR逻辑操作,大于,等于,小于三种比较操作就好”)的最小实现。

    如果能有 PHP 同好的题解能相互学习学习那是最好了,其他语言的看不懂 -_-

    原来还自诩为程序员,被这道题臊的不行,我现在的定义是,没法独自实现一个 C Compiler 的人充其量也不过是 coding fans。

    给自己定下了三年目标:学离散数学、学微积分、学《SICP》

    

建议继续学习:

  1. 腾讯-1亿个数据取前1万大的整数-题解答    (阅读:9026)
  2. 谷歌(Google)2011年校园招聘笔试题    (阅读:8890)
  3. 你是那10%可以实现二分查找算法的程序员吗?    (阅读:6494)
  4. 15道使用频率极高的基础算法题    (阅读:5580)
  5. 新浪微博笔试题:找出共有2个以上标签的用户对    (阅读:4952)
  6. 有道实习生笔试总结    (阅读:4528)
  7. 2014网易前端开发笔试题笔记    (阅读:3920)
  8. 百姓网公开笔试题:查询条件的子集判断    (阅读:2566)
  9. mysql数据库查询优化    (阅读:2535)
  10. 百姓网公开笔试题结果展示    (阅读:2303)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1