Leet Code

Introduction
- 有趣的题目
1. Hot 100 1-10
2. Hot 100 11-20
3. Hot 100 21-30
- 3.1. Merge Two Sorted Lists
  - 3.1.1. 问题分析
  - 3.1.2. 代码实现
- 3.2. Generate Parentheses
  - 3.2.1. 问题分析
4. Hot 100 31-40
5. Hot 100 41-50
- 5.1. Trapping Rain Water
  - 5.1.1. 问题分析
6. 贪心算法
- 理论介绍
- 6.1. 盛最多水的容器

Introduction

有趣的题目

Regular Expression Matching
- 动态规划实现
- 递归调用实现
- 性能差异：递归性能比动态规划差2倍
3sum

1 Hot 100 1-10

1.1 Two sum

2022-06-11:

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

1.1.1 Method1 : Brute Force

Time Complexity: O(n^2)
Space Complexity: O(1)

1.1.2 Method2 : Hash Map

Time Complexity: O(n)
Space Complexity: O(n)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> hm;
        const int n = static_cast<int>(nums.size());
        for (int i = 0; i < n; ++i)
        {
            hm[nums[i]] = i;
        }

        for (int i = 0; i < n; ++i)
        {
            int expected = target - nums[i];
            auto it = hm.find(expected);
            if (it != hm.end() && it->second != i)
            {
                return std::vector<int>{static_cast<int>(i), it->second};
            }
        }
        // never get here
        return std::vector<int>{0, 0};
    }
};

Result:

Runtime: 23 ms, faster than 50.88% of C++ online submissions for Two Sum. Memory Usage: 11.9 MB, less than 15.17% of C++ online submissions for Two Sum.

How to optimize it ?

1.1.3 Optimize Performance

Merge hash find and insert in one loop.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        std::unordered_map<int, int> hm;
        const int n = static_cast<int>(nums.size());
        for (int i = 0; i < n; ++i)
        {
            int expected = target - nums[i];
            auto it = hm.find(expected);
            if (it != hm.end())
            {
                return std::vector<int>{static_cast<int>(i), it->second};
            }
            hm[nums[i]] = i;
        }
        // never get here
        return std::vector<int>{0, 0};
    }
};

Result:

Runtime: 3 ms, faster than 99.87% of C++ online submissions for Two Sum. Memory Usage: 10.8 MB, less than 46.35% of C++ online submissions for Two Sum.

可以点击Leetcode提交通过的 Accepted ，或者力扣通过，查看所有提交的时间分布。找到时间更优的实现，查看代码，分析与自己实现的区别。

查看了Hot Top2题目，实现是差不多的。应该是历史原因，或者case增强导致的差异。

1.2 Add Two Numbers

2022-06-11

https://leetcode.com/problems/add-two-numbers/

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order, and each of their nodes contains a single digit. Add the two numbers and return the sum as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example1:
(2) -> (4) -> (3) (5) -> (6) -> (4)

(7) -> (0) -> (8)

Input: l1 = [2,4,3], l2 = [5,6,4]
Output: [7,0,8]
Explanation: 342 + 465 = 807.

Example 2:
Input: l1 = [0], l2 = [0]
Output: [0]

Example 3:
Input: l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
Output: [8,9,9,9,0,0,0,1]

Constraints:

The number of nodes in each linked list is in the range [1, 100].

0 <= Node.val <= 9

It is guaranteed that the list represents a number that does not have leading zeros.

1.2.1 Implement

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    int carry = 0;
    // malloc optimize:
    ListNode head;
    ListNode* curr = &head;
    curr->val = 0;
    curr->next = nullptr;
    while (nullptr != l1 && nullptr != l2)
    {
        int val = l1->val + l2->val + carry;
        carry = val / 10;
        ListNode* node = new ListNode(val % 10);
        curr->next = node;
        curr = node;
        l1 = l1->next;
        l2 = l2->next;
    }

    if (nullptr == l1)
    {
        l1 = l2;
    }

    while (nullptr != l1)
    {
        int val = l1->val + carry;
        carry = val / 10;
        ListNode* node = new ListNode(val % 10);
        curr->next = node;
        curr = node;
        l1 = l1->next;
    }

    if (0 != carry)
    {
        ListNode* node = new ListNode(carry);
        curr->next = node;
    }

    return head.next;
}

Result:

Runtime: 40 ms, faster than 75.88% of C++ online submissions for Add Two Numbers. Memory Usage: 71.5 MB, less than 50.19% of C++ online submissions for Add Two Numbers.

力扣跑了下，结果更好。国内厂家的硬件看来更优秀(也可能case更少？)。一个朋友告诉我，这个时间是相对的，只具备参考意义。

执行结果：通过

执行用时：20 ms, 在所有 C++ 提交中击败了 89.17% 的用户
内存消耗： 69.5 MB, 在所有 C++ 提交中击败了 15.37%的用户
通过测试用例：1568 / 1568

1.3 Longest Substring Without Repeating Characters

2022-06-11

Given a string s, find the length of the longest substring without repeating characters.

Example 1:
Input: s = "abcabcbb"
Output: 3
Explanation: The answer is "abc", with the length of 3.

Example 2:
Input: s = "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:
Input: s = "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3.
Notice that the answer must be a substring, "pwke" is a subsequence and not a substring.

Constraints:

0 <= s.length <= 5 * 10^4

s consists of English letters, digits, symbols and spaces.

Implementation:

int lengthOfLongestSubstring(string s) {
    if (s.empty())
    {
        return 0;
    }

    std::unordered_map<char, int> hm;
    const int n = static_cast<int>(s.length());
    int maxdis = 1;
    int winstart = 0;
    // case 1: abcde
    //         ^    ^
    //         winstart = 0;
    //         maxdis=1;
    //         set to n - winstart after loop;
    // case 2: dvdfv
    //           ^
    //           set maxdis=2;
    //               winstart=1;
    //             ^
    //             set maxdis=4-1=3;
    //                 winstart=2;
    hm[s[0]] = 0;
    for (int i = 1; i < n; ++i)
    {
        auto it = hm.find(s[i]);
        if (hm.end() != it && it->second >= winstart)
        {
            int distance = i - winstart;
            if (distance > maxdis)
            {
                maxdis = distance;
            }
            winstart = it->second + 1;
            it->second = i;
        }
        else
        {
            hm[s[i]] = i;
        }
    }

    int distance = n - winstart;
    if (distance > maxdis)
    {
        maxdis = distance;
    }

    return maxdis;
}

Result:

Runtime: 23 ms, faster than 57.38% of C++ online submissions for Longest Substring Without Repeating Characters. Memory Usage: 8.3 MB, less than 73.86% of C++ online submissions for Longest Substring Without Repeating Characters.

考虑Key的范围比较有限(uint8)，尝试用rbtree替换掉hash。结果好了一点：

