复杂度

时间复杂度

  • 估算程序指令的执行次数/执行时间

空间复杂度

  • 估算程序指令所需占用的存储空间

大 O 表示法

有了时间复杂度,空间复杂度,那么究竟该用什么来表示其大小呢?我们因此衍生了一种表示方式——大 O 表示法

什么是大 O 表示法呢?表示的是数据规模 n 对应的复杂度

  • 公式:T(n) = O( f(n) )
    • n 为数据规模,即是函数中变量 n
    • f(n)为代码总执行次数与数据规模关系
    • T(n)为代码执行时间

判断方式:

  • 由于在一个程序中可能由多个函数组成,其大 O 是多个复杂度累计的,那么我们只需要关心最复杂的那个即可,因此我们需要去:忽略常数,系数,低阶

    1
    常量阶O(1)) < 对数阶O(logn) <  线性阶O(n) < 线性对数阶O(nlogn) < 平方阶O(n²)...立方阶O(n³)...k方阶 < 指数阶O(2^n) < 阶乘阶O(n!) <n的n次方阶级O(n^n)

线性结构

  • 线性表是具有 N 个相同类型元素的有限序列(N>=0)

(数组,链表,栈,队列,哈希表/散列表)

数组(Array)

数组概念

  • 数组是一种顺序存储的线性表,所有元素的内存地址是连续image-20200910210432530

ArrayList 动态数组

  • ArrayList 函数接口image-20200910211154393

ArrayList 源码分析

属性
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
{
// 版本号
private static final long serialVersionUID = 8683452581122892189L;
// 缺省容量
private static final int DEFAULT_CAPACITY = 10;
// 空对象数组
private static final Object[] EMPTY_ELEMENTDATA = {};
// 缺省空对象数组
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
// 元素数组
transient Object[] elementData;
// 实际元素大小,默认为0
private int size;
// 最大数组容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
}
构造方法
无参构造方法
1
2
3
4
//此时我们创建的ArrayList对象中的elementData长度是1,size为0,只有当第一次进行add时候,elementData变成默认长度10
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
有参构造方法
  • 传参构造
1
2
3
4
5
6
7
8
9
10
11
    //参数大于等于0,就用那个参数,否则抛出异常
public ArrayList(int initialCapacity) {
if (initialCapacity > 0) {
this.elementData = new Object[initialCapacity];
} else if (initialCapacity == 0) {
this.elementData = EMPTY_ELEMENTDATA;
} else {
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public ArrayList(Collection<? extends E> c) {
//将collection对象转换成数组,然后将数组的地址的赋给elementData。
Object[] a = c.toArray();
//大于 0 则用Arrays.copy方法,把collection对象内容拷贝到elemD
//ps:这里是深拷贝,意思是只复制了内容而不是地址,意思是原来的东西变化并不会影响到我复制后的
if ((size = a.length) != 0) {
if (c.getClass() == ArrayList.class) {
elementData = a;
} else {
elementData = Arrays.copyOf(a, size, Object[].class);
}
//假如size = 0 直接把空对象地址给elemD
} else {
// replace with empty array.
elementData = EMPTY_ELEMENTDATA;
}
}
方法
add 方法
  • 带参数的 add 方法
  • 不带参数的 add 方法

LeetCode-数组相关

  • 首先我们要明白用数组解题,或者题目中牵扯到数组的优势与劣势与特点
  • 优势:我们是知道数组的首末索引的,可以方便我们查找遍历
  • 劣势:由于数组每个位置上都有东西,我们有时候插入删除有点麻烦

多指针解法

LeetCode 88.合并两个有序数组![image-20200907141226830](

https://er11.oss-cn-shenzhen.aliyuncs.com/img/image-20200907141226830.png)

采用了双指针的解法:

  • p1,p2 各自指向数组中最后一个数据;

  • p3 指向合并后新数组的最后一个位置;

当 p1,p2 遍历完各自的数组时,或者是 p3 指针遍历到了头的位置的时候:结束循环。

当如果 p1(下标)<0,意味着第一个数组遍历完了,那么就 p3 指向的位置存放 p2 的数据,反之则存放 p1 的数据。

如果 p1 指向数据大于 p2 指向数据,那么 p3 指向位置存放 p1 的数据,反之则存放 p2 的数据。

需要注意,在循环中应该先判断 p1 和 p2 是否小于 0,再进行大小的比较,因为可能会出现 p1 为负数了,会出现:nums1[-1] 这种情况,数组会越界报错。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int p1 = m-1;
int p2 = n-1;
int p3 = m+n-1;
while(p1 >= 0 || p2 >= 0){
if(p1 < 0){
nums1[p3--] = nums2[p2--];
}else if(p2 < 0){
nums1[p3--] = nums1[p1--];
}else if(nums1[p1] >= nums2[p2]){
nums1[p3--] = nums1[p1--];
}else{
nums1[p3--] = nums2[p2--];
}
}
}
}
LeetCode 75.颜色分类![image-20200908134006968](

https://er11.oss-cn-shenzhen.aliyuncs.com/img/image-20200908134006968.png)

采用三指针解法,一个用于记录索引,一个头指针,一个尾指针
如果是 0,则给 left,如果是 1 则不变,如果是 2 则给 right
遍历的结果保证了:left 左边全是 0(不包括 left),right 右边全是 2(不包括 right);

当 i > right 了,则断,否则要把刚交换得到的 1,2 交换回去了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public void sortColors(int[] nums) {
int i = 0;
int left = 0;
int right = nums.length - 1;
while(i <= right){
if(nums[i] == 0){
int tmp = nums[i];
nums[i++] = nums[left];
nums[left++] = tmp;
}else if(nums[i] == 1){
i++;
}else{
int tmp = nums[i];
//换过来的right代表的数可能是0,因此i是不能++的
nums[i] = nums[right];
nums[right--] = tmp;
}
}
}
}
LeetCode 977.有序数组的平方

image-20200909171343270

本来简单点,可以直接把他们全部平方了,然后用 sort 直接排序,但是那样就没意思了。

同样使用三指针,一个记录索引,一个左指针,一个右指针。

由于是从小到大排序,因此索引要在最右边向左走。

终止条件:当 left 与 right 交错时;

假如左指针的数值+右指针数值>0,那么代表右指针数组更大,此时这个位置应该填右指针数值的平方,反之填左指针数值的平方;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public int[] sortedSquares(int[] A) {
int[] ans = new int[A.length];
int i = A.length - 1;
int left = 0;
int right = A.length - 1;
while(left <= right){
if(A[left] + A[right] > 0){
ans[i--] = A[right]*A[right];
right--;
}else{
ans[i--] = A[left]*A[left];
left++;
}
}
return ans;
}
}
LeetCode 面试题 16.16. 部分排序

image-20200910151328344

首先我们看看问题 要求 n - m 尽量最小,意思是要找到符合要求的左端点中最大的,和符合要求的右端点中最小的。

那么又有个问题,什么叫符合要求呢?

首先,对于一个数,假如其左边数都比他小,右边数都比他小,就不包含在需要排序的部分内。

那么符合要求即,对于左端点 m来说,其右边存在一个小于他的数;反之,对于右端点 n来说,其左边存在一个大于他的数

因此我们的程序所要做的就是:

  1. 正向遍历,不停更新最大值,如果当前值小于最大值,那么就是我们要找的右端点 n
  2. 反向遍历,不停更新最小值,如果当前值大于最小值,那么就是我们要找的左端点
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int[] subSort(int[] array) {
if(array.length == 0) return new int[]{-1 , -1};
int right = -1;
int left = -1;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
//正向遍历一遍
for(int i = 0 ; i < array.length ; i++){
if(array[i] >= max){
max = array[i];
}else{
right = i;
}
}
//反向遍历一遍
for(int i = array.length -1 ; i >= 0 ; i --){
if(array[i] <= min){
min = array[i];
}else{
left = i;
}
}
return new int[]{left , right};
}
}

通过代码,我们可以通过【一次遍历+双指针】的方法进行前后同时遍历,做到优化

在上述代码基础上,我们只需要知道尾指针的表达方式 = 数组长度 - 当前遍历下标 i - 1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public int[] subSort(int[] array) {
if(array.length == 0) return new int[]{-1, -1};

int left = -1;
int right = -1;
int max = Integer.MIN_VALUE;
int min = Integer.MAX_VALUE;
int len = array.length;

for(int i = 0; i < len; i++) {
if(array[i] >= max) {
max = array[i];
} else {
right = i;
}

if(array[len - i - 1] <= min) {
min = array[len - i - 1];
} else {
left = len - i - 1;
}
}
return new int[]{left, right};
}
}
LeetCode 11. 盛最多水的容器

