leetcode Python 解释器的问题

2016-11-22 20:01:03 +08:00
 woostundy

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
2623 次点击
所在节点    Python
17 条回复
holyghost
2016-11-22 20:15:28 +08:00
有一个 case 死循环了吧
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
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
2016-11-22 20:21:12 +08:00
还是 java 写省事,我有个算法用 Swift 写的,死活过不去,报超时。后来用 java 写一遍,算法都一样,通过了。
Mistwave
2016-11-22 20:28:48 +08:00
guess(x) 是什么?
woostundy
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
2016-11-22 20:36:59 +08:00
@holyghost 应该是,但我看不出来停留在哪了。 pycharm 里执行正常。
holyghost
2016-11-22 20:38:16 +08:00
@woostundy 结果页有 case 的,点进去看一下就知道了
woostundy
2016-11-22 20:41:28 +08:00
@holyghost 非常简单的 case ,就报超时了。。而在 pycharm 里调试,发现只循环了 4 次
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
2016-11-22 22:00:25 +08:00
@lonelinsky ...多谢,我把 guess 的定义看反了
woostundy
2016-11-22 22:01:42 +08:00
@holyghost
@yangff
已解决,我弱智了,看错了 guess 的返回结果定义,不是我猜的数字小了返回-1 ,而是答案小了返回-1
woostundy
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
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
2016-11-24 10:26:42 +08:00
@raytlty 赞,写的更漂亮了
jedihy
2016-12-22 01:02:31 +08:00
python 位运算并不比除法快。
woostundy
2016-12-22 10:29:30 +08:00
@jedihy 怎么讲?

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/322469

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX