java版——双指针 容量是由最小的那个边决定的，即  area = min(height[legt], height[right]) * (right - left)  然后我们每次移动较小的边，比如， height[left] < height[right] ，那我们就让 left++ 。 为什么呢？ 因为如果我们移动较大的边，那么移动后得到的容量一定会比现在小。即使较大边移动后遇到更大的边，但是容量是由较小边决定的，即容器的高度还是 height[left] ，但是宽度却变小了。所以移动较大边必不可能得到一个更大的容器，而移动较小边是有可能得到一个更大的容器的。  public c...

java版——双指针  public class Solution { public int maxLength (int[] arr) { Set<Integer> set = new HashSet<>(); int left = 0; int right = 0; int maxLen = -1; while(right < arr.length){ // 扩大右指针，直到遇到重复元素 while(right < arr.length && !set.contains(arr[right])){ set.add(arr[right++]...

java版  public class Solution { public String solve (String s, String t) { int i = s.length() - 1; int j = t.length() - 1; int curr = 0; int carry = 0; StringBuffer sb = new StringBuffer(); while(i >= 0 && j >= 0){ int a = s.charAt(i) - '0'; int b = t.charAt(j) - '0'; curr = (a + b + ca...

java版  public class Solution { public String solve (String IP) { if(isIPv4(IP)){ return "IPv4"; }else if(isIPv6(IP)){ return "IPv6"; }else{ return "Neither"; } } private boolean isIPv4(String IP){ String[] strs = IP.split("\\."); int len = strs.length; if(len == 0 || len != 4){ return false; } for(i...

dp[i][0] 表示第 i 天不持有股票，此时可以获得的最大利益， dp[i][1] 表示第 i 天持有股票，此时可以获得的最大利益。那么 dp[i][0] 的值可以来源于 dp[i - 1][0] ，即今天什么也没干，直接继承昨天的状态。或 dp[i - 1][1] + prices[i] ，即昨天持有股票，今天把股票卖了。两者的最大值即为 dp[i][0] 的值。  dp[i][0] = max(dp[i - 1][0], dp[i - 1][1] + prices[i]);  dp[i][1] 的值可以来源于 dp[i - 1][1] ，即今天什么也没干，直接继承昨天的状态。或 dp[...

java版——动态规划 dp[i][j] 表示 str1 的前 i 个字符和 str2 的前 j 个字符的编辑距离。 (以下说的相等是指我们已经知道它们的编辑距离)   如果 str1 的前 i - 1 个字符和 str2 的前 j 个字符相等，那么我们只需要在 str1 最后删除一个字符就可以转化为 str2 。 dp[i][j] = dp[i - 1][j] + 1 如果 str1 的前 i 个字符和 str2 的前 j - 1 个字符相等，那么我们只需要在 str1 最后插入一个字符就可以转化为 str2 。 dp[i][j] = dp[i][j - 1] + 1 如果 str1 的前 ...

java版——回溯 常规版回溯，通俗易懂  public class Solution { ArrayList<String> res = new ArrayList<>(); // 存放结果集 ArrayList<String> ipset = new ArrayList<>(); // 存放每一种合法的ip子集 public ArrayList<String> restoreIpAddresses (String s) { int len = s.length(); if(len < 4 || len > 12){ /...

public class Solution { public String LCS (String s1, String s2) { int len1 = s1.length(); int len2 = s2.length(); // dp[i][j]记录s1长度为i，s2长度为j的最长公共子序列长度 int[][] dp = new int[len1 + 1][len2 + 1]; for(int i = 1; i <= len1; i++){ for(int j = 1; j <= len2; j++){ if(s1.charAt(i - 1) == s2.charAt(j -...

理想情况下每个元素都在自己的位置上，如下：  现在将元素对应位置打乱，并且缺失了一个元素，如下：  那么怎么找到这个缺失元素呢？我们可以依次遍历数组 nums ，每遍历到一个元素，比如 nums[i] ，就将 nums[i] 的值对应的位置做上标记，表示这个位置上的主人出现过，只是现在不在这个位置。遍历结束后，如果某个位置上没有被标记，说明这个位置上的主人缺失了。  `  nums[1] = 3，将3这个位置做标记。  nums[2] = 1，将1这个位置做标记。  nums[3] = 5，将5这个位置做标记。  nums[4] = 1，将1这个位置做标记。  nums[5] = 6，将6这个...

两个栈 st1 和 st2，一个用来存操作数 （st1) ，一个用来存运算符和左括号 (st2)。  当遇到 '(' 就入 st2 栈。 当遇到操作数就如 st1 栈。 当遇到操作符，有两种情况 3.1 如果这个操作符优先级小于等于 st2 栈顶操作符的优先级，则从 st1 中出栈两个操作数，从 st2 中出栈一个操作符，并做运算，将运算结果放入 st1 栈中。 3.2 如果这个操作符优先级大于 st2 栈顶操作符的优先级，则直接入栈。 当遇到 ')' ，每次出栈两个操作数和一个操作符，并将运算结果存入 st1 中，直到 st2 栈顶为 '(' ，并将这个 '(' 出栈。   public c...

java版 方法一：快排 很多人用快排最后一个用例会超时，解决方法是，随机的选取枢轴pivot。  public class Solution { public int findKth(int[] a, int n, int K) { // write code here return quickSort(a, 0, n - 1, K); } private int quickSort(int[] nums, int low, int high, int target) { int i = low, j = high; // 随机选取枢轴，并将它与num[i]交换 int rand = (in...

单调队列——java版 https://liyanzu0926.github.io/2022/03/13/page-4/ public class Solution { public ArrayList<Integer> maxInWindows(int [] num, int size) { Deque<Integer> queue = new LinkedList<>(); ArrayList<Integer> res = new ArrayList<>(); // 初始窗口 for(int i = 0; i < size;...

通过前序和中序构建二叉树同上一题。 求二叉树的右视图可以用层次遍历，找到每一层的最后一个结点并把它并入结果集。  public class Solution { public int[] solve (int[] xianxu, int[] zhongxu) { // write code here TreeNode root = buildTreeByPreorderAndInorder(xianxu, 0, xianxu.length - 1, zhongxu, 0, zhongxu.length - 1); return BFS(root); } private int[] BFS(Tr...

Java版——由前序和中序构建二叉树 https://liyanzu0926.github.io/2022/03/06/second/ public class Solution { public TreeNode reConstructBinaryTree(int [] pre,int [] vin) { return reConstructBinaryTree(pre, 0, pre.length - 1, vin, 0, vin.length - 1); } private TreeNode reConstructBinaryTree(int[] pre, int l1, int r1,...