Runtime: 18 ms, faster than 67.93% of C++ online submissions for Longest Substring Without Repeating Characters. Memory Usage: 8.5 MB, less than 48.70% of C++ online submissions for Longest Substring Without Repeating Characters.

再尝试做下优化，把map改为数组：

int lengthOfLongestSubstring(string s) {
    const int n = s.length();
    int wstart = 0;
    int wlen = 0;

    int cIdxArr[128];
    memset(cIdxArr, 0, sizeof(cIdxArr));

    for (int i = 0; i < n; ++i)
    {
        uint8_t idx = static_cast<uint8_t>(s[i]);
        if (cIdxArr[idx] <= wstart)
        {
            cIdxArr[idx] = i + 1;
            continue;
        }

        if (i - wstart > wlen)
        {
            wlen = i - wstart;
        }

        wstart = cIdxArr[idx];
        cIdxArr[idx] = i + 1;
    }

    if (n - wstart > wlen)
    {
        wlen = n - wstart;
    }

    return wlen;
}

这个效果好了很多：

Runtime: 8 ms, faster than 88.89% of C++ online submissions for Longest Substring Without Repeating Characters.
Memory Usage: 6.9 MB, less than 96.65% of C++ online submissions for Longest Substring Without Repeating Characters.

1.4 Median of Two Sorted Arrays

Given two sorted arrays nums1 and nums2 of size m and n respectively, return the median of the two sorted arrays.

The overall run time complexity should be O(log (m+n)).

Example 1:
Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.

Example 2:
Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.

Constraints:

nums1.length == m

nums2.length == n

0 <= m <= 1000

0 <= n <= 1000

1 <= m + n <= 2000

-106 <= nums1[i], nums2[i] <= 106

1.4.1 代码实现

double findMedianSortedArrays(const vector<int>& nums1, const vector<int>& nums2) {

    bool nums1short = nums1.size() <= nums2.size();
    const auto& snums = nums1short ? nums1 : nums2;
    const auto& lnums = nums1short ? nums2 : nums1;
    int sn = snums.size();
    int ln = lnums.size();
    int expectedLeft = (sn + ln + 1) / 2;
    int left = 0;
    int right = sn;

    while (left < right)
    {
        int i = left + (right - left + 1) / 2;
        int j = expectedLeft - i;
        if (snums[i - 1] > lnums[j])
        {
            right = i - 1;
        }
        else
        {
            left = i;
        }
    }

    int i = left;
    int j = expectedLeft - i;

    int sLeftMax = (0 != i) ? snums[i - 1] : INT32_MIN;
    int lLeftMax = (0 != j) ? lnums[j - 1] : INT32_MIN;
    int sRightMin = (sn != i) ? snums[i] : INT32_MAX;
    int lRightMin = (ln != j) ? lnums[j] : INT32_MAX;
    int leftMax = std::max(sLeftMax, lLeftMax);
    int rightMin = std::min(sRightMin, lRightMin);
    if ((sn + ln) % 2)
    {
        return leftMax;
    }

    return static_cast<double>(leftMax + rightMin) / 2;
}

Result:

Runtime: 51 ms, faster than 61.84% of C++ online submissions for Median of Two Sorted Arrays.
Memory Usage: 89.1 MB, less than 97.35% of C++ online submissions for Median of Two Sorted Arrays.

1.5 Longest Palindromic Substring

Given a string s, return the longest palindromic substring in s.

Example 1:
Input: s = "babad"
Output: "bab"
Explanation: "aba" is also a valid answer.

Example 2:
Input: s = "cbbd"
Output: "bb"

Constraints:

1 <= s.length <= 1000

s consist of only digits and English letters.

1.5.1 暴力遍历

没啥意思，不写了。

1.5.2 动态规划

推导：

s[i..j] 是一个回文子串，则s[i+1 … j-1] 一定是一个回文字串；
定义一个辅助二维数组tag，如果s[i..j] 是一个回文子串，则设置tag[i][j] = true，否则设置 tag[i][j] = false；

string longestPalindrome(string s) {
    int n = static_cast<int>(s.length());
    if (0 == n)
    {
        return s;
    }

    bool tag[n][n];
    int start = 0;
    int pn = 1;

    for (int j = 1; j < n; ++j)
    {
        tag[j][j] = true;

        for (int i = 0; i < j; ++i)
        {
            tag[i][j] = (s[i] == s[j] && (j - i < 3 || tag[i + 1][j - 1]));
            int distance = j - i + 1;
            if (tag[i][j] && distance > pn)
            {
                pn = distance;
                start = i;
            }
        }
    }

    return s.substr(start, pn);
}

Result:

Runtime: 346 ms, faster than 35.58% of C++ online submissions for Longest Palindromic Substring.
Memory Usage: 8.3 MB, less than 65.23% of C++ online submissions for Longest Palindromic Substring.

时间复杂度：O(n^2)
空间复杂度：O(n^2)
tag对交线及左下一半空间是没有使用的，特殊设计下，可以节省tag一半空间；

1.5.3 Manacher算法

1.6 Zigzag Conversion

The string "PAYPALISHIRING" is written in a zigzag pattern on a given number of
rows like this: (you may want to display this pattern in a fixed font for better
legibility)
P   A   H   N
A P L S I I G
Y   I   R
And then read line by line: "PAHNAPLSIIGYIR"

Write the code that will take a string and make this conversion given a number
of rows:

string convert(string s, int numRows);

Example 1:
Input: s = "PAYPALISHIRING", numRows = 3
Output: "PAHNAPLSIIGYIR"

Example 2:
Input: s = "PAYPALISHIRING", numRows = 4
Output: "PINALSIGYAHRPI"
Explanation:
P     I    N
A   L S  I G
Y A   H R
P     I

Example 3:
Input: s = "A", numRows = 1
Output: "A"

1.6.1 问题分析

把原始数据的下标(SourceIndex)按照Zigtag摆放，做个特征观察：

// s.length() = 15, rows=3
0     4     8       12
1  3  5  7  9   11  13  15
2     6     10      14

// s.length() = 15, rows=4
0       6          12
1    5  7      11  13
2  4    8  10      14
3       9          15

元素在垂直线和对交线上；
把垂直线之后，对交线上的元素和垂直线合并到一起，称为一个列（col）；
可以得出:
- 垂直线元素下标 $IndexOfVertical = col * (rows*2 - 2) + row$;
- 对交线元素下标 $IndexOfIntersect = col * (rows*2 - 2) + (numRows - 1) * 2 - row$
按照row, col两层循环的方式访问，O(n)就能做完字符串处理。

1.6.2 代码实现

