这次比赛对python不友好啊，第三题在比赛的时候一直TLE，比赛结束后用C++实现同样的算法就过了😭

第一题Longest Continuous Increasing Subsequence

给定一个数组，找出连续严格递增子数组的最大长度。

扫描一遍数组即可：如果nums[i], nums[i+1], ..., nums[j-1]是当前最长严格递增子数组，下次扫描的时候可以直接从j开始。

class Solution(object):
    def findLengthOfLCIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        ans = i = 0
        while i < len(nums):
            j = i + 1
            while j < len(nums) and nums[j] > nums[j-1]:
                j += 1
            ans = max(ans, j-i)
            i = j
        return ans

第二题Implement Magic Dictionary

给定一个没有重复的单词列表。问给定的另一个单词在修改某个字母之后（必须修改一个字母）是否在单词列表中。
class MagicDictionary(object):

    def __init__(self):
        """
        Initialize your data structure here.
        """
        self.words = set()


    def buildDict(self, dict):
        """
        Build a dictionary through a list of words
        :type dict: List[str]
        :rtype: void
        """
        self.words = set(dict)


    def search(self, word):
        """
        Returns if there is any word in the trie that equals to the given word after modifying exactly one character
        :type word: str
        :rtype: bool
        """
        for i in xrange(len(word)):
            for j in xrange(26):
                c = chr(ord('a')+j)
                if c == word[i]:
                    continue
                tmp = word[:i] + c + word[i+1:]
                if tmp in self.words:
                    return True
        return False



# Your MagicDictionary object will be instantiated and called as such:
# obj = MagicDictionary()
# obj.buildDict(dict)
# param_2 = obj.search(word)

第三题Cut Off Trees for Golf Event

给定一个 n x m 的二维数组，0代表不可到达的地方，1或以上代表可以通行的地方（每个大于1的数字最多出现一个）。现在从(0, 0)出发，要求从小到大依次走遍所有大于1的地方。求完成此要求的最短路径长度。

因为n和m都小于或等于50，所以O(n2m2)应该可以接受的。但是实际情况是python实现会TLE。

O(n2m2)算法：因为每个点最多跟四个点相邻，所以用BFS写最短路径的算法复杂度是O(nm)。从(0, 0)出发，从小到大遍历所有点需要求O(nm)条最短路径。为了快速从小到大遍历所有点，我们需要将所有大于1的点从小到大先排好序。

class Node {
public:
    int x, y, v;
    Node(int a=0, int b=0, int c=0): x(a), y(b), v(c) {}
};


class Solution {
public:
    int cutOffTree(vector<vector<int>>& forest) {
        int n = forest.size(), m = forest[0].size();
        int ans = 0;
        vector<Node> order;

        for (int i = 0; i < n; i ++)
            for (int j = 0; j < m; j ++)
                if (forest[i][j] > 1)
                    order.push_back(Node(i, j, forest[i][j]));

        sort(order.begin(), order.end(), [](const Node& lhs, const Node &rhs)->bool {
            return lhs.v < rhs.v;
        });

        int x = 0, y = 0;
        for (auto p: order) {
            int v = shortestPath(x, y, p.x, p.y, forest);
            if (v == -1)
                return -1;
            ans += v;
            x = p.x;
            y = p.y;
        }
        return ans;
    }

    int shortestPath(int i, int j, int k, int l, vector<vector<int>>& forest) {
        int dx[4] = {1, -1, 0, 0};
        int dy[4] = {0, 0, 1, -1};
        int n = forest.size(), m = forest[0].size();
        vector<Node> stack;
        unordered_set<int> visited;

        stack.push_back(Node(i, j, 0));
        visited.insert(i*m + j);
        for (int cur = 0; cur < stack.size(); cur ++) {
            Node p = stack[cur];
            if (p.x == k && p.y == l)
                return p.v;
            for (int d = 0; d < 4; d ++) {
                int nx = p.x+dx[d];
                int ny = p.y+dy[d];
                if (nx < 0 || ny < 0 || nx >= n || ny >= m)
                    continue;
                if (forest[nx][ny] == 0 || visited.find(nx*m + ny) != visited.end())
                    continue;
                visited.insert(nx*m +ny);
                stack.push_back(Node(nx, ny, p.v+1));
            }
        }
        return -1;
    }
};

第四题Number of Longest Increasing Subsequence

给定一个数组，找出所有最长递增子序列的数目。

经典的动态规划了，不过现在需要找出所有最长递增子序列的数目。下面的程序用我用dp[i]表示以nums[i]结尾的最长递增子序列的长度，f[i]表示以num[i]结尾最长递增子序列的个数。

class Solution(object):
    def findNumberOfLIS(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        if len(nums) == 0:
            return 0
        dp = [1] * len(nums)
        f = [1] * len(nums)
        ans = ml = 1
        for i in xrange(1, len(nums)):
            for j in xrange(i):
                if nums[j] < nums[i]:
                    if dp[j] + 1 > dp[i]:
                        dp[i] = dp[j] + 1
                        f[i] = f[j]
                    elif dp[j] + 1 == dp[i]:
                        f[i] += f[j]
            if dp[i] > ml:
                ml = dp[i]
                ans = f[i]
            elif dp[i] == ml:
                ans += f[i]
        return ans
leetcode contest