Kelvin的胡言乱语

==============> 重剑无锋，大巧不工。

LeetCode题解

之前无数的事实证明，我是一个挖坑的好手。。。这又是一个无比大的坑，不求其它，只求能填上。。。挖坑不填是SB。。。

Two Sum

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

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

Input: numbers={2, 7, 11, 15}, target=9 Output: index1=1, index2=2

最简单的想法，自然是两层for循环数组，一个个去加了试： 

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> vec;
        for (int i = 0; i < nums.size(); ++i) {
            for (int j = i + 1; j < nums.size(); ++j) {
                if (nums[i] + nums[j] == target) {
                    vec.push_back(i + 1);
                    vec.push_back(j + 1);
                    return vec;
                }
            }
        }

        return vec;
    }
};

但结果可想而知，时间超时了。。。这个复杂度是平方级别，看来是不满足要求。经过思考，觉得先给数组排个序会比较好，再查找的话，可以用二分搜索： 

class Solution {
public:
    struct entity {
        int num;
        int index;

        entity(int n, int i) : num(n), index(i) {}

        bool operator<(const entity& that) const {
            return this->num < that.num;
        }
    };

    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> ret;

        vector<entity> sorted_num;
        for (int i = 0; i < nums.size(); ++i)
            sorted_num.push_back(entity(nums[i], i + 1));
        sort(sorted_num.begin(), sorted_num.end());

        vector<entity>::iterator it, end;
        for (it = sorted_num.begin(), end = sorted_num.end(); it != end;) {
            int op = target - it->num;
            vector<entity>::iterator op_it = lower_bound(++it, end, entity(op, 0));
            if (op_it->num == op) {
                --it;

                int idx1 = it->index;
                int idx2 = op_it->index;
                if (idx1 > idx2)
                    swap(idx1, idx2);

                ret.push_back(idx1);
                ret.push_back(idx2);
                return ret;
            }
        }

        return ret;
    }
};

经过改造之后，时间复杂度降到了O(nlogn)级别，所以通过了，这个理论上应该不会有更低的复杂度了，毕竟要遍历一遍。。。

Add Two Numbers

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

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4) Output: 7 -> 0 -> 8

这个题目应该是很简单的，创建一个循环直到两个链表都空了为止，每个循环把两个数加起来，如果有进位，标记一下，下一轮进位。需要注意的是，在循环结束之后，如果还有进位，记得增加一个值为1的结点。代码如下： 

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        bool carry = false;
        ListNode dummy(-1);
        ListNode *last = &dummy;

        while (true) {
            if (!l1 && !l2)
                break;

            int val1 = l1 ? l1->val : 0;
            int val2 = l2 ? l2->val : 0;

            int sum = val1 + val2;
            if (carry) {
                sum += 1;
                carry = false;
            }

            if (sum >= 10) {
                sum -= 10;
                carry = true;
            }

            last->next = new ListNode(sum);
            last = last->next;

            l1 = l1 ? l1->next : NULL;
            l2 = l2 ? l2->next : NULL;
        }

        if (carry)
            last->next = new ListNode(1);

        return dummy.next;
    }
};

其实还有一个更好一点的解法：在一个链表结束后，直接把另外一个长链表剩下的部分挂到结果链表上，处理好进位即可。

Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

这个是查找字符串中最长无重复字符字串的问题。可以假设我已经有一个最长无重复的子串，那么下一步如何做？自然是判断下一个字符在这个子串里有没有，如果没有，加入这个字符，继续查找下一个；如果有，那么就把当前串里这个字符及以前的部分切掉，剩下的仍然是一个无重复的最大子串，继续查找下一个即可。但有一个关键点是，如果高效查找这个子串里是不是已经存在某个字符。简单的自然是循环一遍，不过因为字符数量有限，我采用了数组保存的方式，这样查找就能降到O(1)级别。代码如下： 

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int start = 0;
        int end = 0;
        int longest = 0;

        int position[256] = {0};

        while (end < s.length()) {
            char c = s[end];
            int& pos = position[c];
            if (pos) {
                int len = end - start;
                if (len > longest)
                    longest = len;

                int old_start = start;
                start = pos;

                for (int i = old_start; i < pos; ++i)
                    position[s[i]] = 0;
            }

            pos = end + 1;
            ++end;
        }

        int len = end - start;
        if (len > longest)
            longest = len;

        return longest;
    }
};

其中 position[256] 保存了字符在串中的位置，但因为0被用来表示没有出现，所以位置就只能从1开始了，所以那个 pos = end + 1; 看起来就会比较别扭。。。

Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 of size m and n respectively. Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

题目的意思是，找两个已经排序的数组的中位数，要求时间复杂度是O(log(m+n))。突然间觉得好对不起我的高中数学老师，我竟然不知道中位数是怎么算的了，google了一下才知道，对一个排好序的数列，如果项数是奇数项，中位数就是最中间的数；如果项数是偶数项，中位数就是最中间两个数的平均数。不过，下面的叙述中，为了方便理解，我们以奇数项为例，偶数项其实是一样，不过因为偶数项的中位数要涉及两个数，所以叙述上要麻烦一些。

这个题目明确标明了是Hard，这也是这几题遇到的第一个Hard级别的题。如果将两个数混在一起排好序，取中间就可以了，但这样必然要到排序O(nlog(m+n))的复杂度，达不到要求。要达到O(log(m+n))的复杂度，必然要针对两个数组使用类似二分查找的算法才能满足。仔细分析了一下，发现我们的需求其实是淘汰掉两个数组中大约一半的最小的数，然后剩下的第一个数就是中位数。记要淘汰的个数为C，那么这个C应该等于(m+n)/2。如何淘汰呢？我们采用二分查找的方式：分别找到数组A、B中的第C/2个数，然后比较，如果A[C/2]大于B[C/2]，那么就直接把数组B中C/2及以前的数都淘汰掉，反之就淘汰掉A中C/2及以前的数。然后C减去已淘汰的个数，继续上述过程，直到C为0为止。那么剩下的两个数组中，最小的数就是中位数。当然，如果数组整体长度不够，就用整体长度来代替C/2。

这个做法的正确性可以采用反证法很好地证明：假设A[C/2] > B[C/2]，于是在淘汰B中的C/2个数时，淘汰了我们需要的中位数，那么这个数的位置P必然小于等于C/2，因为按照我们前面的约定，要淘汰掉C个数然后剩下的第一个才是中位数，那么我们就要找到C个小于等于B[P]的数才行。在B中，能淘汰的数是P-1个，要小于C/2，那么必然要求在A中淘汰大于C/2个数。但我们已经知道，A[C/2] > B[C/2] >= B[P]，那么A中自然是没有足够的数供淘汰的，于是正确性得证。

实现代码如下，因为要不停地去判断是偶数项还是奇数项，还要判断数组长度，所以代码写得比较乱： 

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size() + nums2.size();
        int before = (total - 1) / 2;

        int start1 = 0;
        int start2 = 0;

        while (before > 1) {
            if (start1 >= nums1.size()) {
                start2 += before;
                if (total % 2 == 0)
                    return (nums2[start2] + nums2[start2 + 1]) * 1.0 / 2;
                else
                    return nums2[start2];
            }

            if (start2 >= nums2.size()) {
                start1 += before;
                if (total % 2 == 0)
                    return (nums1[start1] + nums1[start1 + 1]) * 1.0 / 2;
                else
                    return nums1[start1];
            }

            int count = before / 2;
            int actual1, n1;
            int actual2, n2;

            int size1 = nums1.size() - start1;
            int size2 = nums2.size() - start2;

            if (count >= size1) {
                actual1 = size1;
                n1 = nums1.back();
            } else {
                actual1 = count;
                n1 = nums1.at(start1 + count - 1);
            }

            if (count >= size2) {
                actual2 = size2;
                n2 = nums2.back();
            } else {
                actual2 = count;
                n2 = nums2.at(start2 + count - 1);
            }

            if (n1 > n2) {
                start2 += actual2;
                before -= actual2;
            } else {
                start1 += actual1;
                before -= actual1;
            }
        }

        if (before == 1) {
            if (start1 >= nums1.size())
                start2 += 1;
            else if (start2 >= nums2.size())
                start1 += 1;
            else {
                if (nums1[start1] > nums2[start2])
                    start2 += 1;
                else
                    start1 += 1;
            }

            before = 0;
        }

        if (total % 2 == 0) {
            if (start1 >= nums1.size())
                return (nums2[start2] + nums2[start2 + 1]) * 1.0 / 2;
            else if (start2 >= nums2.size())
                return (nums1[start1] + nums1[start1 + 1]) * 1.0 / 2;
            else {
                int m1, m2;
                if (nums1[start1] > nums2[start2]) {
                    m1 = nums2[start2];
                    start2 += 1;
                } else {
                    m1 = nums1[start1];
                    start1 += 1;
                }

                if (start1 >= nums1.size())
                    m2 = nums2[start2];
                else if (start2 >= nums2.size())
                    m2 = nums1[start1];
                else {
                    if (nums1[start1] > nums2[start2])
                        m2 = nums2[start2];
                    else
                        m2 = nums1[start1];
                }

                return (m1 + m2) * 1.0 / 2;
            }
        } else {
            if (start1 >= nums1.size())
                return nums2[start2];
            else if (start2 >= nums2.size())
                return nums1[start1];
            else {
                if (nums1[start1] > nums2[start2])
                    return nums2[start2];
                else
                    return nums1[start1];
            }
        }
    }
};

Longest Palindromic Substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

题目的意思是找字符串中最长的回文字符串。初步想法是遍历字符串，然后以当前字符为中轴，同时向前向后进行匹配，找到最长的回文串。感觉应该还有更简单更高效的做法，但目前还没想出来。。代码如下： 

class Solution {
public:
    string longestPalindrome(string s) {
        int longest_start = 0;
        int longest_length = 0;

        int pos = 0;
        while (pos < s.length()) {
            int next = pos + 1;
            int back = pos;
            int start = pos;
            int length = 0;
            while (next < s.length() && back >= 0) {
                if (s[next] == s[back]) {
                    start = back;
                    length += 2;
                    --back;
                    ++next;
                    continue;
                }

                break;
            }

            if (length == 0)
                length = 1;

            if (length > longest_length) {
                longest_start = start;
                longest_length = length;
            }

            next = pos + 1;
            back = pos - 1;
            start = pos;
            length = 1;
            while (next < s.length() && back >= 0) {
                if (s[next] == s[back]) {
                    start = back;
                    length += 2;
                    --back;
                    ++next;
                    continue;
                }

                break;
            }

            if (length > longest_length) {
                longest_start = start;
                longest_length = length;
            }

            ++pos;
        }

        return s.substr(longest_start, longest_length);
    }
};

补充：后来在看到《算法导论》的动态规划的时候，有一道习题就是这个，当时想：哇，可以用动态规划解耶！于是苦苦思索，终于想出解法，其实关键就是将子串是否是回文的信息存下来，供父串来判断。本来以为性能会比前面的算法好，但没想到却比前面的算法要差不少，因为要双重for循环，所以是O(n^2)级，确实是要差一些。代码如下： 

class Solution {
public:
    static const int max_length = 1001;

    bool isPalindrome(const string& s, int start, int count, char *array) {
        char *c = (array + start * max_length) + count;
        if (*c == 1)
            return true;

        if (*c == -1)
            return false;

        if (s.at(start) != s.at(start + count - 1))
            return false;

        if (isPalindrome(s, start + 1, count - 2, array)) {
            *c = 1;
            return true;
        } else {
            *c = -1;
            return false;
        }
    }

    string longestPalindrome(string s) {
        if (s.empty())
            return s;

        char array[max_length][max_length];
        memset(array, 0x00, sizeof(array));

        for (int i = 0; i < s.length(); ++i) {
            array[i][0] = 1;
            array[i][1] = 1;
        }

        int start = 0;
        int count = 1;
        for (int i = 0; i < s.length(); ++i) {
            for (int j = i + 1; j < s.length(); ++j) {
                int len = j - i + 1;
                if (len < count)
                    continue;
                if (isPalindrome(s, i, len, (char *) array)) {
                    if (len > count) {
                        start = i;
                        count = len;
                    }
                }
            }
        }

        return s.substr(start, count);
    }
};

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 text, int nRows);

convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".

