题目描述 输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构) B是A的子结构， 即 A中有出现和B相同的结构和节点值。 例如: 给定的树 A: 3 / \ 4 5 / \ 1 2 给定的树 B： 4 / 1 返回 true，因为 B 与 A 的一个子树拥有相同的结构和节点值。 示例 1： 输入：A = [1,2,3], B = [3,1] 输出：false 示例 2： 输入：A = [3,4,5,1,2], B = [4,1] 输出：true 限制： 0 <= 节点个数 <= 10000 解法 利用递归的思想解决。用A的根节点、左节点、右节点依次尝试是否等B的根节点，如果是则尝试对比下一个节点 go代码如下： func isSubStructure(A *TreeNode, B *TreeNode) bool { if A == ni....
题目 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。 示例 : 给定二叉树 1 / \ 2 3 / \ 4 5 返回 3, 它的长度是路径 [4,2,1,3] 或者 [5,2,1,3]。 解法 可以将二叉树的直径转换为：二叉树的 每个节点的左右子树的高度和 的最大值。 go代码实现如下： var ans int = 0 func diameterOfBinaryTree(root *TreeNode) int { ans = 0 depth(root) return ans } func depth(node *TreeNode) int { if node == nil { return 0 } var leftDepth, rightDepth = depth(node.Left), depth(node.Right) ans = max(leftDepth + rightDepth, ans) return 1 + max(leftDepth, rightDep....
题目 给定一个二叉树，原地将它展开为一个单链表。 例如，给定二叉树 1 / \ 2 5 / \ \ 3 4 6 将其展开为： 1 \ 2 \ 3 \ 4 \ 5 \ 6 解法-递归 题目要求原地展开，故不能使用数组类变量存储全部节点值再重构树。将左右子树分别递归展开，将原左子树变为节点的右子树，再将原右子树变为当前右子树最右节点的右子树。 go代码实现 func flatten(root *TreeNode) { if root == nil { return } flat(root) } func flat(node *TreeNode) { if node == nil { return } flat(node.Left) flat(node.Right) var temp *TreeNode = node.Right node.Right, node.Left = node.Left, nil for node.Right != nil { node = node.Right } node.Right = temp } 或者简化一下代码： func flatte....
题目 将一个按照升序排列的有序数组，转换为一棵高度平衡二叉搜索树。 本题中，一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。 示例: 给定有序数组: [-10,-3,0,5,9], 一个可能的答案是：[0,-3,9,-10,null,5]，它可以表示下面这个高度平衡二叉搜索树： 0 / \ -3 9 / / -10 5 解法 因为左右高度不能大于1，所以可以找个中间节点，保证二叉树的平衡性。找到中间节点作为根节点，然后用递归遍历。另外需要注意的是，求中点不要用 int mid = (begin + end)/2，有溢出风险，稳妥的方法是 int mid = begin + (end-begin)/2。 go代码实现： func sortedArrayToBST(nums []int) *TreeNode { return bst(nums, 0, len(nums)-1) } func bst(nums []int, begin int, end int) *TreeNode { if begin > end { return ni....
题目描述 根据一棵树的前序遍历与中序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 前序遍历 preorder = [3,9,20,15,7] 中序遍历 inorder = [9,3,15,20,7] 返回如下的二叉树： 3 / \ 9 20 / \ 15 7 解法-递归 通过前序遍历的第一个节点可知道root节点，然后利用中序遍历，可以根据root节点把树划分为两个子树，然后递归解决 java代码实现： public TreeNode buildTree(int[] preorder, int[] inorder) { if(preorder.length==0||inorder.length==0){ return null; } TreeNode root=new TreeNode (preorder[0]); for(int i=0;i<preorder.length;i++){ if(preorder[0]==inorder[i]){ // 针对preOrder 左子树子序列（1，i+1） root.left=buildTree(Arr....
题目 给定一个整数 n，求以 1 ... n 为节点组成的二叉搜索树有多少种？ 示例: 输入: 3 输出: 5 解释: 给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 解法-动态规划 假设 n 个节点存在二叉排序树的个数是 G (n)，令 f(i) 为以 i 为根的二叉搜索树的个数，则 G(n) = f(1) + f(2) + f(3) + f(4) + ... + f(n) 当 i 为根节点时，其左子树节点个数为 i-1 个，右子树节点为 n-i，则 f(i) = G(i-1)*G(n-i)f(i)=G(i−1)∗G(n−i) 综合两个公式可以得到 卡特兰数 公式 G(n) = G(0)*G(n-1)+G(1)*G(n-2)+...+G(n-1)*G(0)G(n)=G(0)∗G(n−1)+G(1)∗G(n−2)+...+G(n−1)∗G(0) Java实现 class Solution { public int numTrees(int n) ....
题目 给定一个二叉树，判断其是否是一个有效的二叉搜索树。 假设一个二叉搜索树具有如下特征： 节点的左子树只包含小于当前节点的数。 节点的右子树只包含大于当前节点的数。 所有左子树和右子树自身必须也是二叉搜索树。 示例 1: 输入: 2 / \ 1 3 输出: true 示例 2: 输入: 5 / \ 1 4 / \ 3 6 输出: false 解释: 输入为: [5,1,4,null,null,3,6]。 根节点的值为 5 ，但是其右子节点值为 4 。 解法 比较巧妙的写法：go实现，maxInt64是因为测试用例有int64的值 package main func isValidBST(root *TreeNode) bool { return validate(root, math.MinInt64, math.MaxInt64) } func validate(node *TreeNode, min int, max int) bool { if node == nil { return true } if node....
BFS（广度优先搜索）Java public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); Queue<TreeNode> queue = new ArrayDeque<>(); if (root != null) { queue.add(root); } while(!queue.isEmpty()) { int n = queue.size(); List<Integer> level = new ArrayList<>(); for(int i = 0; i<n; i++) { TreeNode node = queue.poll(); level.add(node.val); if (node.left != null) { queue.add(node.left); } if (node.right != null) { qu....
今天，我们先来学习一下贪心算法（greedy algorithm）。贪心算法有很多经典的应用，比如霍夫曼编码（Huffman Coding）、Prim和Kruskal最小生成树算法、还有Dijkstra单源最短路径算法。 1.买卖股票的最佳时机 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你可以尽可能地完成更多的交易（多次买卖一支股票）。 注意：你不能同时参与多笔交易（你必须在再次购买前出售掉之前的股票）。 示例 1: 输入: [7,1,5,3,6,4] 输出: 7 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5-1 = 4 。 随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6-3 = 3 。 示例 2: 输入: [1,2,3,4,5] 输出: 4 解释: 在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所....
题目描述 编写一个 SQL 查询，查找所有至少连续出现三次的数字。 +----+-----+ | Id | Num | +----+-----+ | 1 | 1 | | 2 | 1 | | 3 | 1 | | 4 | 2 | | 5 | 1 | | 6 | 2 | | 7 | 2 | +----+-----+ 例如，给定上面的 Logs 表， 1 是唯一连续出现至少三次的数字。 +-----------------+ | ConsecutiveNums | +-----------------+ | 1 | +-----------------+ 来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/consecutive-numbers 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。 解法 思路就是多表连接，根据id自增的关系进行判断 select distinct a.Num as ConsecutiveNums from Logs a left join Logs b on a.id+1=b.id left....
题目描述 编写一个 SQL 查询来实现分数排名。 如果两个分数相同，则两个分数排名（Rank）相同。请注意，平分后的下一个名次应该是下一个连续的整数值。换句话说，名次之间不应该有“间隔”。 +----+-------+ | Id | Score | +----+-------+ | 1 | 3.50 | | 2 | 3.65 | | 3 | 4.00 | | 4 | 3.85 | | 5 | 4.00 | | 6 | 3.65 | +----+-------+ 例如，根据上述给定的 Scores 表，你的查询应该返回（按分数从高到低排列）： +-------+------+ | Score | Rank | +-------+------+ | 4.00 | 1 | | 4.00 | 1 | | 3.85 | 2 | | 3.65 | 3 | | 3.65 | 3 | | 3.50 | 4 | +-------+------+ 解法 这个问题分为两部分来看 所有的分数按由大到小的顺序排序 针对排好的分数，给出排名 那第一部分，写出来很轻松 `select Score from Sco....
题目描述 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 注意空字符串可被认为是有效字符串。 示例 1: 输入: "()" 输出: true 示例 2: 输入: "()[]{}" 输出: true 示例 3: 输入: "(]" 输出: false 示例 4: 输入: "([)]" 输出: false 示例 5: 输入: "{[]}" 输出: true 解法 1. 采用Java提供的工具类 利用Java提供的工具类String.contains() 判断是否存在 {}, [], ()，如果存在，利用String.replace() 替换为空字符串 代码如下： public boolean isValid(String s) { if (s.length() <= 0) { return true; } while (s.contains("{}") || s.contains("[]") || s.contains("()")) { s = s.r....
1.题目描述 Write a function to find the longest common prefix string amongst an array of strings. If there is no common prefix, return an empty string "". Example 1: Input: ["flower","flow","flight"] Output: "fl" Example 2: Input: ["dog","racecar","car"] Output: "" Explanation: There is no common prefix among the input strings. Note: All given inputs are in lowercase letters a-z. 题目的意思就是求最长公共前缀。 2.解法 思路就是用第一个字符串（定义为 first）跟其他字符串去比较。是否存在最长公共前缀，开始先假定公共字符串是first，判断是否是其他字符串里的前缀，不匹配时，first减少一个字符，继续比较，当f....
题目描述 Roman numerals are represented by seven different symbols: I, V, X, L, C, D and M. Symbol Value I 1 V 5 X 10 L 50 C 100 D 500 M 1000 For example, two is written as II in Roman numeral, just two one's added together. Twelve is written as, XII, which is simply X + II. The number twenty seven is written as XXVII, which is XX + V + II. Roman numerals are usually written largest to smallest from left to right. However, the numeral for four is not IIII. Instead, the number four is written as IV.....