image-20210827181026893

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int maxArea(int[] height) {
int left = 0;
int right = height.length - 1;
int ans = 0;
while(left < right) {
//得出当前容量 取决于左右挡板中短的那一条
int cur = Math.min(height[left], height[right]) * (right - left);
//更新最大值
ans = Math.max(ans, cur);
//抉择是左移还是右移
if(height[left] < height[right]) {
left++;
} else {
right--;
}
}
return ans;
}
}
LeeetCode 287.寻找重复数

寻找重复数

使用了快慢指针寻找链表中环入口的思想:

链表中慢指针:slow = slow.next → 数组中慢指针:slow = nums[slow];

链表中快指针:fast = fast.next → 数组中快指针:fast = nums[nums[fast]];

slow = fast的时候,并不代表找到了重复的数!只能代表确实有环。

需要第三个指针,当这个指针与慢指针一起走,当他们相遇的时候,就代表找到了重复的数(环的入口)。

可以与剑指 offer 022 寻找链表中环的入口一起记忆。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int findDuplicate(int[] nums) {
int slow = 0;
int fast = 0;
do {
slow = nums[slow];
fast = nums[nums[fast]];
}while(slow != fast);

int finder = 0;
while(finder != slow) {
finder = nums[finder];
slow = nums[slow];
}

return slow;

}
}

排序解法

LeetCode 56.合并区间

合并区间

  • 思路

画一幅图:

我们得到各子数组的起始点和终止点。

通过比较S[i + 1]E[]的大小,就可以判断出需不需要合并

如果S[i + 1]比 E[i ]要小,说明有重叠部分,需要合并,但此时先不忙去合并,而是继续向后遍历,能不能合并成更大的数组

如果S[i +1]比 E[i]要大,说明没有重叠部分,则需要处理前面的部分了(不管前面有没有重叠);

image-20210912205114749

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
public int[][] merge(int[][] intervals) {
int len = intervals.length;
int[] start = new int[len];
int[] end = new int[len];

for(int i = 0; i < len; i++) {
start[i] = intervals[i][0];
end[i] = intervals[i][1];
}

Arrays.sort(start);
Arrays.sort(end);

List<int[]> res = new ArrayList<>();
int globalStart = 0;
for(int i = 0; i < len; i++) {
if(i == len - 1 || start[i + 1] > end[i]) {
res.add(new int[]{start[globalStart], end[i]});
globalStart = i + 1;
}
}


return res.toArray(new int[res.size()][2]);
}
}

链表(List)

链表概念

  • 由于动态数组有个明显缺点:可能会造成内存的大量浪费。那么有没有一种方法能做到——我们用多少空间就申请多少内存呢?当然有,就是用链表了!
  • 链表是一种链式存储的线性表,其元素的内存地址不一定是连续的。

LeetCode-链表相关

  • 首先明白链表解题的特点/优势/劣势
  • 优势:链表的连接方式是通过 next 指针,因此我们只需要修改指向即可轻松的插入与删除
  • 劣势:链表不存在索引这一说,因此我们要查找某个特定元素,只能通过遍历,不能直接找到
  • 特点:我们常常会使用多指针进行操作

203.移除链表元素

image-20200913211912842

采用新建一个链表的解法,可以有效解决假如头节点就是要删除的元素带来的麻烦。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public ListNode removeElements(ListNode head, int val) {
ListNode newhead = new ListNode();
newhead.next = head;
ListNode tmp = newhead;
while(tmp.next != null){
if(tmp.next.val == val){
tmp.next = tmp.next.next;
}else{
tmp = tmp.next;
}
}
return newhead.next;
}
}

86.分割链表/NC23 划分链表

image-20200913212252808

这题比较简单,用两条链表分别保存小于 x 的和大于等于 x 部分。然后最后把两条链表一拼就好了

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public ListNode partition(ListNode head, int x) {
//保存小于x的链表
ListNode fronthead = new ListNode();
ListNode p1 = fronthead;
//保存大于等于x的链表
ListNode backhead = new ListNode();
ListNode p2 = backhead;
while(head != null){
if(head.val < x){
p1.next = new ListNode(head.val);
p1 = p1.next;
}else{
p2.next = new ListNode(head.val);
p2 = p2.next;
}
head = head.next;
}
p1.next = backhead.next;
return fronthead.next;
}
}

876.链表的中间结点

这是快慢指针的基本使用场景:找出中间结点。

通过找到中间结点,我们后面可以有无数奇妙用法!

image-20210830215629195

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
//令快慢指针从同一个结点同时出发写法:
class Solution {
public ListNode middleNode(ListNode head) {

ListNode slow = head, fast = head;

while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;

}
}

//令快指针先走一步的写法:
class Solution {
public ListNode middleNode(ListNode head) {

ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
if(fast == null) return slow;
else if(fast.next == null) return slow.next;
else return slow;
}
}

//为什么要有两种呢?我们在148.排序链表中就可以揭晓答案了

21.合并两个有序链表

image-20210628173202795

思路比较简单:

创建一条新的链表,用一个遍历指针,在两条链表上不停的游走,选中其中数值小的结点放入新链表中。

当循环退出时,可能是其中一条链表遍历完了,那就直接把剩下的链表串在新链表尾部即可;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//头指针
ListNode head = new ListNode(0);
//遍历指针
ListNode p = head;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if(l1 == null) {
p.next = l2;
} else {
p.next = l1;
}
return head.next;

}
}

148.排序链表(快慢指针)

image-20210830212838541

这道题的思路:找到链表的中间结点 + 合并两个有序链表 也就是上面两题的结合

这个方法叫:归并排序

  1. 将链表不停拆分,直到只剩一个元素未知
  2. 递归回溯 进行链表的合并

大致过程如下图所示:

Picture2.png

  • 坑点

一开始想当然的,使用了普通的找中间节点方法,导致出现了栈溢出,死循环问题

1
2
3
4
5
6
7
8
public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

思考一下,这种写法假如只剩下两个结点,返回的 slow 是哪个?没错,是第二个结点。导致这个两个元素的链表根本没拆分掉

因此需要用第二种找中间结点方法(fast 指针先行一步)。我直接将第二种写法套上去,以为能通过,结果又是栈溢出,出现了死循环

原来:在那种写法中,只有两个元素的时候,返回的是第二个元素,而我们应该返回第一个。

1
(fast.next == null) return slow.next;

这种写法应该改为:

1
(fast.next == null) return slow

那么三种写法都是 return slow,因此可以统一成return slow

1
2
3
4
5
6
if(fast == null) return slow;
else if(fast.next == null) return slow;
else return slow;

//统一为
return slow;
  • 排序链表代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
class Solution {
public ListNode sortList(ListNode head) {
//1.递归终止
if(head == null || head.next == null) return head;

//2.递归拆分
//2.1 获取前半部分最后一个节点
ListNode midNode= middleNode(head);
//2.2获取 后半部分的第一个节点
ListNode latter = midNode.next;
//2.3 断开
midNode.next = null;

//3.继续分
ListNode l1 = sortList(head);
ListNode l2 = sortList(latter);
//4.治
ListNode l = mergeTwoLists(l1, l2);
return l;

}

public ListNode middleNode(ListNode head) {
ListNode slow = head, fast = head.next;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}


public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
//头指针
ListNode head = new ListNode(0);
//遍历指针
ListNode p = head;
while(l1 != null && l2 != null) {
if(l1.val <= l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if(l1 == null) {
p.next = l2;
} else {
p.next = l1;
}
return head.next;

}
}

160.相交链表(快慢指针)

image-20200914214153713

这道题其实有点脑筋急转弯的味道。

我们想想 假如各有一个指针分别在 A 链表和 B 链表同时出发,假如他们最后能在某一点相交,那么意味着什么,是不是代表着他们行走的总路程是一样的?(因为每次只走一格,相当于速度相同,而时间又相同,那么速度 X 时间就是路程了)

假如没有相交呢?那么代表着各个指针走了一遍 A 又走了一遍 B,最后走到了 null,代表没有交点咯。

好了 代码如下

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
ListNode p1 = headA;
ListNode p2 = headB;
while(p1 != p2){
p1 = (p1 == null) ? headB : p1.next;
p2 = (p2 == null) ? headA : p2.next;
}
return p1;
}
}

剑指 Offer 24.反转链表

