leetcode轮回计划20181026

91 Decode Ways
题意：给出类似“22726”这种编码的解码方式
思路：简单的动态规划
92 Reverse Linked List II
题意：给定链表和两个整数m和n，翻转链表的第m个节点到第n个节点
思路：背一下吧，这是翻转链表的方程式：

ListNode* next = curr->next;
curr->next = next->next;
next->next = pre->next;
pre->next = next;

Restore IP Address
题意：给定多个数字（多于3个，少于13个），返回所有合法的ip地址，要求用到所有数字。
思路：使用回溯可以解，但是有点儿麻烦
在本题目中，我觉得暴力解法是最好的：

    vector<string> restoreIpAddresses(string s) {
        vector<string> ret;
        string ans;
        
        for (int a=1; a<=3; a++)
        for (int b=1; b<=3; b++)
        for (int c=1; c<=3; c++)
        for (int d=1; d<=3; d++)
            if (a+b+c+d == s.length()) {
                int A = stoi(s.substr(0, a));
                int B = stoi(s.substr(a, b));
                int C = stoi(s.substr(a+b, c));
                int D = stoi(s.substr(a+b+c, d));
                if (A<=255 && B<=255 && C<=255 && D<=255)
                    if ( (ans=to_string(A)+"."+to_string(B)+"."+to_string(C)+"."+to_string(D)).length() == s.length()+3)
                        ret.push_back(ans);
            }    
        
        return ret;
    }

95 Unique Binary Search Trees II
题意：给定n，返回所有的n个节点可能组成的二叉搜索树。要求中序遍历要符合1到n的顺序。
思路：非常典型的分治题目
96 Unique Binary Search Trees
题意：和上题一样的要求，只不过给出的不是全部情况，给出的是数量
思路：简单的动态规划。这道题目也可以使用卡特兰数来求解，代码如下：

int numTrees(int n) {
    //cantalan树
    //C(2n,n)/(n+1)
    long long ans =1;
    for(int i=n+1;i<=2*n;i++){
        ans = ans*i/(i-n);
    }
    return ans/(n+1);
}

98 Validate Binary Search Tree
题意：判断一个给定的二叉搜索树是不是合法的
思路：通过判断该二叉树的中序遍历是不是有序的。
100 Same Tree
题意：判断两棵二叉树是不是完全相同的
思路：简单的分治