题目的意思是，把一个字符串折成锯齿状，然后再按行返回。这是目前为止第一个标记为Easy的题目，实际也确实比较简单，找到规律即可。其实可以发现：对于每一行的下一个字符的位置，都可以根据当前位置算出来，比如对于顶点，同一行的两个顶点之间，除了两个顶点行之外，其它行上的点都重复了两遍，再加上不重复的两个顶点即可，即：(n-2)*2+2。不是顶点的点同样可以用类似的方法推导出。所以只要知道了每行第一个点的位置就好办了，而每行第一个点的位置就是行数所对应的点。代码如下： 

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1 || s.length() <= numRows)
            return s;

        string result;
        result.reserve(s.length());

        const int n = numRows;

        for (int i = 0; i < n; ++i) {
            int next = i;
            bool down = true;
            while (next < s.length()) {
                result.push_back(s[next]);

                if (i == 0 || i == n - 1) {
                    // next += (n - 1 - 1) * 2 + 2;
                    next += (n - 1) << 1;
                    continue;
                }

                if (down)
                    // next += (n - i - 1 - 1) * 2 + 2;
                    next += (n - i - 1) << 1;
                else
                    // next += (i - 1) * 2 + 2;
                    next += i << 1;

                down = !down;
            }
        }

        return result;
    }
};

Reverse Integer

Reverse digits of an integer.

Example1: x = 123, return 321 Example2: x = -123, return -321

题目的意思很简单，反转一个整型数并返回。但这个问题关键并不是考算法，而是在考一些边缘情况，比方说反转后溢出的问题。不说了，提交了两次都被坑，第三次才通过，代码如下： 

class Solution {
public:
    int reverse(int x) {
        int max = static_cast<int>(static_cast<unsigned int>(-1) >> 1);
        if (x == max + 1)
            return 0;

        bool negative = false;
        if (x < 0) {
            negative = true;
            x = -x;
        }

        int max_high = max / 10;
        int max_low  = max % 10;

        int ret = 0;

        int num = 0;
        while (x != 0) {
            num = x % 10;
            x /= 10;

            if (ret > max_high || (ret == max_high && num > max_low))
                return 0;

            ret = ret * 10 + num;
        }

        if (negative)
            ret = -ret;

        return ret;
    }
};

String to Integer (atoi)

Implement atoi to convert a string to an integer.

Hint: Carefully consider all possible input cases. If you want a challenge, please do not see below and ask yourself what are the possible input cases.

Notes: It is intended for this problem to be specified vaguely (ie, no given input specs). You are responsible to gather all the input requirements up front.

这个题目也很简单，实现一个 atoi 函数，但是和上一题一样，关键不是考算法，而是考一些边缘情况，比方说溢出以及无效字符。代码如下： 

class Solution {
public:
    enum state {
        prefix,
        number
    };

    int myAtoi(string str) {
        const int max = static_cast<int>(static_cast<unsigned int>(-1) >> 1);
        const int max_high = max / 10;
        const int max_low  = max % 10;
        int ret = 0;
        bool positive = true;
        state s = prefix;
        for (int i = 0; i < str.length(); ++i) {
            char c = str[i];
            switch (s) {
            case prefix: {
                if (c == ' ' || c == '\t' || c == '\n' || c == '\r')
                    break;

                if (c == '+') {
                    s = number;
                    break;
                }

                if (c == '-') {
                    positive = false;
                    s = number;
                    break;
                }

                if (c >= '0' && c <= '9') {
                    ret = ret * 10 + c - '0';
                    s = number;
                    break;
                }

                return 0;
            }
            case number: {
                if (c < '0' || c > '9')
                    goto end;

                if (ret > max_high)
                    return positive ? max : max + 1;

                if (ret == max_high && (c - '0') > max_low)
                    return positive ? max : max + 1;

                ret = ret * 10 + c - '0';
                break;
            }
            default:
                break;
            }
        }

    end:

        if (!positive) {
            ret = -ret;
        }

        return ret;
    }
};

Palindrome Number

Determine whether an integer is a palindrome. Do this without extra space.

