ARTS(17)

1 Algorithm

给定一个只包含数字的字符串,复原它并返回所有可能的 IP 地址格式。
输入:"25525511135"
输出:["255.255.11.135", "255.255.111.35"]

这是一套比较常见的算法题,通常使用回溯的方法来解决问题,类似的题目有*八皇后*相关的题目。但是值注意的是,IP地址中每一个位,除了0之外,不允许的第一位为0的情况出现。

class Solution(object):
    def restoreIpAddresses(self, s):
        """
        :type s: str
        :rtype: List[str]
        """
        pivots = [0]
        result = []
        while True:
            if len(pivots) == 0:
                break
            pivot = pivots[-1]
            pivots[-1] = pivot + 1
            if pivots[-1] >= len(s):
                pivots = pivots[:-1]
                continue
            if len(pivots) == 1:
                ip = s[:pivots[-1]]
                if self.valid(ip):
                    pivots.append(pivots[-1])
                else:
                    pivots = pivots[:-1]
            elif len(pivots) == 2:
                ip = s[pivots[-2]:pivots[-1]]
                if self.valid(ip):
                    pivots.append(pivots[-1])
                else:
                    pivots = pivots[:-1]
            else:
                ip1 = s[0:pivots[-3]]
                ip2 = s[pivots[-3]:pivots[-2]]
                ip3 = s[pivots[-2]:pivots[-1]]
                ip4 = s[pivots[-1]:]
                if self.valid(ip3) and self.valid(ip4):
                    result.append(".".join([ip1, ip2, ip3, ip4]))
                
        return result

    def valid(self, s):
        if s == "":
            return False
        if len(s) > 1 and s[0] == "0":
            return False
        ip = int(s)
        return 0<= ip <= 255

2 Review

SSCCE
简短,自包含,正确、例子
如果你遇到了代码相关的问题,并且寻求帮助,那么SSCCE会非常有帮助,但是什么是SSCCE呢?
简而言之就是

  • 简单(Short)-将例子的代码足够简单,不要让你的受众感到无聊;
  • 自包含(Self Contained)-每一个必要的内容必须包含;
  • 正确(Correct)-复制和粘贴后就能达到目的;
  • 例子(Example)-展示将要去解决的问题。

2.1 简短(Short)

这个取决于社群和论坛,对于大部分公开的论坛,大部分读者会在超过100行代码后就会停止下去,一旦达到250-300行就开始抱怨。

  • 修短的技巧

如果GUI中包含了40个无关紧要的按钮,将它们去掉。如果它们和问题相关,将其中的一两个加上,如果问题出现了,就是这个问题。
对于包含上百个的入口的数组和表格的问题,同样的道理。如果是GUI排版的问题,将所有的处理逻辑代码去掉。同样的道理,如果是处理逻辑的问题,将GUI减少到最小。
如果你将大量的代码去掉后,你就发现你的问题就很明显了,问题也就解决了。

  • 问题解决了?

通过正确地确定了问题的所在,就离解决问题不远了。处理流程的亮点就在于确定问题的起源来帮助解决了问题。你也可以近距离地看看被移除的部分,查询整个问题。
即是还是不能解决问题,至少完成了重要的一步:确定了有问题的代码。
如果被修建后的代码就是问题精确的例子,你就可以把这个问题呈现给其他人,如果不能,就将问题返回直到这个代码其他内容也被修剪掉。

2.2 自包含(Self Contained)

如果别人根据你给出的代码,经过复制和粘贴就能运行,他们就能很快地帮助到你,这一点非常重要。这也就因为的你的问题就能够被复现,就有很大可能得到他们的帮助。

  • 如何让例子自包含

如果代码包含了文件的I/O,使用数据结构来替换无关的I/O操作。如果输入的文本就是问题的所在,准备好简单的实例输入文件例子。如果问题发生在特定的负载下,使用代码来模拟相应的负载。如果问题是在某个特定环境下的排版问题,强制让她发生。
显然还有一些组件无法在论坛形式上包含,比如数据库等等。但是很多情况下,你可以多想想采用一些其他方式来替换它们。比如一种很常见的方法就是图片,比如图片在代码中很难放置,一种可行的方法就是将它们放置在网络上。

2.3 正确(Correct)

在这个语境下,正确就是确保例子满足规划和协议。为了达到这一点,你需要做到以下几点:

  • 每一行代码必须在62字符以内,但是不要移除缩进;
  • 使用命令规范,如果规范,大部分人都会使用规范的大小写的要求,阅读代码的重要目的就是快速的发现问题,如果遵循规范,会很有帮助的;
  • 确保例子正确,出错的内容也要保持正确。

还有以下几点也要注意:

  • 将所有的资源移到同一个目录下,方便管理和查找;
  • 对于Java代码,移除包声明;
  • 如果可以的话,将代码移到同一个文件下;
  • 验证一下例子。

2.4 例子(Example)

确保代码,能够展示问题。或许你已经花在这个问题上好几个小时,几天还没有眉目。甚至好像永远也无法解决。现在是很好休息的时候,换一种思路解决问题。就跟重启电脑一下,重启是非常有必要的。现在打开网页,看看这个是否解决了。

3 Tips

  • linux 命令中,time <command> 可以查看 <command> 执行需要的时间;
  • NAS 在同步文件的时候,有时间消耗;
  • 所有的RPC调用中,必须考虑timeout。

4 Share

Comments
Write a Comment