string convert(string s, int numRows) {
    if (numRows < 2)
    {
        return s;
    }

    string ret;
    const int n = static_cast<int>(s.length());
    const int numRowsMinus1 = numRows - 1;
    const int countOfFixedCol = numRowsMinus1 * 2;
    const int fixedCols = (n + countOfFixedCol - 1) / countOfFixedCol;

    int idx = 0;
    ret.resize(n);
    for (int r = 0; r < numRows; ++r)
    {
        int srcVerticalIdx = r;
        for (int col = 0; col < fixedCols && srcVerticalIdx < n; ++col)
        {
            ret[idx++] = s[srcVerticalIdx];

            if (r % numRowsMinus1)
            {
                int srcIntersectIdx = srcVerticalIdx + countOfFixedCol - r - r;
                if (srcIntersectIdx < n)
                {
                    ret[idx++] = s[srcIntersectIdx];
                }
            }

            srcVerticalIdx += countOfFixedCol;
        }
    }

    return ret;
}

Result:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Zigzag Conversion.
Memory Usage: 7.9 MB, less than 99.10% of C++ online submissions for Zigzag Conversion.

1.7 Reverse Integer

Given a signed 32-bit integer x, return x with its digits reversed. If reversing x causes the value to go outside the signed 32-bit integer range [-231, 231 - 1], then return 0.

Assume the environment does not allow you to store 64-bit integers (signed or unsigned).

Example 1:
Input: x = 123
Output: 321

Example 2:
Input: x = -123
Output: -321

Example 3:
Input: x = 120
Output: 21

Constraints:

-2³¹ <= x <= 2³¹ - 1

1.7.1 问题分析

仅仅是模10, 除10, 以及用 INT_MIN/INT_MAX 处理个溢出，这题目没啥意思。

考虑特殊性：

一个数字要溢出，一定是位数足够多。如果位数不够则不做检查；
循环内的分支要尽量少。

挑战：除10是一个耗时操作，有没有办法用加法减法展开实现呢？

1.7.2 代码实现

int reverse(int x) {
    // 0x111
    // 0x1010
    constexpr int checkMaxLimit = INT_MAX / 10;
    constexpr int checkMinLimit = INT_MIN / 10;
    constexpr int checkMaxMod = INT_MAX % 10;
    constexpr int checkMinMod = INT_MIN % 10;

    int ret = x % 10;
    const bool noOverflow = ((x < checkMaxLimit && x > checkMinLimit) ||
                             0 == ret || 1 == ret || -1 == ret);

    x /= 10;

    if (noOverflow)
    {
        while (x)
        {
            int d = x % 10;
            ret *= 10;
            ret += d;

            x /= 10;
        }
    }
    else
    {
        if (x >= 0)
        {
            while (x)
            {
                int d = x % 10;

                if (checkMaxLimit > ret ||
                    (checkMaxLimit == ret && d <= checkMaxMod))
                {
                    ret *= 10;
                    ret += d;
                    x /= 10;
                }
                else
                {
                    return 0;
                }
            }
        }
        else
        {
            while (x)
            {
                int d = x % 10;

                if (checkMinLimit < ret ||
                    (checkMinLimit == ret && d >= checkMinMod))
                {
                    ret *= 10;
                    ret += d;
                    x /= 10;
                }
                else
                {
                    return 0;
                }
            }
        }
    }

    return ret;
}

Result:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Reverse Integer.
Memory Usage: 5.9 MB, less than 32.76% of C++ online submissions for Reverse Integer.

1.8 String to Integer (atoi)

Implement the myAtoi(string s) function, which converts a string to a 32-bit
signed integer (similar to C/C++'s atoi function).

The algorithm for myAtoi(string s) is as follows:

1. Read in and ignore any leading whitespace.
2. Check if the next character (if not already at the end of the string) is
   '-' or '+'. Read this character in if it is either. This determines if the
   final result is negative or positive respectively. Assume the result is
   positive if neither is present.
3. Read in next the characters until the next non-digit character or the end
   of the input is reached. The rest of the string is ignored.
4. Convert these digits into an integer (i.e. "123" -> 123, "0032" -> 32). If
   no digits were read, then the integer is 0. Change the sign as necessary
   (from step 2).
5. If the integer is out of the 32-bit signed integer range
   [-2^{31}, 2^{31} - 1], then clamp the integer so that it remains in the
   range. Specifically, integers less than -231 should be clamped to
   -2^{31}, and integers greater than 2^{31} - 1 should be clamped to
   2^{31} - 1.
6. Return the integer as the final result.

Note:
Only the space character ' ' is considered a whitespace character.
Do not ignore any characters other than the leading whitespace or the rest of
the string after the digits.

Example 1:
Input: s = "42"
Output: 42
Explanation: The underlined characters are what is read in, the caret is the
current reader position.
Step 1: "42" (no characters read because there is no leading whitespace)
         ^
Step 2: "42" (no characters read because there is neither a '-' nor '+')
         ^
Step 3: "42" ("42" is read in)
           ^
The parsed integer is 42.
Since 42 is in the range [-2^{31}, 2^{31} - 1], the final result is 42.

Example 2:
Input: s = "   -42"
Output: -42
Explanation:
Step 1: "   -42" (leading whitespace is read and ignored)
            ^
Step 2: "   -42" ('-' is read, so the result should be negative)
             ^
Step 3: "   -42" ("42" is read in)
               ^
The parsed integer is -42.
Since -42 is in the range [-2^{31}, 2^{31} - 1], the final result is -42.

Example 3:
Input: s = "4193 with words"
Output: 4193
Explanation:
Step 1: "4193 with words" (no characters read because there is no leading
        whitespace)
         ^
Step 2: "4193 with words" (no characters read because there is neither a '-'
        nor '+')
         ^
Step 3: "4193 with words" ("4193" is read in; reading stops because the next
             ^
        character is a non-digit)
The parsed integer is 4193.
Since 4193 is in the range [-2^{31}, 2^{31} - 1], the final result is 4193.

Constraints:
- 0 <= s.length <= 200
- s consists of English letters (lower-case and upper-case), digits (0-9), ' ',
  '+', '-', and '.'.

1.8.1 问题分析

如同题目Reverse Integer一样处理边界，其他没啥难度。

1.8.2 代码实现

int myAtoi(string s) {

    constexpr int maxLimit = INT_MAX / 10;
    constexpr int minLimit = INT_MIN / 10;
    constexpr int maxMod = INT_MAX % 10;
    constexpr int minMod = INT_MIN % 10;

    int idx = 0;
    int n = static_cast<int>(s.length());

    while (' ' == s[idx])
    {
        ++idx;
    }

    bool isPositive = true;

    if ('-' == s[idx] || '+' == s[idx])
    {
        isPositive = ('+' == s[idx]);
        ++idx;
    }

    int ret = 0;
    if (isPositive)
    {
        while (isdigit(s[idx]))
        {
            int d = s[idx] - '0';
            if (maxLimit > ret || (maxLimit == ret && d <= maxMod))
            {
                ret *= 10;
                ret += d;
            }
            else
            {
                return INT32_MAX;
            }
            ++idx;
        }
    }
    else
    {
        while (isdigit(s[idx]))
        {
            int d = -(s[idx] - '0');
            if (minLimit < ret || (minLimit == ret && d >= minMod))
            {
                ret *= 10;
                ret += d;
            }
            else
            {
                return INT32_MIN;
            }
            ++idx;
        }
    }

    return ret;
}

Result:

Runtime: 5 ms, faster than 43.05% of C++ online submissions for String to Integer (atoi).
Memory Usage: 7 MB, less than 53.53% of C++ online submissions for String to Integer (atoi).

1.9 Palindrome Number

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 a palindrome while 123 is not.

Example 1:
Input: x = 121
Output: true
Explanation: 121 reads as 121 from left to right and from right to left.

Example 2:
Input: x = -121
Output: false
Explanation: From left to right, it reads -121. From right to left, it becomes 121-. Therefore it is not a palindrome.

Example 3:
Input: x = 10
Output: false
Explanation: Reads 01 from right to left. Therefore it is not a palindrome.

Constraints:

-2³¹ <= x <= 2³¹ - 1

Follow up: Could you solve it without converting the integer to a string?

1.9.1 问题分析

1.9.2 实现代码

bool isPalindrome(int x) {
    if (x < 0)
    {
        return false;
    }

    int ds[10];
    int dn = 1;
    ds[0] = x % 10;
    x /= 10;

    while (x)
    {
        ds[dn] = x % 10;
        x /= 10;
        ++dn;
    }

    int middle = dn / 2;
    for (int i = 0, j = dn - 1; i < middle; ++i, --j)
    {
        if (ds[i] != ds[j])
        {
            return false;
        }
    }

    return true;
}

Result:

Runtime: 14 ms, faster than 76.36% of C++ online submissions for Palindrome Number.
Memory Usage: 5.8 MB, less than 91.12% of C++ online submissions for Palindrome Number.

1.10 Regular Expression Matching

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).