这个题目也很简单，判断一个数字是否是回文数，但有一个关键点是，要求不能分配多余的空间。其实这个是有一点模糊的，因为多余的空间也没有指明是堆空间还是连栈空间都不能分配。前面有一个题目是反转数字，这个题目可以用到，将这个数字反转，如果和原来的数字相同，那么肯定是回文数，反之就不是。不过，前面那个反转需要考虑是否溢出的问题，这里就不需要，如果一个数字是回文数，那反转后因为是它本身，所以肯定不会溢出；如果反转后溢出了，那原来的数字肯定不是回文数。不过，因为考虑到原来的算法需要分配栈空间去保存临时变量，于是我改造了一个递归的版本（这其实不过是自欺欺人：难道函数调用的栈帧分配就不是多余空间吗。。），不过好歹是通过了测试，代码如下： 

class Solution {
public:
    int reverse(int x) {
        if (x == 0) return 0;
        return (x % 10) * static_cast<int>(pow(10, static_cast<int>(log10(x)))) + reverse(x / 10);
    }

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

        return x == reverse(x);
    }
};

Regular Expression Matching

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

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

The function prototype should be: bool isMatch(const char *s, const char *p)

Some examples: isMatch("aa","a") → false isMatch("aa","aa") → true isMatch("aaa","aa") → false isMatch("aa", "a*") → true isMatch("aa", ".*") → true isMatch("ab", ".*") → true isMatch("aab", "c*a*b") → true

这个题目要实现一个正则表达式引擎，比较难，但还好内容比较少，只需要处理普通字符和'.'以及'*'就可以了。正则表达式需要用到NFA和DFA，以及NFA朝DFA的转换，之前没有系统地学习过这方面的知识，所以下面的实现参考了 这篇文章 和 这篇文章 。代码如下： 

class state;
typedef std::set<state*> state_set;
typedef std::vector<state*> state_vector;
typedef std::map<char, state_vector> trans_map;
typedef std::map<state*, state_set> dfa_map;

static const int episilon_transition = 0;

class state {
public:
    state(bool accepting) : accept_(accepting) {}

    void add_transition(char c, state *s) {
        // disable this test to increase performance
        // if (c != episilon_transition) {
        //     auto it = trans_.find(c);
        //     assert(it == trans_.end());
        // }

        trans_[c].push_back(s);
    }

    bool accepting() const { return accept_; }
    void set_accepting(bool accepting) { accept_ = accepting; }

    bool epsilon_closure(state_set& closure) {
        if (closure.find(this) != closure.end()) return accept_;

        closure.insert(this);

        auto it = trans_.find(episilon_transition);
        if (it == trans_.end()) return accept_;

        bool accept = accept_;
        for (auto& s : it->second) {
            if (closure.find(s) == closure.end())
                if (s->epsilon_closure(closure) && !accept)
                    accept = true;
        }

        return accept;
    }

    void move(char c, state_set& states) {
        auto it = trans_.find(c);
        if (it == trans_.end()) return;

        for (auto& s : it->second)
            states.insert(s);
    }

    const state_vector *next(char c) {
        auto it = trans_.find(c);
        if (it == trans_.end())
            return nullptr;

        return &(it->second);
    }

private:
    bool accept_;
    trans_map trans_;
};

class regexp_engine {
public:
    regexp_engine(const std::string& pattern)
        : nfa_start_(nullptr), dfa_start_(nullptr) {
        build_nfa(pattern);
        build_dfa();
    }

    ~regexp_engine() {
        for (auto& s : all_states_) delete s;
    }

    bool match(const std::string& str) {
        state *s = dfa_start_;
        for (size_t i = 0; i < str.length(); ++i) {
            char c = str.at(i);

            const state_vector *next = s->next(c);
            if (!next) return false;

            assert(next->size() == 1);
            s = next->at(0);
        }

        return s->accepting();
    }

private:
    state *new_state(bool accepting) {
        state *s = new state(accepting);
        all_states_.push_back(s);
        return s;
    }

    bool epsilon_closure(const state_set& states, state_set& closure) {
        bool accept = false;
        for (auto& s : states) {
            if (s->epsilon_closure(closure))
                accept = true;
        }
        return accept;
    }

    void move(char c, const state_set& current_closure,
              state_set& next_closure, bool& accept) {
        state_set next;
        for (auto& s : current_closure) {
            s->move(c, next);
        }
        accept = epsilon_closure(next, next_closure);
    }