所谓的单链表反转,就是把每个节点的指针域由原来的指向下一个节点变为指向其前一个节点。

但是单链表并没有一个指向前一个节点的指针域,因此准备一个指针 pre 用于存储每个节点前一个节点

还需要一个指针 next 保存当前下一个节点。

在遍历过程中:先保存要修改的节点的下一个节点(很关键 顺序不能错咯)然后修改当前节点的下一个指向,然后把 pre 指针和 head 指针都向后移动即可。

记忆方式:从右向左进行操作(记录下一个节点 → 修改当前节点 → 移动之前节点 → 移动 head)。

最后返回的是 pre 这也不能搞错。

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null;
ListNode next = null;
while(head != null){
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}
}

148.重排链表

image-20210831205553383

主要分为三个部分:

  1. 找到中间结点,将链表拆分为两条
  2. 将后半部分链表进行反转
  3. 合并两个链表(不是接在尾部,是在两根链表上游走着合并)

由于我们前两个步骤已经驾轻就熟了,问题在于如何合并两个链表:

保存两个链表的 Next 结点。

插入

移动

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public void merge(ListNode left, ListNode right) {
ListNode leftNext;
ListNode rightNext;

//把right 插入到left中,每插入一次就移动一次left right指针
//当left为最后一个元素时遍历完两条链表
while(left.next != null && right != null) {
//1.保存left right的下一个节点
leftNext = left.next;
rightNext = right.next;

//2.插入部分
left.next = right;
right.next = leftNext;

//3.移动部分
left = leftNext;
right = rightNext;
}

}
  • 完整代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public void reorderList(ListNode head) {
if(head == null) return;

ListNode midNode = middleNode(head);
ListNode q = reverseList(midNode.next);

midNode.next = null;
ListNode p = head;

merge(p, q);

}

public ListNode middleNode(ListNode head) {

ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}

public ListNode reverseList(ListNode head) {
ListNode pre = null, next = null;
while(head != null) {
next = head.next;
head.next = pre;
pre = head;
head = next;
}
return pre;
}

public void merge(ListNode left, ListNode right) {
ListNode leftNext;
ListNode rightNext;

//把right 插入到left中,每插入一次就移动一次left right指针
//当left为最后一个元素时遍历完两条链表
while(left.next != null && right != null) {
//1.保存left right的下一个节点
leftNext = left.next;
rightNext = right.next;

//2.插入部分
left.next = right;
right.next = leftNext;

//3.移动部分
left = leftNext;
right = rightNext;
}

}
}

234.回文链表(快慢指针)

image-20200915193926482

这道题的解法综合性很强(在我看来)

  • 整体思路: 用快慢指针方法找到中间结点,然后将后半部分链表翻转过来,然后将所得的链表与原链表前半部分进行比较

其中快慢指针就不讲了,翻转链表怎么翻转呢?详情请看 剑指 Offer 24.反转链表

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public boolean isPalindrome(ListNode head) {
ListNode pre = null;
ListNode next = null;
ListNode fast = head;
ListNode slow = head;
//偶数的话就是前者情况 奇数就是后者情况
while(fast != null && fast.next != null){
slow = slow.next;
fast = fast.next.next;
}
//反转后半部分链表
while(slow != null){
next = slow.next;
slow.next = pre;
pre = slow;
slow = next;
}
while(head != null && pre != null){
if(head.val != pre.val){
return false;
}
head = head.next;
pre = pre.next;
}
return true;
}
}

2.两数相加

image-20200917221620390

这题我的思路是先不管那个进位的事情,先单纯把对应的数加起来放在一个链表上(在这里我假设放在 L1 上),然后再另外写一个函数去处理(进行进位处理)那个数

这题其实有个好的地方,就是各链表上的数是逆序存储的,相当于加法的时候帮我们自动对齐了。太好了。

那么这道题我们要考虑的其实就四种情况:

  1. L1 长度 >= L2 长度
  2. L1 长度 < L2 长度
  3. 末位不需要进位(这里的末位其实是头 自己知道就好)
  4. 末位需要进位(这里的末位其实是头 自己知道就好)

其中第一种情况其实是最好解决的,就一个末位假如大于 10 进位就好了。

第二种的方法我们可以把提前结束的地方直接接 l2 上,也可以解决

第三种末位不需要进位就不说了

第四种需要进位,就再新建一个头,放进位的 1 就 ok

为什么进位只能是 1,不能是 2?因为最大也就 9 + 9 = 18

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode p1 = l1;
ListNode p2 = l2;

while(p1 != null){
if(p2 != null){
p1.val += p2.val;
p2 = p2.next;
}
//l2长度大于l1 那么直接把p2接p1后面 而且因为没了 直接break
if(p1.next == null && p2 != null){
p1.next = p2;
break;
}
p1 = p1.next;
}
func(l1);
return l1;
}
public void func(ListNode head){
while(head != null){
if(head.val >= 10){
head.val = head.val%10;
if(head.next == null){
//假如是末位 大于10 那么就需要新建一个头 放1用
head.next = new ListNode(0);
}
head.next.val += 1;
}
head = head.next;
}
}
}

19.删除链表的倒数第 N 个结点(快慢指针/双指针)

image-20210829161341444

这道题,同样是用快慢指针的思想去做。但是不同的在于,快慢指针不仅仅是局限于慢指针走一步,快指针走两步,快慢指针可以是保持恒定距离的一组指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
//如果只有一个
if(head.next == null) return null;
//定义快慢指针
ListNode fast = head;
ListNode slow = head;
//快指针先行
while(n > 0) {
fast = fast.next;
n--;
}
//特判:如果fast = null,说明我们需要剔除的正好是头结点
if(fast == null) return head.next;
//快慢一起走
while(fast.next != null) {
slow = slow.next;
fast = fast.next;
}
//上面循环退出后slow后一个结点为需要剔除的结点
slow.next = slow.next.next;
//返回头
return head;

}
}

NC69 链表中倒数最后 k 个结点(快慢指针/双指针)

image-20210829222646204

和上面的删除第 N 个结点基本类似,只不过需要额外考虑的是假如链表中只有五个元素,缺要倒数第 6 个结点至尾结点的全部结点的话,是不显示的,需要返回 null

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
*
*
* @param pHead ListNode类
* @param k int整型
* @return ListNode类
*/
public ListNode FindKthToTail (ListNode pHead, int k) {
// write code here
// 快慢指针
if(pHead == null || k < 0) return null;
ListNode slow = pHead, fast = pHead;
while(k > 0) {
if(fast == null) return null;
fast = fast.next;
k--;
}
if(fast == null) return pHead;
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;
}
}
1
2
3
4
5
while(fast != null) {
slow = slow.next;
fast = fast.next;
}
return slow;

需要注意的是,如果循环中判断条件为fast != null ,那么结束循环的时候,slow 所在的位置就是在倒数第 K 个结点处

1
2
3
4
5
while(fast.next != null) {
slow = slow.next;
fast = fast.next;
}
return slow.next;

如果是fast.next != null slow 所在的下个结点位置才是倒数第 K 个结点

141.环形链表 (快慢指针)

环形链表

判断链表有没有环,可以使用快慢指针来做
当一个链表有环时,快慢指针都会陷入环中进行无限次移动,然后变成了追及问题。想象一下在操场跑步的场景,只要一直跑下去,快的总会追上慢的。当两个指针都进入环后,每轮移动使得慢指针到快指针的距离增加一,同时快指针到慢指针的距离也减少一,只要一直移动下去,快指针总会追上慢指针。

快慢指针在环上追及

如果存在环,如何判断环的长度呢?方法是,快慢指针相遇后继续移动,直到第二次相遇。两次相遇间的移动次数即为环的长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public boolean hasCycle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(true) {
try {
slow = slow.next;
fast = fast.next.next;
} catch(Exception e) {
return false;
}
if(slow == fast) {
return true;
}
}
}
}

142.环形链表 II / 剑指 Offer II 022. 链表中环的入口节点

image-20210911171032020

这道题其实就是在判断有无环的基础上加强了一步:找到环的入口

找到环的入口方法如下:

  1. 用快慢指针进行判断是否有环
  2. 如果有环,此时让一个指针在链表头部开始走(每次都一步),同时 slow 指针在相遇位置开始同步走
  3. 当新指针与 slow 指针相遇时,所在位置就是环的入口

具体的证明过程:https://blog.csdn.net/qq_43121830/article/details/105333211

移动过程:

移动1

移动2

移动3