Example 1:
Input: s = "aa", p = "a"
Output: false
Explanation: "a" does not match the entire string "aa".

Example 2:
Input: s = "aa", p = "a*"
Output: true
Explanation: '*' means zero or more of the preceding element, 'a'. Therefore, by repeating 'a' once, it becomes "aa".

Example 3:
Input: s = "ab", p = ".*"
Output: true
Explanation: ".*" means "zero or more (*) of any character (.)".

Constraints:

1 <= s.length <= 20

1 <= p.length <= 30

s contains only lowercase English letters.

p contains only lowercase English letters, '.', and '*'.

It is guaranteed for each appearance of the character '*', there will be a previous valid character to match.

1.10.1 问题分析

特殊字符*可以匹配前一个字符0次或任意多次，因此，一次失配发生后，需要回溯再试。这是典型的动态规划问题：

假设s长度sn，p长度pn；
定义 dp[sn][pn]，其中dp[i][j] 表示 s 的前 i 个字符与 p 的前 j 个字符是否匹配；
dp[sn-1][pn-1] 为 true 则匹配，否则失配；

先做几个匹配矩阵观察特征： s=aaa,p=aaa

s\p	0	1	2
0	T	F	F
1	F	T	F
2	F	F	T

s=aaa,p=baa

s\p	0	1	2
0	F	F	F
1	F	F	F
2	F	F	F

s=aaa,p=aaaa

s\p	0	1	2	3
0	T	F	F	F
1	F	T	F	F
2	F	F	T	F

s=aaa,p=a*aaa

s\p	0	1	2	3	4
0	T	T	T	F	F
1	T	T	T	T	F
2	T	T	T	T	T

s=aaa,p=b*aaa

s\p	0	1	2	3	4
0	F	F	T	F	F
1	F	F	F	T	F
2	F	F	F	F	T

首先定义一个操作:

bool IsMatchChar(char sc, char pc)
{
  return sc == pc || '.' == pc;
}

归纳下特征，期待能定义一个方程：

1. if p[j] != '*':
   dp[i][j] = dp[i-1][j-1] && isMatchChar(s[i], p[j])

2. if p[j] == '*':
   if isMatchChar(s[i], p[j-1]):
       dp[i][j] = (dp[i-1][j] || dp[i][j-2]) &&
   else:
       dp[i][j] = dp[i][j-2]

可以做的另一个优化是如果某一行都是false，则肯定无法匹配，可以提前终止。

1.10.2 代码实现 - 动态规划

bool isMatch(string s, string p) {
    int sn = static_cast<int>(s.length());
    int pn = static_cast<int>(p.length());

    if (0 == sn)
    {
        if (0 == pn)
        {
            return true; // both s and p empty
        }

        // p <AnyChar>*\+ matches empty s.
        if (pn % 2)
        {
            return false;
        }
        for (int j = 1; j < pn; j += 2)
        {
            if ('*' != p[j])
            {
                return false;
            }
        }
        return true;
    }

#define IsMatchChar(sc, pc) (sc == pc || '.' == pc)

    bool dp[sn][pn];
    // memset(dp, 0x0, sn * pn);

    // process dp[0][0] ~ dp[0][pn]
    // s[0]: a
    // p:    a
    //       a*b*c*
    //       aa*
    //       b*c*a*a
    dp[0][0] = IsMatchChar(s[0], p[0]);
    int hastrue = dp[0][0];
    for (int j = 1; j < pn; ++j)
    {
        if (p[j] != '*')
        {
            if (p[j - 1] == '*')
            {
                dp[0][j] = IsMatchChar(s[0], p[j]);
                hastrue |= dp[0][j];
                continue;
            }

            // p[j-1] must be matched s[0],
            // only set asterisk position to true if asterisk and
            // dot are intersect in rest of pattern.
            for (; j < pn; ++j)
            {
                dp[0][j] = false;

                ++j;
                // now j always greater than 2
                if (j < pn)
                {
                    dp[0][j] = (p[j] == '*') && dp[0][j - 2];
                }
            }
            break;
        }
        else
        {
            dp[0][j] = dp[0][j-1] || (j > 1 && dp[0][j-2]);
            hastrue |= dp[0][j];
        }
    }
    if (!hastrue)
    {
        return false;
    }

    for (int i = 1; i < sn; ++i)
    {
        // s size from 2 to sn, p size is 1, so dp[i][0] must be false.
        dp[i][0] = false;
        hastrue = dp[i][0];
        for (int j = 1; j < pn; ++j)
        {
            if (p[j] != '*')
            {
                dp[i][j] = dp[i-1][j-1] && IsMatchChar(s[i], p[j]);
            }
            else
            {
                if (IsMatchChar(s[i], p[j-1]))
                {
                    dp[i][j] = dp[i-1][j] || (j > 1 && dp[i][j-2]);
                }
                else
                {
                    dp[i][j] = (j > 1 && dp[i][j-2]);
                }
            }
            hastrue |= dp[i][j];
        }

        if (!hastrue)
        {
            return false;
        }
    }

    return dp[sn-1][pn-1];
}

Result:

Runtime: 5 ms, faster than 73.15% of C++ online submissions for
Regular Expression Matching. Memory Usage: 6.3 MB, less than 82.40% of C++ online submissions for
Regular Expression Matching.