    bool equal(const state_set& closure1, const state_set& closure2) {
        if (closure1.size() != closure2.size()) return false;

        auto end2 = closure2.end();
        for (auto& s : closure1) {
            if (closure2.find(s) == end2)
                return false;
        }
        return true;
    }

    void dfa_scan(const state_set& current_closure,
                  dfa_map& dstate2nstates, state *current_state) {
        for (char c : inputs_) {
            state_set next_closure;
            bool accept = false;
            move(c, current_closure, next_closure, accept);
            if (!next_closure.empty()) {
                bool exists = false;
                for (auto& it : dstate2nstates) {
                    if (equal(next_closure, it.second)) {
                        current_state->add_transition(c, it.first);
                        if (accept) it.first->set_accepting(true);

                        exists = true;
                        break;
                    }
                }

                if (!exists) {
                    state *s = new_state(accept);
                    current_state->add_transition(c, s);
                    dstate2nstates[s] = next_closure;
                    dfa_scan(next_closure, dstate2nstates, s);
                }
            }
        }
    }

    void build_dfa() {
        state_set init_closure;
        bool accept = nfa_start_->epsilon_closure(init_closure);

        dfa_map dstate2nstates;
        dfa_start_ = new_state(accept);
        dstate2nstates[dfa_start_] = init_closure;

        dfa_scan(init_closure, dstate2nstates, dfa_start_);
    }

    void build_nfa(const std::string& regexp) {
        nfa_start_ = new_state(false);
        state *s = nfa_start_;
        state *e = nfa_start_;

        for (size_t i = 0; i < regexp.length(); ++i) {
            char c = regexp.at(i);

            if (c == '*') {
                s->add_transition(episilon_transition, e);
                e->add_transition(episilon_transition, s);
            } else if (c == '.') {
                state *start = new_state(false);
                state *end = new_state(false);

                for (char x = 'a'; x <= 'z'; ++x) {
                    start->add_transition(x, end);
                    inputs_.insert(x);
                }
                for (char x = 'A'; x <= 'Z'; ++x) {
                    start->add_transition(x, end);
                    inputs_.insert(x);
                }

                e->add_transition(episilon_transition, start);
                s = start;
                e = end;
            } else {
                state *start = new_state(false);
                state *end = new_state(false);
                start->add_transition(c, end);

                e->add_transition(episilon_transition, start);
                s = start;
                e = end;

                inputs_.insert(c);
            }
        }

        e->set_accepting(true);
    }

private:
    state *nfa_start_;
    state *dfa_start_;
    std::set<char> inputs_;
    state_vector all_states_;
};

class Solution {
public:
    bool isMatch(string s, string p) {
        regexp_engine re(p);
        return re.match(s);
    }
};

在写完上面这段程序后，因为时间性能表现不佳（毕竟太重量级），我又进行了复盘，发现其实像'.*'和'a*'的DFA都非常简单（a*就是一个状态，然后有一个a路径迁移到自己，并且这个状态是可接受状态），可以人肉构建DFA从而省去从NFA到DFA转换牺牲的性能。基本思路就是一个字符一个字符地解析，遇到'a*'或者'.*'就特殊处理，但程序写完后，发现对于'.*a'处理不了：按照我的思路，应该是一个从a到z迁移到自己的状态，再有一个a路径指向另外一个最终状态，但这其实就是NFA就不是DFA了（因为a路径迁移到了两个状态）。人肉转换后，发现这个DFA其实是两个状态M和N，对于bcd等路径，M迁移到自己，对于a路径，M迁移到N。而对于N来说，对于a路径，迁移到自己，对于bcd等路径，迁移到M，其中N是最终状态。这时我才认识到，表达式前后是互相影响的，并不能简单按单元来分割表达式从而顺序地构造DFA，所以这条路走不通。但在写这个失败程序的过程中，我又发现了另一种思路：虽然不能按单元来顺序构造DFA，但我们可以按单元来顺序匹配，根本不需要构造DFA！例如表达式'.*a'和字符串'ba'，我们可以先匹配'.*'和''，再匹配剩下的'a'和'ba'；发现失败，我们再尝试匹配'.*'和'b'，再匹配剩下的'a'和'a'，发现可以匹配成功了。这样整个代码好懂很多，而且性能有了很大提升。代码如下： 

