解码方法
解题思路，这道题很明显是可以用动态规划来解决的。因为当前状态和前一个状态有关，当满足这个条件的时候，可以尝试用动态规划去解决问题。然后解题的关键就在于如何去寻找状态转移公式。
可以想象一下，当新增一个数字的时候，我们总是会把它单独放到前一个答案的后面，然后再次寻找前一个答案能够和新增的数字组成两个数字的解码。所以状态转移就找到了。需要注意的一个地方是需要考虑新增数字为0的时候。
AC代码:
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
if(s[0] == '0') return 0;
if(n == 1) return 1;
vector<int> dp(n, 0);
dp[0] = 1;
int single = 1;
int last = s[0] - '0';
for(int i = 1; i < s.size(); ++i) {
int tmp = s[i] - '0';
if(last*10+tmp > 26) single = 0;
if(tmp == 0) {
dp[i] = single;
single = 0;
last = 0;
}else {
dp[i] = dp[i-1] + single;
last = tmp;
single = dp[i-1];
}
}
return dp[n-1];
}
};
反转链表 II
题目要求一趟扫描，不难想到用双指针的方法。对于链表的操作，最好添加一个头前指针防止出现地址越界错误，这里我们记录需要开始反转的指针，和它前面一个指针，然后对于后面反转的节点进行反转。
AC代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int m, int n) {
if(m == n) return head;
ListNode *res = new ListNode(-1);
res->next = head;
ListNode *pre, *start, *last;
start = res;
for(int i = 0; i < m; ++i) {
pre = start;
start = start->next;
}
ListNode* ope = start->next;
last = start;
while(n-m > 1) {
ListNode* tmp = ope;
ope = ope->next;
tmp->next = start;
start = tmp;
m++;
}
last->next = ope->next;
ope->next = start;
pre->next = ope;
return res->next;
}
};
复原IP地址
解题思路，利用回溯的方法，因为有效的答案由四个整数组成，而每个整数位于0-255，所以我们可以每次拿1-3个位置的数字，循环的拿，然后判断回溯得到答案。
AC代码:
class Solution {
public:
vector<string> res;
void back(string &s, int num, string& path) {
//cout << s << " " << num << " " << path << endl;
if(num == 4) {
if(s.size() == 0) {
path.erase(path.end()-1);
res.push_back(path);
}
return;
}
int l = path.size();
for(int j = 1; j <= 3; ++j) {
if(j <= s.size()) {
string key = s.substr(0, j);
if((key.size() > 1 && key[0] == '0') || stoi(key) > 255) continue;
path += key;
path +='.';
string tmp = s.substr(j, s.size()-j);
back(tmp, num+1, path);
path = path.substr(0, l);
}
}
}
vector<string> restoreIpAddresses(string s) {
if(s.size() == 0 || s.size() > 12) return res;
string p;
back(s, 0, p);
return res;
}
};
二叉树的中序遍历
解题思路，这道题更像是考察知识点的题目，因为关于二叉树的遍历，想必都应该会了解。如果你不知道，不会吧不会吧不会吧! 利用递归是最好理解的，但是题目要求用迭代完成，而又比较知道的是”递归==栈”。
AC代码:
/**
* 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 {
public:
vector<int> res;
void MidOrder(TreeNode *t){
if(t != NULL){
MidOrder(t->left);
res.push_back(t->val);
MidOrder(t->right);
}
}
vector<int> inorderTraversal(TreeNode* root) {
//MidOrder(root);
stack<TreeNode*> stn;
if(root == NULL) return res;
TreeNode* ope = root;
while(ope || !stn.empty()) {
while(ope) {
stn.push(ope);
ope = ope->left;
}
ope=stn.top();
stn.pop();
res.push_back(ope->val);
ope=ope->right;
}
return res;
}
};
不同的二叉搜索树 II
解题思路，刚开始一直死磕回溯，死活解不出不来，郁闷。后面看解析，貌似用递归更好。
AC代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
vector<TreeNode*> dfs(int start, int end) {
vector<TreeNode*> res;
if(start > end) {
return {nullptr};
}
for(int i = start; i <= end; ++i) {
for (auto l : dfs(start, i-1)) {
for (auto r : dfs(i+1, end)) {
TreeNode* current_tree = new TreeNode(i, l, r);
res.push_back(current_tree);
}
}
}
return res;
}
vector<TreeNode*> generateTrees(int n) {
if(n == 0) return {};
return dfs(1, n);
}
};
不同的二叉搜索树
这道题和上面题目的意思是一样的，只不过这道题是输出种类数量，当然我们可以直接用上一道的答案输出容器数量就可以了。但是这道题可以用动态规划的方式去求。
定义数组 :
- G(n): 长度为 n 的序列能构成的不同二叉搜索树的个数。
- F(i, n): 以 i 为根、序列长度为 n 的不同二叉搜索树个数(1≤i≤n)。 初始化 : G(0)=1,G(1)=1
转移方程 : F(i, n)=G(i−1)⋅G(n−i)
答案 : G(n) = F(1, n) + F(2, n) + … + F(n, n);
也就是 : G(n) = G(0)⋅G(n−1) + G(1)⋅G(n−2) + … + G(n−1)⋅G(0);
ps:这个递推公式其实就是卡特兰数点击查看更多
AC代码:
class Solution {
public:
int numTrees(int n) {
vector<int> G(n + 1, 0);
G[0] = 1;
G[1] = 1;
for (int i = 2; i <= n; ++i) {
for (int j = 1; j <= i; ++j) {
G[i] += G[j - 1] * G[i - j];
}
}
return G[n];
}
};
交错字符串
看到这道题，感觉递归就完事了，然后加上一堆if，递归，测试组ac，提交超时，艹。懊悔啊，怎么就要用递归，怎么就没有加备忘录，对于递归不加备忘录真的是大傻x。看到题解之后，发现貌似用动态规划更好解决。所以叛变利用动态规划解题了。
三步走，定义动态规划数组。
定义dp(i, j) 表示 $s_1$ 的前 i 个元素和 $s_2$ 的前 j 个元素是否能交错组成 $s_3$ 的前 i + j 个元素。
初始化: dp(0,0) = 1，dp[0][i:s2]，dp[i:s1][0]
动态转移方程: dp[i][j] = (dp[i-1][j] && (s1[i-1] == s3[i+j-1])) || (dp[i][j-1] && (s2[j-1] == s3[i+j-1]));
AC代码:
class Solution {
public:
bool isInterleave(string s1, string s2, string s3) {
if(s1.size() + s2.size() != s3.size()) return false;
vector<vector<int>> dp(s1.size()+1, vector<int>(s2.size()+1, 0));
int n = s1.size(), m = s2.size();
dp[0][0] = 1;
for(int i = 1; i <= n; ++i) dp[i][0] = dp[i-1][0]&&(s1[i-1] == s3[i-1]);
for(int i = 1; i <= m; ++i) dp[0][i] = dp[0][i-1]&&(s2[i-1] == s3[i-1]);
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= m; ++j) {
dp[i][j] = (dp[i-1][j] && (s1[i-1] == s3[i+j-1])) || (dp[i][j-1] && (s2[j-1] == s3[i+j-1]));
}
}
return dp[n][m];
}
};
验证二叉搜索树
解题思路，一开始走错方向，用队列广度搜索判断每个节点是否二叉搜索树，没有考虑到之前此节点之前的父节点，所以 error 。后面想到有效的二叉搜索树用中序展开就是一个递增的数组序列，那么用中序搜索判断是否递增即可。但是在这个上面遇到了一个恶心的东西，就是最小值初始化，刚开始尝试先迭代找到最小的，然后 -1 就可以得到，但是 [-2147483648] 把人恶心到了。所以参考 LONG_MIN 作为最小值初始化。
AC代码:
/**
* 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 {
public:
bool isValidBST(TreeNode* root) {
if(root == NULL) return true;
stack<TreeNode*> stn;
TreeNode* ope = root;
long long pre = LONG_MIN;
while(ope || !stn.empty()) {
while(ope) {
stn.push(ope);
ope = ope->left;
}
ope=stn.top();
stn.pop();
if(pre >= ope->val) return false;
else pre = ope->val;
ope=ope->right;
}
return true;
}
};
恢复二叉搜索树
**使用 O(n) 空间复杂度的解法很容易实现。
你能想出一个只使用常数空间的解决方案吗？**
解题思路，因为有了中序遍历的思路，其实这道题解题关键在于排序找出逆序对，然后交换两个节点的值就可以，但是我们之前的中序遍历，一是使用递归，二是使用栈迭代，都会消耗O(n)的空间复杂度。如果是常数空间的方案需要用到morris遍历。后续会补充morri遍历的相关介绍。
AC代码:
//利用栈迭代
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
void recoverTree(TreeNode* root) {
TreeNode *first = nullptr, *second = nullptr;
if(root == nullptr) return;
TreeNode* cur = root;
TreeNode* pre = nullptr;
stack<TreeNode*> stn;
while (cur || !stn.empty()){
while(cur) {
stn.push(cur);
cur = cur->left;
}
cur = stn.top();
stn.pop();
//cout << cur->val << " ";
if(pre && pre->val > cur->val) {
if(first == nullptr) first = pre;
second = cur;
}
pre = cur;
cur = cur->right;
}//cout << endl;
//cout << first->val << second->val << endl;
int tmp = first->val;
first->val = second->val;
second->val = tmp;
}
};
相同的树
解题思路，刚开始看到这道题，想到的办法是输出前序和中序，因为这样是可以前中后两个排序就可以确定唯一的树。但是后面想了一下，是不是可以用递归，从头结点开始判断，然后递归判断其左右树。
AC代码:
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
bool isSameTree(TreeNode* p, TreeNode* q) {
if(p == nullptr && q == nullptr) return true;
if(p && q && q->val == p->val) {
return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
}
return false;
}
};
