LeetCode原题 算法 1.动态规划：dp[i][j]表示str1[0,i-1]和str2[0,j-1]的最长公共子序列 2.初始状态：dp[x][0] = 0, dp[0][x] = 0 3.过渡公式： 如果str1[i]==str2[j], dp[i][j] = dp[i-1][j-1] + 1; 如果str1[i]!=str2[j], dp[i][j] = MAX(dp[i-1][j], dp[i][j-1]); public int longestCommonSubsequence(String text1, String text2) { int[][] dp...

算法 1.多数投票算法 2.出现次数超过一半的数字则超过其他所有数字出现次数之和 3.保存两个变量，result和times，遍历数组 如果当前数字等于result，times加一 如果当前数字不等于result，且times不等于0，times减一 如果当前数字不等于result，且times等于0，置result为当前数字，times为1 public int majorityElement(int[] nums) { // checkArguments(nums); int result = nums[0]; int times = 1; fo...

算法 使用两个HashSet public int[] intersection(int[] nums1, int[] nums2) { HashSet<Integer> set1 = new HashSet<>(); for (int x : nums1) { set1.add(x); } HashSet<Integer> set2 = new HashSet<>(); for (int x : nums2) { if (set1.contains(x)) { ...

算法 1.每个节点有三种路径：贯穿节点的路径，贯穿左子节点的路径，贯穿右子节点的路径 2.贯穿节点的路径等于左子树的深度+右子树的深度，左子节点和右子节点的路径可以递归计算 3.比较最大的即可 public int diameterOfBinaryTree(TreeNode root) { if(root == null){ return 0; } int diameter = depth(root.left) + depth(root.right); int ldiameter = diameterOfBinaryTree(root.l...

LeetCode98. 验证二叉搜索树 算法 1.递归 2.重载一个函数，界定节点值的范围(lower, upper) 3.递归判断左子树和右子树是否是二叉搜索树 public boolean isValidBST(TreeNode root) { return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE); } private boolean isValidBST(TreeNode root, long lower, long upper) { if (root == null) { return ...

递归 算法 递归 public void preorder(TreeNode root, List<Integer> list) { if (root != null) { list.add(root.val); preorder(root.left, list); preorder(root.right, list); } } public void inorder(TreeNode root, List<Integer> list) { if (root != null) { ...

算法 1.ArrayList保存所有元素；Random用于随机获取；HashMap的键是元素，值是键在ArrayList中的位置索引，用LinkedHashSet保存可以以O(1)的时间获取迭代器并删除第一个 2.插入： HashMap中不存在，新建一个LinkedHashSet添加索引； HashMap中存在，直接获取LinkedHashSet并添加索引； 最后将元素添加到ArrayList中； 3.删除： HashMap中不存在，删除失败； HashMap中存在 获得LinkedHashSet中的第一个位置索引并删除之； 随后把ArrayList中的最后一个位置的元素替换这个删除掉的位...

算法 1.统计陆地（1）的个数 2.统计重边个数，没遇到一个陆地检查其下方和右方是否也是陆地，如果是就含有一个重边 3.4*陆地个数-2*重边个数即是岛屿周长 public int islandPerimeter(int[][] grid) { int row = grid.length; int col = grid[0].length; int grids = 0; int repeatEdges = 0; for (int i = 0; i < row; i++) { for (int j = 0; j < col...

算法 1.动态规划：dp[i][j]表示(0,0)到(i,j)位置的最小路径和 2.初始状态：dp[i][0] = dp[i-1][0] + matrix[i][0]；dp[0][i] = dp[0][i-1] + matrix[0][i] 3.过渡公式：dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j]；到(i,j)的最小路径和等于上方和左方的较小路径和加上当前位置值 public int minPathSum(int[][] matrix) { int row = matrix.length; int ...

算法 1.递归 2.重载一个函数sumNumbers(TreeNode root, int sum)表示计算到root节点为止的sum值 3.当左右子节点都为null时，是叶子节点，返回sum 4.当左或右子节点不为null时，不是叶子节点，递归计算左或右子节点的sum值 public int sumNumbers(TreeNode root) { if (root == null) { return 0; } return sumNumbers(root, root.val); } private int sumNumbers(TreeNod...

原题插入删除替换代价都是1 算法 1.动态规划：dp[i][j]表示word1的前i个字符编辑成word2的前j个字符需要的最小操作数 2.初始状态：dp[i][0] = i，i次删除；dp[0][i] = i，i次插入 3.过渡公式： 当i字符等于j字符时：dp[i][j] = dp[i-1][j-1]，不需要额外操作 当i字符不等于j字符时：dp[i][j] = Math.min(insert, delete, replace) int insert = dp[i][j-1] + 1; i个编辑成j-1个字符，再插入一个j int delete = dp[i-1][j] + 1; i-...

算法 1.回溯法：回溯的过程是函数的进入与退出 2.记录左括号和右括号的数量： 当左括号数量小于n时继续添加左括号 当右括号数量小于左括号时继续添加右括号 public List<String> generateParenthesis(int n) { ArrayList<String> result = new ArrayList<>(10); backtrack("", 0, 0, n, result); return result; } private void backtrack(String string, in...

算法 HashMap + HashSet public boolean uniqueOccurrences(int[] arr) { HashMap<Integer, Integer> map = new HashMap<>(); for (int x : arr) { map.put(x, map.getOrDefault(x, 0) + 1); } return map.size() == new HashSet<Integer>(map.values()).size(); }

算法 1.递归 2.如果n小于0，x取倒数，使n大于0，转换为正数幂 3.如果n大于等于0，分为奇数和偶数递归计算 ps：防止溢出使用long整型 public double myPow(double x, int n) { if (n < 0) { long l = - (long) n; return 1.0 / myPowOfPositive(x, l); } else { return myPowOfPositive(x, n); } } private double myPowOfPositive...