问答

当前位置
  • 首页
  • 问答
  • 关于Lintcode 570. Find the Missing Number II

关于Lintcode 570. Find the Missing Number II

  • Ta: Stella助教

老师好!关于lintcode 570. Find the Missing Number II这道题。我有如下三个python2的答案,第一个可以过但是第二、三个均报错(if str[0] != '0' and int(str[:i + 1]) in remaining:
IndexError: string index out of range)。version1和version2两者的区别只在dfs里面第一行:version2 加了len(remaining) == 1这个条件。

请教老师是什么问题呢???感谢!

version 1:

    def findMissing2(self, n, str):
    # write your code here
    remaining = {i for i in range(1, n + 1)}
    res = []
    self.dfs(n, str, remaining, res)
    return res[0][0]


def dfs(self, n, str, remaining, res):
    if len(str) == 0:
        res.append(list(remaining))
        return

    for i in range(2):
        if str[0] != '0' and int(str[:i + 1]) in remaining:
            remaining.remove(int(str[:i + 1]))
            self.dfs(n, str[i + 1:], remaining, res)
            remaining.add(int(str[:i + 1]))

version 2:

    def findMissing2(self, n, str):
    # write your code here
    remaining = {i for i in range(1, n + 1)}
    res = []
    self.dfs(n, str, remaining, res)
    return res[0][0]


def dfs(self, n, str, remaining, res):
    if len(str) == 0 and len(remaining) == 1:
        res.append(list(remaining))
        return

    for i in range(2):
        if str[0] != '0' and int(str[:i + 1]) in remaining:
            remaining.remove(int(str[:i + 1]))
            self.dfs(n, str[i + 1:], remaining, res)
            remaining.add(int(str[:i + 1]))

version 3:

def findMissing2(self, n, str):
    # write your code here
    remaining = {i for i in range(1, n + 1)}
    self.res = 0
    self.dfs(n, str, remaining)
    return self.res


def dfs(self, n, str, remaining):
    if len(str) == 0 and len(remaining) == 1:
        self.res = list(remaining)[0]
        return

    for i in range(2):
        if str[0] != '0' and int(str[:i + 1]) in remaining:
            remaining.remove(int(str[:i + 1]))
            self.dfs(n, str[i + 1:], remaining)
            remaining.add(int(str[:i + 1]))

3 个回复

2019-09-17 carry

因为你加了这个len(remaining) == 1这个条件。那这个的长度就是1了呀,然后你下面的循环是range(2),它循环就会越界,因为str的长度没有那么长


2019-09-17 Wei

谢谢助教老师的回答!不过remaining在这里是我定义的一个set,表示还剩下哪个数字没有出现过,所以最后就是应该剩下一个作为答案的?它的长度和str剩下的字符串长度是没有关系的吧?可以请老师再解释一下吗?

感谢!


2019-09-18 carry

在你第二份代码,你str每次进入那个循环dfs的时候,要先判断str是否已经为空串了,要是已经空串了,它就不能进入dfs下一层递归,那个int(str[:i + 1])就会越界了。

class Solution:
    """
    @param n: An integer
    @param str: a string with number from 1-n in random order and miss one number
    @return: An integer
    """
    def findMissing2(self, n, str):
        # write your code here
        remaining = {i for i in range(1, n + 1)}
        res = []
        self.dfs(n, str, remaining, res)
        return res[0][0]

    def dfs(self, n, str, remaining, res):
        if len(str) == 0 and len(remaining) == 1:
            res.append(list(remaining))
            print(res)
            return 

        for i in range(2):
            if str and str[0] != '0' and int(str[:i + 1]) in remaining :
                remaining.remove(int(str[:i + 1]))
                self.dfs(n, str[i + 1:], remaining, res)
                remaining.add(int(str[:i + 1]))

这样修改了就可以过了。你第一份代码没加那个len(remaining) == 1因为当str空串的时候就直接return了,并且刚刚后台的测试数据集都保证了肯定有唯一解,所以那个时候return了就也能AC了。所以就是我一开始说的str长度可能会没那么长,导致越界。

我来回答

您没有权限

为提高问答质量,问答版块发言权限只向九章学员开放

登录 注册

© Jiu Zhang 2013-. All rights reserved. 京ICP备16004690号-1