1.10.3 代码实现 - 递归调用

分治、动态规划问题都可以用递归调用实现，代码简单，但性能会差。这个问题的递归分析如下：

如果p已经到结尾('\0')
- 如果s也到结尾，则完全匹配；
- 如果s还没到结尾，则不匹配；
如果p不是结尾，且p[1]是'*'
- 如果p和s当前字符匹配，优先贪心检测，保持不懂，s递增；
- 如果上述尝试最终失败，则把p和*忽略，尝试s和p+2匹配；
如果p不是结尾，且p[1]不是'*'
- 如果当前字符匹配，则继续尝试p+1, s+1

代码实现如下：

bool isMatchRecursive(const char *s, const char *p)
{
    if ('\0' == *p)
    {
        return '\0' == *s;
    }

    bool isMatchChar = ('\0' != *s && (*s == *p || '.' == *p));

    if (p[1] == '*')
    {
        // greedy check, advance s.
        if (isMatchChar && isMatchRecursive(s + 1, p))
        {
            return true;
        }

        // greedy fail, ignore p && p[1] for p[1] is '*'
        return isMatchRecursive(s, p + 2);
    }

    return isMatchChar && isMatchRecursive(s + 1, p + 1);
}

bool isMatch(string s, string p)
{
    return isMatchRecursive(s.c_str(), p.c_str());
}

递归版本参考了Allen的实现。

Result:

Runtime: 18 ms, faster than 37.32% of C++ online submissions for Regular Expression Matching.
Memory Usage: 6.4 MB, less than 82.40% of C++ online submissions
for Regular Expression Matching.

对比DP的结果，性能差了2倍。

2 Hot 100 11-20

2.1 Container With Most Water

You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).

Find two lines that together with the x-axis form a container, such that the container contains the most water.

Return the maximum amount of water a container can store.

Notice that you may not slant the container.

Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.

Example 2:
Input: height = [1,1]
Output: 1

Constraints:

n == height.length

2 <= n <= 105

0 <= height[i] <= 104

2.1.1 问题分析

这是一个贪心问题。维度为n，假设左边垂线下标为i，右边垂线下标为j。

开始时， $area = min(height[i], height[j]) * (j - i)$
假设 $height[i] > height[j]$
- 有 $min(height[i], height[j]) = heightt[j]$
- 如果我们把i右移，$min(height[i], height[j])不可能比height[j]更大；
- i右移必然导致面积进一步减少，因此不需要尝试；
- 因此应该是j左移；所以我们把j左移，基因不做区间i,j-1的分析；
假设 $height[i] < height[j]$
- 同上，容易得出i右移，进一步做区间i+1,j的分析
假设 $height[i] = height[j]$
- 无论移动i或j均可，我们实现为左移j；

时间复杂度 $O(n)$ ，空间复杂度$O(1)$

2.1.2 代码实现

int maxArea(vector<int>& height) {
    if (height.empty())
    {
        return 0;
    }

    int left = 0;
    int right = static_cast<int>(height.size() - 1);
    int area = 0;

    while (left < right)
    {
        int w = right - left;
        int h;
        if (height[left] < height[right])
        {
            h = height[left];
            ++left;
        }
        else
        {
            h = height[right];
            --right;
        }
        int thisArea = h * w;
        if (thisArea > area)
        {
            area = thisArea;
        }
    }

    return area;
}

Result:

Runtime: 114 ms, faster than 65.14% of C++ online submissions for Container With Most Water.
Memory Usage: 59 MB, less than 81.43% of C++ online submissions for Container With Most Water.

2.2 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, 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.

Example 1:
Input: num = 3
Output: "III"
Explanation: 3 is represented as 3 ones.

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

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

Constraints:

1 <= num <= 3999

2.2.1 问题分析

Roman numerals规则是从左向右，按照数字从大到小。我们根据粘连规则，生成一个数值表。

static constexpr int ia[] = {
    1000, 900, 500, 400,
    100, 90, 50, 40,
    10, 9, 5, 4,
    1};
static constexpr int n = sizeof(ia) / sizeof(ia[0]);
static constexpr int na[] = {
    1, 2, 1, 2,
    1, 2, 1, 2,
    1, 2, 1, 2,
    1};
static constexpr const char* sa[] = {
    "M", "CM", "D", "CD",
    "C", "XC", "L", "XL",
    "X", "IX", "V", "IV",
    "I"};

2.2.2 代码实现

string intToRoman(int num) {
    static constexpr int ia[] = {
        1000, 900, 500, 400,
        100, 90, 50, 40,
        10, 9, 5, 4,
        1};
    static constexpr const char* sa[] = {
        "M", "CM", "D", "CD",
        "C", "XC", "L", "XL",
        "X", "IX", "V", "IV",
        "I"};
    static_assert(sizeof(ia)/sizeof(ia[0]) == sizeof(sa)/sizeof(sa[0]));
    // MMM + DCCC + LXXX + VIII
    static constexpr int n = sizeof(ia) / sizeof(ia[0]);
    std::string roman;
    roman.resize(16);
    int rn = 0;
    for (int i = 0; i < n; ++i)
    {
        while (num >= ia[i])
        {
            roman[rn++] = sa[i][0];
            if (sa[i][1] != '\0')
            {
                roman[rn++] = sa[i][1];
            }

            num -= ia[i];
        }

        if (0 == num)
        {
            roman.resize(rn);
            break;
        }
    }

    return roman;
}

Result:

Runtime: 4 ms, faster than 90.13% of C++ online submissions for Integer to Roman.
Memory Usage: 6.1 MB, less than 49.82% of C++ online submissions for Integer to Roman.

2.3 Roman to Integer

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

Example 1:
Input: s = "III"
Output: 3
Explanation: III = 3.

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

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

Constraints:

1 <= s.length <= 15

s contains only the characters ('I', 'V', 'X', 'L', 'C', 'D', 'M').

It is guaranteed that s is a valid roman numeral in the range [1, 3999].

2.3.1 问题分析

上一个问题的逆向转换，为了让程序跑的快，应该尽可能减少分支。

2.3.2 代码实现

int romanToInt(string s) {
    static int ia[89];
    static bool inited = false;
    if (!inited)
    {
        ia['M'] = 1000;
        ia['D'] = 500;
        ia['C'] = 100;
        ia['L'] = 50;
        ia['X'] = 10;
        ia['V'] = 5;
        ia['I'] = 1;
        inited = true;
    }

    int i = 0;
    int num = 0;
    int n1 = static_cast<int>(s.length()) - 1;
    while (i < n1)
    {
        int idx = s[i];
        int nidx = s[i + 1];
        int v = ia[idx];
        int nv = ia[nidx];
        if (v >= nv)
        {
            num += v;
            ++i;
        }
        else
        {
            num += nv - v;
            i += 2; // consumed two chars
        }
    }

    if (i == n1)
    {
        num += ia[static_cast<int>(s[n1])];
    }

    return num;
}

Result:

