CONTENTS
LeetCode 91. 解码方法（中等）
【题目描述】
一条包含字母 A-Z 的消息通过以下映射进行了编码：
"1" -> 'A'"2" -> 'B'..."25" -> 'Y'"26" -> 'Z'
然而，在解码已编码的消息时，你意识到有许多不同的方式来解码，因为有些编码被包含在其它编码当中（"2" 和 "5" 与 "25"）。
例如，"11106" 可以映射为：
"AAJF"，将消息分组为(1, 1, 10, 6)；"KJF"，将消息分组为(11, 10, 6)。
消息不能分组为 (1, 11, 06)，因为 "06" 不是一个合法编码（只有 "6" 是合法的）。
注意，可能存在无法解码的字符串。
给你一个只含数字的非空字符串 s，请计算并返回解码方法的总数 。如果没有合法的方式解码整个字符串，返回 0。
题目数据保证答案肯定是一个 32 位的整数。
【示例 1】
输入：s = "12"
输出：2
解释：它可以解码为 "AB"（1 2）或者 "L"（12）。
【示例 2】
输入：s = "226"
输出：3
解释：它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。
【示例 3】
输入：s = "06"
输出：0
解释："06" 无法映射到 "F" ，因为存在前导零（"6" 和 "06" 并不等价）。
【提示】
1 < = s . l e n g t h < = 100 1 <= s.length <= 100 1<=s.length<=100
s 只包含数字，并且可能包含前导零。
【分析】
简单的动态规划问题，直接分析状态表示与计算：
- 状态表示： f [ i ] f[i] f[i] 表示前 i i i 个字符可以解码出的字符串集合的数量。
- 状态计算：对于
s[i]，有两种可能的情况：s[i]表示单独的一位，这样可以解码出的字符串数量就等于前 i − 1 i - 1 i−1 个字符能解码出的字符串数量，即 f [ i − 1 ] f[i - 1] f[i−1]。这种情况需要保证s[i]为'1' ~ '9'；s[i]与s[i - 1]一起表示两位数，同理可以解码出的字符串数量等于 f [ i − 2 ] f[i - 2] f[i−2]。这种情况需要保证s[i - 1] == '1'或s[i - 1] == '2' && s[i] == '0' ~ '6'。
一个字符都没有为一种方案的起点，即初始化 f[0] = 1。当字符串有前导零时一定不合法，因为第一个 0 无法匹配。
【代码】
class Solution {
public:
int numDecodings(string s) {
int n = s.size();
s = ' ' + s;
vector<int> f(n + 1);
f[0] = 1;
for (int i = 1; i <= n; i++) {
if (s[i] > '0') f[i] += f[i - 1];
if (s[i - 1] == '1' || s[i - 1] == '2' && s[i] <= '6') f[i] += f[i - 2];
}
return f[n];
}
};
LeetCode 92. 反转链表 II（中等）
【题目描述】
给你单链表的头指针 head 和两个整数 left 和 right，其中 left <= right。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表。
【示例 1】
输入：head = [1,2,3,4,5], left = 2, right = 4
输出：[1,4,3,2,5]
【示例 2】
输入：head = [5], left = 1, right = 1
输出：[5]
【提示】
链表中节点数目为 n n n
1 < = n < = 500 1 <= n <= 500 1<=n<=500
− 500 < = N o d e . v a l < = 500 -500 <= Node.val <= 500 −500<=Node.val<=500
1 < = l e f t < = r i g h t < = n 1 <= left <= right <= n 1<=left<=right<=n
【分析】
反转的思路是首先将区间内的每一对相邻节点反向连接，然后将区间的首节点接到区间后的下一个节点，最后将区间前的上一个节点接到区间的末尾节点。
区间内共有 right - left 对节点需要翻转，首先我们定义指针 a 和 b 分别指向第一对需要翻转的前后两个节点，然后可以定义一个临时指针 c 用来记录 b->next，即每对节点的翻转过程如下：
c = b->next；b->next = a；a = b；b = c。
区间内部翻转完成后再连接首尾即可：
p->next->next = b；p->next = a。
【代码】
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode() : val(0), next(nullptr) {}
* ListNode(int x) : val(x), next(nullptr) {}
* ListNode(int x, ListNode *next) : val(x), next(next) {}
* };
*/
class Solution {
public:
ListNode* reverseBetween(ListNode* head, int left, int right) {
auto dummy = new ListNode(-1, head), p = dummy;
for (int i = 0; i < left - 1; i++) p = p->next; // 移动到 left 的前一个节点
auto a = p->next, b = p->next->next;
for (int i = 0; i < right - left; i++) { // 区间内要翻转 right - left 对节点
auto c = b->next;
b->next = a;
a = b, b = c;
}
p->next->next = b; // 将翻转后的尾部接上
p->next = a; // 将翻转区间的前一个结点接上翻转后的首部
return dummy->next;
}
};
LeetCode 93. 复原 IP 地址（中等）
【题目描述】
有效 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
例如："0.1.2.201" 和 "192.168.1.1" 是有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是无效 IP 地址。
给定一个只包含数字的字符串 s，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你不能重新排序或删除 s 中的任何数字。你可以按任何顺序返回答案。
【示例 1】
输入：s = "25525511135"
输出：["255.255.11.135","255.255.111.35"]
【示例 2】
输入：s = "0000"
输出：["0.0.0.0"]
【示例 3】
输入：s = "101023"
输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
【提示】
1 < = s . l e n g t h < = 20 1 <= s.length <= 20 1<=s.length<=20
s 仅由数字组成
【分析】
直接暴力搜索即可，可以枚举三个分界点的位置第一个分界点 i i i 的位置应该在 0 ∼ 2 0\sim 2 0∼2（假设下标从 0 开始，分界点在索引的右侧），且最大为 n − 4 n - 4 n−4（不然后面的分界点没地方放）；同理第二个分界点 j j j 的位置为 i + 1 ∼ i + 3 i + 1\sim i + 3 i+1∼i+3，且最大为 n − 3 n - 3 n−3，第三个分界点 k k k 的位置最小为 n − 4 n - 4 n−4（否则最后一段数字长度必定超过 3），最大为 n − 2 n - 2 n−2，因此位置为 m a x ( j + 1 , n − 4 ) ∼ j + 3 max(j + 1, n - 4)\sim j + 3 max(j+1,n−4)∼j+3。
分割出来四段字符串后判断每一段是否都是合法的，只需要判断数值范围是否在 0 ∼ 255 0\sim 255 0∼255 之间以及是否含有前导零即可。
也可以用 DFS 搜索，从第一位开始搜索每一段整数，每一段长度最大不超过 3，如果已经搜索完最后一位且刚好分出了 4 段合法的整数说明找到一个答案。
【代码】
【枚举分界点方法】
class Solution {
public:
vector<string> restoreIpAddresses(string s) {
vector<string> res;
int n = s.size();
if (n < 4) return res;
for (int i = 0; i < 3 && i <= n - 4; i++)
for (int j = i + 1; j < 4 + i && j <= n - 3; j++)
for (int k = max(j + 1, n - 4); k < 4 + j && k <= n - 2; k++) {
string s1 = s.substr(0, i + 1), s2 = s.substr(i + 1, j - i);
string s3 = s.substr(j + 1, k - j), s4 = s.substr(k + 1, n - k - 1);
if (check(s1) && check(s2) && check(s3) && check(s4))
res.push_back(s1 + "." + s2 + "." + s3 + "." + s4);
}
return res;
}
bool check(string& s) {
if (stoi(s) > 255) return false; // 是否位于 0 ~ 255 之间
if (s.size() > 1 && s[0] == '0') return false; // 前导零
return true;
}
};
【DFS 方法】
class Solution {
public:
vector<string> res;
vector<string> restoreIpAddresses(string s) {
if (s.size() > 12) return res; // 超过 12 位一定不合法
dfs(s, 0, 0, "");
return res;
}
void dfs(string& s, int u, int k, string ip) { // u 表示当前搜索的字符索引，k 表示 ip 中构成的整数数量
if (k > 4) return; // 剪枝
if (u == s.size()) {
if (k == 4) { // 刚好构成四个整数
ip.pop_back(); // 去掉末尾的 '.'
res.push_back(ip);
}
return;
}
for (int i = u, t = 0; i < u + 3 && i < s.size(); i++) { // t 表示当前构成的数的大小
t = t * 10 + s[i] - '0'; // 将当前位加进来后先转为整数
if (i > u && s[u] == '0' || t > 255) return; // 有前导零或当前数已经大于 255 了就没必要再搜索
dfs(s, i + 1, k + 1, ip + to_string(t) + ".");
}
}
};
LeetCode 94. 二叉树的中序遍历（简单）
【题目描述】
给定一个二叉树的根节点 root，返回它的中序遍历。
【示例 1】
输入：root = [1,null,2,3]
输出：[1,3,2]
【示例 2】
输入：root = []
输出：[]
【示例 3】
输入：root = [1]
输出：[1]
【提示】
树中节点数目在范围 [ 0 , 100 ] [0, 100] [0,100] 内
− 100 < = N o d e . v a l < = 100 -100 <= Node.val <= 100 −100<=Node.val<=100
进阶：递归算法很简单，你可以通过迭代算法完成吗？
【分析】
递归遍历二叉树非常简单，不理解的可以看树和图的遍历方式详解：【UCB CS 61B SP24】Lecture 22 & 23: Tree and Graph Traversals, DFS, BFS。
本题的 Tips 中提到尝试用迭代算法完成，那么分析一下如何不用递归实现中序遍历。
对于每个节点，如果其左子树存在，就需要先遍历左子树，但是当前点也不能扔掉，因为遍历完左子树还要回来遍历当前节点，因此如果当前节点有左子树就先将当前点压入栈中。
如果当前节点的左子树已经遍历完了，就可以遍历自身了，遍历完就可以出栈，如果有右子树，那么就对右子树继续执行相同的操作遍历，如果没有右子树就可以出栈下一个节点，也就是当前节点的父节点。
【代码】
【递归方法】
/**
* 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<int> res;
vector<int> inorderTraversal(TreeNode* root) {
if (!root) return res;
if(root->left) inorderTraversal(root->left);
res.push_back(root->val);
if (root->right) inorderTraversal(root->right);
return res;
}
};
【迭代方法】
/**
* 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<int> inorderTraversal(TreeNode* root) {
vector<int> res;
stack<TreeNode*> stk;
while (root || stk.size()) { // 当前节点不为空或栈不为空时循环操作
while (root) { // 一直走到没有左子树为止
stk.push(root);
root = root->left;
}
root = stk.top(); // root 为空时说明栈顶元素可以被遍历了
stk.pop();
res.push_back(root->val);
root = root->right; // 如果没有右子树 root 就为空，下一次出栈的就是 root 的父节点
}
return res;
}
};
LeetCode 95. 不同的二叉搜索树 II（中等）
【题目描述】
给你一个整数 n n n，请你生成并返回所有由 n n n 个节点组成且节点值从 1 1 1 到 n n n 互不相同的不同二叉搜索树。可以按任意顺序返回答案。
【示例 1】
输入：n = 3
输出：[[1,null,2,null,3],[1,null,3,2],[2,1,3],[3,1,null,null,2],[3,2,null,1]]
【示例 2】
输入：n = 1
输出：[[1]]
【提示】
1 < = n < = 8 1 <= n <= 8 1<=n<=8
【分析】
由 1 ∼ n 1\sim n 1∼n 构成的二叉搜索树的数量是有公式的，也就是卡特兰数（Catalan Number）。
显然需要用爆搜找到所有情况，二叉搜索树的中序遍历结果是有序的，对于任何一个子树也一样。
因此任何一个子树的所有节点值一定都是 1 ∼ n 1\sim n 1∼n 中的一段连续序列，假设序列区间为 [L, R]，这个子树的根节点可以是这段连续序列中的任意一个点，我们枚举根节点，假如当前根节点为 k k k，那么左子树的节点一定在序列 [L, k - 1] 中，右子树的节点一定在序列 [k + 1, R] 中。
假如左子树一共有 x x x 种不同的组合方式，右子树一共有 y y y 种，那么以当前节点为根的子树就应该有 x ∗ y x * y x∗y 种不同的组合方式（乘法原理），即左子树的所有方案中每一棵子树都可以和右子树的每一棵子树搭配。
注意写代码时对于每种不同的左右子树组合都需要创建新的根节点，因为爆搜最后返回的是某一段区间中所有根节点可能产生的子树，如果不创建新的根节点那么每次组合不同的子树都会更新根节点指针的左右子树。但是对于某个确定的根节点，左右子树是可以重复使用的，即相同结构的左子树可能会和很多不同结构的右子树搭配形成一棵新的子树，代码中没必要将相同结构的子树复制多份。
【代码】
/**
* 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*> generateTrees(int n) {
return dfs(1, n);
}
vector<TreeNode*> dfs(int l, int r) {
if (l > r) return {nullptr};
vector<TreeNode*> res;
for (int k = l; k <= r; k++) { // 枚举根节点
vector<TreeNode*> leftChild = dfs(l, k - 1);
vector<TreeNode*> rightChild = dfs(k + 1, r);
// 枚举左右子树所有组合情况与子树的根节点进行搭配
for (TreeNode* lc: leftChild)
for (TreeNode* rc: rightChild) {
TreeNode* root = new TreeNode(k); // 注意别在 for 循环外创建根节点，因为指针会被覆盖更新
root->left = lc;
root->right = rc;
res.push_back(root);
}
}
return res;
}
};