移动4

  • 具体代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
public ListNode detectCycle(ListNode head) {

ListNode slow = head, fast = head;
while(fast != null && fast.next != null) {
slow = slow.next;
fast = fast.next.next;

if(slow == fast) {
ListNode p = head;
while(p != slow) {
p = p.next;
slow = slow.next;
}
return p;
}
}
return null;
}
}

栈 (Stack)

栈概念

栈源码分析

LeetCode-栈相关

面试题 03.02. 栈的最小值

image-20200924161616748

这题可以用双栈的方法去解,分为主栈和副栈;

  • 主栈:和正常的栈一样进行push&pop

  • 副栈:对我们push 和 pop 的值进行特判,假如符合才进行相应操作,副栈维护着一个特殊的序列;

那么对于本题,我们的副栈有着什么特殊的地方呢?

  1. 我们所要push 的值必须要小于/等于此时的栈顶元素
  2. 我们所要pop 的值必须是辅助栈的栈顶元素我们才让辅助栈也 pop,只有这样我们才能保证 pop 掉留下的元素是其次第二小,第三小…的元素
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class MinStack {
private Stack<Integer> MainStack;
private Stack<Integer> Helper;

/** initialize your data structure here. */
public MinStack() {
MainStack = new Stack<Integer>();
Helper = new Stack<Integer>();
}

public void push(int x) {
MainStack.push(x);
if(!Helper.isEmpty()){
if(Helper.peek()>=x){
Helper.push(x);
}
}else{
Helper.push(x);
}
}

public void pop() {
int temp = MainStack.pop();
if(temp == Helper.peek()){
Helper.pop();
}
}

public int top() {
return MainStack.peek();
}

public int getMin() {
return Helper.peek();
}
}

739.每日温度

image-20200924190753703

引入概念 单调栈

  • 单调递增栈:栈中数据出栈的序列为单调递增序列
  • 单调递减栈:栈中数据出栈的序列为单调递减序列

ps:这里不需要保证在栈中的元素要保持单调递增/递减的顺序

那么这题怎么用单调栈的方法来解呢?准确的说用单调递增栈的方法来解呢?

这题的意思就是找到每个位置离他最近的那个比他大的数,那么我们遇到比自己小的就存栈里,碰到一个大的就把自己栈顶的数据弹出来与当前的下标进行减法运算,即为差值,也就是我们需要等待的日子。

不要忘了,当前遍历到的这个数也有可能比之前没弹出来的数要大,所以要 while()挨个看看,而不是 if();

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public int[] dailyTemperatures(int[] T) {
//特判
if(T.length == 0 || T.length == 1 || T == null){
return new int[]{};
}
//构造栈
Stack<Integer> helper = new Stack<>();
//答案数组
int[] ans = new int[T.length];
//遍历
for(int i = 0 ; i < T.length ; i++){
//记得这里是while不是if,因为遇到了一个大的有可能比之前的没弹出来的也要大,要都判断一次;
while(! helper.isEmpty() && T[helper.peek()] < T[i]){
int day = helper.pop();
ans[day] = i - day;
}
//入栈
helper.push(i);
}
return ans;
}
}

剑指 Offer09.用两个栈实现队列

image-20200925211651494

这题其实比较简单,一个栈正常存,另一个用来维护成队列的特性即可;

在 push 数据的时候S1正常存,然后假如要 pop 了,就把第一个栈存储的数据一个一个的 pop 出来,push 在S2中,然后再 popS2的数据出去即可;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class CQueue {
Stack<Integer> s1;
Stack<Integer> s2;
//初始化栈,一个用于正常存,一个是辅助栈;
public CQueue() {
s1 = new Stack<>();
s2 = new Stack<>();
}

public void appendTail(int value) {
//正常存
s1.push(value);
}

public int deleteHead() {
//假如s2有数据,代表着之前的数据还没处理完,不用把辅助栈s1数据存进来
if(!s2.isEmpty()){
return s2.pop();
}
//假如s2没数据,s1有数据,就把s1数据存进来
if(s2.isEmpty() && !s1.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
//假如s2没数据,s1没数据,返回-1
if(s1.isEmpty() && s2.isEmpty()){
return -1;
}
return s2.pop();

}
}

第一个 if 条件判断后也是return s2.pop(),可以简化成两个 if 条件进行栈的维护;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public int deleteHead() {
//假如s2没数据,s1有数据,就把s1数据存进来
if(s2.isEmpty() && !s1.isEmpty()){
while(!s1.isEmpty()){
s2.push(s1.pop());
}
}
//假如s2没数据,s1没数据,返回-1
if(s1.isEmpty() && s2.isEmpty()){
return -1;
}
return s2.pop();

}

队列

队列概念

LeetCode-队列相关

239.滑动窗口最大值

image-20200924171609555

这道题分析一下,我们的窗口随着移动,前面先进来的数要先被窗口卡在外面,那么符合先进先出,是队列;

我们要考虑一个区间内的最大值,又有一点栈的味道,那到底这题要用哪种呢,能不能都用呢?

由此,我们可不可以有一种数据结构是包含了队列的(FIFO)和栈的(FILO)的特点的呢?

双向队列

image-20200924172108383

我们遍历数组,把数组放在队列中,而且我们的头要保证是每一趟中最大的,把头的值给到我们的结果数组,遍历完成后,我们的结果数组也形成了。

那么解决这道题,我们首先要形成题目中的”窗口”:用 L 和 R 分别表示左右边框。

  • R=i,就是遍历的下标
  • L=i-k+1,也就是右边框减去窗口的宽再加 1

我们遍历途中,遇到了一个数,假如我们之前的数值都是小于该数的,那么全部弹出,并且保存该数,判断该数有没有被窗口卡住,假如此时已经形成窗口了,就把该数赋给我们的结果数组。

我们这有个问题:为什么我们的双向队列不直接存数呢?直接把那个数给数组不是更简单,为什么要多此一举,存下标,然后再把该下标放进数组里,把值传过去呢?

好问题,因为我们要判断我们的队首元素有没有被窗口卡在外面,而去判断有没有卡在外面依据,就是我们的下标与下标进行比较,只要符合了,就把该下标所在的值赋予结果数组即可;而反过来,我们存放数据的话,就要用 map 映射去找下标,然后比较,不是更麻烦吗?

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 0 || nums == null) {
return new int[]{};
}
//结果数组
int[] result = new int[nums.length - k + 1];
//建立一个双向队列存储窗口的下标,而不是值;
Deque<Integer> queue = new LinkedList<>();
//用i代表当前滑窗的最后一个元素
for (int i= 0 ; i < nums.length ; i++) {
//为了保证从小到大,把之前小于现在遍历到的值的数全部弹出
while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) {
queue.pollLast();
}
//添加当前值对应的数组下标
queue.addLast(i);
//判断该值所在的下标是否被窗口卡在外面
if(queue.peekFirst() <= i - k){
queue.pollFirst();
}
//假如此时的窗口长度刚好成型或已经成型的时候,保存当前窗口最大值
if (i - k + 1 >= 0){
result[i - k + 1] = nums[queue.peek()];
}
}
return result;
}
}

300.最长上升子序列

看到这种最长上升,我下意识想到了单调栈的解法,但后来写了发现有些地方的 pop 很繁琐,那么我就想到了另一种方法,单调队列

我们用一个数组去维护成一个单调队列,保证其是单调递增的,在遍历数组的时候,如果遇到比尾部的数字还大的,那么就肯定比队列前面已经存在的数字都要大,那么就直接插入在尾部;如果碰到了比尾部小的,我们找到前面第一个比他大的位子,替换掉;

这里有个巧妙地方法就是引入了二分法去找该插入的位子,关于二分的话在算法篇我们再详细讲讲左右区间选择问题和最后到底用左端点还是右端点,这里学问还是有很多的。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
public int lengthOfLIS(int[] nums) {
//特判
if(nums.length == 0 || nums == null) return 0;
//不停更新这个数组 维护一个伪队列 保持其单调递增
int[] a = new int[nums.length];
//len+1就是最长的序列了
int len = 0;
//存放第一个数 用于后续比较
a[len] = nums[0];
//遍历数组,如果大于单调队列的尾部 就直接加入尾部
//如果小于的话 就找到第一个比他比他大的数,把它换掉,保留了后续增长的可能性
for (int i = 0; i < nums.length ; i++) {
//如果比尾部大,直接加尾部
if(nums[i] > a[len]) {
a[++len] = nums[i];
//否则用二分找位子
} else {
int l = 0, r = len + 1;
while(l < r) {
int m = l + (r - l) / 2;
//如果这个数过大 那么就换右区间找
if(a[m] < nums[i]) l = m + 1;
//反之 换左区间
else r = m;
}
//找到了 退出循环 替换数字
a[r] = nums[i];
}
}
return len + 1;
}
}

