算法 1.双指针 2.先保存奇数头节点和偶数头节点（避免引用中的属性发生变化） 3.一个引用指向奇数节点，一个引用指向偶数节点，开始往后处理结点指向 4.结束的条件是，偶数节点不为null且偶数节点的next不为null 5.最后将偶数头节点挂到奇数链表尾节点 public ListNode oddEvenList(ListNode head) { if (head == null || head.next == null) { return head; } ListNode oddHead = head; ListNode evenHe...

算法：twoPass 1.空间换取时间 2.up数组记录前面有多少个连续比自己小的数，down数组记录后面有多少个连续比自己小的数 3.第二次遍历计算最长山脉长度 public int longestMountain(int[] A) { int N = A.length; int[] up = new int[N]; int[] down = new int[N]; for (int i = 1; i < A.length; i++) { if (A[i] > A[i-1]) { up[i] = up[...

算法 1.按照每组的左区间排序 2.遍历每组区间，找到以当前start开始最多能到达的end， 2.1 当start=end时，片段无法继续往后拼接返回-1 2.2 否则，这样就是一个片段，然后把end赋给start接着遍历下一个窗口 public int videoStitching(int[][] clips, int T) { Arrays.sort(clips, (a, b) -> a[0] - b[0]); int result = 0; for (int start = 0, end = 0, i = 0; start < T; sta...

LeetCode39. 组合总和 算法 题目要求：可以重复使用数字，解集唯一 1.排序数组 2.遍历数组的每个数，当作一个解的第一个数，然后依然从当前位置（可以重复使用数字）递归寻找子结果 2.1 遍历到target小于数组中的值时不会有解，停止遍历 2.2 遍历到target等于数组中的值时即发现一个解，下面不可能存在解（数组由小到大排序），停止遍历 ps：避免解集重复，当遍历的位置是开始的第一个位置或者不等于它上一个位置时才算上这一个数 3.遍历每一个子结果，和解的第一个数合并即是一个解，很多个子结果合并即是解集 public List<List<Integer&g...

算法：栈 1.用栈保存各部分计算的和 2.遍历表达式，使用 sign 变量记录运算符，初始化是 '+'；使用 number 变量记录字符串中的数字部分的数字值是多少 2.0 遇到空格时跳过 2.1 遇到数字时继续遍历求这个完整的数字的值，保存到 number 中 2.2 遇到左括号时递归求这个括号里面的表达式的值 先遍历找到对应的右括号，因为可能里面还嵌有多对括号，使用一个变量 counterPartition 统计括号对数直到变量为 0 2.3 遇到运算符时或者到表达式末尾时，就去计算上一个运算符并把计算结果 push 进栈，然后保存新的运算符到 sign 如果是 + ，不要计算，pus...

算法 1.层次遍历 2.每层遍历取最后一个节点即是右视图可以看到的节点 public List<Integer> rightSideView(TreeNode root) { ArrayList<Integer> list = new ArrayList<Integer>(10); if (root == null) { return list; } Deque<TreeNode> deque = new LinkedList<TreeNode>(); deque.off...

算法 滑动窗口 1.初始化区间左右范围start=0，end=0 2.从第一个字符开始遍历，每次找到相同字符的lastIndex；如果比end大，更新end 3.当遍历到end时，划分一个区间，同时更新区间的左范围start=end+1 public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String s = scanner.nextLine(); System.out.println(partitionLabels(s...

算法 1.双指针遍历，name指针和typed指针分别从两个字符串的第一个字符开始遍历，终止遍历的条件是typed指针遍历结束 2.当name的指针没有遍历结束时，比较两指针的字符是否相等 2.1如果相等，都加1移到下一个字符 2.2如果不相等，再看typed的指针是否是长按导致的重复字符，如果是就移到下一个字符，如果不是就返回false ps：代码优化精简 public boolean isLongPressedName(String name, String typed) { int i = 0; for (int j = 0; j < typed.leng...

算法 1.快慢指针找到中间节点 2.可以看出找到的中间节点是一定挂在末尾不会变的，所以将其再移动一个位置，并且把它前面的节点挂个null表示前半部分链表结束 3.翻转后半部分链表 4.将翻转后的后半部分链表逐个插入前半部分即可 public void reorderList(ListNode head) { if (head == null) { return; } ListNode slow = head; ListNode fast = head; while (fast != null && fast.nex...

算法 动态规划 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 = new int[text...

算法 1.设置伪结点，方便处理 2.双指针prev和curr 3.当遇到当前节点值和下一节点值相等的节点时，进行while循环找到下一个不相等的节点，挂到prev节点上 4.当遇到当前节点值和下一节点值不相等的节点时，prev和curr都移动到下一个节点接着遍历就行 public ListNode deleteDuplicates(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode prev = dummy; ListNode curr = hea...

算法 从后往前比较字符 1.用back记录退格符'#'的个数，遍历指针对应的向前移动以此跳过退格符删除的字符 2.当指针对应的字符在两个字符串中不相等或者其中一个字符串先遍历完毕时，退出返回不相等 3.当两个字符串同时遍历完毕时，退出返回相等 public boolean backspaceCompare(String S, String T) { int i = S.length() - 1, j = T.length() - 1, back; while (true) { back = 0; while (i >= 0 &...

算法 层序遍历 1.使用队列层序遍历二叉树 2.维护一个max，从最底层开始计算最大路径和 3.当节点是叶子节点时，节点值和max比较取最大值 4.当节点不是叶子节点时，有这么几种可能的路径和: 4.1 当前节点值 4.2 MAX(左子节点值, 右子节点值) + 当前节点值 4.3 左子节点值 + 右子节点值 + 当前节点值 取三者最大，同时当前节点值要更新为MAX(4.1, 4.2)，继续上一层的计算 public int maxPathSum(TreeNode root) { if (root == null) { return 0; } ...

算法 二分查找 1.初始范围为1，x 2.当middle*middle <= x && (middle+1)*(middle+1) > x时，返回结果 3.当middle*middle < x时，到右半部分继续寻找 4.当middle*middle > x时，到左半部分继续寻找 ps：避免溢出使用逆向运算 public int mySqrt(int x) { if (x <= 0) { return 0; } int left = 1, right = x; while (true) { ...