中序遍历二叉搜索树，得到的值序列是有序序列。因此，中序遍历二叉树，访问某个节点的时候，如果出现了反序情况，那么表明该树不是二叉搜索树。 层序遍历完全二叉树，判断孩子是否存在，存在则进入状态1，不存在则进入状态0，则层序遍历完全二叉树满足状态机：s → 状态1 → 状态0 → e，其中状态1和状态0有自旋边。如果遍历二叉树时，出现状态0变成状态1的情况，那么表明该树不是完全二叉树。  import java.util.*; public class Solution { /** * 二叉搜索树的全局顺序，-1表示由小到大，0表示全等，1表示由大到小。 */ private int order; ...

数学排列组合题。向左和向右走的步数总共是(m + n - 2)，总步数全排列是(m + n - 2)!，其中每种走法重复(m - 1)! * (n - 1)!次。 所以不同的走法共：(m + n - 2)! / (m - 1)! / (n - 1)!。  public class Solution { /** * 数学运算表达式：(m + n - 2)! / (m - 1)! / (n - 1)! * @param m int整型 * @param n int整型 * @return int整型 */ public int uniquePaths (int m, int n) { int to...

如下面代码所示，Java的封装类型Integer也实现了将十进制转换为其他进制的方法。 public class Solution { /** * 进制转换 * @param M int整型 给定整数 * @param N int整型 转换到的进制 * @return string字符串 */ public String solve (int M, int N) { return Integer.toString(M, N).toUpperCase(); } }

import java.util.ArrayList; import java.util.Arrays; import java.util.HashMap; public class Solution { public ArrayList<ArrayList<Integer>> threeSum(int[] num) { if (num == null || num.length < 3) return new ArrayList<>(0); Arrays.sort(num);//排序处理，方便后面去重 //存放原数组的相反数，key为原数组值，val...

import java.util.LinkedHashMap; import java.util.Map; public class Solution { private final LinkedHashMap<Integer, Integer> cache; public Solution(int capacity) { this.cache = new LinkedHashMap((int) (capacity / 0.75f + 2), 0.75f, true) { @Override protected boolean removeEldestEntry(Map.Entry...

（算法思路详见《算法导论（第3版）》15.4 最长公共子序列 ）  public class Solution { private static final String EMPTY = "-1"; private String currLCS = ""; /** * longest common subsequence * @param s1 string字符串 the string * @param s2 string字符串 the string * @return string字符串 */ public String LCS (String s1, String s2) { if (s1...

采用后序遍历。当访问当前节点值的时候，统计并保存两个变量：以当前节点为一端的路径的最大路径和，全局最大路径和。 当访问当前节点值的时候，已知的值有： 当前全局最大路径和Max，以左子树根节点为一端的路径的最大路径和L，以右子树根节点为一端的路径的最大路径和R，当前节点值V。 求当前全局最大路径和Max，正常比较需要比较6次，①V与Max②Max与V+L③Max与V+R④Max与V+L+R⑤Max与L⑥Max与R。 但是由于采用的是递归，左右子树都已经跟Max比较过了，因此⑤和⑥是多余的。因此仅需要比较4次。 利用数学不等式分析发现，如果L、R都是正数，那么当前全局最大路径和Max = Max{...

发现规律：如果数组两端恰好是“杯壁”，即数组两端的值是第一和第二大的，那么 雨水的面积 = 以数组长度为底且以最长杯壁为高的矩形面积 - 墙壁面积 - 空白面积; 其中， 以数组长度为底且以最长杯壁为高的矩形面积 = 第一大的值 * (|第一大的值的下标 - 第二大的值的下标| + 1); 墙壁面积，即数组元素的和，可以累加计算得出，在遍历数组的时候就可以顺便累加; 空白面积 = (第一大的值 - 第二大的值) * (|第一大的值的下标 - 第二大的值的下标|)。 因此，得到一个解题思路——尽可能地找“杯壁”。 注意事项：使用Java语言，还要注意两个int类型相乘可能会溢出，导致计算结果不正...

转换二维变量：将i和j，转化为，h和l，即最高和最低价格的下标，其中必须满足h >= l。 import java.util.*; public class Solution { /** * * @param prices int整型一维数组 * @return int整型 */ public int maxProfit (int[] prices) { if (prices == null || prices.length <= 1) return 0; int h = 0,l = 0;//最高和最低点的价格的下标，必须满足h >= l int max = 0; for (...

用java语言也能通过，但是运行时间耗费2.7s。 import java.util.*; /* * public class ListNode { * int val; * ListNode next = null; * } */ public class Solution { /** * @param head1 ListNode类 * @param head2 ListNode类 * @return ListNode类 */ public ListNode addInList(ListNode head1, ListNode head2) { // write code here Deq...

  #牛客试题#输入一个链表，反转链表后，输出新链表的表头。 https://www.nowcoder.com/questionTerminal/75e878df47f24fdc9dc3e400ec6058ca