树形结构

(二叉树,AVL 树,红黑树,B 树,堆,Trie 哈夫曼树,并查集)

img

二叉搜索树

  • 二叉搜索树中每个节点的特点
    • 比保存在左子树的任何键值都要大
    • 比保存在右子树的任何键值都要小

平衡二叉搜索树

对于要查找元素 6 的情况:

下图左边是二叉搜索树,时间复杂度为 0(n);而右边是经过调整(旋转)后的平衡二叉搜索树,此时树的高度减少了一半,查找效率变为 O(log2n)

二叉搜索树对比

  • 平衡树旋转保持平衡性

平衡二叉搜索树旋转

堆的本质是一颗【完全二叉树】,因此放在了树形结构这一章节

用堆进行存储数据需要符合以下三条规则:

  1. 元素可比较性:数据集中的元素可以进行比较,就是要实现 Comparable 接口。
  2. 节点最大/最小性:每个节点的元素必须大于或小于该节点的孩子节点的元素;
  3. 堆是一棵完全二叉树。
  • 最大堆和最小堆

最小堆中每个节点的优先级小于或者等于它的子节点;

最大堆则相反,每个节点的优先级都大于或者等于它的子节点。

如下图:

最大堆和最小堆

堆的大小是提前知道的,在 java 集合中堆是通过 ArrayList 数组实现的:

根据堆的性质,我们有一个想法:

有一个容器,其大小不超过 k 时,就不断存入元素,只要容量超过 k,就剔除其中最大的元素,重复该过程,当遍历所有元素后,该容器中剩下的刚好就是最小的 k 个元素。

那么哪种容器能实现以上性质呢?第一时间想到的就是最大堆

Java 内置了【优先队列】,就是基于堆实现的,默认是最小堆:

1
PriorityQueue<Integer> minHeap = new PriorityQueue<>();

可以传入 Comparator 改变堆的形式,构造成最大堆。

1
2
3
4
5
6
//comparaTo写法
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> b.compareTo(a)); // 注意参数a、b的顺序和compareTo方法中a、b的位置
//第二种写法
PriorityQueue<Integer> maxHeap = new PriorityQueue<>((a, b) -> (b - a));
//第三种直观的写法
PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

如果想构造成其他优先级,需要实现Comparable接口,重写compareTo()方法

1
2
3
4
5
6
Comparable<Integer> comparable = new Comparable<Integer>() {
@Override
public int compareTo(Integer o) {
return 0;
}
};
  • 注意

PriorityQueue对元素采用的是堆排序,该排序只能保证【根】是最大/最小元素,并不能保证整个堆的有序排列

LeetCode- 堆相关

剑指 offer 面试题 40 :最小的 K 个数

使用堆数据结构来辅助得到最小的 k 个数。堆的性质是每次可以找出最大或最小的元素。我们可以使用一个大小为 k 的最大堆(大顶堆),将数组中的元素依次入堆,当堆的大小超过 k 时,便将多出的元素从堆顶弹出。我们以数组 [5, 4, 1, 3, 6, 2, 9], k=3 为例展示元素入堆的过程,如下面动图所示:

入堆出堆的过程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(k == 0) return new int[]{};

PriorityQueue<Integer> maxHeap = new PriorityQueue<>(Comparator.reverseOrder());

for(int i = 0; i < arr.length; i++) {
maxHeap.offer(arr[i]);
if(maxHeap.size() > k) {
maxHeap.poll();
}
}

int[] res = new int[k];
for(int i = 0; i < k; i++) {
res[i] = maxHeap.remove();
}
return res;
}
}

LeetCode 23.合并 K 个升序链表

合并K个升序链表

由于学习了最小堆,我们可以利用最小堆的性质(poll 方法每次都能获取堆中最小值)将链表元素存入最小堆中,新建一个链表去遍历最小堆即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
ListNode newHead = new ListNode(0);
if(lists == null) return null;
PriorityQueue<ListNode> minHeap = new PriorityQueue<>(new Comparator<ListNode>() {
@Override
public int compare(ListNode o1, ListNode o2) {
return o1.val - o2.val;
}
});

for(ListNode head : lists) {
while(head != null) {
minHeap.offer(head);
head = head.next;
}
}

ListNode cur = newHead;
while(minHeap.size() > 0) {
ListNode tmp = minHeap.poll();
cur.next = tmp;
cur = cur.next;
}
cur.next = null;
return newHead.next;

}
}

LeetCode - 树相关

  • 我们可以先不考虑整个树应该怎么解,可以考虑假如就三个结点(根 左子树 右子树)这个时候应该怎么求解,然后把这个解题思路放大 映射到整个树结构;
  • 树解题一般都要用到递归的方法 那么就要明白递归最重要的三部曲
  • 递归的终止条件
  • 每一层递归要进行什么处理
  • 每一层递归的返回值是什么

572. 另一个树的子树

image-20201004160328789

  • 这题要点在于,是不是把是不是子树问题转换成了是不是同树问题;

    判断同树的方法就算:要么都为空,要么值相等,其他情况肯定都不是同树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public boolean isSubtree(TreeNode s, TreeNode t) {
//如果子树为空 肯定是主树的子树了
if(t == null) return true;
//如果主树为空,由于此题的子树一定部位空,那么就不属于子树
if(s == null) return false;
//判断一下 此时是否是同树
if(isSametree(s,t)) return true;
//返回要么是左子树要么右子树,否则就都不是
return isSubtree(s.left, t) || isSubtree(s.right, t);
}

public boolean isSametree(TreeNode s, TreeNode t) {
//此处都为空,都遍历到头了 就有可能是树
if(s == null && t == null) return true;
//一个未空一个不为空,肯定不是同树
if(s == null || t == null) return false;
//值不同,不可能为同树
if(s.val != t.val) return false;
//判断左边和右边
return isSametree(s.left, t.left) && isSametree(s.right, t.right);

}
}

236.二叉树的最近公共祖先

image-20201027131924221

首先要明确什么最近公共祖先的概念,不然你遍历的时候做什么处理都不清楚

  • 最近公共祖先如果找到一个节点,发现左子树出现结点 p,右子树出现节点 q,或者 左子树出现结点 q,右子树出现节点 p,那么该节点就是节点 p 和 q 的最近公共祖先;或者是一个结点本身就是 p 或者 q,其左子树或右子树出现了 q 或者 p,那么 p/q 本身就是最近的公共祖先

  • 递归的终止条件:比叶子结点还深的话就返回 null,假如现在的 root 就是 p/q 的话就返回 root,用于后续判断;

    1
    if(root == null || root == p || root == q) return root;
  • 每一层递归要进行什么处理:由于要遍历整个树,因此每一层递归应该开启左右子树的递归,因此我们要把传入的参数由

    root 改为 root.left 和 root.right

    1
    2
    TreeNode left = lowestCommonAncestor(root.left, p, q);
    TreeNode right = lowestCommonAncestor(root.right, p, q);
  • 每一层递归的返回值是什么:这个其实是这道题的困难点,我们到底该返回什么值?依据又是什么呢?

    回到我们这题 最近公共祖先 的定义,结合返回值我们可以分析以下三种情况:

    1. 假如我们的左右子树都【没有】返回值 那很可惜 只能返回 NULL 了
    2. 假如我们的左右子树都【有】返回值代表着什么?代表我们现在处于的这个根就是我们要找的 最近公共祖先
    3. 假如有一边不为空 那也不赖了 我们至少找到了用于判断 最近公共祖先 的一半条件了,我们就把不为空的那部分返回了,另一部分继续找就好了
    1
    2
    3
    if (left == null && right == null) return null;
    else if (left != null && right != null) return root;
    else return left == null ? right : left;

完整代码:

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
//返回值就两种情况 要么就是值 要么就是空的 换句话说 假如一个根左右两边返回上来的值都不为空 那么这个跟肯定就是pq的最近公共祖先了
if(root == null || root == p || root == q) return root;
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if (left == null && right == null) return null;
else if (left != null && right != null) return root;
else return left == null ? right : left;
}
}

144.二叉树的前序遍历

image-20201029222130128

如果用递归写,那就没意思了,我们下面试试用迭代来遍历

