youxiwang

题解

/ 注册

全部文章 / 题解（共91篇）

题解 | JAVA 递归 #没有重复项数字的全排列# [P3]

就暴力递归 + 回溯(省空间) 每次递归, 从小到大(所以一上来要对num进行排序)遍历待选的数, 选到的数从remain中删除，并插入perm中。 O(n!) O(n!) import java.util.*; public class Solution { ArrayList<...

Java

2022-03-07

5 784

题解 | # JAVA Morris Traversal二叉搜索树与双向链表# [P3]

要求时间O(1), 那就只能Morris Traversal了。 Morris这个视频讲的挺清楚 https://www.youtube.com/watch?v=wGXB9OWhPTg 只需要以下变化 1. 记录第一个visited node作为ans输出 2. 记录lastVisited nod...

Java

2022-03-05

2 443

题解 | JAVA 双指针 #接雨水问题# [P0]

双指针l, r从两边向中间逼近 lMaxH记录l左侧最高的柱子高度 rMaxH记录r右侧最高的柱子高度核心思想是: - 如果lH < rH 那么所有l左侧的柱子也 < rH (i.e. lMax < rH). 如果同时lH < lMaxH, 则l的盛水量为...

Java

2022-03-05

0 381

题解 | JAVA #数据流中的中位数# [P0]

Insert通过binarySearch寻找插入位. 将一个数x插入一个有序数组中，插入位置就是标准二分查找(不论左闭右开还是左闭右闭)的最终左下标“l”。多加一嘴留着自己复习: 二分查找提前输出或不提前输出不影响排序结果，但影响有duplicate情况下的插入位置不提前输出(不论左闭右开...

Java 二分查找

2022-03-04

0 303

题解 | #寻找峰值# [P2]

对于i: 如果i左右相邻的柱子都没i高，那么i就是peak, return i. 如果i右边相邻的柱子比i高，那么i的右侧一定存在peak, binarySearch right 如果i左边相邻的柱子比i高，那么i的左侧一定存在peak, binarySearch left (如果左右都比i高,两...

Java

2022-03-03

0 260

题解 | #合并k个已排序的链表# [P1]

普通mergeSort 时间: O(nlogn) 空间: O(k) k为list的个数(所有list都会在递归栈上) worstcase还是O(n), i.e.每个list的长度都为1 [{1},{2}, ... {n}] import java.util.*; public class So...

Java

2022-02-22

0 351

题解 | JAVA #删除有序链表中重复的元素-II# [P3]

sentinal指向之前遍历过的所有unique元素组成的链表。 lastUnique指向该链表的最后一个元素遍历时每发现一个unique元素(与相邻元素值不想等)，将其append到lastUnique的后面就完事儿了。时间 O(n) 空间 O(1) import java.util.*...

Java

2022-02-22

0 467

题解 | JAVA 递归#给单链表加一# [P1]

对于链表，如果要从后往前操作，一般就是用递归最方便每次递归完返回进位（0 或者 1). 链表最前方加上个sentinal node以防最高位进位，e.g. (99+1=100) 时间 O(n) 空间 O(n): basecase时每一位的node都在栈上 import java.util.*;...

Java

2022-02-22

0 500

题解 | JAVA 快排#单链表的排序 [P3]

看大部分解体都是用的mergeSort, 所以就写个quickSort的版本. 就是最普通的QuickSort只不过把数字换成Node存到一个Array里时间: O(nlogn) 空间: O(n) import java.util.*; public class Solution { p...

Java

2022-02-22

0 301

题解 | #滑动窗口的最大值# [P0-T2]

在第i个数要找左侧窗口内的最大数。所以又可以单调栈套娃唯一需要变化的就是栈上只保留窗口以内的数，所以栈上存下标以查看栈上最老的数是否还在窗口内。再来一遍口诀：找右边的就从右往左，找左边的从左往右找小的就递增，找大的就递减这里找左边最大, 那就是从左向右+递减。 import java.u...

Java 滑动窗口

2022-02-11

1 487