Runtime: 16 ms, faster than 52.66% of C++ online submissions for Roman to Integer.
Memory Usage: 6.1 MB, less than 62.92% of C++ online submissions for Roman to Integer.

2.4 Longest Common Prefix

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 "".

Example 1:
Input: strs = ["flower","flow","flight"]
Output: "fl"

Example 2:
Input: strs = ["dog","racecar","car"]
Output: ""
Explanation: There is no common prefix among the input strings.

Constraints:

1 <= strs.length <= 200

0 <= strs[i].length <= 200

strs[i] consists of only lowercase English letters.

2.4.1 问题分析

非常简单的字符串遍历检查相等的题目。可能的优化包括：

把字符串length()检查单独提出来，减少高频循环体里的if；
在到达一定长度以前，按照long处理检测。

2.4.2 代码实现

string longestCommonPrefix(vector<string>& strs) {
    int ns = static_cast<int>(strs.size());
    int min = INT32_MAX;

    for (int i = 0; i < ns; ++i)
    {
        if (min > static_cast<int>(strs[i].length()))
        {
            min = strs[i].length();
        }
    }

    const long* l0 = reinterpret_cast<const long*>(strs[0].c_str());
    int jIdx = 0;
    for (int left = min; left > 8; left -= 8)
    {
        for (int i = 1; i < ns; ++i)
        {
            if (l0[jIdx] != reinterpret_cast<const long*>(
                    strs[i].c_str())[jIdx])
            {
                left = 0;
                break;
            }
        }
    }

    jIdx *= 8;

    const string &s = strs[0];
    for (; jIdx < min; ++jIdx)
    {
        for (int i = 1; i < ns; ++i)
        {
            if (s[jIdx] != strs[i][jIdx])
            {
                return s.substr(0, jIdx);
            }
        }
    }

    return s.substr(0, min);
}

Result:

Runtime: 3 ms, faster than 91.10% of C++ online submissions for Longest Common Prefix.
Memory Usage: 9.2 MB, less than 45.97% of C++ online submissions for Longest Common Prefix.

2.5 3Sum

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]

Example 2:
Input: nums = []
Output: []

Example 3:
Input: nums = [0]
Output: []

Constraints:

0 <= nums.length <= 3000

-10^5 <= nums[i] <= 10^5

2.5.1 问题分析

对数据排序。

按照三层循环：

第一层循环j从0..N-2;
- 如果 nums[i] > 0, 直接break；
第二层循环开始前，设置k=N-1，之后循环j从i+1..k;
- 如果 nums[i] + nums[j] > 0，直接break；
地三层循环递减k，但保持k > j && nums[k]>-(nums[i] + nums[j]);

可以看出，虽然三层循环，但第二层第三层循环合并从i+1到N，因此时间复杂度依然是O(n^2).

尝试把二/三层循环的迭代用二分搜索实现，性能变差了，估计和测试case、局部性，分支有关。

2.5.2 代码实现

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ret;

    const int n = static_cast<int>(nums.size());
    if (n < 3)
    {
        return ret;
    }

    std::sort(nums.begin(), nums.end());
    if (nums[0] > 0 || nums[n - 1] < 0)
    {
        return ret;
    }

    ret.reserve(nums.size()>>2);

    const int n1 = n - 1;
    const int n2 = n - 2;

    for (int i = 0; i < n2 && nums[i] <= 0; ++i)
    {
        if (i > 0 && nums[i] == nums[i - 1])
        {
            continue; // prevent repeat
        }

        int k = n1;
        for (int j = i + 1; j < k; ++j)
        {
            if (j > i + 1 && nums[j] == nums[j - 1])
            {
                continue; // prevent repeat
            }
            int t = nums[i] + nums[j];
            if (t > 0)
            {
                break; // now at least nums[j] > 0, so nums[x(x>j)] > 0
            }
            t = -t;

            while (k > j && nums[k] > t)
            {
                --k;
            }
            if (j == k)
            {
                break;
            }
            if (nums[k] == t)
            {
                ret.push_back({nums[i], nums[j], t});
            }
        }
    }

    return ret;
}

Result:

Runtime: 111 ms, faster than 68.23% of C++ online submissions for 3Sum.
Memory Usage: 20.1 MB, less than 52.76% of C++ online submissions for 3Sum.

这个是二分搜索的版本：

vector<vector<int>> threeSum(vector<int>& nums) {
    vector<vector<int>> ret;

    const int n = static_cast<int>(nums.size());
    if (n < 3)
    {
        return ret;
    }

    std::sort(nums.begin(), nums.end());
    if (nums[0] > 0 || nums[n - 1] < 0)
    {
        return ret;
    }

    ret.reserve(nums.size()>>2);

    const int n1 = n - 1;
    const int n2 = n - 2;
    int l = 0;
    int r = n1;
    do
    {
        int mid = (l + r + 1) / 2;
        if (nums[mid] < 0)
        {
            l = mid + 1;
        }
        else
        {
            r = mid - 1;
        }
    }
    while (l <= r);
    const int positiveStartIdx = l;

    for (int i = 0; i < n2; ++i)
    {
        int v1 = nums[i];
        if (v1 > 0)
        {
            break;
        }

        if (i > 0 && nums[i] == nums[i - 1])
        {
            // prevent repeat
            continue;
        }

        r = n1;
        for (int j = i + 1; j < n1; ++j)
        {
            if (j > i + 1 && nums[j] == nums[j - 1])
            {
                // prevent repeat
                continue;
            }
            int v2 = nums[j];
            int v3 = v1 + v2;
            if (v3 > 0)
            {
                break;
            }
            v3 = -v3;
            l = std::max(j + 1, positiveStartIdx);
            if (l > r)
            {
                break;
            }
            do
            {
                int mid = (l + r + 1) / 2;
                if (nums[mid] == v3)
                {
                    ret.emplace_back(std::vector<int>{v1, v2, v3});
                    break;
                }
                else if (nums[mid] < v3)
                {
                    l = mid + 1;
                }
                else
                {
                    r = mid - 1;
                }
            } while (l <= r);
        }
    }

    return ret;
}

2.6 3Sum Closest

Given an integer array nums of length n and an integer target, find three integers in nums such that the sum is closest to target.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:
Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:
Input: nums = [0,0,0], target = 1
Output: 0

Constraints:

3 <= nums.length <= 1000

-1000 <= nums[i] <= 1000

-10^4 <= target <= 10^4

2.6.1 问题分析

这个题目和 2.5 非常类似。把等于0的检查替换为检测绝对值是否更小。

一个可能的优化方向，检测sum和target的特征，是否可以通过二分法减少遍历范围。后续抽时间尝试。

2.6.2 代码实现