首先要明白 前序遍历是怎么遍历的:根节点 - 左节点 - 右节点

OK,接下来由于我们需要去把遍历出来的结果保存在数组里面返回,那么思路就出来了:

用一个栈去辅助遍历:

  • 当前遍历结点不为空,直接加入数组,然后压入栈中,向左子树进发
  • 如果未空,返回之前保存的栈顶,然后遍历右子树(也就是遍历这个未空节点的兄弟节点)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> list = new ArrayList<>();
if(root == null) return list;
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
list.add(cur.val);
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
cur = cur.right;
}
}
return list;
}
}

94.二叉树的中序遍历

image-20201030112007435

同样的,我们来想想中序遍历顺序:左节点 → 根节点 → 右节点

我们和前序遍历使用了相同模板,只不过里面的细节变了些:

  • 如果遍历的结点不为空,别急着把值加入数组,压入栈中,继续向左子树进发
  • 如果未空,说明到了最左边啦,那首先弹出栈顶(返回上一级)然后把这个值存入数组,同时向右子树进发
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
//中序遍历:左 → 根 → 右
List<Integer> list = new ArrayList<>();
Stack<TreeNode> stack = new Stack<>();

TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
stack.push(cur);
cur = cur.left;
} else {
cur = stack.pop();
list.add(cur.val);
cur = cur.right;
}
}
return list;
}
}

145.二叉树的后序遍历

image-20201030130346848

后序遍历的遍历顺序:左节点 → 右节点 → 根节点

看起来比较难以实现吧?那我们换一种思路:

我们知道先序遍历是:根节点 → 左节点 → 右节点

那我们如果反过来遍历就是:右节点 → 左节点 → 根节点

反过来遍历可以依靠链表的头插法。

由于我们先遍历的左节点 再遍历 右节点得到这个结果

那么我们假如先遍历右节点,再遍历左节点:左节点 → 右节点 → 根节点 ,这正好是我们后序遍历结果

那么如何实现呢?可以使用头插法来实现第一步,而后调整遍历左右节点顺序来实现第二步

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public List<Integer> postorderTraversal(TreeNode root) {
LinkedList<Integer> list = new LinkedList<>();
Stack<TreeNode> stack = new Stack<>();
TreeNode cur = root;
while(cur != null || !stack.isEmpty()) {
if(cur != null) {
list.addFirst(cur.val);
stack.push(cur);
cur = cur.right;
} else {
cur = stack.pop();
cur = cur.left;
}
}
return list;
}
}

102.二叉树的层次遍历

树层次遍历

这道题由于要返回一个二维数组,可以理解成每个元素里的内容是每一层的左右结点;

那么层次遍历是怎么遍历的呢:根结点 → 左子树 A → 右子树 B→ 左子树 A 的左子树 → 左子树 A 的右子树 → 右子树 B 的左子树 → 右子树 B 的右子树……

那就可以用队列来实现啦:

  • 先把根结点假如队列中,如果不为空 就加入数组中
  • 判断该结点是否有子树(先判断左 再判断右),有的话加入队列之中
  • 我们可以通过queue.size()得到队列的大小,也就是一层有多少个结点,通过这个就可以知道我们的子数组有几个元素了
  • 在每一次的循环结束后,把我们得到的这一层的子数组都加入我们结果数组即可
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> list = new ArrayList<>();
Queue<TreeNode> queue = new LinkedList<>();
TreeNode cur = root;
if(cur != null) queue.offer(cur);
while(!queue.isEmpty()) {
int curSize = queue.size();
List<Integer> sublist = new ArrayList<>();
while (curSize > 0) {
TreeNode curr = queue.poll();
sublist.add(curr.val);
if (curr.left != null) {
queue.add(curr.left);
}
if (curr.right != null) {
queue.add(curr.right);
}
curSize--;
}
list.add(sublist);
}
return list;
}
}

101.对称二叉树

image-20201031202611983

什么叫对称的二叉树?很简单,如果根结点为空 是对称,如果不为空,那么判断其左右子树是否==对称==,如果==对称==,那么这个树是==对称==的;

那么怎么知道他们的左右子树是不是==对称==的呢?很简单,左子树的左孩子与右子树的右孩子==对称==,左子树的右孩子与右子树的左孩子==对称==,那么这个树是对称的…

那么问题又来了…怎么知道他们的…ok,打住,看到这我们已经非常清楚递归的每一步应该干什么了吧?

  • 递归的终止条件:左结点为空,判断右结点是否为空;右结点为空,判断左结点是否为空;

    1
    2
    if(left == null) return right == null;
    if(right == null) return left == null;
  • 每一层递归要进行什么处理:分别传入新的参数

    1
    isMirror(left.left, right.right) && isMirror(left.right, right.left);
  • 每一层递归的返回值是什么:真值【true or false】

    1
    return left.val == right.val

代码:

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null) return true;
return isMirror(root.left, root.right);
}

private boolean isMirror(TreeNode left, TreeNode right) {
if(left == null) return right == null;
if(right == null) return left == null;
return left.val == right.val && isMirror(left.left, right.right) && isMirror(left.right, right.left);
}
}

98.验证二叉搜索树

image-20201031210034522

这道题其实让我学到了新知识:那就是二叉搜索树的中序遍历是一个递增的序列;

那么这道题就可以利用这个特性了,解题思路:中序遍历得到一个序列,判断是不是递增的 → 树是不是二叉搜索树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public boolean isValidBST(TreeNode root) {
List<Integer> list = new ArrayList<>();
inOrder(root, list);
for(int i = 0; i < list.size() - 1; i++) {
if(list.get(i) >= list.get(i + 1)) return false;
}
return true;

}
private void inOrder(TreeNode node, List<Integer> list) {
if(root == null) return null;
inOrder(node.left, list);
list.add(node.val);
inOrder(node.right, list);
}
}

108.将有序数组转换为二叉搜索树

image-20201031212019514

上面我们学到了怎么把搜索树转换成一个有序数组,那么接下来让我们反着来,把一个有序数组转换成二叉搜索树

二叉搜索树有什么特性?我们再复习一次:

  • 节点的左子树只包含小于当前节点的数。
  • 节点的右子树只包含大于当前节点的数。
  • 所有左子树和右子树自身必须也是二叉搜索树。

现在我们的数组是一个==有序数组==,意味着他已经是排序好了的(升序);也就是选定一个下标,其左边的值一定小于他,其右边的值一定大于他。在其左边的部分和右边部分亦是如此。

那难道我们这个下标可以随便选嘛?不是的,这道题还有个条件:平衡

  • 平衡要求左右子树高度差的绝对值不超过 1。

那我们就得用二分法,把相对高度控制在 1 了

  • 递归的终止条件:把二分的终止条件拿来用 → left > right;用于控制相对高度差为 1;

    1
    if(left > right) return null;
  • 每一层递归要进行什么处理:首先需要计算出中值,然后创建一个新的节点,把中值交给他,同时数组左半边就是他的左子树了,同理,数组右半边就是它的右子树了

    1
    2
    3
    4
    int mid = (left + right) / 2;
    TreeNode root = new TreeNode(nums[mid]);
    root.left = biuldBST(nums, left, mid - 1);
    root.right = biuldBST(nums, mid + 1, right);
  • 每一层递归的返回值是什么:构建二叉树嘛,那返回值自然是结点了

    1
    return root;

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
TreeNode root = biuldBST(nums, 0, nums.length - 1);
return root;
}
private TreeNode biuldBST(int[] nums, int left, int right) {
if(left > right) return null;
int mid = (left + right) / 2;
TreeNode root = new TreeNode(nums[mid]);
root.left = biuldBST(nums, left, mid - 1);
root.right = biuldBST(nums, mid + 1, right);
return root;
}
}

99.恢复二叉搜索树

image-20201106182812384

看到二叉搜索树这个条件发生想起来:中序遍历是升序数组

这题要恢复二搜索树,无非就是把升序数组中,影响了升序这个条件的两个值交换即可;

比如一个序列:1、2、3、4、5 他是有序的,而1、3、2、4、5是无序的,其中的 2 和 3 就是影响了升序的那两匹害群之马 s

由于少不了要与之前的值进行比较,因此少不了一个 pre 结点,用于记录上次遍历的结点

又由于要恢复,因此不仅仅要找到这两个值,还需要记录这两个值;

1
2
3
4
5
6
//上次遍历的结点
TreeNode pre;
//第一个错的结点
TreeNode first;
//第二个错的结点
TreeNode second;

