Leetcode刷题笔记 3

dearfl

2021-06-25

9. Palindrome Number

Q: Given an integer x, return true if x is palindrome integer.

An integer is a palindrome when it reads the same backward as forward. For example, 121 is palindrome while 123 is not.

判断一个数是否为回文数，本题判定负数均不属于回文数。最简单的思路当然是把数字转成字符串或者字符数组，然后判定是否是回文。但是题目进阶的要求是不做这个转化，这样这个题目就有难度了。这里会用到一个比较巧妙的技巧，我们通过这个技巧得到这个数的前半部分和后半部分的反转，从而判定整个数是否是回文数。具体来说，我们一边将这个数除10，一边将除10的余数构造成另一个数，然后这个过程中，我们可以根据这两个数而判定原数是否是回文数。举个例子，如1234321，每次循环我们可以得到如下数字<123432, 1>,<12345, 12>,<1234,123>，进行到这里就足够了，因为这里1234/10==123，因此我们就可以判定1234321是回文数，如果原数是偶数位的，那我们判定两数是否相等。但是这种做法对于一些特例是不成立的，当x有后置0且x本身不为0时，我们相当于在判定x/10是否为回文数，而结论不成立。因此我们只需要判断是否是特例，再根据这种做法判定即可。以下分别是我自己的代码和别人相同思路的代码。

cpp
// mine
bool isPalindrome(int x) {
    if (x < 0 || x % 10 == 0 && x != 0) { return false; }
    int k = 0;
    while (x >= k) {
        if (x == k || x / 10 == k) {
            return true;
        }
        k = k * 10 + x % 10;
        x = x / 10;
    }
    return false;
}
bool isPalindrome(int x) {
    if (x < 0 || x % 10 == 0 && x != 0) { return false; }
    int reverse = 0;
    while (reverse < x) {
        reverse = reverse * 10 + x % 10;
        x /= 10;
    }
    return x == reverse || reverse / 10 == x;
}

10. Regular Expression Matching

Q: Given an input string (s) and a pattern (p), implement regular expression matching with support for ‘.’ and ‘*’ where:

‘.’ Matches any single character.
‘*’ Matches zero or more of the preceding element.

The matching should cover the entire input string (not partial).

这个题要求实现简单的正则匹配功能，我的第一反应是递归，思路相对比较简单，只是写起来比较繁琐。这里不再赘述思路，况且过了比较长时间了，这种题的思路也比较复杂，也不是想说就能说明白的。

cpp
bool isMatch(string s, string p) {
    char c;
    if (p.empty()) {
        return s.empty();
    }
    if (p.length() > 1 && p[1] == '*') {
        if (isMatch(s, p.substr(2))) {
            return true;
        } else if (s.length() > 0 && (p[0] == '.' || p[0] == s[0])) {
            return isMatch(s.substr(1), p);
        }
    } else if (s.length() > 0 && (p[0] == '.' || p[0] == s[0])) {
        return isMatch(s.substr(1), p.substr(1));
    }
    return false;
}

除了递归做法外，这道题还有DP的做法，设dp[i][j]是字符串s,p的子串s[0,i]和p[0,j]是否匹配，可以得到相应的状态转换方程。不过DP方法比较难懂，状态转换方程较为复杂，这里我就不说啥了，毕竟虽然能看懂，但自己想出来是不可能的。

cpp
bool isMatch(string s, string p) {
    vector<vector<bool> > dp(s.size() + 1, vector<bool>(p.size() + 1, false));
    int m = s.length(), n = p.length();
    dp[0][0] = true;
    for (int i = 1; i <= n; i++) {
        dp[0][i] = i > 1 && p[i-1] == '*' && dp[0][i-2];
    }
    for (int i = 1; i <= m; i++) {
        for (int j = 1; j <= n; j++) {
            if (p[j-1] == '*') {
                dp[i][j] = dp[i][j-2] || ((p[j-2] == s[i-1] || p[j-2] == '.') && dp[i-1][j]);
            } else {
                dp[i][j] = dp[i-1][j-1] && (p[j-1] == '.' || p[j-1] == s[i-1]);
            }
        }
    }
    return dp[m][n];
}

11. Container with Most Water

Q: Given n non-negative integers a1, a2, …, an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

Notice that you may not slant the container.

这个题可以用o(n^2)的笨办法做出来，勉强不会超时，但同时这个题也有o(n)的方法，其思路是：一个容器的容量为$min(a_ {i}, a_ {j}) \times ABS(i - j)$，那么我们可以先从ABS(i - j)最大，即i=1,j=n时开始，逐步向中心遍历，因为乘法的一个乘数只会逐渐变小，那么另一个乘数必须变大，才能让我们的结果尽可能大。同时由于木桶的短板原理，即使我们将更高的一块木板变得更高，容量也不会变得更大。因此我们必须从更短的那一侧逐渐向内搜索，才有可能得到更大的容量。也就是说，通过这些前提条件，我们可以这样对搜索范围进行剪枝，完全略过那些不存在答案的搜索空间。

