ARTS 第 12 周

每周完成一个 ARTS：
Algorithm: 每周至少做一个 LeetCode 的算法题
Review: 阅读并点评至少一篇英文技术文章
Tips: 学习至少一个技术技巧
Share: 分享一篇有观点和思考的技术文章

Contents:

• Algorithm: 22. Generate Parentheses
• Review: Using Machine Learning to Solve Real-World Problems
• Tip: 删除 LaTeX 中的段落缩进
• Share: 《Using Machine Learning to Solve Real-World Problems》翻译

Algorithm

22. Generate Parentheses

题目：22. Generate Parentheses

难度：Medium

题意：给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

示例：给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

解法：

本题解法参考了B站up主_Michelle小梦想家_的这个视频。

本题使用了递归法，又即「回溯法」。思路是：

1. 如果当前剩下的左右括号的数目大于 0，那么直接添加左右括号到名为 curr 的当前字符串中；
2. 因为最后一个括号一定为右括号，所以如果右括号的数目为 0，说明左括号已经全部使用（匹配）完毕，那么就可以将当前字符串 curr append 进 result 中；
3. 检查当前剩下的右括号的数目是否小于左括号的数目，如果是，说明这样的匹配是错误的，那么直接跳出递归，终止程序

代码如下：

class Solution(object):
    def generateParenthesis(self, n):
        """
        :type n: int
        :rtype: List[str]
        """

        if n == 0:
            return []
        result = []

        self.helper('', n, n, result)
        return result

    def helper(self, curr, n_left, n_right, result):
        if n_right < n_left:
            return
        if n_right == 0:
            result.append(curr)
            return result
        if n_left > 0:
            self.helper(curr + '(', n_left - 1, n_right, result)
        if n_right > 0:
            self.helper(curr + ')', n_left, n_right - 1, result)

时间复杂度和空间复杂度的分析比较困难，这里参考 LeetCode 的结论，均为。

Review

Using Machine Learning to Solve Real-World Problems

这周 review 的文章是 Medium 上的一篇推荐文章，Using Machine Learning to Solve Real-World Problems。这篇文章是作者参加 Lambda School 课程的一篇笔记，笔记的内容是一项 Kaggle 比赛，使用DrivenData.org提供的数据，预测坦桑尼亚境内井水泵的好坏与是否需要维修，以节省金钱时间和人力。详细内容请看 Share 部分我的翻译版本。

Tips

删除 LaTeX 中的段落缩进

这个技巧看起来很简单，但是我发现我需要翻遍一页半的谷歌搜索结果才能找到答案。这里提供一下找到的方法。

LaTeX 会将前面有空行或用 \par 标记定义的任何内容归类为一个新段落。默认情况下，LaTeX 会缩进每个段落的第一行。要关闭此功能，将以下内容放在文档顶部或.sty文件中：

\setlength{\parindent}{0in}

Share

《Using Machine Learning to Solve Real-World Problems》翻译

《Using Machine Learning to Solve Real-World Problems》翻译