而要整理出升序数组,需要中序遍历,当然了,在中序的时候应该进行一些操作 去找出那两个奇怪的值;

那么中序遍历中:

  • 递归的终止条件:结点为空的时候终止

    1
    if(root == null) return;
  • 每一层递归要进行什么处理:正常中序遍历的同时,需要将上次遍历的结点的值与当前遍历到的结点的值进行比较

    如果==pre.val > root.val,即之前结点的值大于当前的==,就 pre 结点就是第一个出问题的结点

    ok,重点来了,为什么second = root 没有在 if 条件中进行,而是单独的呢?

    因为假如我们出问题的两个数值并不相连,比如1、5、3、4、2、6、7序列中出问题的是5 和 2

    first 是 5,没有问题,但假如 second = root 写在 if 中,second 就是 3 了;

    因此 当下一次判断出前面的值比后面的值大了,出问题的(second 的值)就不是前面那个值(比如说上述序列中的 4)

    而是后面的 root 代表的值(比如上面说的 2);因此 second 才是正确的;

    1
    2
    3
    4
    5
    6
    if(pre != null && pre.val > root.val) {
    if(first == null) first = pre;
    second = root;
    }
    pre = root;
    inOrder(root.right);
  • 每一层递归的返回值是什么:由于这个函数的功能主要是用于找出结点,也不是建立什么树,因此无须返回值

  • 完整代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
//上次遍历的结点
TreeNode pre;
//第一个错的结点
TreeNode first;
//第二个错的结点
TreeNode second;
public void recoverTree(TreeNode root) {
inOrder(root);
int temp = first.val;
first.val = second.val;
second.val = temp;
}
private void inOrder(TreeNode root) {
if(root == null) return;
inOrder(root.left);
if(pre != null && pre.val > root.val) {
if(first == null) first = pre;
second = root;
}
pre = root;
inOrder(root.right);
}
}

剑指 Offer 07.重建二叉树

重建二叉树

  • 分析

前序遍历:根 → 左 → 右,中序遍历:左 → 根 → 右

可以得到以下 2 点:

  1. 前序遍历列表:第一个元素永远是 【根节点 (root)】
  2. 中序遍历列表:根节点 (root)【左边】的所有元素都在根节点的【左分支】,【右边】的所有元素都在根节点的【右分支】
  • 思路
  1. 通过【前序遍历列表】确定【根节点 (root)】
  2. 在【中序遍历列表】中找到 root 所在的索引位置index
  3. 通过 index,将【前序遍历列表】和【中序遍历列表】划分成了左右分支(四个小数组)
  4. 将上述得到的左右分支作为参数,传入下一次递归中
  • 代码

Arrays.copyOfRange(arr, from ,to)

  • arr:要复制的数组
  • from:起始点下标(取得到)
  • to:终止点下标(取不到)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode buildTree(int[] preorder, int[] inorder) {

//记住递归三部曲:
//1 终止条件
//2 路径选择
//3 撤销(有时候不需要)

TreeNode root = null;
root = DFS(root, preorder, inorder, 0);
return root;



}

public TreeNode DFS(TreeNode root, int[] preorder, int[] inorder, int index) {
if(preorder == null || preorder.length == 0) return null;

root = new TreeNode(preorder[0]);

for(int i = 0; i < inorder.length; i++) {
if(inorder[i] == root.val) {
index = i;
break;
}
}

root.left = DFS(root, Arrays.copyOfRange(preorder,1, index + 1), Arrays.copyOfRange(inorder, 0, index), index);
root.right = DFS(root, Arrays.copyOfRange(preorder, index + 1, preorder.length), Arrays.copyOfRange(inorder, index + 1, inorder.length), index);
return root;


}
}

串结构

LeetCod-串相关

  • 串的问题一般都需要用到 DP 的思想去解决

242.有效的字母异位词

image-20201004161742293

这题一开始我想到的是用类似于异或运算的方法去解决,用一个数组去表示答案,遍历两个字符串,如果有相同的就消掉为 0,最后再遍历一次数组,假如发现有不是 0 的 代表两个字符串并不是字母异位的。

方法一:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public boolean isAnagram(String s, String t) {
//特判 假如字符串长度都不同,也就没有比的必要了
if(s.length() != t.length()) return false;
int[] arr = new int[26];//为什么是26个呢 因为26个单词嘛 26个多一个保险点
//都转成字符数组
char[] a1 = s.toCharArray();
char[] a2 = t.toCharArray();
for(int i = 0 ; i < s.length() ; i++) {
//一个加
arr[a1[i] - 97]++;
//一个减少
arr[a2[i] - 97]--;
}
for(int i = 0 ; i < arr.length ; i++) {
//有不是0的代表没消掉
if(arr[i] != 0) return false;
}
return true;
}
}

后来看答案,好像有个方法可以直接排序后直接比较 学到了

方法二:

1
2
3
4
5
6
7
8
9
10
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) return false;
char[] a1 = s.toCharArray();
char[] a2 = t.toCharArray();
Arrays.sort(a1);
Arrays.sort(a2);
return Arrays.equals(a1, a2);
}
}

151.翻转字符串里的单词

image-20201004172342276

看到这种翻转题,我条件反射就想到了用栈,FILO 的性质太适合了。

那么怎么用栈呢?整体思路就是:遇到了空格 那么前面肯定是一个单词了,把他 push 进栈里面;

整个遍历结束后,用一个字符串接受答案,一个接一个 pop 出来就好;

这题的小细节很多,比如,我们可以在尾部加一个空格方便判断是单词

由于题目要求,保证前面是不能有空格的,那么就得先 pop 一个出来,再添加后续的单词;

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
class Solution {
public String reverseWords(String s) {
//倒序输出 很自然想到了栈
Stack<String> stack = new Stack<>();
StringBuilder tmp = new StringBuilder();
//为了保证判断的一致性 在尾部添加一个空格
s += " ";
for(int i = 0; i < s.length(); i++) {
//如果遇到空格 发现是一个单词了 就把之前的push
if(s.charAt(i) == ' ') {
if(tmp.length() != 0) {
stack.push(tmp.toString());
//别忘了重置tmp
tmp = new StringBuilder();
}
} else {
//没遇到空格 就把遇到的单词拼在一起
tmp.append(s.charAt(i));
}
}
//如果栈为空 说明就是个空串
if(stack.isEmpty()) return "";
//答案字符串
StringBuilder res = new StringBuilder();
//由于末尾的空格是不要的 那么就得先pop掉最上面的
res.append(stack.pop());
//遍历栈 不停的加
while(!stack.isEmpty()) {
res.append(" ");
res.append(stack.pop());
}
return res.toString();

}
}

344.反转字符串 - NC103 反转字符串

反转字符串

使用双指针去做:一个指向头,一个指向尾

首先保存头字符,令头字符等于尾字符,再让尾字符等于保存的字符,移动头尾指针;

这道题字符串以 char 数组形式出现

1
2
3
4
5
6
7
8
9
10
class Solution {
public void reverseString(char[] s) {
int left = 0, right = s.length - 1;
while(left < right) {
char tmp = s[left];
s[left++] = s[right];
s[right--] = tmp;
}
}
}

image-20210901205409594

这道题的字符串以 String 形式出现:

那就使用toCharArray()方法将字符串转成 char 数组形式即可:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
/**
* 反转字符串
* @param str string字符串
* @return string字符串
*/
public String solve (String str) {
// write code here
char[] s = str.toCharArray();
int left = 0, right = s.length - 1;
while(left < right) {
char tmp = s[left];
s[left++] = s[right];
s[right--] = tmp;
}
return new String(s);
}
}

图形结构

(邻接矩阵,邻接表)

哈希表

哈希表概念

哈希表方法

哈希表源码 实现

LeetCode-哈希表相关

3.无重复的最长字符串

image-20201009174019820

我们使用哈希表去维护一个窗口,保证窗口内的字符串是没有重复字符的。最后把窗口内的字符串长度返回即可