cpp
int maxArea(vector<int>& height) {
    int n = height.size(), l = 0, r = n - 1, res = 0;
    while (l < r) {
        res = max(res, min(height[l], height[r]) * (r - l));
        // 必须从较短的木板朝中心靠拢，才有可能得到更大的res
        if (height[l] < height[r]) {
            l++;
        } else {
            r--;
        }
    }
    return res;
}

12. Integer to Roman

Q: 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, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 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.

将一个整数转换为罗马数字的形式，爷吐了。

cpp
string intToRoman(int num) {
    int digit;
    string res, tmp;
    string digits = "IVXLCDM ";
    for (int i = 0; num; i++) {
        digit = num % 10;
        tmp = "";
        if (digit == 9) {
            tmp = digits.substr(2 * i, 1) + digits.substr(2 * i + 2, 1);
        } else if (digit == 4) {
            tmp = digits.substr(2 * i, 2);
        } else {
            if (digit > 4) {
                digit -= 5;
                tmp += digits.substr(2 * i + 1, 1);
            }
            while (digit--) {
                tmp += digits.substr(2 * i, 1);
            }
        }
        res = tmp + res;
        num /= 10;
    }
    return res;
}

13. Roman to Integer

Q: 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, 2 is written as II in Roman numeral, just two one’s added together. 12 is written as XII, which is simply X + II. The number 27 is written as XXVII, which is XX + V + II.

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 a roman numeral, convert it to an integer.

将一个罗马数字转换为普通的整数，相比上一题，这一题还是简单不少。

cpp
 int romanToInt(string s) {
     int ans = 0;
     char pc = 0;
     int val[256] = {0};
     val['M'] = 1000;
     val['D'] = 500;
     val['C'] = 100;
     val['L'] = 50;
     val['X'] = 10;
     val['V'] = 5;
     val['I'] = 1;
     for (auto& c : s) {
         if (val[pc] < val[c]) {
             ans += val[c] - (val[pc] << 1);
         } else {
             ans += val[c];
         }
         pc = c;
     }
     return ans;
 }

14. Longest Common Prefix

Q: Write a function to find the longest common prefix string amongst an array of strings.

If there is no common prefix, return an empty string “”.

这题其实比较简单，关键在于需要考虑很多细节。我个人写的不太简洁，这里贴一段别人写的比较简洁的代码。

cpp
string longestCommonPrefix(vector<string>& strs) {
    string prefix = "";
    for (int idx = 0; strs.size() > 0; prefix += strs[0][idx], idx++) {
        for (int i = 0; i < strs.size(); i++) {
            if (idx >= strs[i].size() || (i > 0 && strs[i][idx] != strs[i - 1][idx])) {
                return prefix;
            }
        }
    }
    return prefix;
}

17. Letter Combinations of a Phone Number

Q: Given a string containing digits from 2-9 inclusive, return all possible letter combinations that the number could represent. Return the answer in any order.

这个题也没啥好说的，我也是第一思路递归，把当前数字键上的字母和余下数字序列的所有答案组合起来。队列做法相对巧妙一些，也稍微难写一些，但也没有太大难度。

