V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
fszaer
V2EX  ›  分享发现

leetcode 也是很会玩啦

  •  
  •   fszaer · 2015-06-13 17:36:57 +08:00 · 2512 次点击
    这是一个创建于 3211 天前的主题,其中的信息可能已经有所发展或是发生改变。

    https://leetcode.com/problems/invert-binary-tree/

    This problem was inspired by this original tweet by Max Howell:
    Google: 90% of our engineers use the software you wrote (Homebrew),but you can’t invert a binary tree on a whiteboard so fuck off.

    这题还是easy的哦WWWWW

    12 条回复    2015-06-15 11:50:21 +08:00
    101
        1
    101  
       2015-06-13 17:44:45 +08:00
    ryd994
        2
    ryd994  
       2015-06-14 09:50:46 +08:00 via Android
    目前看见最好的就是强制cast指针,除了可移植性可能不太好之外
    还有什么能比O(1)更快……
    kcworms
        3
    kcworms  
       2015-06-14 12:56:18 +08:00
    @ryd994 怎么做才能O(1)呢?难道你说的是保持二叉树本身不变,访问的时候翻转地访问左右子树?
    msg7086
        4
    msg7086  
       2015-06-15 00:32:20 +08:00
    @kcworms 相当于交换对象方法的函数地址。
    用ruby的话来说,就相当于
    alias :temp, :left
    alias :left, :right
    alias :right, :temp

    这样本来你访问n.left的时候,就变成调用Node::right()了。

    估计只对动态语言有效?
    ryd994
        5
    ryd994  
       2015-06-15 02:23:46 +08:00
    @msg7086 C有效啊
    只要编译器不要瞎重排struct里的内存分配就行
    msg7086
        6
    msg7086  
       2015-06-15 02:39:58 +08:00
    @ryd994 求个AC的代码观摩下~
    ryd994
        7
    ryd994  
       2015-06-15 02:45:23 +08:00   ❤️ 1
    @msg7086 /t/197730 48楼那个应该可以吧
    msg7086
        8
    msg7086  
       2015-06-15 03:23:05 +08:00   ❤️ 1
    @ryd994 我觉得这个应该AC不了吧。
    静态语言取数据是跟着地址走。动态语言才是当场根据方法名来求值的吧。
    ryd994
        9
    ryd994  
       2015-06-15 03:28:28 +08:00
    @msg7086 这个编译的时候就可以知道啊
    ryd994
        10
    ryd994  
       2015-06-15 03:32:28 +08:00
    @msg7086 只是编译器取指针时如何解释的区别
    原本left编译成left的地址,现在left编译为right的地址
    msg7086
        11
    msg7086  
       2015-06-15 03:35:41 +08:00   ❤️ 1
    @ryd994 但是对于online judge来说,判断答题是否正确的代码是不可能被你修改的吧。
    如果是Ruby的话强行Monkey Patch进Meta Class大概还有可能AC,C语言我觉得没戏。
    你可以试试?
    kcworms
        12
    kcworms  
       2015-06-15 11:50:21 +08:00
    @msg7086 #7里提到的方法和修改二叉树本身有区别。如果是aReverseNode->left->left->right这样访问没问题,但代码里有其他参数为NormalNode的函数就不好使了,需要全部改掉。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   965 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 28ms · UTC 21:16 · PVG 05:16 · LAX 14:16 · JFK 17:16
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.