emm……结果每个session就一道题？

似乎简单题是30分钟，中等题是40分钟，难题是60分钟，而且还会出来一些写bash的题目之类的。感觉没什么特别的意思，还是去做top interview问题好了。

99

题意

给你一个二叉搜索树，里面两个元素被交换了。请将二叉搜索树复原。

分析

用O(n)的空间复杂度的话，非常直接。对树进行中序遍历，把结果存下来，然后把这个结果排序，和原来比较一下，就知道是哪两个数交换了。于是一遍过。（不需要交换结点，只需要交换值，这一点倒是很简单。）

emm，如果需要常数空间复杂度，那就需要一些其他的比较复杂的遍历方式了（比如Morris Traversal中序遍历），而不是单纯的中序遍历（O(logn)的栈空间）。具体参见https://siddontang.gitbooks.io/leetcode-solution/content/tree/recover_binary_search_tree.html，因为时间紧迫，所以就不写了。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
/*
O(n)空间：把BST的全部元素都提取出来，然后排序；对BST做一个中序遍历，比较哪两个元素有差异。最后换回来。
常数空间的话，其实在中序遍历的过程中就可以判断哪两个元素是逆序的，记录下来
*/
class Solution {
private:
    vector<pair<int, TreeNode*>> curTree;
    
    void midTrav(TreeNode* root) {
        if (root == NULL)
            return;
        midTrav(root->left);
        curTree.push_back(make_pair(root->val, root));
        midTrav(root->right);
    }
    
public:
    void recoverTree(TreeNode* root) {
        midTrav(root);
        vector<pair<int, TreeNode*>> sortedTree(curTree);
        sort(sortedTree.begin(), sortedTree.end());
        
        TreeNode *x = NULL, *y = NULL;
        
        for (int i = 0; i < sortedTree.size(); i++) {
            if (curTree[i].first != sortedTree[i].first || curTree[i].second != sortedTree[i].second) {
                if (x == NULL)
                    x = curTree[i].second;
                else
                    y = curTree[i].second;
            }
        }
        
        swap(x->val, y->val);
    }
};

时间是80.86%。

115

题意

有两个字符串，S和T。计算S中与T相等的子序列的数量。

分析

那么可以用动态规划的想法：对于f[i]，它表示，以S[i]结尾的S的某个子串能够与T的前几个字母匹配。但是这样不好做。不如定义f[i][j]，表示以S[i]结尾的S的子串中，能够与T[0..j]完全匹配的数量。所以我们得到了一个递推方程：f[i][j] = sum(f[k][j - 1] (S[i] == T[j])), k = 0..i-1;，解的时间复杂度大约为O(mn^2)。显然，应用一些简单的部分和知识，这一时间可以缩减到O(mn)。

代码

class Solution {
public:
    int numDistinct(string s, string t) {
        
        if (s.length() < t.length())
            return 0;
        
        int n = s.length(), m = t.length();
        // f[i][j]，表示以S[i]结尾的S的子串中，能够与T[0..j]完全匹配的数量
        int f[n+1][m+1];
        memset(f, 0, sizeof(f));
        
        for (int i = 0; i < n; i++) {
            if (s.substr(i, 1) == t.substr(0, 1))
                f[i][0] = 1;
        }
        
        for (int j = 1; j < m; j++) {
            for (int i = 0; i < n; i++) {
                // f[i][j] = sum(f[k][j - 1] (S[i] == T[j])), k = 0..i-1
                f[i][j] = 0;
                if (s.substr(i, 1) == t.substr(j, 1)) {
                    for (int k = 0; k < i; k++)
                        f[i][j] += f[k][j-1];
                }
            }
        }
        
        int ans = 0;
        for (int i = 0; i < n; i++)
            ans += f[i][m-1];
        return ans;
    }
};

时间为1.38%，毕竟复杂度比较大了。

653

题意

一个二叉搜索树，给定数k，找出其中是否有两个元素的和=k。

分析

此题过于简单了，不过我做得不够聪明。只要把树用中序遍历序列化，然后在两侧用两个指针找就可以了。当然用哈希表也可以。数据似乎过于的弱了，我瞎搞也搞出来了。

代码

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
    vector<int> tree;
    void midTrav(TreeNode* root) {
        if (root == NULL)
            return;
        midTrav(root->left);
        tree.push_back(root->val);
        midTrav(root->right);
    }
    
    bool findVal(TreeNode* root, int val) {
        if (root == NULL)
            return false;
        if (val < root->val)
            return findVal(root->left, val);
        else if (val == root->val)
            return true;
        else
            return findVal(root->right, val);
    }
    
public:
    bool findTarget(TreeNode* root, int k) {
        midTrav(root);
        for (int i = 0; i < tree.size(); i++) {
            if (findVal(root, k - tree[i]) && tree[i] + tree[i] != k)
                return true;
        }
        return false;
    }
};

时间是42.98%。