22. Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

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

要求产生所有包含n对括号的合法字符串。 这一看就是递归的题，我开始用DFS来解，假设□表示所有n-1对括号的合法字符串，则要产生所有n对括号的合法字符串，有三种可能的情况，可以把新的括号对加在原有字符串的前面，后面或者包住之前的字符串，即”()□”、”□()”和”(□)”。但是有一个问题，即如果□是”()()()()”这样的形式，则新增的括号放在前面和后面是同一种，所以需要判断□是否对称。 第一版代码如下：

typedef struct Par_Pair {
    string par;
    bool is_symmetric;
};
class Solution {
public:
    void dfs(int step, vector<Par_Pair>& ans)
    {
        if (step == 1) {
            Par_Pair pp;
            pp.par = "()";
            pp.is_symmetric = true;
            ans.push_back(pp);
            return;
        }
        dfs(step – 1, ans);
        int sz = ans.size();
        for (int i = 0; i < sz; i++) {
            if (ans[i].is_symmetric) {
                Par_Pair pp;
                pp.is_symmetric = false;
                pp.par = "(" + ans[i].par + ")";
                ans.push_back(pp);
                ans[i].par = "()" + ans[i].par;
            }
            else {
                Par_Pair pp;
                pp.is_symmetric = false;
                pp.par = "()" + ans[i].par;
                ans.push_back(pp);
                pp.par = ans[i].par + "()";
                ans.push_back(pp);
                ans[i].par = "(" + ans[i].par + ")";
            }
        }
    }
    vector<string> generateParenthesis(int n)
    {
        vector<Par_Pair> ans;
        dfs(n, ans);
        vector<string> rs;
        for (int i = 0; i < ans.size(); i++)
            rs.push_back(ans[i].par);
        return rs;
    }
};

本代码提交WA，当n=4时，会漏掉”(())(())”这种情况，这种情况是两个”(())”；同时会重复”()(())()”这种情况，因为n=3时”()(())”和”(())()”是不同合法字符串，且不对称，当n=4时，增加一对括号，可以在前或后，导致出现重复。

看网上题解，用递归方法，真是漂亮。不是考虑同时增加一对括号，而是左右括号分别考虑。在放置括号时，为了合法，总是使剩余的左括号数少于右括号数，且当左右括号数相等时，先放置左括号。

其实自己枚举下剩余左右括号的数目left和right的大小关系，只有<、=、>三种关系，考虑下每种关系合法的放置操作即可。

class Solution {
public:
    void recur_gen(int left, int right, string s, vector<string>& ans)
    {
        if (left == 0 && right == 0) {
            ans.push_back(s);
            return;
        }
        if (left > 0)
            recur_gen(left – 1, right, s + "(", ans);
        if (right > 0 && left < right)
            recur_gen(left, right – 1, s + ")", ans);
    }
    vector<string> generateParenthesis(int n)
    {
        vector<string> ans;
        string s = "";
        recur_gen(n, n, s, ans);
        return ans;
    }
};

本代码提交AC，用时0MS。

12. Integer to Roman

Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M.

Symbol       Value
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

For example, two is written as II in Roman numeral, just two one’s added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II.

Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV. Because the one is before the five we subtract it making four. The same principle applies to the number nine, which is written as IX. There are six instances where subtraction is used:

• I can be placed before V (5) and X (10) to make 4 and 9. 
• X can be placed before L (50) and C (100) to make 40 and 90. 
• C can be placed before D (500) and M (1000) to make 400 and 900.

Given an integer, convert it to a roman numeral. Input is guaranteed to be within the range from 1 to 3999.

Example 1:

Input: 3
Output: "III"

Example 2:

Input: 4
Output: "IV"

Example 3:

Input: 9
Output: "IX"

Example 4:

Input: 58
Output: "LVIII"
Explanation: L = 50, V = 5, III = 3.

Example 5:

Input: 1994
Output: "MCMXCIV"
Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

本题要求把一个阿拉伯数字转换为罗马数字。 首先要了解罗马数字的表示形式，具体看Roman numerals WIKI。 罗马数字由上左图的7个基本字母组成，直接递归很容易求解。但是会有一些特殊情况，比如4，如果递归求解就是IIII，为了简便，采用5-1也就是IV的形式。上面右图就是基本的特殊情况。考虑特殊情况之后的递归代码如下：

class Solution {
public:
    string work(int num, string cur)
    {
        if (num >= 1000)
            return work(num – 1000, cur + "M");
        if (num >= 500) {
            if (num >= 900)
                return work(num – 900, cur + "CM");
            return work(num – 500, cur + "D");
        }
        if (num >= 100) {
            if (num >= 400)
                return work(num – 400, cur + "CD");
            return work(num – 100, cur + "C");
        }
        if (num >= 50) {
            if (num >= 90)
                return work(num – 90, cur + "XC");
            return work(num – 50, cur + "L");
        }
        if (num >= 10) {
            if (num >= 40)
                return work(num – 40, cur + "XL");
            return work(num – 10, cur + "X");
        }
        if (num >= 5) {
            if (num >= 9)
                return work(num – 9, cur + "IX");
            return work(num – 5, cur + "V");
        }
        if (num < 5) {
            if (num >= 4)
                return work(num – 4, cur + "IV");
            while (num > 0) {
                cur += "I";
                num–;
            }
            return cur;
        }
    }
    string intToRoman(int num) { return work(num, ""); }
};

本代码提交AC，用时32MS，这么多if语句，真是不够优雅。后来看到网上一种解法，简洁漂亮许多，贴出来学习一下：

class Solution {
public:
    string intToRoman(int num)
    {
        vector<int> nums = { 1, 4, 5, 9, 10, 40, 50, 90, 100, 400, 500, 900, 1000 };
        vector<string> symbol = { "I", "IV", "V", "IX", "X", "XL", "L", "XC", "C", "CD", "D", "CM", "M" };
        string ans = "";
        for (int i = nums.size() – 1; i >= 0; i--) {
            while (num >= nums[i]) {
                ans += symbol[i];
                num -= nums[i];
            }
        }
        return ans;
    }
};

本代码提交AC，用时56MS，比上一版稍慢，不够这版更好看。