如何维护呢?为了保证窗口内无重复字符,那么对于每次遍历新考虑的字符,有以下三种情况:

  1. 如果没出现过,【当前位置- 左侧窗口+ 1】就为当下子字符串的长度,和 max 取最大。同时更新 HashMap
  2. 如果出现过
    • 为出现在 left 左侧的,由于计算最长长度是以 left 为起点,则可以认为同样是没出现过的字符,与第一种情况做相同处理
    • 为出现在 left 右侧的,那么 left 到当前遍历到的位置全部都作废了,不可能是没有重复的了,那就需要把 left 更新到后一位。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public int lengthOfLongestSubstring(String s) {
int ans = 0, left = 0;
Map<Character,Integer> map = new HashMap<>();
char[] a = s.toCharArray();
for(int i = 0; i < s.length(); i++) {
//如果存在了这个字符 就取偏右方的那个
if(map.containsKey(a[i])) {
//map.get返回的是key的索引 为什么要+1呢 是因为假如有重复的字符了 就要向右偏移一位
left = Math.max(left, map.get(a[i]) + 1);
}
//map.put方法 把 a[i]放到i的位子上
map.put(a[i], i);
ans = Math.max(ans, i - left + 1);
}
return ans;
}

}

1.两数之和

image-20210626223457061

一开始做着题还是用的 C 语言,傻傻的两层 for 循环,后来接触过了 Hash 的概念,了解了这种题可以用 Hash 的性质去做

1
2
输入:nums = [3,2,4], target = 6
输出:[1,2]

那么就可以在 Hash 中构建成:(3,0) (2,1) (4,2)这样的键值对形式

然后只要在遍历原来数组的时候,通过算差值:目标值 - 当前数组值,判断 map 中是否含有这个差值,通过这个差值的 key,找到 value(下标),这样子就能够以当前下标,和找到的下标构建成数组并返回了

  • 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
for(int i = 0; i < nums.length; i++) {
map.put(nums[i], i);
}
for(int i = 0; i < nums.length; i++) {
int dv = target - nums[i];
//需要注意的是 有可能差值与当前数组的值相同,这是需要避免的情况。
if(map.containsKey(dv) && map.get(dv) != i) {
return new int[]{i, map.get(dv)};
}
}
return new int[]{};
}
}

//由于题目要求可以按照任意顺序返回,那么可以用以下写法,省去一个for循环
class Solution {
public int[] twoSum(int[] nums, int target) {
HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
// for(int i = 0; i < nums.length; i++) {
// map.put(nums[i], i);
// }
for(int i = 0; i < nums.length; i++) {
int dv = target - nums[i];
if(map.containsKey(dv)) {
return new int[]{i, map.get(dv)};
}
map.put(nums[i], i);
}
return new int[]{};
}
}

146.LRU 缓存机制

LRU缓存机制

由于题目要求:要在$O(1)$时间复杂度内完成get 和 put操作,那我们想到了链表,但他存数据用的又是 key value 形式,明显的 HashMap 的形式,那就让我们有些困扰了。

在 HashMap 中有一种子类:LinkedHashMap,它保有 HashMap 的特性,同时内部还有一个双向链表维护键值对的顺序,每个键值对既位于哈希表中,也位于双向链表中,它能提供两种特殊的插入顺序和访问顺序:

  1. 插入顺序:先添加的在前面,后添加的在后面。修改操作不影响顺序
  2. 访问顺序:所谓访问指的是 get/put 操作,对一个键执行 get/put 操作后,其对应的键值对会移动到链表末尾,所以最末尾的是最近访问的,最开始的是最久没有被访问的,这就是访问顺序。

这正好符合我们的 LRU 类性质

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class LRUCache {

LinkedHashMap<Integer, Integer> cache;
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
cache = new LinkedHashMap<Integer, Integer>(capacity, 0.75f, true) {
@Override
protected boolean removeEldestEntry(Map.Entry eldest) {
return cache.size() > capacity;
}
};
}

public int get(int key) {
return cache.getOrDefault(key, -1);
}

public void put(int key, int value) {
cache.put(key, value);
}
}

但是有可能面试的时候,考官不让我们用现成的 API,要我们自己造 双链表 + HashMap 的形式去实现,我们也不能不会:

如下图所示,首先在 Map 中查询 key,基于 key 在双向链表中进行 get 和 put 操作。

哈希表 + 双向链表实现LRU

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
class LRUCache {

HashMap<Integer, Node> map;
DoubleLinkedList cache;
int capacity;
public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
cache = new DoubleLinkedList();
}

//获取操作
public int get(int key) {
if(!map.containsKey(key)) return -1;

//由于是被用了一次,需要重新put一次
int value = map.get(key).value;
put(key, value);

return value;
}

//插入操作
public void put(int key, int value) {
Node node = new Node(key, value);

//假如map中没有,则新增
if(!map.containsKey(key)) {
//如果缓存容量达到上限
if(map.size() == capacity) {
int k = cache.deleteLRU();
map.remove(k);
}
cache.addFirst(node);
} else {
//这里不能delete(node),因为这里的node是新建的,必须从map中获取旧的
cache.delete(map.get(key));
cache.addFirst(node);
}

map.put(key, node);
}
}

//先造双向链表的节点
class Node {
public int key;
public int value;
public Node prev;
public Node next;

public Node(int key, int value) {
this.key = key;
this.value = value;
}
}

//链表
class DoubleLinkedList {

//最近被使用的节点
Node head;
//最近最少被使用的节点
Node tail;

public DoubleLinkedList() {
head = new Node(0, 0);
tail = new Node(0, 0);

head.next = tail;
tail.prev = head;
}

//头插法
public void addFirst(Node node) {
//首先操作结点
node.next = head.next;
node.prev = head;

//接着操作原本head节点后的节点
head.next.prev = node;

//最后操作头结点
head.next = node;

}

//删除传入的结点
public int delete(Node node) {
int key = node.key;

node.prev.next = node.next;
node.next.prev = node.prev;

node.prev = null;
node.next = null;

return key;
}

//删除最近最久未被使用的结点(LRU结点)
public int deleteLRU() {
if(head.next == tail) return -1;
return delete(tail.prev);
}

}

最后附上牛客的 WC134 设计 LRU 缓存结构 大致差不多

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
import java.util.*;



public class Solution {

class LRUCache {

HashMap<Integer, Node> map;
DoubleLinkedList cache;
int capacity;

public LRUCache(int capacity) {
this.capacity = capacity;
map = new HashMap<>();
cache = new DoubleLinkedList();
}

public int get(int key) {
if(!map.containsKey(key)) return -1;

int value = map.get(key).value;
put(key, value);

return value;
}

public void put(int key, int value) {

Node node = new Node(key ,value);

if(map.containsKey(key)) {
cache.delete(map.get(key));
cache.addFirst(node);
}else {
if(map.size() == capacity) {
int k = cache.deleteLRU();
map.remove(k);
}
cache.addFirst(node);
}
map.put(key, node);

}

}

public class Node {

public int key;
public int value;

public Node prev;
public Node next;

public Node(int key, int value) {
this.key = key;
this.value = value;
}
}

public class DoubleLinkedList {

Node head;
Node tail;

public DoubleLinkedList() {
head = new Node(0, 0);
tail = new Node(0, 0);

head.next = tail;
tail.prev = head;
}


public void addFirst(Node node) {
node.next = head.next;
node.prev = head;

head.next.prev = node;

head.next = node;
}

public int delete(Node node) {
int k = node.key;

node.next.prev = node.prev;
node.prev.next = node.next;

node.prev = null;
node.next = null;

return k;
}

public int deleteLRU() {
if(head.next == tail) return -1;
return delete(tail.prev);
}

}

/**
* lru design
* @param operators int整型二维数组 the ops
* @param k int整型 the k
* @return int整型一维数组
*/

public int[] LRU (int[][] operators, int k) {
// write code here
LRUCache cache = new LRUCache(k);
ArrayList<Integer> list = new ArrayList<>();

for(int i = 0; i < operators.length; i++) {

if(operators[i][0] == 1) {
cache.put(operators[i][1], operators[i][2]);
} else {
int value = cache.get(operators[i][1]);
list.add(value);
}
}

int[] res = new int[list.size()];
for(int i = 0; i < list.size(); i++) {
res[i] = list.get(i);
}
return res;
}



}

5792. 统计平方和三元组的数目

统计平方和三元组的数目

  • 思路

通过一个 HashMap 去存储【i , i^2】的键值对,再通过两层 for 循环去查找是否有以【i _ i + j _ j】为 key 的 Value,有的话就代表构成了一个平方和三元组

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public int countTriples(int n) {
HashMap<Integer, Integer> map = new HashMap();
int ans = 0;
//存
for(int i = 1; i <= n; i++) {
map.put(i, i * i);
}
//两层循环遍历查找
for(int i = 1; i < n; i++) {
for(int j = 1; j < n; j++) {
if(map.containsValue(i * i + j * j)) ans++;
}
}
return ans;
}
}