Interview-Notes

class Solution { // dp[n] 代表 爬到n接楼梯的方法数 // 递推公式：f(n) = f(n-1) + f(n-2) // 初始值dp[0] = 1;dp[1] = 1; // 遍历顺序：从小到大 public int climbStairs(int n) { int[] res = new int[n+1]; res[0] = 1; res[1] = 1; for(int i = 2; i <= n; i++){ res[i] = res[i-1] + res[i-2]; } return res[n]; } }

class Solution { //动态规划 // dp[i][j] 意味着将word1的前i个字符转化为word2的前j个字符的最少操作数 // dp[i][0] = i; dp[0][j] = j; //递推公式：if (s.charAt(i) == s.charAt(j)) dp[i][j] == dp[i - 1][j - 1] // else dp[i][j] = Math.max(dp[i - 1][j -1] + 1, dp[i-1][j] + 1, dp[i][j-1] + 1); // 对应替换的 public int minDistance(String word1, String word2) { int n = word1.length(); int m = word2.length(); int[][] dp = new int[n + 1][m + 1]; for (int i = 0; i <= n; i++) { dp[i][0] = i; } for (int j = 0; j <= m; j++) { dp[0][j] = j; } for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { if (word1.charAt(i - 1) == word2.charAt(j - 1)) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = Math.min(dp[i-1][j-1] + 1 , Math.min(dp[i-1][j] + 1, dp[i][j-1] + 1)); } } } return dp[n][m]; } }

class Solution { // 把当前元素作为矩阵的右下角，用一个数组记录当前行到当前位置的连续的1的个数，得到矩阵的最大宽 // 垂直遍历，计算宽和高，得到面积，求出对应位置面积的最大值 public int maximalRectangle(char[][] matrix) { int row = matrix.length; int col = matrix[0].length; int maxArea = 0; int[][] maxWidth = new int[row][col]; // 记录以当前元素为右下角的最大宽 for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (matrix[i][j] == '1') { maxWidth[i][j] = (j > 0) ? maxWidth[i][j - 1] + 1 : 1; } } } for (int i = 0; i < row; i++) { for (int j = 0; j < col; j++) { if (matrix[i][j] == '1') { int width = maxWidth[i][j]; int area = width; for (int k = i - 1; k >= 0; k--) { width = Math.min(maxWidth[k][j], width); //构建矩形的最大宽 area = Math.max(width*(i - k + 1), area); } maxArea = Math.max(area, maxArea); } } } return maxArea; } }

class Solution { public int numTrees(int n) { int[] dp = new int[n+1]; //dp[i]表示n个节点组成的二叉搜索数的种数 dp[1] = 1; dp[0] = 1; //递推公式：选定任意点i作为根节点，则左子树为[1,i-1];右子树为[i+1,n]; //dp[i] = ∑(dp[i-1] * dp[n-i]) // dp[1] = 1 // 遍历顺序：从前向后 for (int i = 2; i <=n; i++) { // 总共有多少个节点 for (int j = 1; j <= i; j++) { // 选哪一个做根节点 dp[i] += dp[j-1]*dp[i-j]; } } return dp[n]; } }

/** * 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 { // 1.层序遍历，每次删除两个节点，判断轴对称的两个节点的值是否相等，并将他们的左右子节点的轴对称位置添加进行 // 2.递归 public boolean isSymmetric(TreeNode root) { // if (root == null) { // return true; // } // return isMirror(root.left, root.right); if (root == null) { return true; } Queue<TreeNode> que = new LinkedList<>(); que.offer(root.left); que.offer(root.right); while (!que.isEmpty()) { int len = que.size(); for (int i = len; i > 0; i -= 2) { TreeNode tmp1 = que.poll(); TreeNode tmp2 = que.poll(); if (tmp1 == null && tmp2 == null) { continue; } if (tmp1 == null || tmp2 == null || tmp1.val != tmp2.val) { return false; } que.offer(tmp1.left); //轴对称的添加节点 que.offer(tmp2.right); que.offer(tmp1.right); que.offer(tmp2.left); } } return true; } // public boolean isMirror(TreeNode left, TreeNode right) { // if (left == null && right == null) return true; // if (left == null || right == null) return false; // return left.val == right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left); // } }

/** * 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<List<Integer>> resList = new ArrayList<List<Integer>>(); // public List<List<Integer>> levelOrder(TreeNode root) { // checkFun(root); // return resList; // } // public void checkFun(TreeNode node){ // Queue<TreeNode> que = new LinkedList<TreeNode>(); // if(node == null){ // return; // } // que.offer(node); // while(!que.isEmpty()){ // List<Integer> itemList = new ArrayList();//每一层的元素放到一个列表里 // int len = que.size(); //遍历每一层的节点时。将他们的左右节点放入队列，队列的size就是整个 // while(len > 0){ //层的元素个数 // TreeNode tmpNode = que.poll(); // itemList.add(tmpNode.val); // if(tmpNode.left != null){ // que.offer(tmpNode.left); // } // if(tmpNode.right != null){ // que.offer(tmpNode.right); // } // len--; // } // resList.add(itemList); // } // } // 层序遍历，经典算法题，首先把头结点添加到队列，然后将队列中的元素按顺序poll(),如果左右节点不为空，则将左右节点添加到队列 public List<List<Integer>> levelOrder(TreeNode root) { List<List<Integer>> res = new ArrayList<>(); if (root == null) { return res; } Queue<TreeNode> que = new LinkedList<>(); que.offer(root); while (!que.isEmpty()) { int len = que.size(); List<Integer> level = new ArrayList<>(); while (len > 0) { TreeNode tmp = que.poll(); level.add(tmp.val); if (tmp.left != null) { que.offer(tmp.left); } if (tmp.right != null) { que.offer(tmp.right); } len--; } res.add(level); } return res; } }

/** * 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 { // 1. 层序遍历，用一个变量记录总共有多少层 // 2.递归 public int maxDepth(TreeNode root) { if (root == null) { return 0; } int leftDepth = maxDepth(root.left); int rightDepth = maxDepth(root.right); return Math.max(leftDepth,rightDepth) + 1; // if (root == null) { // return 0; // } // Queue<TreeNode> que = new LinkedList<>(); // que.offer(root); // int count = 0; // while (!que.isEmpty()) { // int len = que.size(); // count++; // while (len > 0) { // TreeNode tmp = que.poll(); // if (tmp.left != null) { // que.offer(tmp.left); // } // if (tmp.right != null) { // que.offer(tmp.right); // } // len--; // } // } // return count; } }

/** * 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; * } * } */ public class Solution { // 对于一颗二叉树，前序遍历的第一个值是根节点的值，根据根节点的值和中序遍历可以得到左右子树 // 递归的得到左右子树的根节点 // 从先序遍历中取出第一个元素创建根节点。 // 在中序遍历中找到该根节点的位置，这将中序遍历分为两部分，左边是树的左子树，右边是树的右子树。 // 递归地使用左子树的先序和中序遍历结果重建左子树。 // 递归地使用右子树的先序和中序遍历结果重建右子树。 // 返回根节点 int preIndex = 0; HashMap<Integer, Integer> hs = new HashMap<>(); public TreeNode buildTree(int[] preorder, int[] inorder) { for (int i = 0; i < inorder.length; i++) { hs.put(inorder[i], i); } return buildTreeRecursive(preorder, 0, inorder.length - 1); } // recursive 递归 // 利用前序遍历的顺序构建子树，中序遍历得到左子树和右子树的范围 public TreeNode buildTreeRecursive(int[] preorder, int left , int right) { if (left > right) { return null; } int rootVal = preorder[preIndex++]; // 前序遍历的第一个节点总是当前子树的根 TreeNode root = new TreeNode(rootVal); int index = hs.get(rootVal); root.left = buildTreeRecursive(preorder, left, index - 1); root.right = buildTreeRecursive(preorder, index + 1, right); return root; } }

/** * 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 { // 用一个列表存储先序遍历的结果，再构建单链表，将列表中的节点的左指针赋值为空，右指针指向列表中的下一个位置 List<TreeNode> res = new ArrayList<>(); public void flatten(TreeNode root) { if (root == null) { return; } preOrder(root); for (int i = 0; i < res.size() - 1; i++) { // 这里是小于 res.size() - 1,确保不会数组越界 TreeNode node = res.get(i); node.left = null; node.right = res.get(i + 1); } } public void preOrder(TreeNode root) { if (root == null) { return; } res.add(root); preOrder(root.left); preOrder(root.right); } }

/** * 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; * } * } */ // 空间复杂度O(N) 递归的深度，最坏是节点的个数 // 时间复杂度O(H) 树的高度 // 方法： 递归 + 后序遍历 // 对于一个节点，他能向上层节点提供的最大值是当前节点的值 + max(左,右子树的最大路径) // 当前节点嘴和路径中点的最大路径和 = 左右子树的的最大路径 + 当前节点的值 class Solution { private int maxSum = Integer.MIN_VALUE; public int maxPathSum(TreeNode root) { maxGain(root); return maxSum; } private int maxGain(TreeNode node) { if (node == null) { return 0; } int leftGain = Math.max(maxGain(node.left), 0); int rightGain = Math.max(maxGain(node.right), 0); maxSum = Math.max(maxSum, node.val + leftGain + rightGain); // 更新最大值 return node.val + Math.max(leftGain, rightGain); // 返回不作为路径终点时能贡献的最大值 } }