- 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
题意：判断两棵二叉树是不是完全相同的
思路：简单的分治