class Solution {
public:
    bool match(const char *p, const char *s) {
        if (!(*p)) return !(*s);

        if (*p == '*') {
            assert(0);
        } else if (*p == '.') {
            if (*(p + 1) == '*') {
                if (match(p + 2, s))
                    return true;

                while (*s) {
                    if (match(p + 2, ++s))
                        return true;
                }
                return false;
            }
            return *s && match(p + 1, s + 1);
        } else {
            if (*(p + 1) == '*') {
                if (match(p + 2, s))
                    return true;

                while (*s == *p) {
                    if (match(p + 2, ++s))
                        return true;
                }
                return false;
            }
            return (*p == *s) && match(p + 1, s + 1);
        }
    }

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

后来看论坛发现，还有一种用DP解的方式，仔细看了原理，原来是人肉将上面的递归版本改成了迭代版本，大神真是无处不在。。

Container With Most Water

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 line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.

Note: You may not slant the container and n is at least 2.

这个题目的意思是，有一些高度不同的木板，相邻的木板之间的距离都是1，拿两块木板做成一个桶，求这个桶能装的最大的水量。其实所谓的桶只有高度和宽度，没有长度，所以实际上是求矩形面积，矩形的宽度是两块木板的距离，高度是以矮的那一块木板为准。

最原始的思路，当然是brute-force，代码如下： 

class Solution {
public:
    int maxArea(vector<int>& height) {
        int max = 0;
        for (int i = 0; i < height.size(); ++i) {
            for (int j = i + 1; j < height.size(); ++j) {
                int h = std::min(height[i], height[j]);
                int w = j - i;
                int a = h * w;
                if (max < a)
                    max = a;
            }
        }

        return max;
    }
};

代码逻辑正确，但很不幸，超时了。。看来出题者需要比平方级更低的时间复杂度。于是再仔细分析下，发现对于任意一块木板，它所能围成的最大面积，取决于所能达到的最大宽度。这样我们就可以从最矮的木板来：它能达到的最大宽度必然是到最边上的木板的距离（注意有两边，取较大者），那么第二高的也是这样。但如果最矮的是在最边上，那么第二高的就需要先去掉最边上的最矮的这块木板。照着这个思路，有下面的代码： 

class Solution {
public:
    int maxArea(vector<int>& height) {
        std::vector<std::pair<int, int>> height2index;
        height2index.reserve(height.size());

        for (int i = 0; i < height.size(); ++i)
            height2index.push_back(std::make_pair(height[i], i));

        // 从低到高排列
        std::sort(height2index.begin(), height2index.end(),
                  [](const std::pair<int, int>& l, const std::pair<int, int>& r) {
                      if (l.first != r.first) return l.first < r.first;
                      return l.second < r.second;
                  });

        int max = 0;
        int s = 0, e = height.size() - 1;
        for (const auto& it : height2index) {
            int i = it.second;
            int h = it.first;
            int w = std::max(std::abs(i - s), std::abs(i - e));
            max = std::max(max, h * w);

            // 表示下标为i的这块木板用过了，其实应该再需要一个容器，
            // 但为了性能，就复用了height，因为这个vector已经不用了
            height[i] = -1;

            // 对于边上的已经用过的木板，我们需要移
            // 除掉，因为接下来的木板都比用过的要高
            while (s < height.size() && height[s] == -1) ++s;
            while (e >= 0 && height[e] == -1) --e;
        }

        return max;
    }
};

看了论坛，还有一种更巧妙的只需要一层循环的解：假定最大面积就是距离最远的两块木板，如果内部的木板要比这个面积大，因为宽度小了，那么高度必须要比最边上矮的那块高，越朝里循环，高度要求就越来越高，这样就可以跳过许多不必要的计算：实在是妙！

Integer to Roman

Given an integer, convert it to a roman numeral.

Input is guaranteed to be within the range from 1 to 3999.

这个题目还是比较简单的，就是把一个阿拉伯数字转换成罗马数字，并且已经规定了范围在[1, 3999]之内。以前只看过钟表上的罗马数字（只有1-12），所以特地去维基百科查了一下，发现更大的数字的组成规律跟1-10类似。代码如下： 

class Solution {
public:
    std::string intToRoman(int num) {
        if (num >= 1000) {
            int count = num / 1000;
            int left  = num % 1000;

            return std::string(count, 'M') + intToRoman(left);
        }

        if (num >= 900) {
            int left = num % 900;
            return "CM" + intToRoman(left);
        }

        if (num >= 500) {
            int count = num / 100;
            int delta = count - 5;
            int left  = num % (500 + delta * 100);
            return "D" + std::string(delta, 'C') + intToRoman(left);
        }

        if (num >= 400) {
            int left = num % 400;
            return "CD" + intToRoman(left);
        }

        if (num >= 100) {
            int count = num / 100;
            int left  = num % 100;
            return std::string(count, 'C') + intToRoman(left);
        }

        if (num >= 90) {
            int left = num % 90;
            return "XC" + intToRoman(left);
        }

        if (num >= 50) {
            int count = num / 10;
            int delta = count - 5;
            int left  = num % (50 + delta * 10);
            return "L" + std::string(delta, 'X') + intToRoman(left);
        }

        if (num >= 40) {
            int left = num % 40;
            return "XL" + intToRoman(left);
        }

        if (num >= 10) {
            int count = num / 10;
            int left  = num % 10;
            return std::string(count, 'X') + intToRoman(left);
        }

        switch (num) {
        case 9: return "IX";
        case 8: return "VIII";
        case 7: return "VII";
        case 6: return "VI";
        case 5: return "V";
        case 4: return "IV";
        case 3: return "III";
        case 2: return "II";
        case 1: return "I";
        case 0: return "";
        }
    }
};

Roman to Integer

Given a roman numeral, convert it to an integer.

Input is guaranteed to be within the range from 1 to 3999.

这个题目是上一个题目的“反函数”，要求从罗马数字转换成阿拉伯数字，也比较简单，我的实现比较暴力，代码如下： 

class Solution {
public:
    int roman2int(const char *s) {
        int num = 0;

        while (*s == 'M') {
            ++s;
            num += 1000;
        }

        if (*s == 'C' && *(s + 1) == 'M') {
            s += 2;
            num += 900;
        }

        if (*s == 'D') {
            ++s;
            num += 500;
            while (*s == 'C') {
                ++s;
                num += 100;
            }
        }

        if (*s == 'C' && *(s + 1) == 'D') {
            s += 2;
            num += 400;
        }

        while (*s == 'C') {
            ++s;
            num += 100;
        }

        if (*s == 'X' && *(s + 1) == 'C') {
            s += 2;
            num += 90;
        }

        if (*s == 'L') {
            ++s;
            num += 50;
            while (*s == 'X') {
                ++s;
                num += 10;
            }
        }

        if (*s == 'X' && *(s + 1) == 'L') {
            s += 2;
            num += 40;
        }

        while (*s == 'X') {
            ++s;
            num += 10;
        }

        if (*s == 'I' && *(s + 1) == 'X') {
            s += 2;
            num += 9;
        }

        if (*s == 'V') {
            ++s;
            num += 5;
            while (*s == 'I') {
                ++s;
                num += 1;
            }
        }

        if (*s == 'I' && *(s + 1) == 'V') {
            s += 2;
            num += 4;
        }

        while (*s == 'I') {
            ++s;
            num += 1;
        }

        assert(!(*s));
        return num;
    }

    int romanToInt(string s) {
        return roman2int(s.c_str());
    }
};

Longest Common Prefix

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

这个题目也很简单，求一组字符串的最长前缀，代码如下： 

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        if (strs.empty()) return "";
        if (strs.size() == 1) return strs[0];

        const std::string& base = strs[0];
        int pos = 0;

        int min = base.length();
        for (int i = 1; i < strs.size(); ++i)
            if (strs[i].length() < min)
                min = strs[i].length();

        for (pos = 0; pos < min; ++pos) {
            for (int i = 1; i < strs.size(); ++i) {
                if (strs[i][pos] == base[pos])
                    continue;

                return base.substr(0, pos);
            }
        }

        return base.substr(0, pos);
    }
};
2016-01-20 2017-05-09 Algorithm, C++, LeetCode Kelvin Hu

Generated by Emacs 25.x (Org mode 9.x)

Copyright © 2012 - Kelvin Hu   -   Powered by org-page