import java.util.*; public class Solution { public int Jump (int n, int[] A) { // 0作为起始点，n-1作为终点 int step = 0; // 跨了X步 int dist = 0; // 跨了X步最远能到哪个点 int i = 0; while (dist < n-1) { int lastDist = dist; // X步(i.e.上一步)能跨到的范围内 while (i <= lastDist) { // 跨x+1步最远能到哪个点 dist = Math.max(i + A[i], dist)...

空间: O(Max(m, n))， 时间: O(mn) 定义LCS(i, j)为s1.substring(0, i+1)和s2.substring(0, j+1)的最长公共序列。 对于每一对i, j，以下两种情况： 如果s1[i] = s2[j], LCS(i, j) = LCS(i-1, j-1) + 1 如果s1[i] != s2[j], LCS(i, j) = MAX(LCS(i-1,j), LCS(i, j-1))  代码： // no space optimization - O(mn) space. import java.util.*; public class Solution...

dp, 定义: min(i)为arr[0,i]包含arr[i]的最小子数乘积 max(i)为arr[0,i]包含arr[i]的最大子数乘积 注意min,max都是可正可负 很明显 min(i+1)只有三种可能： 1. = min(i) * arr[i+1] // 比如min(i) = -1, arr[i+1] = 2 2. = max(i) * arr[i+1] // 比如max(i) = 1, arr[i+1] = -2或者0.5 2. = arr[i+1] // 比如min(i) = -1, max(i) = 0.5, arr[i+1] = -2 那么min(i+1) = Math.min...

自知表达能力不行肯定讲不清楚，干脆找了个讲的清楚的视频链接 https://www.youtube.com/watch?v=rf6uf3jNjbo 这里我直接recursion了 没去记忆了。 时间O(n^2), 每次recursion会分两支新的recursion 空间O(n), 递归n层，所以栈最高也是n层。 想要动态规划+记忆就把F(n, x, y)存个HashMap<String, LinkedList> key = String.formart("%d-%d-%d", n, x, y) value就是solve(n,x,y)的return值。 import java.ut...

DP解 import java.util.*; public class Solution { public int uniquePaths (int m, int n) { int[][] mem = new int[m][n]; // fill first row/col with 1 Arrays.fill(mem[0], 1); for (int[] row : mem) row[0] = 1; for (int r = 1; r < m; r++) { for (int c = 1; c < n; c++) { mem[r][c] = mem[r-1][c] + mem[...

这题因为是找最浅的leaf node，明显BFS会更合适。 那对于二叉树，BFS就是levelOrder traversal。找到第一个leaf就直接return当前深度。 时间O(n) 空间O(n) import java.util.*; public class Solution { public int run (TreeNode root) { if (root == null) return 0; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); int depth = 0; while (!q.is...

正常level-order traversal，每层到一个array里 反向打印就用Linklist的descendingIterator, 或者用stack存每层的值就行。\ import java.util.*; public class Solution { public int[][] levelOrderBottom (TreeNode root) { if (root == null) return new int[0][]; LinkedList<int[]> list = new LinkedList<>(); Queue<TreeNode>...

可以这样去给每一层的node编号： root = 0； root.left = root << 1; root.right = (root << 1) + 1; A 0 / \ / \ B C => 00 01 / \ \ / \ \ D E F 000 001 011  遍历就用preOrder recursive。parent根据自己的编号给child assign编号 遍历过程中用一个List<int[2]>去记录目前为止每层(0 based)看到过的的最大,最小编号。 遍历结束后把list里每一层的最大最小编号求差，输出最大差+1就是结果 比如...

跟这题一样的 https://blog.nowcoder.net/n/4012546b98ae4356ab926184ed323c58 import java.util.*; public class Solution { public boolean isCompleteTree (TreeNode root) { if (root == null) return false; Queue<TreeNode> q = new LinkedList<>(); q.offer(root); boolean ended = false; while(!q.isEmpty()...

每个node的max直径是(leftTreeHeight + rightTreeHeight). 设个Gobal var存目前看到的最大diameter. dfs返回当前node为root的treeHeight。 import java.util.*; public class Solution { int diameter = 0; public int diameterOfBinaryTree (TreeNode root) { dfs(root); return diameter; } // returns height of the tree int dfs(TreeNode root...

利用search tree的性质，在每个node上其实已经知道p和q分别在哪个child subtree。 对于一个node，以下三种情况可以直接确定该node就是LCA. left里有一个target，root本身是一个target right里有一个target, root本身是一个target left, right里各有一个target  然后如果node不是LCA, 那么两个target要么都在left child, 要么都在right child. 所以只需要check其中的一边 (其实check的node都在一条确定的path上). 时间，空间复杂度都是O(h) worst-ca...

跟精华解法里第二个HashMap的一样思路 JAVA版 类似于用preOrder和inOrder重构一个right-first-preOrder traversal. https://blog.nowcoder.net/n/983254e186b2484c855622e68136bbc6 在recurse的同时记录当前node的层数，然后print该层第一个visit到的node. 因为是right-first-preOrder, 每层第一个visit的noded就是最右边的node.  import java.util.*; public class Solution { public in...

整体思路 - serialize和deserialize都用先序遍历实现 题目里的例子：  先序遍历就用标准recursion，null用#表示，node用“|"分割：  visit(root); recurse(left); recurse(right);  serialize结果："1|2|#|#|3|6|#|#|7|#|#|" (最后多个"|"，但是不影响) deserialize可以直接把Scanner当queue用。Scanner.next()相当于Queue.poll(). 在每个node Scanner所看到的String对应的是 node1: "1|2|#|#|3|6|#|#|...

搜索二叉树: in-order traversal (iterative). 记录上一次visit的值 (lastPoped)。没次visit只要check值是不是小于lastPoped.  相同解法也可以用recursion实现，但是需要把lastPoped存成global。 完全二叉树: level-order traversal (iterative). 层序遍历中第一次看到null就让ended=true，表示所有非null的node都遍历完了。 那么之如果再见到非null的node那么tree就不是complete。 import java.util.*; public class ...