cpp
// 递归写法
vector<string> letterCombinations(string digits) {
    vector<string> ans;
    vector<string> map{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    if (digits.empty()) {
        return {};
    } else if (digits.length() == 1) {
        for (int i = 0; i < map[digits[0] - '2'].length(); i++) {
            ans.push_back(map[digits[0] - '2'].substr(i, 1));
        }
        return ans;
    } else {
        for (int i = 0; i < map[digits[0] - '2'].length(); i++) {
            for (auto& s : letterCombinations(digits.substr(1))) {
                ans.push_back(map[digits[0] - '2'][i] + s);
            }
        }
        return ans;
    }
}
// 队列写法
vector<string> letterCombinations(string digits) {
    vector<string> ans;
    vector<string> map{"abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    queue<string> q;
    q.push("");
    string tmp;
    while (!q.empty()) {
        tmp = q.front();
        q.pop();
        if (tmp.length() == digits.length()) {
            if (tmp.length() != 0) {
                ans.push_back(tmp);
            }
        } else {
            for (int i = 0; i < map[digits[tmp.length()] - '2'].length(); i++) {
                q.push(tmp + map[digits[tmp.length()] - '2'].substr(i, 1));
            }
        }
    }
    return ans;
}

20. Valid Parentheses

Q: Given a string s containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.

An input string is valid if:

Open brackets must be closed by the same type of brackets.
Open brackets must be closed in the correct order.

使用栈来处理即可，左括号推入栈。右括号则检查栈顶是否有匹配的左括号。没有即不匹配，有则将其推出栈即可。所有字符遍历过后，如果栈内不为空，则说明，有部分左括号没有匹配的右括号。如果为空，则说明所有的括号都是匹配的。

cpp
bool isMatchChar(char c1, char c2) {
    return c1 == '[' && c2 == ']' || c1 == '(' && c2 == ')' || c1 == '{' && c2 == '}';
}
bool isValid(string s) {
    stack<char> stk;
    for (auto& c : s) {
        if (c == ']' || c == '}' || c == ')') {
            if (stk.empty() || !isMatchChar(stk.top(), c)) {
                return false;
            }
            stk.pop();
        } else {
            stk.push(c);
        }
    }
    return stk.empty();
}

21. Merge Two Sorted Lists

Q: Merge two sorted linked lists and return it as a sorted list. The list should be made by splicing together the nodes of the first two lists.

将两个有序的链表合并，这个题我是选择递归做法的，相对来说比较简单，我们只需要选出两个头节点里最小的那个，然后将剩下的两个链表递归的合并，再将合并好的链表接到最小的头节点后面即可。相对来说，非递归的写法还是比较难写的。

cpp
/*
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    if (!l1) { return l2; }
    if (!l2) { return l1; }
    ListNode* minNode = l1->val < l2->val ? l1 : l2;
    ListNode* maxNode = l1->val < l2->val ? l2 : l1;
    minNode->next = mergeTwoLists(minNode->next, maxNode);
    return minNode;
}
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
    ListNode dummy(0), *tail = &dummy;
    while (l1 && l2) {
        if (l1->val < l2->val) {
            tail->next = l1;
            l1 = l1->next;
        } else {
            tail->next = l2;
            l2 = l2->next;
        }
        tail = tail->next;
    }
    // we have to connect the rest part to the returned linked list
    tail->next = l1 ? l1 : l2;
    return dummy.next;
}

22. Generate Parentheses

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

给出括号的对数，生成所有合法的包含指定对数括号的字符串，第一反应是递归，对于n的case，我们生成i和n-i的所有case，然后将他们两两组合起来，同时再生成n-1的case，再将他们包在一对括号里。但是这样做需要去除相同的项。即如下

cpp
vector<string> generateParenthesis(int n) {
    vector<string> ans;
    if (n == 0) {
        ans = {};
    }
    else if (n == 1) {
        ans = {"()"};
    } else {
        for (int i = 1; i < n; i++) {
            for (auto& s1 : generateParenthesis(i)) {
                for (auto& s2 : generateParenthesis(n - i)) {
                    ans.push_back(s1 + s2);
                }
            }
        }
        for (auto& s : generateParenthesis(n - 1)) {
            ans.push_back("(" + s + ")");
        }
        set<string> ss(ans.begin(), ans.end());
        ans.clear();
        for (auto& s : ss) {
            ans.push_back(s);
        }
    }
    return ans;
}

当然这个题有另外一种更加巧妙的递归方式，我们把问题分为3部分，case(1)/case(i)/case(n-i-1)，然后我们进行这样的组合，"(" + case(i) + ")" + case(n-i-1)，基础的case当然是case(0)返回包含一个空字符串的集合。这种递归方式得到的解是没有重复和遗漏的。我们先看代码：

cpp
vector<string> generateParenthesis(int n) {
    vector<string> ans;
    if (n == 0) {
        return { "" };
    }
    for (int i = 0; i < n; i++) {
        for (auto& s1 : generateParenthesis(i)) {
            for (auto& s2 : generateParenthesis(n - i - 1)) {
                ans.push_back("(" + s1 + ")" + s2);
            }
        }
    }
    return ans;
}

为什么这样可以做到不重不漏呢，我们先来看相对比较明显的不重复性。假设ANS(n)是n对应的所有字符串的集合，以下均假设n>0。对于两个不同的答案来说，要相等即意味着字符串所有位置均相等，对于以上代码来说，就是要每次push_back答案字符串进入ans时，都要保证s1和s2至少有一个和其他的答案不同，也就是说ANS(i)和ANS(n-i-1)内没有重复元素。即只要保证对于[0, n-1]区间内的所有k来说来说，ANS(k)都不包含重复元素，则ANS(n)也不包含重复元素。这个我们可以通过数学归纳法比较简单的得到保证，不再赘述。

再看没有遗漏，没有遗漏意味着所有答案都是符合"(" + case(i) + ")" + case(n-i-1)这样的形式的，同时所有这样形式的字符串都是答案。后者是显然的，因为这样的字符串显然是合法的。我们知道合法的字符串第一个字符肯定是左括号，而且在字符串中有唯一一个与之匹配的右括号，且我们可以肯定，被这两个括号括起来的字符串肯定也是合法的，否则的话整个字符串也是不合法的。同样，右侧不包含在括号之内的字符串也是合法的。因此整个字符串肯定可以写成"(" + case(i) + ")" + case(n-i-1)的形式，其中，case(n-i-1)和case(i)均有可能为空。

最后通过双重循环，我们的答案包含了所有形如"(" + case(i) + ")" + case(n-i-1)的字符串，即保证了返回值里所有的字符串均是合法的答案，且没有重复的答案。