使用Python

解答动态

• 

  PEP 8 Python代码的样式指南列出了许多建议结束语：变量和；函数应该是snake\u case逗号后面应该跟一个空格二进制运算符应该被一个空格包围（例如，l==r而不是l==r，r+1而不是r+1） 有些函数/变量名可能是由编码挑战指定给您的，但是对于所有其他的你应该遵循PEP 8约定。
  OptimizationsLoop range for i in range（l，r+1）：
  假设你的范围是1到\$10^9\$，如果循环中的代码每次迭代花费10纳秒以上，这个循环将花费10秒以上。这对翻译语言要求很高。如果可以删除该循环，您会做得更好。
  请稍后对此进行详细说明。
  Counting-vs-existence if坏数字。计数（i） ==0:
  您正在搜索错误数字列表，对列表中值i的出现次数进行计数。
  badNumbers包含不同的元素
  由于badNumbers包含唯一的元素，因此计数将为0或1。更重要的是，一旦我们找到第一个匹配项，我们就可以停止计数，即使保证了唯一性，因为我们正在用零来测试计数。你真正想要的只是问我的值是否是坏数字。你写的和我们说的一模一样：如果我在badNumbers:
  这是仍然是一个\$O（n）\$操作，但是会更快。正如在另一个答案中提到的，将坏数字转换为一个集合将加快运算速度，使之成为一个\$O（1）\$运算。但是让我们研究另一个选项。
  减少数据 您的示例badNumbers=[37，7，22，15，49，60]，l=3和r=48显示出更多的低效。坏数字包含超出的数字。一遍又一遍地看那些数字（例如坏数字。计数（i） ==0或i（在badNumbers中）是浪费时间的。
  我们可以过滤掉“坏”的坏数字，这些坏数字只会浪费时间。
  badNumbers=[number for number in badNumbers if llt；=r]
  组织数据 您正在循环处理候选数字，然后进行有效搜索，查看候选号码是否在坏号码列表中。如果对该列表进行了排序，则只需维护一个指向下一个不匹配错误数字的索引，并在每次找到匹配项时递增该索引。
  将该索引与上一个索引相结合步骤：
  badNumbers=排序（如果llt；=r，则x代表x）
  Now在您的示例中，badNumbers将是[7，15，22，37]
  Now，it=iter（badNumbers）会创建一个迭代器遍历列表，按顺序，bad_number=next（it）会从列表中提取下一个错误的数字，我们也摆脱了上面提到的讨厌的索引。
  但是我真的很想摆脱第一个循环，所以让我们采取不同的方法。
  Gap Length and End Posts [7，15，22，37]
  在这个数组中，我们可以立即看到前两个坏数之间有15-7-1个好数，下一对之间有22-15-1个好数，最后一对之间有37-22-1个坏数。这几乎是所有我们需要得到最长的运行良好的数字！
  缺少的是列表开头和结尾处的正确数字。我们可以通过添加一些“end posts”来解决这个问题，额外的坏数字超出了好的范围end点数：
  baddumbers=[l-1]+排序（如果llt；=r，则x代表x）+[r+1]
  为l=3和r=48，这将创建badNumbers=[2，7，15，22，37，49]。
  现在，每对数字都可以用来确定
  PairWise 由于我们想要成对地获取数字，因此可以参考Python itertools库以获得适当的函数。它不是内置的，但是成对的配方可以从more-itertools安装。
  将这些数字作为一对，计算一对坏值之间的好值数目，并记住最大值。为了提高效率，可以将内部计算的负1延迟到最后，因为\$\max{（x\u i-1）}==\max{（x\u i）}-1\$
  从更多itertools导入pairwisedef goodSegment（bad\u numbers，l，r）：bad\u numbers=[l-1]+sorted（如果llt；=r，则x代表bad\u numbers）+[r+1]gap\u length=（b-a代表a，b in pairwise（bad_numbers））return max（gap_length）-1badNumbers=[5，4，2，15]l=1r=10 result=goodSegment（badNumbers，l，r）print（result） 如果没有更多的itertools可用，您可以使一些东西几乎等价于
  def pairwise（numbers）：return zip（numbers[：-1]，numbers[1:]） 它可能更快，虽然它会占用三倍的内存。
  
• 

  它是\$O（n*m）\$，因为坏数字。计数（i） ，n和m是坏数的长度和从左到右的范围。如果你将坏数转换成一个集合，并检查我是否在集合中，你可以将这个值减少到\$O（n+m）\$。
  你在函数中做了很多不必要的事情。您只需要当前数量和您在一行中看到的最大数量的数字，这些数字不在坏数字中。您不需要使用任何list.
  Btw，在一些地方，您可以通过使用elif而不是使用else和嵌套if/else块来使当前代码更平坦。特别是如果i==r:和len（子范围）==1:。这些可以更改为elif，然后底部的else块可以不缩进。
  
• End