int threeSumClosest(vector<int>& nums, int target) {
    const int n = static_cast<int>(nums.size());
    const int n1 = n - 1;
    const int n2 = n - 2;

    std::sort(nums.begin(), nums.end());
    int ret = nums[0] + nums[1] + nums[2];
    int absRet = abs(ret - target);

    for (int i = 0; i < n2; ++i)
    {
        if (i > 0 && nums[i] == nums[i - 1])
        {
            continue; // prevent repeat
        }

        int k = n1;
        for (int j = i + 1; j < k; )
        {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum == target)
            {
                return sum; // best match
            }

            if (abs(sum -target) < absRet)
            {
                ret = sum;
                absRet = abs(ret - target);
            }

            if (sum > target)
            {
                --k;
            }
            else
            {
                ++j;
            }
        }
    }

    return ret;
}

2.7 Letter Combinations of a Phone Number

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.

A mapping of digits to letters (just like on the telephone buttons) is given below. Note that 1 does not map to any letters.

Example 1:
Input: digits = "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

Example 2: Input: digits = ""
Output: []

Example 3:
Input: digits = "2"
Output: ["a","b","c"]

Constraints:

0 <= digits.length <= 4

digits[i] is a digit in the range ['2', '9'].

2.7.1 问题分析

生成九宫格字母标，按照字符串遍历处理。

2.7.2 代码实现

vector<string> letterCombinations(string digits) {
    const int n = static_cast<int>(digits.length());
    constexpr const char* ss[] = {
        "abc", "def",
        "ghi", "jkl", "mno",
        "pqrs", "tuv", "wxyz"
    };
    constexpr int ns[] = {
        3, 3,
        3, 3, 3,
        4, 3, 4
    };

    vector<string> ret;

    if (0 == n)
    {
        return ret;
    }

    const int i0 = digits[0] - '2';
    if (1 == n)
    {
        ret.resize(ns[i0]);
        ret[0] += ss[i0][0];
        ret[1] += ss[i0][1];
        ret[2] += ss[i0][2];
        if (ns[i0] == 4)
        {
            ret[3] += ss[i0][3];
        }
        return ret;
    }

    const int i1 = digits[1] - '2';
    int size = ns[i0] * ns[i1];
    if (2 == n)
    {
        ret.resize(size);
        int vi = 0;
        for (int i = 0; i < ns[i0]; ++i)
        {
            for (int j = 0; j < ns[i1]; ++j)
            {
                ret[vi] += ss[i0][i];
                ret[vi] += ss[i1][j];
                ++vi;
            }
        }

        return ret;
    }

    const int i2 = digits[2] - '2';
    size *= ns[i2];
    if (3 == n)
    {
        int size = ns[i0] * ns[i1] * ns[i2];
        ret.resize(size);
        int vi = 0;
        for (int i = 0; i < ns[i0]; ++i)
        {
            for (int j = 0; j < ns[i1]; ++j)
            {
                for (int k = 0; k < ns[i2]; ++k)
                {
                    ret[vi] += ss[i0][i];
                    ret[vi] += ss[i1][j];
                    ret[vi] += ss[i2][k];
                    ++vi;
                }
            }
        }

        return ret;
    }

    const int i3 = digits[3] - '2';
    size *= ns[i3];
    ret.resize(size);
    int vi = 0;
    for (int i = 0; i < ns[i0]; ++i)
    {
        for (int j = 0; j < ns[i1]; ++j)
        {
            for (int k = 0; k < ns[i2]; ++k)
            {
                for (int x = 0; x < ns[i3]; ++x)
                {
                    ret[vi] += ss[i0][i];
                    ret[vi] += ss[i1][j];
                    ret[vi] += ss[i2][k];
                    ret[vi] += ss[i3][x];
                    ++vi;
                }
            }
        }
    }

    return ret;
}

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Letter Combinations of a Phone Number.
Memory Usage: 6.3 MB, less than 99.67% of C++ online submissions for
Letter Combinations of a Phone Number.

2.8 4Sum

Given an array nums of n integers, return an array of all the unique
quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
- 0 <= a, b, c, d < n
- a, b, c, and d are distinct.
- nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Example 1:\\
Input: nums = [1,0,-1,0,-2,2], target = 0\\
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:\\
Input: nums = [2,2,2,2,2], target = 8\\
Output: [[2,2,2,2]]

Constraints:
- 1 <= nums.length <= 200
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9

2.8.1 问题分析

这是 2.5 的扩展题目。后续再写吧。

2.9 Remove Nth Node From End of List

Given the head of a linked list, remove the nth node from the end of the list and return its head.

Example 1:
Input: head = [1,2,3,4,5], n = 2
Output: [1,2,3,5]

Example 2:
Input: head = [1], n = 1
Output: []

Example 3:
Input: head = [1,2], n = 1
Output: [1]

Constraints:

The number of nodes in the list is sz.

1 <= sz <= 30

0 <= Node.val <= 100

1 <= n <= sz

Follow up: Could you do this in one pass?

2.9.1 问题分析

单链表删除某节点的问题。在一轮扫描中检测到倒数第n个节点，还是有点意思的。

先设置next从head开始前进n个节点。之后设置del节点为head，然后让del和next同步前进。当next为nil时，del就是需要删除的节点。

DummyHead是一种工程上好理解的方法，但是用pointer to head的方法可以节省一个dummyHead。

2.9.2 代码实现

ListNode* removeNthFromEnd(ListNode* head, int n) {
    ListNode* next = head;

    // it's safe because 1 <= n <= sz
    for (int i = 0; i < n; ++i)
    {
        next = next->next;
    }

    if (nullptr == next)
    {
        return head->next; // delete head
    }

    ListNode* prevDel = head;

    for (next = next->next; nullptr != next; next = next->next)
    {
        prevDel = prevDel->next;
    }

    prevDel->next = prevDel->next->next;
    return head;
}

Runtime: 6 ms, faster than 59.15% of C++ online submissions for Remove Nth Node From End of List.
Memory Usage: 10.7 MB, less than 74.83% of C++ online submissions for Remove Nth Node From End of List.

2.10 Valid Parentheses

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.

Example 1:
Input: s = "()"
Output: true

Example 2:
Input: s = "()[]{}"
Output: true

Example 3:
Input: s = "(]"
Output: false

Constraints:

1 <= s.length <= 104

s consists of parentheses only '()[]{}'.

2.10.1 问题分析

题目比较简单。性能的关键点有2个：

s.length()不是偶数，必然不匹配，提前返回false；
检测三种括号的分支会引入性能损失，分析特征，提取共性。

2.10.2 代码实现

