质量可靠的小企业网站建设_跨境电商平台有哪些个人可以做_免费ip地址代理_凡科网小程序

Leetcode: 0091-0099题速览

本文材料来自于LeetCode solutions in any programming language | 多种编程语言实现 LeetCode、《剑指 Offer（第 2 版）》、《程序员面试金典（第 6 版）》题解

遵从开源协议为知识共享版权归属-相同方式共享 4.0 国际公共许可证

研一在读备战就业，制此集合便于空闲时间浏览，有任何疑惑问题欢迎讨论，共同进步

Leetcode: 0091-0099题速览
- [91. 解码方法](https://leetcode.cn/problems/decode-ways)
- - 题目描述
  - 解法
  - - 方法一：动态规划
    - - Python3
      - Java
      - C++
- [92. 反转链表 II](https://leetcode.cn/problems/reverse-linked-list-ii)
- - 题目描述
  - 解法
  - - 方法一：模拟
    - - Python3
      - Java
      - C++
- [93. 复原 IP 地址](https://leetcode.cn/problems/restore-ip-addresses)
- - 题目描述
  - 解法
  - - 方法一：DFS
    - - Python3
      - Java
      - C++
- [94. 二叉树的中序遍历](https://leetcode.cn/problems/binary-tree-inorder-traversal)
- - 题目描述
  - 解法
  - - 方法一：递归遍历
    - - Python3
      - Java
      - C++
- [95. 不同的二叉搜索树 II](https://leetcode.cn/problems/unique-binary-search-trees-ii)
- - 题目描述
  - 解法
  - - 方法一：DFS
    - - Python3
      - Java
      - C++
- [96. 不同的二叉搜索树](https://leetcode.cn/problems/unique-binary-search-trees)
- - 题目描述
  - 解法
  - - 方法一：动态规划
    - - Python3
      - Java
      - C++
- [97. 交错字符串](https://leetcode.cn/problems/interleaving-string)
- - 题目描述
  - 解法
  - - 方法一：记忆化搜索
    - - Python3
      - Java
      - C++
- [98. 验证二叉搜索树](https://leetcode.cn/problems/validate-binary-search-tree)
- - 题目描述
  - 解法
  - - 方法一：递归
    - - Python3
      - Java
      - C++
- [99. 恢复二叉搜索树](https://leetcode.cn/problems/recover-binary-search-tree)
- - 题目描述
  - 解法
  - - 方法一：中序遍历
    - - Python3
      - Java
      - C++

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.length <= 100
s 只包含数字，并且可能包含前导零。

难度：中等

标签：字符串,动态规划

解法

方法一：动态规划

我们定义 $f [i]$ 表示字符串的前 $i$ 个字符的解码方法数，初始时 $f [0] = 1$ ，其余 $f [i] = 0$ 。

考虑 $f [i]$ 如何进行状态转移。

如果第 $i$ 个字符（即 $s [i - 1]$ ）单独形成编码，那么它对应一种解码方式，即 $f [i] = f [i - 1]$ 。前提是 $\neq 0$ 。
如果第 $i - 1$ 个字符和第 $i$ 个字符组成的字符串在 $[1, 26]$ 范围内，那么它们可以作为一个整体，对应一种解码方式，即 $f [i] = f [i] + f [i - 2]$ 。前提是 $\neq 0$ ，且 $s [i - 2] s [i - 1]$ 在 $[1, 26]$ 范围内。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是字符串的长度。

Python3

class Solution:def numDecodings(self, s: str) -> int:n = len(s)f = [1] + [0] * nfor i, c in enumerate(s, 1):if c != "0":f[i] = f[i - 1]if i > 1 and s[i - 2] != "0" and int(s[i - 2 : i]) <= 26:f[i] += f[i - 2]return f[n]

Java

class Solution {public int numDecodings(String s) {int n = s.length();int[] f = new int[n + 1];f[0] = 1;for (int i = 1; i <= n; ++i) {if (s.charAt(i - 1) != '0') {f[i] = f[i - 1];}if (i > 1 && s.charAt(i - 2) != '0' && Integer.valueOf(s.substring(i - 2, i)) <= 26) {f[i] += f[i - 2];}}return f[n];}
}

C++

class Solution {
public:int numDecodings(string s) {int n = s.size();int f[n + 1];memset(f, 0, sizeof(f));f[0] = 1;for (int i = 1; i <= n; ++i) {if (s[i - 1] != '0') {f[i] = f[i - 1];}if (i > 1 && (s[i - 2] == '1' || s[i - 2] == '2' && s[i - 1] <= '6')) {f[i] += f[i - 2];}}return f[n];}
};

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
1 <= n <= 500
-500 <= Node.val <= 500
1 <= left <= right <= n

进阶： 你可以使用一趟扫描完成反转吗？

难度：中等

标签：链表

解法

方法一：模拟

定义一个虚拟头结点 dummy，指向链表的头结点 head，然后定义一个指针 pre 指向 dummy，从虚拟头结点开始遍历链表，遍历到第 left 个结点时，将 pre 指向该结点，然后从该结点开始遍历 right - left + 1 次，将遍历到的结点依次插入到 pre 的后面，最后返回 dummy.next 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (1)$ 。其中 $n$ 为链表的长度。

Python3

## Definition for singly-linked list.
## class ListNode:
##     def __init__(self, val=0, next=None):
##         self.val = val
##         self.next = next
class Solution:def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:if head.next is None or left == right:return headdummy = ListNode(0, head)pre = dummyfor _ in range(left - 1):pre = pre.nextp, q = pre, pre.nextcur = qfor _ in range(right - left + 1):t = cur.nextcur.next = prepre, cur = cur, tp.next = preq.next = curreturn dummy.next

Java

/*** Definition for singly-linked list.* public class ListNode {*     int val;*     ListNode next;*     ListNode() {}*     ListNode(int val) { this.val = val; }*     ListNode(int val, ListNode next) { this.val = val; this.next = next; }* }*/
class Solution {public ListNode reverseBetween(ListNode head, int left, int right) {if (head.next == null || left == right) {return head;}ListNode dummy = new ListNode(0, head);ListNode pre = dummy;for (int i = 0; i < left - 1; ++i) {pre = pre.next;}ListNode p = pre;ListNode q = pre.next;ListNode cur = q;for (int i = 0; i < right - left + 1; ++i) {ListNode t = cur.next;cur.next = pre;pre = cur;cur = t;}p.next = pre;q.next = cur;return dummy.next;}
}

C++

/*** 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) {if (!head->next || left == right) {return head;}ListNode* dummy = new ListNode(0, head);ListNode* pre = dummy;for (int i = 0; i < left - 1; ++i) {pre = pre->next;}ListNode *p = pre, *q = pre->next;ListNode* cur = q;for (int i = 0; i < right - left + 1; ++i) {ListNode* t = cur->next;cur->next = pre;pre = cur;cur = t;}p->next = pre;q->next = cur;return dummy->next;}
};

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.length <= 20
s 仅由数字组成

难度：中等

标签：字符串,回溯

解法

方法一：DFS

我们定义一个函数 $df s (i)$ ，表示从字符串 $s$ 的第 $i$ 位开始，搜索能够组成的 IP 地址列表。

函数 $df s (i)$ 的执行步骤如下：

如果 $i$ 大于等于字符串 $s$ 的长度，说明已经完成了四段 IP 地址的拼接，判断是否满足四段 IP 地址的要求，如果满足则将当前 $I P$ 加入答案。

如果 $i$ 小于字符串 $s$ 的长度，此时还需要拼接 $I P$ 地址的一段，此时需要确定这一段 $I P$ 地址的值。如果该值大于 $255$ ，或者当前位置 $i$ 为 $0$ 且 $i$ 之后的若干位的数值大于 $0$ ，则说明不满足要求，直接返回。否则，将其加入 $I P$ 地址列表，并继续搜索下一段 $I P$ 地址。

时间复杂度 $\times 3^4)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为字符串 $s$ 的长度。

Python3

class Solution:def restoreIpAddresses(self, s: str) -> List[str]:def check(i: int, j: int) -> int:if s[i] == "0" and i != j:return Falsereturn 0 <= int(s[i : j + 1]) <= 255def dfs(i: int):if i >= n and len(t) == 4:ans.append(".".join(t))returnif i >= n or len(t) >= 4:returnfor j in range(i, min(i + 3, n)):if check(i, j):t.append(s[i : j + 1])dfs(j + 1)t.pop()n = len(s)ans = []t = []dfs(0)return ans

Java

class Solution {private int n;private String s;private List<String> ans = new ArrayList<>();private List<String> t = new ArrayList<>();public List<String> restoreIpAddresses(String s) {n = s.length();this.s = s;dfs(0);return ans;}private void dfs(int i) {if (i >= n && t.size() == 4) {ans.add(String.join(".", t));return;}if (i >= n || t.size() >= 4) {return;}int x = 0;for (int j = i; j < Math.min(i + 3, n); ++j) {x = x * 10 + s.charAt(j) - '0';if (x > 255 || (s.charAt(i) == '0' && i != j)) {break;}t.add(s.substring(i, j + 1));dfs(j + 1);t.remove(t.size() - 1);}}
}

C++

class Solution {
public:vector<string> restoreIpAddresses(string s) {int n = s.size();vector<string> ans;vector<string> t;function<void(int)> dfs = [&](int i) {if (i >= n && t.size() == 4) {ans.push_back(t[0] + "." + t[1] + "." + t[2] + "." + t[3]);return;}if (i >= n || t.size() >= 4) {return;}int x = 0;for (int j = i; j < min(n, i + 3); ++j) {x = x * 10 + s[j] - '0';if (x > 255 || (j > i && s[i] == '0')) {break;}t.push_back(s.substr(i, j - i + 1));dfs(j + 1);t.pop_back();}};dfs(0);return ans;}
};

94. 二叉树的中序遍历

题目描述

给定一个二叉树的根节点 root ，返回 它的中序遍历 。

示例 1：

在这里插入图片描述

输入：root = [1,null,2,3]
输出：[1,3,2]

示例 2：

输入：root = []
输出：[]

示例 3：

输入：root = [1]
输出：[1]

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

进阶: 递归算法很简单，你可以通过迭代算法完成吗？

难度：简单

标签：栈,树,深度优先搜索,二叉树

解法

方法一：递归遍历

我们先递归左子树，再访问根节点，接着递归右子树。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点数，空间复杂度主要取决于递归调用的栈空间。

Python3

## Definition for a binary tree node.
## class TreeNode:
##     def __init__(self, val=0, left=None, right=None):
##         self.val = val
##         self.left = left
##         self.right = right
class Solution:def inorderTraversal(self, root: Optional[TreeNode]) -> List[int]:def dfs(root):if root is None:returndfs(root.left)ans.append(root.val)dfs(root.right)ans = []dfs(root)return ans

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private List<Integer> ans = new ArrayList<>();public List<Integer> inorderTraversal(TreeNode root) {dfs(root);return ans;}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);ans.add(root.val);dfs(root.right);}
}

C++

/*** 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> ans;function<void(TreeNode*)> dfs = [&](TreeNode* root) {if (!root) {return;}dfs(root->left);ans.push_back(root->val);dfs(root->right);};dfs(root);return ans;}
};

95. 不同的二叉搜索树 II

题目描述

给你一个整数 n ，请你生成并返回所有由 n 个节点组成且节点值从 1 到 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

难度：中等

标签：树,二叉搜索树,动态规划,回溯,二叉树

解法

方法一：DFS

我们设计一个函数 $df s (i, j)$ ，返回由 $[i, j]$ 组成的所有可行的二叉搜索树，那么答案就是 $df s (1, n)$ 。

函数 $df s (i, j)$ 的执行步骤如下：

如果 $i > j$ ，那么说明此时没有数字可以构成二叉搜索树，返回由一个空节点组成的列表。
如果 $\leq j$ ，那么我们枚举 $[i, j]$ 中的数字 $v$ 作为根节点，那么根节点 $v$ 的左子树由 $[i, v - 1]$ 组成，右子树由 $[v + 1, j]$ 组成，最后将左右子树的所有组合笛卡尔积，即 $left \times right$ ，加上根节点 $v$ ，得到以 $v$ 为根节点的所有二叉搜索树。

时间复杂度 $\times G(n))$ ，空间复杂度 $\times G(n))$ 。其中 $G (n)$ 是卡特兰数。

Python3

## Definition for a binary tree node.
## class TreeNode:
##     def __init__(self, val=0, left=None, right=None):
##         self.val = val
##         self.left = left
##         self.right = right
class Solution:def generateTrees(self, n: int) -> List[Optional[TreeNode]]:def dfs(i: int, j: int) -> List[Optional[TreeNode]]:if i > j:return [None]ans = []for v in range(i, j + 1):left = dfs(i, v - 1)right = dfs(v + 1, j)for l in left:for r in right:ans.append(TreeNode(v, l, r))return ansreturn dfs(1, n)

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {public List<TreeNode> generateTrees(int n) {return dfs(1, n);}private List<TreeNode> dfs(int i, int j) {List<TreeNode> ans = new ArrayList<>();if (i > j) {ans.add(null);return ans;}for (int v = i; v <= j; ++v) {var left = dfs(i, v - 1);var right = dfs(v + 1, j);for (var l : left) {for (var r : right) {ans.add(new TreeNode(v, l, r));}}}return ans;}
}

C++

/*** 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) {function<vector<TreeNode*>(int, int)> dfs = [&](int i, int j) {if (i > j) {return vector<TreeNode*>{nullptr};}vector<TreeNode*> ans;for (int v = i; v <= j; ++v) {auto left = dfs(i, v - 1);auto right = dfs(v + 1, j);for (auto l : left) {for (auto r : right) {ans.push_back(new TreeNode(v, l, r));}}}return ans;};return dfs(1, n);}
};

96. 不同的二叉搜索树

题目描述

给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：

在这里插入图片描述

输入：n = 3
输出：5

示例 2：

输入：n = 1
输出：1

提示：

1 <= n <= 19

难度：中等

标签：树,二叉搜索树,数学,动态规划,二叉树

解法

方法一：动态规划

我们定义 $f [i]$ 表示 $[1, i]$ 能产生的二叉搜索树的个数，初始时 $f [0] = 1$ ，答案为 $f [n]$ 。

我们可以枚举节点数 $i$ ，那么左子树节点数 $\in [0, i - 1]$ ，右子树节点数 $k = i - j - 1$ ，左子树节点数和右子树节点数的组合数为 $\times f[k]$ ，因此 $\sum_{j = 0}^{i - 1} f[j] \times f[i - j - 1]$ 。

最后返回 $f [n]$ 即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 为节点数。

Python3

class Solution:def numTrees(self, n: int) -> int:f = [1] + [0] * nfor i in range(n + 1):for j in range(i):f[i] += f[j] * f[i - j - 1]return f[n]

Java

class Solution {public int numTrees(int n) {int[] f = new int[n + 1];f[0] = 1;for (int i = 1; i <= n; ++i) {for (int j = 0; j < i; ++j) {f[i] += f[j] * f[i - j - 1];}}return f[n];}
}

C++

class Solution {
public:int numTrees(int n) {vector<int> f(n + 1);f[0] = 1;for (int i = 1; i <= n; ++i) {for (int j = 0; j < i; ++j) {f[i] += f[j] * f[i - j - 1];}}return f[n];}
};

97. 交错字符串

题目描述

给定三个字符串 s1、s2、s3，请你帮忙验证 s3 是否是由 s1 和 s2 交错组成的。

两个字符串 s 和 t 交错的定义与过程如下，其中每个字符串都会被分割成若干非空子字符串：

s = s₁ + s₂ + ... + s_n
t = t₁ + t₂ + ... + t_m
|n - m| <= 1
交错是 s₁ + t₁ + s₂ + t₂ + s₃ + t₃ + ... 或者 t₁ + s₁ + t₂ + s₂ + t₃ + s₃ + ...

注意：a + b 意味着字符串 a 和 b 连接。

示例 1：

在这里插入图片描述

输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbcbcac”
输出：true

示例 2：

输入：s1 = “aabcc”, s2 = “dbbca”, s3 = “aadbbbaccc”
输出：false

示例 3：

输入：s1 = “”, s2 = “”, s3 = “”
输出：true

提示：

0 <= s1.length, s2.length <= 100
0 <= s3.length <= 200
s1、s2、和 s3 都由小写英文字母组成

进阶：您能否仅使用 O(s2.length) 额外的内存空间来解决它?

难度：中等

标签：字符串,动态规划

解法

方法一：记忆化搜索

我们记字符串 $s_1$ 的长度为 $m$ ，字符串 $s_2$ 的长度为 $n$ ，如果 $\neq |s_3|$ ，那么 $s_3$ 一定不是 $s_1$ 和 $s_2$ 的交错字符串，返回 false。

接下来，我们设计一个函数 $df s (i, j)$ ，表示从 $s_1$ 的第 $i$ 个字符和 $s_2$ 的第 $j$ 个字符开始，能否交错组成 $s_3$ 的剩余部分。那么答案就是 $df s (0, 0)$ 。

函数 $df s (i, j)$ 的计算过程如下：

如果 $\geq m$ 并且 $\geq n$ ，那么说明 $s_1$ 和 $s_2$ 都已经遍历完毕，返回 true。

如果 $i < m$ 并且 $s_1[i] = s_3[i + j]$ ，那么说明 $s_1[i]$ 这个字符是 $s_3[i + j]$ 中的一部分，因此递归地调用 $df s (i + 1, j)$ 判断 $s_1$ 的下一个字符能否和 $s_2$ 的当前字符匹配，如果能匹配成功，就返回 true。

同理，如果 $j < n$ 并且 $s_2[j] = s_3[i + j]$ ，那么说明 $s_2[j]$ 这个字符是 $s_3[i + j]$ 中的一部分，因此递归地调用 $df s (i, j + 1)$ 判断 $s_2$ 的下一个字符能否和 $s_1$ 的当前字符匹配，如果能匹配成功，就返回 true。

否则，返回 false。

为了避免重复计算，我们可以使用记忆化搜索。

时间复杂度 $\times n)$ ，空间复杂度 $\times n)$ 。其中 $m$ 和 $n$ 分别是字符串 $s_1$ 和 $s_2$ 的长度。

Python3

class Solution:def isInterleave(self, s1: str, s2: str, s3: str) -> bool:@cachedef dfs(i: int, j: int) -> bool:if i >= m and j >= n:return Truek = i + jif i < m and s1[i] == s3[k] and dfs(i + 1, j):return Trueif j < n and s2[j] == s3[k] and dfs(i, j + 1):return Truereturn Falsem, n = len(s1), len(s2)if m + n != len(s3):return Falsereturn dfs(0, 0)

Java

class Solution {private Map<List<Integer>, Boolean> f = new HashMap<>();private String s1;private String s2;private String s3;private int m;private int n;public boolean isInterleave(String s1, String s2, String s3) {m = s1.length();n = s2.length();if (m + n != s3.length()) {return false;}this.s1 = s1;this.s2 = s2;this.s3 = s3;return dfs(0, 0);}private boolean dfs(int i, int j) {if (i >= m && j >= n) {return true;}var key = List.of(i, j);if (f.containsKey(key)) {return f.get(key);}int k = i + j;boolean ans = false;if (i < m && s1.charAt(i) == s3.charAt(k) && dfs(i + 1, j)) {ans = true;}if (!ans && j < n && s2.charAt(j) == s3.charAt(k) && dfs(i, j + 1)) {ans = true;}f.put(key, ans);return ans;}
}

C++

class Solution {
public:bool isInterleave(string s1, string s2, string s3) {int m = s1.size(), n = s2.size();if (m + n != s3.size()) {return false;}vector<vector<int>> f(m + 1, vector<int>(n + 1, -1));function<bool(int, int)> dfs = [&](int i, int j) {if (i >= m && j >= n) {return true;}if (f[i][j] != -1) {return f[i][j] == 1;}f[i][j] = 0;int k = i + j;if (i < m && s1[i] == s3[k] && dfs(i + 1, j)) {f[i][j] = 1;}if (!f[i][j] && j < n && s2[j] == s3[k] && dfs(i, j + 1)) {f[i][j] = 1;}return f[i][j] == 1;};return dfs(0, 0);}
};

98. 验证二叉搜索树

题目描述

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效二叉搜索树定义如下：

节点的左子树只包含小于当前节点的数。
节点的右子树只包含大于当前节点的数。
所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

在这里插入图片描述

输入：root = [2,1,3]
输出：true

示例 2：

在这里插入图片描述

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 10⁴] 内
-2³¹ <= Node.val <= 2³¹ - 1

难度：中等

标签：树,深度优先搜索,二叉搜索树,二叉树

解法

方法一：递归

我们可以对二叉树进行递归中序遍历，如果遍历到的结果是严格升序的，那么这棵树就是一个二叉搜索树。

因此，我们使用一个变量 $\textit{prev}$ 来保存上一个遍历到的节点，初始时 $\textit{prev} = -\infty$ ，然后我们递归遍历左子树，如果左子树不是二叉搜索树，直接返回 $\textit{False}$ ，否则判断当前节点的值是否大于 $\textit{prev}$ ，如果不是，返回 $\textit{False}$ ，否则更新 $\textit{prev}$ 为当前节点的值，然后递归遍历右子树。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉树的节点个数。

Python3

## Definition for a binary tree node.
## class TreeNode:
##     def __init__(self, val=0, left=None, right=None):
##         self.val = val
##         self.left = left
##         self.right = right
class Solution:def isValidBST(self, root: Optional[TreeNode]) -> bool:def dfs(root: Optional[TreeNode]) -> bool:if root is None:return Trueif not dfs(root.left):return Falsenonlocal previf prev >= root.val:return Falseprev = root.valreturn dfs(root.right)prev = -infreturn dfs(root)

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private TreeNode prev;public boolean isValidBST(TreeNode root) {return dfs(root);}private boolean dfs(TreeNode root) {if (root == null) {return true;}if (!dfs(root.left)) {return false;}if (prev != null && prev.val >= root.val) {return false;}prev = root;return dfs(root.right);}
}

C++

/*** 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 isValidBST(TreeNode* root) {TreeNode* prev = nullptr;function<bool(TreeNode*)> dfs = [&](TreeNode* root) {if (!root) {return true;}if (!dfs(root->left)) {return false;}if (prev && prev->val >= root->val) {return false;}prev = root;return dfs(root->right);};return dfs(root);}
};

99. 恢复二叉搜索树

题目描述

给你二叉搜索树的根节点 root ，该树中的恰好两个节点的值被错误地交换。请在不改变其结构的情况下，恢复这棵树 。

示例 1：

在这里插入图片描述

输入：root = [1,3,null,null,2]
输出：[3,1,null,null,2]
解释：3 不能是 1 的左孩子，因为 3 > 1 。交换 1 和 3 使二叉搜索树有效。

示例 2：

在这里插入图片描述

输入：root = [3,1,4,null,null,2]
输出：[2,1,4,null,null,3]
解释：2 不能在 3 的右子树中，因为 2 < 3 。交换 2 和 3 使二叉搜索树有效。

提示：

树上节点的数目在范围 [2, 1000] 内
-2³¹ <= Node.val <= 2³¹ - 1

进阶：使用 O(n) 空间复杂度的解法很容易实现。你能想出一个只使用 O(1) 空间的解决方案吗？

难度：中等

标签：树,深度优先搜索,二叉搜索树,二叉树

解法

方法一：中序遍历

中序遍历二叉搜索树，得到的序列是递增的。如果有两个节点的值被错误地交换，那么中序遍历得到的序列中，一定会出现两个逆序对。我们用 first 和 second 分别记录这两个逆序对中较小值和较大值的节点，最后交换这两个节点的值即可。

时间复杂度 $O (n)$ ，空间复杂度 $O (n)$ 。其中 $n$ 是二叉搜索树的节点个数。

Python3

## Definition for a binary tree node.
## class TreeNode:
##     def __init__(self, val=0, left=None, right=None):
##         self.val = val
##         self.left = left
##         self.right = right
class Solution:def recoverTree(self, root: Optional[TreeNode]) -> None:"""Do not return anything, modify root in-place instead."""def dfs(root):if root is None:returnnonlocal prev, first, seconddfs(root.left)if prev and prev.val > root.val:if first is None:first = prevsecond = rootprev = rootdfs(root.right)prev = first = second = Nonedfs(root)first.val, second.val = second.val, first.val

Java

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode() {}*     TreeNode(int val) { this.val = val; }*     TreeNode(int val, TreeNode left, TreeNode right) {*         this.val = val;*         this.left = left;*         this.right = right;*     }* }*/
class Solution {private TreeNode prev;private TreeNode first;private TreeNode second;public void recoverTree(TreeNode root) {dfs(root);int t = first.val;first.val = second.val;second.val = t;}private void dfs(TreeNode root) {if (root == null) {return;}dfs(root.left);if (prev != null && prev.val > root.val) {if (first == null) {first = prev;}second = root;}prev = root;dfs(root.right);}
}

C++

/*** 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* prev = nullptr;TreeNode* first = nullptr;TreeNode* second = nullptr;function<void(TreeNode * root)> dfs = [&](TreeNode* root) {if (!root) return;dfs(root->left);if (prev && prev->val > root->val) {if (!first) first = prev;second = root;}prev = root;dfs(root->right);};dfs(root);swap(first->val, second->val);}
};

质量可靠的小企业网站建设_跨境电商平台有哪些个人可以做_免费ip地址代理_凡科网小程序

Leetcode: 0091-0099题速览

目录

题目描述

解法

方法一：动态规划

Python3

Java

C++

题目描述

解法

方法一：模拟

Python3

Java

C++

题目描述

解法

方法一：DFS

Python3

Java

C++

题目描述

解法

方法一：递归遍历

Python3

Java

C++

题目描述

解法

方法一：DFS

Python3

Java

C++

题目描述

解法

方法一：动态规划

Python3

Java

C++

题目描述

解法

方法一：记忆化搜索

Python3

Java

C++

题目描述

解法

方法一：递归

Python3

Java

C++

题目描述

解法

方法一：中序遍历

Python3

Java

C++

最新新闻

热搜词