孙云增的博客

题目给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？ 示例:12345678910输入: 3输出: 5解释:给定 n = 3, 一共有 5 种不同结构的二叉搜索树: 1 3 3 2 1 \ / / / \ \ 3 2 1 1 3 2 / / \ \ 2 1 2 3 思路 + 代码动态规划。 假设 整数 n对应的二叉搜索树数量为 G(n)。 每个节点 i ∈ (0,n] 为根节点对应的二叉搜索树数量为 F(i)。 则， G(n) = F(1) + F(2) + F(3) + … + F(n)。 而 节点i 为根节点的二叉搜索树，可以分为 i-1 个左子树 跟 n-i个右子树，F(i) = G(i-1)*G(n-i); 因此 G(n) = G(0)G(n-1) + G(1)G(n-2) + G(2)G(n-3...

题目实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。 示例:12345678Trie trie = new Trie();trie.insert("apple");trie.search("apple"); // 返回 truetrie.search("app"); // 返回 falsetrie.startsWith("app"); // 返回 truetrie.insert("app"); trie.search("app"); // 返回 true 说明: 你可以假设所有的输入都是由小写字母 a-z 构成的。保证所有输入均为非空字符串。 思路 + 代码题解 实现一个链表，每一个链表节点存储的是数组，数组包含所有可能的键（这里指26个字符）。 类似于HashMap的entry结构。 123456789101112131415161718192021222324252627...

题目在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。 示例： 12345678输入: 1 0 1 0 01 0 1 1 11 1 1 1 11 0 0 1 0输出: 4 思路 + 代码是动态规划的题目。 关键在于问题的转化。 问题转化为最长边长。 然后截止当前位置的最长边长是左边、上边及右上三者中的最小值 + 1。 12345678910111213141516171819class Solution { public int maximalSquare(char[][] matrix) { if(matrix.length==0 || matrix[0].length==0) return 0; int row = matrix.length; int col = matrix[0].length; int[][] dp = new int[row+1][col+1]; int max_side = 0; for...

题目一个机器人位于一个 m x n 网格的左上角 （起始点在下图中标记为“Start” ）。 机器人每次只能向下或者向右移动一步。机器人试图达到网格的右下角（在下图中标记为“Finish”）。 问总共有多少条不同的路径？ 思路 + 代码动态规划。。用回溯竟然做不出来 123456789101112131415161718class Solution { public int uniquePaths(int m, int n) { if(m<=0 || n<=0) return 0; int[][] dp = new int [m][n]; for(int i=0; i<m; i++){ for(int j=0; j<n; j++){ if(i==0) dp[i][j] = 1; else if(j==0) ...

题目给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。 示例：12输入: [1,2,3,4]输出: [24,12,8,6] 说明：请不要使用除法，且在 O(n) 时间复杂度内完成此题。 思路 + 代码不能常规的循环暴力解决，因为时间限制在O(n)内。 考虑上三角/下三角的乘法。 123456789101112131415161718class Solution { public int[] productExceptSelf(int[] nums) { int len = nums.length; int[] res = new int[len]; Arrays.fill(res, 1); int left = 1, right=1; for(int i=0; i<len; i++) { // 只经过左指针操作，res[0...

题目给定一个二叉树，原地将它展开为链表。 例如，给定二叉树： 12345 1 / \ 2 5 / \ \3 4 6 将其展开为： 12345678910111 \ 2 \ 3 \ 4 \ 5 \ 6 题解 + 思路一开始想的是递归，但是递归是由底向顶递归生成，而这道题是由顶到底生成，虽然存在子问题，但是仍难以求解。 其实可以看做如下步骤： 找到左子树的最右节点。 12345 1 / \ 2 5 / \ \3 4 6 将右子树移到左子树的最右节点。 123456789 1 / 2 / \ 3 4 \ 5 \ 6 右子树换为左子树，左子树置为 null 1234567891 \ 2 / \ 3 4 \ 5 \ 6 从右节点开始，继续该操作 12345678910111 \ 2 \ ...

题目给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。 例如，给出 n = 3，生成结果为： 1234567[ "((()))", "(()())", "(())()", "()(())", "()()()"] 思路 + 代码回溯法，通过两个整数统计“（”与“）”的数量。 1234567891011121314151617181920class Solution { private List<String> res = new ArrayList<>(); public List<String> generateParenthesis(int n) { if(n<1) return res; backtracing("", 0, 0, n); return res; &#...

题目给定一个二叉树，它的每个结点都存放着一个整数值。 找出路径和等于给定数值的路径总数。 路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。 二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。 示例1：123456789101112131415root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8 10 / \ 5 -3 / \ \ 3 2 11 / \ \3 -2 1返回 3。和等于 8 的路径有:1. 5 -> 32. 5 -> 2 -> 13. -3 -> 11 思路 + 代码双重递归。 首先建立一个递归寻找以每个节点为根节点的路径查找。 再建立一个递归遍历每一个节点，并以该节点为根节点。 1234567891011121314151617181920212223242526272829303132/** * Definition for a binar...

题目给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。 返回可以使最终数组和为目标数 S 的所有添加符号的方法数。 示例1：1234567891011输入: nums: [1, 1, 1, 1, 1], S: 3输出: 5解释: -1+1+1+1+1 = 3+1-1+1+1+1 = 3+1+1-1+1+1 = 3+1+1+1-1+1 = 3+1+1+1+1-1 = 3一共有5种方法让最终目标和为3。 注意： 数组非空，且长度不会超过20。 初始的数组的和不会超过1000。 保证返回的最终结果能被32位整数存下。 思路 + 代码首先是回溯方法。 12345678910111213141516class Solution { private int cnt = 0; public int findTargetSumWays(int[] nums, int S) { dfs(nums, S, 0, 0); ...

题目编写一个程序，找到两个单链表相交的起始节点。 思路 + 代码1. 最容易想到的，两层遍历求解。 12345678910111213141516171819202122232425262728/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { * val = x; * next = null; * } * } */public class Solution { public ListNode getIntersectionNode(ListNode headA, ListNode headB) { if(headA==null || headB==null) return null; ListNode tmp; ...