bool isValid(string s) {
    const int n = static_cast<int>(s.length());
    if (n % 2)
    {
        return false;
    }

    char pair[128];
    pair[')'] = '(';
    pair[']'] = '[';
    pair['}'] = '{';

    vector<char> acc;
    acc.resize(n);
    int csi = 0;

    for (int i = 0; i < n; ++i)
    {
        // reduce branch to optimize performance, check left quickly
        // ( 28 -> 0010,1000 -> 0010,1001 -> & 10 = 00
        // ) 29 -> 0010,1001 -> 0010,1010 -> & 10 = 10
        // [ 5B -> 0101,1011 -> 0101,1100 -> & 10 = 00
        // ] 5D -> 0101,1101 -> 0101,1110 -> & 10 = 10
        // { 7B -> 0111,1011 -> 0111,1100 -> & 10 = 00
        // } 7D -> 0111,1101 -> 0111,1110 -> & 10 = 10
        int v1 = s[i] + 1;
        if ((v1 & 0b10) == 0)
        {
            acc[csi++] = s[i];
        }
        else
        {
            if (0 == csi || acc[csi - 1] != pair[static_cast<int>(s[i])])
            {
                return false;
            }
            --csi;
        }
    }

    return 0 == csi;
}

Result:

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Valid Parentheses.
Memory Usage: 6.3 MB, less than 50.83% of C++ online submissions for Valid Parentheses.

3 Hot 100 21-30

3.1 Merge Two Sorted Lists

You are given the heads of two sorted linked lists list1 and list2.

Merge the two lists in a one sorted list. The list should be made by splicing together the nodes of the first two lists.

Return the head of the merged linked list.

Example 1:
Input: list1 = [1,2,4], list2 = [1,3,4]
Output: [1,1,2,3,4,4]

Example 2:
Input: list1 = [], list2 = []
Output: []

Example 3:
Input: list1 = [], list2 = [0]
Output: [0]

Constraints:

The number of nodes in both lists is in the range [0, 50].

-100 <= Node.val <= 100

Both list1 and list2 are sorted in non-decreasing order.

3.1.1 问题分析

典型的归并排序。

3.1.2 代码实现

ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
    ListNode dummy;
    ListNode* cur = &dummy;

    while (reinterpret_cast<long>(list1) & reinterpret_cast<long>(list2))
    {
        ListNode **next = list1->val <= list2->val ? &list1 : &list2;
        cur->next = *next;
        cur = cur->next;
        (*next) = cur->next;
    }

    cur->next = nullptr != list1 ? list1 : list2;

    return dummy.next;
}

Result:

Runtime: 8 ms, faster than 77.59% of C++ online submissions for Merge Two Sorted Lists.
Memory Usage: 14.7 MB, less than 81.32% of C++ online submissions for Merge Two Sorted Lists.

3.2 Generate Parentheses

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

Example 1:
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:
Input: n = 1
Output: ["()"]

Constraints:

1 <= n <= 8

3.2.1 问题分析

4 Hot 100 31-40

Nothing.

5 Hot 100 41-50

5.1 Trapping Rain Water

https://leetcode.com/problems/trapping-rain-water/

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it can trap after raining.

Example 1:
Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6
Explanation: The above elevation map (black section) is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped.

Example 2:
Input: height = [4,2,0,3,2,5]
Output: 9

Constraints:

n == height.length

1 <= n <= 2 * 104

0 <= height[i] <= 105

5.1.1 问题分析

      |_|
      |_|                |_|
      |_|_|  |_|         |_|
 |_|  |_|_|  |_|_|  |_|  |_|
h 1  0 4 2  0 2 1  0 1  0 3
i 0  1 2 3  4 5 6  7 8  9 10

|
|
|           |--|
|--|        |  |
|  |  |--|  |  |
|  |  |  |  |  |
-----------------------------------------

观察特征：从index=0开始向右遍历，先找到第一个height[idx+1]比height[idx]大的位置，作为左边界，并把每个height[idx]保存进去。继续向右遍历，找到下一个height[idx]大于 height[idx+1]的位置，则height[idx+1]是结束位置，计算这个区间内的雨水量。

为了一遍计算，需要把所有内部高度高度累加起来。

6 贪心算法

理论介绍

算法导论第16章专门论述了贪心算法。其基本步骤如下：

将最优化问题转换为，对其做出一次选择后，只剩下一个子问题需要求解；
证明做出贪心选择后，原问题总是存在最优解，即贪心选择总是安全的；
证明做出贪心选择后，剩余的子问题满足性质：最优解与子问题组合，即可得到原问题最优解，这样就得到了最优子结构。

贪心算法与动态规划的区别，是动态规划是自底向上的，先求解子问题的解，再求解较大子问题的解，较大子问题解一般依赖一个或多个较小子问题的解。贪心算法是总是做出最优选择，之后求解剩下的唯一子问题。贪心算法选择时可能依赖之前已经做出的选择，但不依赖任何将来的选择或子问题的解。

最优子结构性质：如果一个问题的最优解包含其子问题的最优解，则称此问题具有最优子结构。

贪心问题可以解决分数背包问题，0-1背包问题需要用动态规划。霍夫慢编码适用贪心算法。

6.1 盛最多水的容器

Top 100 已经做过这个题目：2.1.

Leet Code

目录

Introduction

有趣的题目

1 Hot 100 1-10

1.1 Two sum

1.1.1 Method1 : Brute Force

1.1.2 Method2 : Hash Map

1.1.3 Optimize Performance

1.2 Add Two Numbers

1.2.1 Implement

1.3 Longest Substring Without Repeating Characters

1.4 Median of Two Sorted Arrays

1.4.1 代码实现

1.5 Longest Palindromic Substring

1.5.1 暴力遍历

1.5.2 动态规划

1.5.3 Manacher算法

1.6 Zigzag Conversion

1.6.1 问题分析

1.6.2 代码实现

1.7 Reverse Integer

1.7.1 问题分析

1.7.2 代码实现

1.8 String to Integer (atoi)

1.8.1 问题分析

1.8.2 代码实现

1.9 Palindrome Number

1.9.1 问题分析

1.9.2 实现代码

1.10 Regular Expression Matching

1.10.1 问题分析

1.10.2 代码实现 - 动态规划

1.10.3 代码实现 - 递归调用

2 Hot 100 11-20

2.1 Container With Most Water

2.1.1 问题分析

2.1.2 代码实现

2.2 Integer to Roman

2.2.1 问题分析

2.2.2 代码实现

2.3 Roman to Integer

2.3.1 问题分析

2.3.2 代码实现

2.4 Longest Common Prefix

2.4.1 问题分析

2.4.2 代码实现

2.5 3Sum

2.5.1 问题分析

2.5.2 代码实现

2.6 3Sum Closest

2.6.1 问题分析

2.6.2 代码实现

2.7 Letter Combinations of a Phone Number

2.7.1 问题分析

2.7.2 代码实现

2.8 4Sum

2.8.1 问题分析

2.9 Remove Nth Node From End of List

2.9.1 问题分析

2.9.2 代码实现

2.10 Valid Parentheses

2.10.1 问题分析

2.10.2 代码实现

3 Hot 100 21-30

3.1 Merge Two Sorted Lists

3.1.1 问题分析

3.1.2 代码实现

3.2 Generate Parentheses

3.2.1 问题分析

4 Hot 100 31-40

5 Hot 100 41-50

5.1 Trapping Rain Water

5.1.1 问题分析

6 贪心算法

理论介绍

6.1 盛最多水的容器