V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
推荐学习书目
Learn Python the Hard Way
Python Sites
PyPI - Python Package Index
http://diveintopython.org/toc/index.html
Pocoo
值得关注的项目
PyPy
Celery
Jinja2
Read the Docs
gevent
pyenv
virtualenv
Stackless Python
Beautiful Soup
结巴中文分词
Green Unicorn
Sentry
Shovel
Pyflakes
pytest
Python 编程
pep8 Checker
Styles
PEP 8
Google Python Style Guide
Code Style from The Hitchhiker's Guide
woostundy
V2EX  ›  Python

leetcode Python 解释器的问题

  •  
  •   woostundy · 2016-11-22 20:01:03 +08:00 · 2637 次点击
    这是一个创建于 2925 天前的主题,其中的信息可能已经有所发展或是发生改变。

    https://leetcode.com/problems/guess-number-higher-or-lower/ 这道题我以为很简单,用二分法写了一下,但执行时候报超时(而且为了增加效率我把除法改成了位运算),我自己拿到 pycharm 里试了一下没问题。不知道是哪段代码让 leetcode 不能通过的。

        def guessNumber(self, n):
            """
            :type n: int
            :rtype: int
            """
            if n < 2:
                return n
            deep = 1
            x = n >> deep
            while 1:
                result = guess(x)
                deep += 1
                if result < 0:
                    x = x + (n >> deep)
                elif result > 0:
                    x = x - (n >> deep)
                else: 
                    return x
    
    17 条回复    2016-12-22 10:29:30 +08:00
    holyghost
        1
    holyghost  
       2016-11-22 20:15:28 +08:00 via iPhone
    有一个 case 死循环了吧
    yangff
        2
    yangff  
       2016-11-22 20:17:26 +08:00
    -1 : My number is lower
    1 : My number is higher
    0 : Congrats! You got it!
    woostundy
        3
    woostundy  
    OP
       2016-11-22 20:20:28 +08:00
    ```
    def guessNumber(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n < 2:
    return n
    low = 1
    high = n
    while 1:
    x = (low + high) / 2
    result = guess(x)
    if result < 0:
    low = x - 1
    elif result > 0:
    high = x + 1
    else:
    return x
    ```

    换了一种方式,然并卵啊,依然不好使。
    问题是这俩写法我在 pycharm 里都是正常的
    finab
        4
    finab  
       2016-11-22 20:21:12 +08:00 via iPhone
    还是 java 写省事,我有个算法用 Swift 写的,死活过不去,报超时。后来用 java 写一遍,算法都一样,通过了。
    Mistwave
        5
    Mistwave  
       2016-11-22 20:28:48 +08:00 via iPhone
    guess(x) 是什么?
    woostundy
        6
    woostundy  
    OP
       2016-11-22 20:34:16 +08:00
    @Mistwave 预定义的一个函数,返回你猜的数字:
    -1 : My number is lower
    1 : My number is higher
    0 : Congrats! You got it!
    woostundy
        7
    woostundy  
    OP
       2016-11-22 20:36:59 +08:00
    @holyghost 应该是,但我看不出来停留在哪了。 pycharm 里执行正常。
    holyghost
        8
    holyghost  
       2016-11-22 20:38:16 +08:00 via iPhone
    @woostundy 结果页有 case 的,点进去看一下就知道了
    woostundy
        9
    woostundy  
    OP
       2016-11-22 20:41:28 +08:00
    @holyghost 非常简单的 case ,就报超时了。。而在 pycharm 里调试,发现只循环了 4 次
    lonelinsky
        10
    lonelinsky  
       2016-11-22 21:51:52 +08:00
    二分逻辑写错了,注意 guess 的定义,简单改了下

    ```
    class Solution(object):
    def guessNumber(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n < 2:
    return n
    low = 1
    high = n
    while 1:
    x = (low + high) // 2
    result = guess(x)
    if result < 0:
    high = x - 1
    elif result > 0:
    low = x + 1
    else:
    return x
    ```
    woostundy
        11
    woostundy  
    OP
       2016-11-22 22:00:25 +08:00
    @lonelinsky ...多谢,我把 guess 的定义看反了
    woostundy
        12
    woostundy  
    OP
       2016-11-22 22:01:42 +08:00
    @holyghost
    @yangff
    已解决,我弱智了,看错了 guess 的返回结果定义,不是我猜的数字小了返回-1 ,而是答案小了返回-1
    woostundy
        13
    woostundy  
    OP
       2016-11-22 22:07:37 +08:00
    第一种写法最终的答案应该是这样

    ```
    def guessNumber(self, n):
    """
    :type n: int
    :rtype: int
    """
    if n < 2:
    return n
    deep = 1
    x = n >> deep
    while 1:
    result = guess(x)
    deep += 1
    if result > 0:
    x = x + (n >> deep) + 1
    elif result < 0:
    x = x - (n >> deep) - 1
    else:
    return x
    ```
    raytlty
        14
    raytlty  
       2016-11-23 22:39:19 +08:00
    ```
    lhs, rhs = 1, n
    while lhs < rhs:
    mid = (lhs + rhs) >> 1
    lhs, rhs = [(mid, mid), (mid+1, rhs), (lhs, mid-1)][guess(mid)]
    ```
    woostundy
        15
    woostundy  
    OP
       2016-11-24 10:26:42 +08:00
    @raytlty 赞,写的更漂亮了
    jedihy
        16
    jedihy  
       2016-12-22 01:02:31 +08:00
    python 位运算并不比除法快。
    woostundy
        17
    woostundy  
    OP
       2016-12-22 10:29:30 +08:00
    @jedihy 怎么讲?
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   1055 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 32ms · UTC 20:35 · PVG 04:35 · LAX 12:35 · JFK 15:35
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.